An Overlapping Community Detection Algorithm In Complex Networks

Complex network can be used to describe Internet, Social relationship network, Biologicalnetwork, Industrial communication network, WWW etc.. Along with the in-depth study ofcomplex networks, researchers have found that a lot of actual networks have community structure,and there are overlapping and interrelated characteristics between communities. As a basis forresearching complex network structure, the division of overlapping communities has become thekey issue of the study of complex networks.In the complex network structure, edge reflects the interaction, cooperation, mutualinfluences relations between nodes in the network, it can only belong to a single community.Therefore, the implementation of community division by using the edge characteristic can makeresults reflect the role and function of nodes in complex networks more truly. Based on thisconsideration, this paper presents an overlapping communities detection algorithm based on edgesin complex networks(Spectral Analysis Based on Edge Clustering, SAEC). The algorithm regardsthe community as a set of edges, expresses edge in the original network as node in line graph.According to the basic principle of spectral clustering based on the transition probability matrix,the algorithm defines the node similarity and constructs the kernel matrix, obtains the transitionprobability matrix, calculates the eigenvalues and eigenvectors of the transition probability matrix,finds corresponding k value of the biggest eigengap, extracts the first k eigenvectors, clustersedges combined with the K-Means clustering algorithm, and gets link communities andoverlapping nodes between communities according to the clustering result.In order to verify the performance of the proposed algorithm, this paper chooses to test onreal network, such as Zachary karate network, Dolphin social network, Word association network,Scientific collaboration network etc., compares with and analyses NEWMAN fast algorithm,CPM, EAGLE, Hierarchical clustering algorithm based on edges on the result of division,accuracy and running time. The experimental results show that our algorithm can correctly realizeoverlapping communities detection in complex networks, and has lower time complexity.