Distance, dissimilarity index, and network community structure

Phys Rev E Stat Nonlin Soft Matter Phys. 2003 Jun;67(6 Pt 1):061901. doi: 10.1103/PhysRevE.67.061901. Epub 2003 Jun 10.

Abstract

We address the question of finding the community structure of a complex network. In an earlier effort [H. Zhou, Phys. Rev. E 67, 041908 (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.

MeSH terms

  • Algorithms
  • Biophysics / methods
  • Cluster Analysis
  • Computational Biology / methods
  • Fungal Proteins / metabolism
  • Models, Biological
  • Models, Statistical
  • Neural Networks, Computer
  • Protein Binding
  • Saccharomyces cerevisiae / metabolism
  • Software
  • Yeasts / physiology*

Substances

  • Fungal Proteins