A Modularity-Based Graph Clustering Method For Identifying Community Structures In Complex Networks

Network community structure is one of the important topological properties in complex networks research.By detecting community structures in the networks,one can analyze the topological properties of complex networks to uncover functional modules in them.Identifying important network community structures in large-scale complex networks has become one of the hot spots of current research.In recent years,graph clustering algorithms have been successfully applied to discover community in complex networks,such as social network,biological network,citation network,and so on.The thesis presents a new graph clustering algorithm LMC based on the local modularity for detecting dense community structures.The main works are as follows:(1)Give the definition of the edge weights based on vertex similarity indices,and then present the definition of community structures and the fitness function.Among them,the modularity indicates the tightness of community structures.(2)Propose a graph clustering algorithm LMC based on "seeding edge-expanding" for complex networks.First,according to the definition of edge weights,select the seeding edges to form an initial cluster.Then calculate the modularity of this clustering and the fitness value related to its neighbor to expand the cluster until the modularity reach to the maximum value.During this process,a vertex may belong to more than one community structures.(3)The presented algorithm LMC is a soft clustering which can detect the dense community structures in complex networks.We demonstrate that our algorithm LMC is highly effective at discovering dense community structure in both computer-generated networks and real world protein-protein interaction networks.