Research Of Community Detection Algorithm Based On The Relationship Between Neighbor Nodes

There are many different types of complex networks which all contain their own internal community structure in the real world.The community detection algorithm can help us to discover the internal structure and topological characteristics of complex networks.At present,a variety of community detection algorithms have been developed,which are widely used in various fields of the real life because of their great practical value.Most of the community detection algorithms are proposed based on similarity measures or Modularity maximization.However,the similarity-based methods is faced with the problem that the input parameters are hard to determine and the specific complex network cannot be divided accurately;The community detection algorithm based on Modularity maximization has very high time complexity when seeking the partial best partition,and the maximum Modularity does not necessarily correspond to the real division of the network in many cases.This paper is devoted to propose a fast and accurate community detection algorithm so as to solve this problem.In this paper,a new method of similarity measures is proposed based on the relationship between neighbor nodes.Different from the traditional similarities,the similarity considers not only the number of common neighbors but also the exclusion degree between two adjacent nodes.Therefore,it can reflect the similarity degree between two adjacent nodes from the node structure more objectively and comprehensively.Then,in order to find the core in different communities more quickly and accurately,this paper defines the influence of a node on its neighbors as its local density,and regard the node with the greatest density in a community as a core.This density calculation method considers that the density of a node is the sum of its influence on all its neighbors,the greater the influence of the node,the greater the density and greater attraction to other nodes.Through this local density,the core in the network can be much easier discovered,while avoiding the randomness of the core selection,so as to make the algorithm results more stable.On the basis of the similarity and the local density,this paper proposes a simple but effective community detection algorithm(called CDRN)based on the neighborhood relationship between nodes.CDRN uses the neighborhood relationship between nodes to combine the advantages of similarity-based methods and core-based methods ingeniously.It neither needs to optimize the target function nor needs to master the information about the number of communities in the network,and it can provide a unique and accurate network partition in multiple runs.According to this similarity,CDRN groups nodes together to obtain the initial community structure in the first step.Then,CDRN adjusts the initial community structure according to cores discovered through a new local density.Finally,CDRN expands communities to yield final community structure.In order to evaluate the performances of CDRN objectively,this paper makes a comparative analysis comprehensively between CDRN algorithm and seven well-known community detection algorithms in six small size networks with class information and five larger size networks without class information.Experimental results show that CDRN outperforms the seven compared algorithms in most cases.Furthermore,the experiment also verified the stability of the threshold range of similarity proposed in this paper on different community structures by LFR benchmark networks.Finally,the robustness of CDRN is verified on the incomplete network which sampled from the networks with real community structure.Synthesizing the above studies and experiments,we can know that CDRN can quickly discover the core of community and can automatically detect the community structure from the networks with different types and sizes stably and accurately.It is a non-heuristic,time complexity near linear,robust community detection algorithm.