Advanced

Network bipartivity

Holme, P.; Liljeros, F.; Edling, Christofer LU and Kim, B. J. (2003) In Physical Review E 68.
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
publishing date
type
Contribution to journal
publication status
published
subject
keywords
sociologi, optimization, ising-model, sociology, statistical-mechanics, collective behavior, complex networks
in
Physical Review E
volume
68
publisher
American Physical Society
ISSN
1063-651X
language
English
LU publication?
no
id
84f1ad04-e506-409e-a149-e7d1f062b5d0 (old id 2301144)
date added to LUP
2012-01-24 14:08:02
date last changed
2016-09-13 15:41:32
@misc{84f1ad04-e506-409e-a149-e7d1f062b5d0,
  abstract     = {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.},
  author       = {Holme, P. and Liljeros, F. and Edling, Christofer and Kim, B. J.},
  issn         = {1063-651X},
  keyword      = {sociologi,optimization,ising-model,sociology,statistical-mechanics,collective behavior,complex networks},
  language     = {eng},
  publisher    = {ARRAY(0x7a2cfe0)},
  series       = {Physical Review E},
  title        = {Network bipartivity},
  volume       = {68},
  year         = {2003},
}