Network bipartivity

被引:109
作者
Holme, P [1 ]
Liljeros, F
Edling, CR
Kim, BJ
机构
[1] Umea Univ, Dept Phys, S-90187 Umea, Sweden
[2] Swedish Infect Dis Control, Dept Epidemiol, S-17182 Solna, Sweden
[3] Stockholm Univ, Dept Sociol, S-10691 Stockholm, Sweden
[4] Ajou Univ, Dept Mol Sci & Technol, Suwon 442749, South Korea
关键词
D O I
10.1103/PhysRevE.68.056107
中图分类号
O35 [流体力学]; O53 [等离子体物理学];
学科分类号
070204 ; 080103 ; 080704 ;
摘要
Systems with two types of agents with a preference for heterophilous interaction produce networks that are more or less close to bipartite. We propose two measures quantifying the notion of bipartivity. The two measures-one well known and natural, but computationally intractable, and the other computationally less complex, but also less intuitive-are examined on model networks that continuously interpolate between bipartite graphs and graphs with many odd circuits. We find that the bipartivity measures increase as we tune the control parameters of the test networks to intuitively increase the bipartivity, and thus conclude that the measures are quite relevant. We also measure and discuss the values of our bipartivity measures for empirical social networks (constructed from professional collaborations, Internet communities, and field surveys). Here we find, as expected, that networks arising from romantic online interaction have high, and professional collaboration networks have low, bipartivity values. In some other cases, probably due to low average degree of the network, the bipartivity measures cannot distinguish between romantic and friendship oriented interaction.
引用
收藏
页码:561071 / 561071
页数:12
相关论文
共 58 条
[11]   ON THE COMPUTATIONAL-COMPLEXITY OF ISING SPIN-GLASS MODELS [J].
BARAHONA, F .
JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1982, 15 (10) :3241-3253
[12]   On the properties of small-world network models [J].
Barrat, A ;
Weigt, M .
EUROPEAN PHYSICAL JOURNAL B, 2000, 13 (03) :547-560
[13]  
BEARMAN PS, UNPUB
[14]   Mean field solution of the Ising model on a Barabasi-Albert network [J].
Bianconi, G .
PHYSICS LETTERS A, 2002, 303 (2-3) :166-168
[15]   Interface motion and pinning in small-world networks [J].
Boyer, D ;
Miramontes, O .
PHYSICAL REVIEW E, 2003, 67 (03) :4-035102
[16]  
CALDARELLI G, CONDMAT0212026
[17]  
Cheeseman P C., 1991, INT JOINT C ARTIFICI, V91, P331
[18]  
Davis G. F., 2003, Strategic Organization, V1, P301, DOI 10.1177/14761270030013002
[19]   Evolution of networks [J].
Dorogovtsev, SN ;
Mendes, JFF .
ADVANCES IN PHYSICS, 2002, 51 (04) :1079-1187
[20]   How can statistical mechanics contribute to social science? [J].
Durlauf, SN .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1999, 96 (19) :10582-10584