Distance, dissimilarity index, and network community structure

Abstract

We address the question of finding the community structure of a complex network. In an earlier effort [H. Zhou, {\em Phys. Rev. E} (2003)], the concept of network random walking is introduced and a distance measure defined. Here we calculate, based on this distance measure, the dissimilarity index between nearest-neighboring vertices of a network and design an algorithm to partition these vertices into communities that are hierarchically organized. Each community is characterized by an upper and a lower dissimilarity threshold. The algorithm is applied to several artificial and real-world networks, and excellent results are obtained. In the case of artificially generated random modular networks, this method outperforms the algorithm based on the concept of edge betweenness centrality. For yeast's protein-protein interaction network, we are able to identify many clusters that have well defined biological functions.

10 pages, 7 figures, REVTeX4 format

References in corpus (4)

• Community structure in social and biological networks
• Cooperative Game Theory Approaches for Network Partitioning
• Hierarchical organization of modularity in metabolic networks
• Network Landscape from a Brownian Particle's Perspective

Cited by in corpus (49)

• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Comparing community structure identification
• Community detection in networks: A user guide
• Clique percolation in random networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• A Method to Find Community Structures Based on Information Centrality
• Identifying "communities" within energy landscapes
• Statistical significance of communities in networks
• Coarse-Graining and Self-Dissimilarity of Complex Networks
• Spectral and Dynamical Properties in Classes of Sparse Networks with Mesoscopic Inhomogeneities
• Hierarchical characterization of complex networks
• Median evidential c-means algorithm and its application to community detection
• Subgraphs and network motifs in geometric networks
• Preferential attachment of communities: the same principle, but a higher level
• Finding and testing network communities by lumped Markov chains
• Fundamental statistical features and self-similar properties of tagged networks
• Uncovering the community structure associated with the diffusion dynamics of networks
• Accuracy and Precision of Methods for Community Identification in Weighted Networks
• Unveiling community structures in weighted networks
• Random field Ising model and community structure in complex networks
• Yeast Protein Interactome Topology Provides Framework for Coordinated-Functionality
• Limitation of multi-resolution methods in community detection
• Inversion method for content-based networks
• The critical point of k-clique percolation in the Erdos-Renyi graph
• Process Flow Diagram of an Ammonia Plant as a Complex Network
• Broad lifetime distributions for ordering dynamics in complex networks
• Maximal entropy random walk in community finding
• Spectral transitions in networks
• Constrained spin dynamics description of random walks on hierarchical scale-free networks
• Community detection and Social Network analysis based on the Italian wars of the 15th century
• Combinatorial approach to Modularity
• An integrative dynamical perspective for graph theory and the study of complex networks
• The Similarity of Global Value Chains: A Network-Based Measure
• Finding Community Structure Based on Subgraph Similarity
• Community detection based on first passage probabilities
• Partition of Networks into Basins of Attraction
• Inter-arrival times of message propagation on directed networks
• Detecting groups of similar components in complex networks
• An alternative approach to determining average distance in a class of scale-free modular networks
• Hippocluster: an efficient, hippocampus-inspired algorithm for graph clustering
• The Community Structure of Econophysicist Collaboration Networks
• Spectral clustering via adaptive layer aggregation for multi-layer networks
• Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations
• A bibliometric approach to Systematic Mapping Studies: The case of the evolution and perspectives of community detection in complex networks
• Gaussian Networks Generated by Random Walks
• Transforming Graph Representations for Statistical Relational Learning
• Multiple predator based capture process on complex networks
• Evaluating community structure in large network with random walks