Community Detection Based On Modularity And K-plexes

Complex network is a highly complex network and an abstract form of complex system.The research of complex network is widely concerned.At the same time,complex networks can be used to model various complex systems,such as physical,biological,economic,social and information systems.The complex network presents the characteristics of scale-free,small world and community structure.Among them,community structure is the most important structural feature in complex network,which corresponds to the functional unit of network.Community identification(detection)plays an important role in analyzing the structure or characteristics of a complex network.It can reveal the relationship between the internal structure and function of the network,and thus predict the function of the network.Among many community detection algorithms,modularity-based optimization models are widely used.However,it has been proved that these models are usually significantly restricted in "resolution limit".In practical application,small communities are of great significance.Therefore,to solve this problem,the following researches are carried out in this paper:(1)Based on k-plexes,this paper proposes a novel community detection algorithm,called modularity optimization with k-plexes algorithm(MOKP).This MOKP algorithm applies k-plexes to construct community seeds in the network,and then uses the concept of modularity optimization to assign the remaining nodes of this network.And this algorithm is free of the "resolution limit" problem,that is,the algorithm can identify small communities.(2)To save the computational time of this algorithm,this paper improves MOKP algorithm from the following two aspects(IMOKP).(i)k-Core is used to reduce the size of the network before the generation of community seeds.(ii)The distribution order of the remaining nodes of the network is adjusted from alphabetic order to descending order of the degree of the vertices,and the community label is added in the process of nodes assignment.(3)In order to verify the effectiveness of these algorithms,a lot of experiments are carried out in this paper.We choose five real-world networks and four synthetics to perform our algorithms.And for the metrics,three widely and classical used metrics are adopted to evaluate the accuracy of detected communities.This paper also proposes a newly defined index,namely small community level.Extensive experimental results demonstrate that,on various networks,our proposed algorithms perform better than many other classical algorithms in regard to the accuracy of detected communities.And in terms of the small community level,our proposed algorithms can effectively identify small communities on multiple networks as well.IMOKP algorithm performs well than MOKP algorithm in terms of running time and accuracy of detected communities.Experiments on the real protein-protein network show the validity of community detection and even the small community detection.