Abstract:
Determining community structure in networks is fundamental to the analysis of the structural and functional properties of those networks, including social networks, computer networks, and biological networks. Modularity function Q, which was proposed by Newman and Girvan, was once the most widely used criterion for evaluating the partition of a network into communities. However, modularity Q is subject to a serious resolution limit. In this paper, we propose a new function for evaluating the partition of a network into communities. This is called community coefficient C. Using community coefficient C, we can automatically identify the ideal number of communities in the network, without any prior knowledge. We demonstrate that community coefficient C is superior to the modularity Q and does not have a resolution limit. We also compared the two widely used community structure partitioning methods, the hierarchical partitioning algorithm and the normalized cuts (Ncut) spectral partitioning algorithm. We tested these methods on computer-generated networks and real-world networks whose community structures were already known. The Ncut algorithm and community coefficient C were found to produce better results than hierarchical algorithms. Unlike several other community detection methods, the proposed method effectively partitioned the networks into different community structures and indicated the correct number of communities.