Identifying structural hole spanners to maximally block information propagation

Abstract 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