Abstract:

Structural holes take up key positions in social networks, and they play an intermediary role in information diffusion. To efficiently and accurately identify nodes which occupy structural holes in social networks with community structure, we propose a structural hole identification algorithm based on overlapping communities and structural hole degree. We attempt to find a set of nodes which possess the most information superiority and control superiority. The basic idea is to locate the overlapping nodes between communities in the first place, and then calculate the structural hole degree of overlapping nodes by measuring the nonredundancy degree through an integration of adjacent differences and community connection differences. A set of structural holes can be finally found out according to the ascending order of nodes' structural hole degree. Experiments on real datasets show that the proposed algorithm has the best identification accuracy and the lowest time complexity in comparison with the network constraint index algorithm, the betweenness centrality algorithm and the MaxD algorithm.

Key words: social network;complex network;structural hole;overlapping community;nonredundancy;structural hole degree