A nature-inspired influence propagation model for the community expansion problem

作者：Bi, Yuanjun; Wu, Weili^*; Zhu, Yuqing; Fan, Lidan; Wang, Ailian

来源：Journal of Combinatorial Optimization, 2014, 28(3): 513-528.

DOI：10.1007/s10878-013-9686-9

• Community expansion
• Physical model
• Social influence
• Linear programming

Influence propagation has been widely studied in social networks recently. Most of these existing work mainly focuses on the individual influence or the seed set influence. However, a large range of real world applications are related with the influence from communities. In this paper, we argue that the specific structure of community makes the influence propagation from a community different from previous influence propagation from an individual or a seed set. Inspired by the charged system in the physic, a new community influence propagation model is built, which provides a natural description about the process of influence propagation and explains why the influence makes communities expand. Based on this physical model, we define the community expansion problem. And two objective functions are proposed for choosing proper candidates to enlarge a community, taking into account the cost and benefit. Then a linear programming approach is designed to maximize those two objective functions. To validate our ideas and algorithm, we construct experiments on three real-world networks. The results demonstrate that our model and algorithm are effective in choosing proper candidates for expanding a community, comparing to other two algorithms.

• 出版日期2014-10
• 单位太原理工大学