Research On Mining Hierarchical Structural Hole Spanners Of The Network

Structural hole was first put forward by the sociologist Burt in 1992 and it has a wide range of research in the field of sociology. Structural holes refer to a class of nodes which occupy the important position in the information diffusion, it is a gap between two non-redundant actors. If there is no direct connection between the two actors, such gaps seems to be caves in the network from an overall perspective, therefore, sociologists defined that caves as structural holes. The nodes which occupied the location of the structure hole in the network have advantages to control the information diffusion. According to the study, the 50% of the information diffusion controlled by the 5% of structural holes, even 1% of structural holes control 25% of the information diffusion in the Twitter social network. In recent years, mining structural holes has attracted more and more researchers, and some algorithms are proposed. We found that these algorithms are all under a single granularity. The researchers have studied how to mining structural holes under a single granularity. However, there are a lot of actual networks, whose structure with hierarchical multiple granularity. So, it is of great significance to mining and make an analysis of the structural holes of the networks under the multi-granularity.Above all, in this dissertation, some methods are proposed to mining hierarchical multi-granular structural holes of the network based on Burt’s theory of structural holes. For the un-weighted networks, a methods named HI-SH is firstly proposed to mining multi-granular structural holes, and some analyses of structural holes under the multi-granularity are also given based on this method. Then a method called WHI-SH is proposed to mining multi-granular structural holes of the weighted networks.In this dissertation, the main is summrized as follows.First of all, we introduce the research status of the measurement index and the mining algorithm of the structural holes occupant.Since Burt put forward structural holes, the structural holes have made great development in the field of sociology, medicine, computer science. The measurement indicators for the structural holes are summarized in this dissertation, including the effective scale, efficiency, restriction degree, level degree, pagerank, etc. Then introduced the algorithms of mining structural holes, included HIS algorithm, MAXD algorithm, W_HIS algorithm, W_CIHIS algorithm.Secondly, a method named HI-SH is proposed to mining multi-granular structural holes of the network with hierarchical structure.A method named HI-SH is firstly proposed to mining multi-granular structural holes of the un-weighted network. In this method, we detect the community of the network in each hierarchical granularity. According to the theory of two-step information diffusion, structural holes mining algorithms are used to mining top k% structural holes in each granularity. We analyze the evolution of the structural holes under different granularity. Experiments on adyouth bbs data and scientific cooperation network data which include public data Topic 16 and real data and bbs data. The results show that structural holes of the network is dynamically and structural holes ranking under single granularity can’t represent the whole networks. For different network,it does not exist a certain granularity which the structural holes are the optimal. Both the coarse granularity and fine granularity are not better than middle granularity.Thirdly, a method named WHI-SH is proposed to mining multi-granular structural holes of the weighted network.This dissertation is based on the method that mining multi-granular structural holes of the network with hierarchical structure. We consider the weight of edges between two nodes. This multiple granularity thought will be applied to the structural holes algorithms on weighted network. A method named WHI-SH is proposed to mining multi-granular structural holes of the weighted network. In this method, first, we add weight to edges between nodes in the network and detect community of network in each hierarchical granularity. Then, according to the theory of two-step information diffusion, structural holes mining weighted algorithms are used to mining top k% structural holes in each granularity. Finally, we analyze the evolution of the structural holes under different granularity. Experiments on scientific cooperation network data which include public data Topic 16+w and the ICML₁0+w real data. In the analysis of structural holes, we use SIR virus propagation model for simulation analysis. Analoging information transmission process on the experimental results of scientific research cooperation networks actual data sets and public data sets.Through the two different methods, the algorithms have been verified on the experimental data both in weighted network and un-weighted network. Finally we can get the network’s evolution process by analying of the change of structural holes.