1 Introduction
The last decade witnessed the exponential growth of a variety of large-scale networks such as social networks, citation networks, collaboration networks, biological networks, wireless networks, etc. With the unprecedented scale growth of network size, there are high demands for developing efficient yet scalable algorithms to explore some unique properties of such massive networks. Most social networks exhibit the so-called community structure property. That is, the vertices in a network can be grouped into different sets of cohesive groups (communities) [11], where vertices in the same community share similar attributes, interests and resources. The communities in a network play a significant role in information diffusion within the network, information within a community circulates very quickly and diffuses to other communities through community boundaries or bridges. On the other hand, there is a consensus among social scientists [8] that a person who plays a bridge role between different communities can acquire more potential resources from these communities and has more control over the information that is being transmitted. For example, Burt [8] studied social structures of many organizations and introduced the notion of structural holes (SH) as positions that can bridge diverse groups and bring benefits to the beholder. It is shown that the information obtained from people in the same community tends to be homogeneous, while the information through the contacts with people from different communities are much more non-redundant [24]. Therefore, a person who develops relations with people from multiple different communities will gain more benefits. Structural hole spanners were studied initially by Lou et al. [19] and later by Rezvani et al. [23]. For example, a community in an academic collaboration network represents a group of people with the similar research interests, and people (structural hole spanners) who can bridge different research communities are more potent to combine ideas from different research groups and create interdisciplinary works. Structural hole spanners have a wide range of practical applications. For example, in community detection, identifying central hubs that connect different groups can help isolate and identify communities [31]. In Epidemic diseases and rumors spreading, quarantining structural hole spanners can stop the spread of infection and rumors into other communities [5] , [13], [20]. In viral marketing, the most influential structural hole spanners can speed-up the new product marketings to different groups [4], [17], [26], [27], [28], [32]. In graph compression, structural holes are good candidates for \$k\$-shattering [16] as they connect diverse parts of a network together, and their removal will result in the network disconnected.