Research On Overlapping Community Detection Method Based On Density Peaks

In the real world, many complex systems contain a large number of constituent units orsubsystems, which can be abstracted in terms of Complex network models. In complexnetwork models, the constituent units or subsystems are represented by “nodes”, and therelationships among “nodes” are represented by “edges” correspondingly. Complex networkhas a very wide range of applications, such as the actor collaboration network, friendshipnetwork, academic co-authorship network and email network that in the social field, themetabolic networks, protein-protein interaction network and the gene regulatory networks inbiology and bioinformatics, the Power network, Internet network and the network oftelephone line in the technology field, and so on. In particular, the rapid development ofInternet technology has made the world smaller in recent decades, which makes the worldgetting smaller. The humans have lived in the world that full of the all kinds of complexnetworks. Therefore, the study of complex networks is increasingly becoming a hot researchtopic.Currently, with the study of the complex networks, scholars have found many interestingproperties such as the small world and scale-free properties. Furthermore, scholars have foundthat the community structure of the real networks. The nodes in the same community tend tohave high concentrations of edges, while the ones between different groups often have lowconcentrations. Therefore, community structure of complex networks occupies very importantposition in the process of the development.Traditional methods for identifying communities mainly have the graph partitioning andthe hierarchical clustering. Hierarchical clustering techniques can be classified in twocategories which are agglomerative algorithm and divisive algorithm. With the modularityproposed by Newman, some algorithms based on modularity optimization have beenproposed. However, in many cases of the real world, the nodes are not restricted to belong toonly one community, but may belong to multiple communities. It means that the network cancontain overlapping parts. Then a lot of methods of detecting overlapping communities havebeen proposed by scholars. The overlapping communities can truly reflect the structure of thereal networks. Recently, scholars applied the statistical inference to propose the methods ofdetecting overlapping community. Examples include GN algorithm, SPAEM algorithm. Theycan detect overlapping community structure very well.This article mainly studies the overlapping community of complex network. We havestudied the idea of the paper in the science that the clustering by fast search and find of density peaks, and put forward the overlapping community detection method based on density peaks.In this paper, based on the reviews of the community detection algorithms, analysis andsummary of the existing traditional algorithms are performed firstly. And then, the paperdescribes a clustering method which is recently proposed in Science-“clustering by fastsearch and find of density peaks”, and analysis the scope of the algorithm.By introducing the algorithm into overlapping community detection problem, analgorithm so called “overlapping community detection method based on density peaks” isproposed. Firstly, the algorithm designs a new algorithm to get the distance matrix to avoid thedeficiency of the existing distance matrix being filled with integers and with lots of duplicatenumbers. Then, the process of searching the center is performed similar as the originalalgorithm. The points being surrounded by neighbors with lower local density and havingrelatively large distance from the points with a higher local density are designated to clustercenters. After the cluster centers have been found, each vertex is not necessarily assigned to asingle community, but to be assigned to the each community by a certain probability. Then wecalculate the probability distribution matrix to get the results of the cluster assignment, whichmakes it possible to detect the overlapping communities. In order to verify the effectiveness ofthe proposed algorithm, it is applied to real networks, such as karate network, dolphin networkand other network. The results of the karate and dolphin are similar to the results of theoriginal data. For the large-scale network, the results are better than the other algorithm.By introducing the clustering method called by “clustering by fast search and find ofdensity peaks” into the overlapping community detection problem, we propose a new methodto detect overlapping communities. The proposed algorithm overcomes the defects ofadjacency matrix being filled with integers by defining a new distance matrix, and uses theprobability depicting the possibility of each node that belongs to different clusters. Theproposed algorithm is simple and easy to understand in this paper. It can be used for thecommunity division and classify the overlapping community, and can be extended to theweighted networks. In addition, the algorithm is not preset the number of communities, thecommunity can be determined the number of classes and node cluster center by decision graph.And, the experimental results on the real networks show that all proposed method performsvery well.