Overlapping Community Discovery Algorithm Based On Clique Graph Clustering

Network science is a subject that studies the qualitative and quantitative laws of complex networks,the relevant research involves various topological structures and properties.Research object comes from a variety of practical networks such as the mobile communication network,the traffic network,the power network,etc.The common feature of these networks is that the whole network is composed of many communities.The connection between nodes within the same community is relatively close,otherwise it is relatively sparse.Community structure is of great significance for understanding the nature of the network and making full use of the network information,and community discovery has become an important project.Traditional community discovery algorithms focus on quantitative characterization of communities and effective mining of community structure,each node only belongs to one community.However,the networks often have the overlapping characteristics.There are many ‘wall-riding nodes',which may belong to multiple communities at the same time.Mining the overlapping community structure and analyzing the property of overlapping nodes will help us understand the specific structure of the actual network.Lehmann and others proposed a method to detect the overlapping and hierarchical community structures in 2010.Regarding the community as the set of edges,and making the community discovery on the edge,we can get the overlapping communities of the original network.But,the number of edges is often larger than the nodes' in many real networks.In order to reduce the computing time and realize the overlapping community structure discovery,this paper presents a new idea,which is based on the fact that the number of cliques in the actual network is often less than the edges',considering each community in the network as a collection of cliques,and making spectrum cluster analysis,after that converting the clique community to the node.Because the nodes can belong to the different cliques,the nodes can belong to the different communities.So not only we obtain the overlapping community structures,but also due to the full coupling of solidarity structure,this algorithm can retain the characteristics of close connection of nodes within the clique,which makes the overlapping community partition more exact.At the same time,the definition of paired community membership degree and paired community median centrality of the overlapping nodes is proposed,which can be used to judge the transitivity of the overlapping nodes among the communities they belong to.