Distance, dissimilarity index, and network community structure

被引:191
作者
Zhou, HJ [1 ]
机构
[1] Max Planck Inst Colloids & Interfaces, D-14424 Potsdam, Germany
来源
PHYSICAL REVIEW E | 2003年 / 67卷 / 06期
关键词
D O I
10.1103/PhysRevE.67.061901
中图分类号
O35 [流体力学]; O53 [等离子体物理学];
学科分类号
070204 ; 080103 ; 080704 ;
摘要
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.
引用
收藏
页数:8
相关论文
共 13 条
[1]   The SWISS-PROT protein sequence database and its supplement TrEMBL in 2000 [J].
Bairoch, A ;
Apweiler, R .
NUCLEIC ACIDS RESEARCH, 2000, 28 (01) :45-48
[2]   Protein interactions - Two methods for assessment of the reliability of high throughput observations [J].
Deane, CM ;
Salwinski, L ;
Xenarios, I ;
Eisenberg, D .
MOLECULAR & CELLULAR PROTEOMICS, 2002, 1 (05) :349-356
[3]  
Flake G. W., 2000, Proceedings. KDD-2000. Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, P150, DOI 10.1145/347090.347121
[4]   SET OF MEASURES OF CENTRALITY BASED ON BETWEENNESS [J].
FREEMAN, LC .
SOCIOMETRY, 1977, 40 (01) :35-41
[5]   Community structure in social and biological networks [J].
Girvan, M ;
Newman, MEJ .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2002, 99 (12) :7821-7826
[6]   MIPS:: a database for genomes and protein sequences [J].
Mewes, HW ;
Frishman, D ;
Güldener, U ;
Mannhaupt, G ;
Mayer, K ;
Mokrejs, M ;
Morgenstern, B ;
Münsterkötter, M ;
Rudd, S ;
Weil, B .
NUCLEIC ACIDS RESEARCH, 2002, 30 (01) :31-34
[7]   Hierarchical organization of modularity in metabolic networks [J].
Ravasz, E ;
Somera, AL ;
Mongru, DA ;
Oltvai, ZN ;
Barabási, AL .
SCIENCE, 2002, 297 (5586) :1551-1555
[8]   A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisiae [J].
Uetz, P ;
Giot, L ;
Cagney, G ;
Mansfield, TA ;
Judson, RS ;
Knight, JR ;
Lockshon, D ;
Narayan, V ;
Srinivasan, M ;
Pochart, P ;
Qureshi-Emili, A ;
Li, Y ;
Godwin, B ;
Conover, D ;
Kalbfleisch, T ;
Vijayadamodar, G ;
Yang, MJ ;
Johnston, M ;
Fields, S ;
Rothberg, JM .
NATURE, 2000, 403 (6770) :623-627
[9]   Comparative assessment of large-scale data sets of protein-protein interactions [J].
von Mering, C ;
Krause, R ;
Snel, B ;
Cornell, M ;
Oliver, SG ;
Fields, S ;
Bork, P .
NATURE, 2002, 417 (6887) :399-403
[10]  
Wasserman S., 1994, SOCIAL NETWORK ANALY