Finding structural hole spanners based on community forest model and diminishing marginal utility in large scale social networks

摘要

Structural hole spanners play key role in information diffusion, community detection, epidemic diseases and rumors spreading, link prediction and viral marketing, the discovery for them is a key research work in the area of social networks. Some scholars have proposed inspired models and methods based on Mathematics, Sociology, and Economics. In this paper, we try to give a more visual and detailed definition of structural hole spanner based on the existing work, and propose a novel algorithm to identify structural hole spanner based on community forest model and diminishing marginal utility. Our work includes following four folds. Firstly we revealed the diminishing marginal utility phenomenon in the process of community reconstruction. Secondly we proved that metrics based on local or one-sided features cannot be used as a criterion for judging structural hole spanner. Thirdly we proved that the influence of SHS is not related with the distribution of SHS in the network. Fourthly we develop a novel algorithm to identify SHS. Our algorithm has slightly better performance than the state-of-the-art algorithms. It worked well on Zachary’s karate club, American College Football, ground-truth samples sampled from DBLP, ground-truth samples sampled from Youtube and large-scale collaboration network DBLP.