Research On Discovery Algorithm Of Key Node In Social Network

Network is everywhere, the typical network of human society, Wechat, Weibo, and variouskinds of social networking sites such as Facebook are all parts of Social Network. SocialNetwork is a far away from a new researcharea, it has been studied by researchers from19century. And now, the development of society and technology, further deepening of modernscientific research, have also been promoting the study of complex networks and SocialNetworks.The research of Social Network research can’t be separated the basic content: key nodes.The mining of key node saims at finding the important nodes of network, which are veryimportant for measuring the invulnerability, efficiency androbustness of network. As far asfinding the key nodes, effective strategies can be formulated pertinently, so that network can becontrolled effectively and able to serve humanity better.There are various kinds important node mining algorithms proposed by researchers.Distinguishing by the basic ideas, these algorithms are divided into algorithms based on globalinformation and algorithms based on local network information. The algorithms based on globalinformation with high accuracy as well as high complexity which is usually higher than O(N3).This kind of algorithms usually choose the globel imformation such as the distance betweennodes and the center as the evaluation indicators of importance, they do not apply to large-scalenetworks because of high computational complexity,especially the massive data processingwhose nodes more than a hundred million with high clustering coefficient;The algorithms thatbased on local information usually choose local imformation as the evaluation indicators ofimportance. Degrees of nodes are the simplest local imformation, and the degrees of nodes aswell as its neighbor nodes are a little more complex. These algorithms just choose the specificinformation of nodes or finite Layer of its neighbor nodes, so they have lower time complexityas well as loweraccuracy.Based on questions above, this paper researches literaturesof representative algorithms ofimportant nodes mining of recent years,analyzes some representative algorithms of importantnodes mining, and based on this analysis and local, semi-localinformation, proposes a newimportant nodes mining algorithm of Social Network. The importance of nodes is a relativeconcept which can use “high”and”low” to express its degree of importance, so we can conducta frame (high,low)to distinguish importance and define two indexsf iandg i. is thedegrees ofv iand its neighbor, is the clustering coefficient of nodes.The index isnormalized. Based on the indexs above and according to D-S evidence theory, we can conductbasic probability distribution function (BPA)m fiandm pi, it mesns the level of support of the importance of nodes under frame. They are synthesized into a function by D-S evidence theory,m fiandm piare merged into a now index-DSC(D-S clustering centrality) whose importanceof nodes are quantified in the form of probability to get the sequence of nodes importance.Because the algorithm only considers local information of network, it has low timecomplexity. The results of the tests based on artificial data and the actual test data show that, thealgorithm is much better than on some representative mining algorithms such as the algorithmbased on node betweenness centrality index and the algorithm based on node near to centralityindex. Compared with other Mining algorithms based on local or semi-local information, thisalgorithm has significantly improved the accuracy.This paper has deeply studied important nodes mining algorithms of Social Network,starting from constructing a new importance of nodes, has analyzed and summarized the currentmain stream mining algorithms,has researched the basic question of network science: importantnodes mining.