Research On Detecting Structural Hole Spanners Based On Community Structure

Structural hole is a ubiquitous phenomenon in real network.Burt’s structural hole theory points out that individuals or firms that occupy the structural hole position in the social structure can gain more career opportunities or competitive advantages.In information networks,individuals occupying structural holes can obtain more critical information and resources from different groups,thus affecting the information propagation in network and the relationship among individuals.In the field of sociology,structural holes are gaps between non-redundant contacts and play an intermediary role between-different-individuals or groups.Intermediates between individuals or groups can gain abundant information and control their network relationship,and the individual who occupies the bridging position in network can gain great benefits.The structural hole plays a key role in obtaining-the effective information of the network,and detecting structural hole can optimize the network structure and enhance the robustness of network.As an important method of network structure analysis,structural hole theory has obtained rich achievements in different fields and disciplines.Previous studies show that the real network has the characteristics of community structure besides the small world and scale-free characteristics.The information in the network is transmitted from one community to others,and the non-redundant information can be obtained by spanning different communities.Structural hole spanners have the potential to obtain information and resources from multiple communities,and play an intermediary role in the process of information propagation between communities.The community structure has important significance and role for the research of structural hole,while the existing structural holes detection methods mainly considered the network topology.The community structure based algorithms mainly considered the effect of structural holes in the process of information propagation between different communities,with few considered the intermediary position between communities and the community characteristics of nodes.Such as neglected the effect of the quantity and scale of connected communities of nodes spanning structural holes.The focus of this dissertation is how to find structural hole spanners in networks by combining community structure.Firstly,we combine the multi-granularity with community structure,and find that the community structure in network partition under different granularity would change.The community has the characteristic of hierarchical structure,community under the rough granularity may be divided into multiple communities while under thin granularity.The structural hole position under different granularity in the network will be different,and influence the extent of node spanning the structural hole.Therefore,the combination of multi-granularity and community structure can detect the structural hole spanners more accurately in the network under different granularity.Based on this idea,this dissertation proposed a method of recognition and analysis of structural hole spanners in multi-granularity based on community structure,named MG_MaxD.Then,by using the network topology and the community inner structure,the dissertation analyzes the factors that affect the nodes to span structural hole and puts forward two definitions.That is,the neighbor importance and the community influence.Through the analysis,it is foundthat the community characteristics of node can be used to measure the extent of nodes spanning the structural holes,and then a novel structural hole measurement is proposed.Based on the analysis of the bridging property and the propagation ability of the structural hole spanner in networks,this dissertation proposed a method for mining structural hole spanners using the network topology and the community inner structures,namely NTCIS.This dissertation focus on the detection of structural hole spanners in the network,the main work is as follows:(1)Analyzing the commonly used measurements of structural hole spanners,such as degree,betweenness centrality and PageRank.The detection methods of structural hole spanner is classified into two categories,which are summarized in two aspects:the network topology and the community structure.Applying the structural hole theory to other researches was discussed in the practical application of structural hole.(2)Since the community structure has the characteristics of hierarchical,the extent of nodes spanning the structural hole will change under different granularity.Based on the existing structural hole detection method,a new method of structural hole detection in community structure under multi-granularity is proposed.The algorithm not only takes into account the important characteristics of community structure of network,but also combined the multi-granularity with the community partition.Thus it can effectively find the structural hole spanners in the network under different levels of granularity.The feasibility of the algorithm is verified on both public and real datasets,and compared with another important method.Finally,it is verified that the proposed algorithm can discover the extent of node to span structural hole will constant change under different granularity.(3)Most of the structural hole detection method are based on the network topology,while less to research on the community inner structure.Firstly,two novel definitions are proposed by using network topology and community inner structure respectively,that is the neighbor importance and the community influence.According to the characteristics of nodes in community structure,a new structural hole measurement is proposed.Finally,this dissertation proposed the algorithm for miningstructural hole spanner based on the network topology and the community inner structure,namely NTCIS.The experimental results show that the NTCIS algorithm can accurately find.the structural hole spanners of the network,and these nodes are bridged with more and larger communities,which play a more important intermediary role between different individuals.