Generalized Structural Holes Finding Algorithm by Bisection in Social Communities

Structural holes" is a conception proposed by sociologist Ronald Burt [1], which refer to the absence of ties between two parts of a network. in this paper, we develop this conception and proposed a new conception called generalized structural holes" between communities in social network and proposed an effective algorithm to find them. We believe that generalized structural holes play a key role in many aspects on social networks, such as communication between communities, diffusion of innovation, information spreading. We prove that such problem of finding generalized structural holes is NP-complete, and we propose a heuristic algorithm to find these generalized structural holes. Experiments on both synthetic and real word data set show that the discovery of generalized structural is effective and efficient, and the results also demonstrate that the real word networks have a hierarchical community structure, and our algorithm perform very well on them.