The theory of structural holes suggests that individuals would benefit from filling the ``holes'' (called as structural hole spanners) between people or groups that are otherwise disconnected.
The fundamental challenge we want to address is to detect users who span structural holes in social networks and how the structural hole spanners influence the information diffusion?
We explore the problem of mining structural hole spanners through information diffusion in social networks (Lou and Tang, WWW'13). We precisely define the problem of mining top-k structural hole spanners in large-scale social networks and provide an objective (quality) function to formalize the problem. Two instantiation models (HIS and MaxD) have been developed to implement the objective function. The optimization is proved to be NP-hard, and we design an efficient algorithm with provable approximation guarantees.
Related data sets and codes: [Structural hole&Information diffusion]