Identifying structural hole spanners to maximally block information propagation

An individual can obtain high profits by playing a bridge role among different communities in a social network, thus acquiring more potential resources from the communities or having control over the information transmitted within the network. Such an individual usually is referred to as a structural hole spanner in the network. Existing studies on the identification of important structural hole spanners focused on only whether a person bridges multiple communities without emphasizing the tie strength of that person connecting to his bridged communities. However, a recent study showed that such tie strength heavily affects the profit the person obtains by playing the bridge role. In this study, we aim to identify the most important hole spanners in a large-scale social network who have strong ties with their bridged communities. Accordingly, we first formulate the top-k structural hole spanner problem to identify k nodes in the network such that their removals will block the maximum numbers of information propagations within the network. Due to the NP-hardness of the problem, we then propose a novel (1−ϵ)-approximation algorithm, where ϵ is a given constant with 0 < ϵ < 1. Although the approximate solution provides a guaranteed performance, it takes some time to deliver the solution, which may not be acceptable in practice. Therefore, we devise a fast, yet scalable, heuristic algorithm for the problem. Finally, we evaluate the performance of the proposed algorithms through extensive experiments, using real-world datasets. The experimental results show that the proposed algorithms are very promising. Especially, the found hole spanners block more than 24% of the information propagations compared to existing algorithms.