Random field Ising model and community structure in complex networks

被引:46
作者
Son, SW [1 ]
Jeong, H
Noh, JD
机构
[1] Korea Adv Inst Sci & Technol, Dept Phys, Taejon 305701, South Korea
[2] Chungnam Natl Univ, Dept Phys, Taejon 305764, South Korea
关键词
D O I
10.1140/epjb/e2006-00155-4
中图分类号
O469 [凝聚态物理学];
学科分类号
070205 ;
摘要
We propose a method to determine the community structure of a complex network. In this method the ground state problem of a ferromagnetic random field Ising model is considered on the network with the magnetic field B-s = +infinity, B-t = -infinity, and B-i not equal s,B-t=0 for a node pair s and t. The ground state problem is equivalent to the so-called maximum flow problem, which can be solved exactly numerically with the help of a combinatorial optimization algorithm. The community structure is then identified from the ground state Ising spin domains for all pairs of s and t. Our method provides a criterion for the existence of the community structure, and is applicable equally well to unweighted and weighted networks. We demonstrate the performance of the method by applying it to the Barbasi-Albert network, Zachary karate club network, the scientific collaboration network, and the stock price correlation network. (Ising, Potts, etc.)
引用
收藏
页码:431 / 437
页数:7
相关论文
共 36 条
  • [1] Alava MJ, 2001, PHASE TRANS, V18, P143, DOI 10.1016/S1062-7901(01)80009-4
  • [2] Statistical mechanics of complex networks
    Albert, R
    Barabási, AL
    [J]. REVIEWS OF MODERN PHYSICS, 2002, 74 (01) : 47 - 97
  • [3] Emergence of scaling in random networks
    Barabási, AL
    Albert, R
    [J]. SCIENCE, 1999, 286 (5439) : 509 - 512
  • [4] Superparamagnetic clustering of data
    Blatt, M
    Wiseman, S
    Domany, E
    [J]. PHYSICAL REVIEW LETTERS, 1996, 76 (18) : 3251 - 3254
  • [5] Topology of correlation-based minimal spanning trees in real and model markets
    Bonanno, G
    Caldarelli, G
    Lillo, F
    Mantegna, RN
    [J]. PHYSICAL REVIEW E, 2003, 68 (04)
  • [6] Clauset A, 2004, PHYS REV E, V70, DOI 10.1103/PhysRevE.70.066111
  • [7] Evolution of networks
    Dorogovtsev, SN
    Mendes, JFF
    [J]. ADVANCES IN PHYSICS, 2002, 51 (04) : 1079 - 1187
  • [8] Ford L. R, 1962, FLOWS NETWORKS
  • [9] Method to find community structures based on information centrality
    Fortunato, S
    Latora, V
    Marchiori, M
    [J]. PHYSICAL REVIEW E, 2004, 70 (05) : 13
  • [10] APPLICATION OF STATISTICAL-MECHANICS TO NP-COMPLETE PROBLEMS IN COMBINATORIAL OPTIMIZATION
    FU, YT
    ANDERSON, PW
    [J]. JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1986, 19 (09): : 1605 - 1620