The Research On Some Partition Algorithm Of Community Structure Based On Node Similarity

A complex network is a network with extraordinary complex topological features.The connection between its elements is neither random nor obvious.Many real world networks,such as transportation networks,social communication networks,and genetic regulatory networks,are complex.The research of complex networks is a young and dynamic area of scientific research,which has attracted great attention for scholars.Community structure is the common features of many real networks,and it is the most important characteristic structure in complex network.Community structures usually correspond to functional modules in the real network,such as web pages with the same topic in the web network or microcirculation modules in the metabolic network.Therefore,studying the community structure in complex network is promising.In order to detect the community structure in the complex network,the scholars have proposed many efficient algorithms from different angles.the common way of detecting community structure include aggregation algorithm based on similarity measure,information theoretic algorithm,algorithm based on principal component analysis and maximizing modular algorithm.In this thesis,based on similarity measure,we partition the node belong to which community by defining computing method of similarity between nodes,and two detecting community algorithm have been proposed:(1)The method of detecting community based on node similarity.Firstly,The computing method of node similarity has been improved based on RA;Secondly,to undirected and unweighted graph,the detecting community structure algorithm has been proposed based on an improved cohesion thought;Finally we use accuracy and modularity as a measure of the criterion of detecting community.By using some real networks to evaluate the performance of the algorithm,the results show that the algorithm can detect community structure accurately in the complex network.(2)A detecting community structure algorithm based on the relative distance of nodes.First,based on NGD(normalized google distance),a method of computing the relative distance of nodes has been improved.Then,by combining the clustering idea,every core node in community has been selected.Finally,we divided the nodes into the communities where the closest core node is in.Compared with other algorithms,the algorithm has low time complexity.At the same time,the experimental results show that the detecting result is accurate.To sum up,based on similarity measure,this thesis is to detect the community structure in complex networks by defining the computing method of nodes' similarity.the more similar the two nodes are,a greater chance the two nodes have that they are in the same community.Based on node's similarity,the detecting comminity algorithm has been proposed.