Comparison and validation of community structures in complex networks

Abstract

The issue of partitioning a network into communities has attracted a great deal of attention recently. Most authors seem to equate this issue with the one of finding the maximum value of the modularity, as defined by Newman. Since the problem formulated this way is NP-hard, most effort has gone into the construction of search algorithms, and less to the question of other measures of community structures, similarities between various partitionings and the validation with respect to external information. Here we concentrate on a class of computer generated networks and on three well-studied real networks which constitute a bench-mark for network studies; the karate club, the US college football teams and a gene network of yeast. We utilize some standard ways of clustering data (originally not designed for finding community structures in networks) and show that these classical methods sometimes outperform the newer ones. We discuss various measures of the strength of the modular structure, and show by examples features and drawbacks. Further, we compare different partitions by applying some graph-theoretic concepts of distance, which indicate that one of the quality measures of the degree of modularity corresponds quite well with the distance from the true partition. Finally, we introduce a way to validate the partitionings with respect to external data when the nodes are classified but the network structure is unknown. This is here possible since we know everything of the computer generated networks, as well as the historical answer to how the karate club and the football teams are partitioned in reality. The partitioning of the gene network is validated by use of the Gene Ontology database, where we show that a community in general corresponds to a biological process.

To appear in Physica A; 25 pages

References in corpus (14)

• The structure and function of complex networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Fast algorithm for detecting community structure in networks
• Cooperative Game Theory Approaches for Network Partitioning
• Hierarchical organization of modularity in metabolic networks
• Specificity and stability in topology of protein networks
• Comparing community structure identification
• Community detection in complex networks using Extremal Optimization
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Local modularity measure for network clusterizations
• Identifying "communities" within energy landscapes
• Network Landscape from a Brownian Particle's Perspective
• Complex Networks

Cited by in corpus (9)

• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Near linear time algorithm to detect community structures in large-scale networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Limited resolution in complex network community detection with Potts model approach
• Inference for graphs and networks: Extending classical tools to modern data
• Consistent Community Identification in Complex Networks
• Modular Networks for Validating Community Detection Algorithms
• The way to uncover community structure with core and diversity