Design And Implementation Of Structural Hole Detection Algorithms In Social Networks

The nodes connecting different communities are called the structural spanners.There are some ways of detecting the structural holes has already be used but there are some shortcomings,such as,the method of detecting the structural hole spanners based on local topology has ignored the network topology,and it is bad for extension of the large scale social network.In order to detection the influential points in the network,our works are as follows:First,we proposed a new algorithm of structural hole spanners based on the topological of two-step neighbor.Against the low accuracy of traditional structural hole measurement,we proposed a new measurement of E-Burt,computing the effective scale of the note and the topological of two-step neighbor and the result used as evaluation index of the importance of the nodes.We propose the E-B algorithm for structural hole spanners detection.The E-B algorithm and set the selected node metric to zero for iterations and compute it two-step neighbor only the next iteration which reduces the time complexity greatly.Finally analysis the efficiency and the accurately and verify the accuracy of the algorithm and compare with classical structural hole spanners algorithm.Second,structural hole spanners not only has the advantage of control but also information advantages,in the chapter four,we proposed a structural hole finding algorithm based on network action log and it mainly divided into three steps:stepl.Build model according associative matrix and action log in the real data set which is collected of a given network history and action log.step2.Use the extended the largest expectation algorithm GEM in the process of parameter learning.The parameters are updated on the real data set until the convergence and each node in the network have a pair of parameters that represent the active participation and the negative participation of the nodes in the community.step3.Implement the algorithm of Top-k structure hole detection according to the parameters and measure and sort the positive score and negative scores of each node and select Top-k structure hole set.We can find that the method based on network topology and action log find the structural spanners are more precision and the weakness is the slowness of the learning phase.