Limits...
Stability in flux: community structure in dynamic networks.

Bryden J, Funk S, Geard N, Bullock S, Jansen VA - J R Soc Interface (2010)

Bottom Line: We show that if nodes rewire their edges based on fixed node states, the network modularity reaches a stable equilibrium which we quantify analytically.Furthermore, if node state is not fixed, but can be adopted from neighbouring nodes, the distribution of group sizes reaches a dynamic equilibrium, which remains stable even as the composition and identity of the groups change.These results show that dynamic networks can maintain the stable community structure that has been observed in many social and biological systems.

View Article: PubMed Central - PubMed

Affiliation: School of Biological Sciences, Royal Holloway, University of London, Egham TW20 0EX, UK. john.bryden@rhul.ac.uk

ABSTRACT
The structure of many biological, social and technological systems can usefully be described in terms of complex networks. Although often portrayed as fixed in time, such networks are inherently dynamic, as the edges that join nodes are cut and rewired, and nodes themselves update their states. Understanding the structure of these networks requires us to understand the dynamic processes that create, maintain and modify them. Here, we build upon existing models of coevolving networks to characterize how dynamic behaviour at the level of individual nodes generates stable aggregate behaviours. We focus particularly on the dynamics of groups of nodes formed endogenously by nodes that share similar properties (represented as node state) and demonstrate that, under certain conditions, network modularity based on state compares well with network modularity based on topology. We show that if nodes rewire their edges based on fixed node states, the network modularity reaches a stable equilibrium which we quantify analytically. Furthermore, if node state is not fixed, but can be adopted from neighbouring nodes, the distribution of group sizes reaches a dynamic equilibrium, which remains stable even as the composition and identity of the groups change. These results show that dynamic networks can maintain the stable community structure that has been observed in many social and biological systems.

Show MeSH

Related in: MedlinePlus

Autocorrelation measures for node and state group properties (p = 1.0; q = r = w = 0.01). Node state (pulses) measures the fraction of nodes that are in the same state at time t + d as they were at time t. Node neighbourhood (circles) measures the fraction of node pairs that are neighbours at time t + d that were also neighbours at time t. Group overlap (crosses) measures the relative overlap in group membership between time t and time t + d. Note that all three measures drop rapidly with initial increases in correlation distance; thereafter, some correlation remains at the group level, while node-level correlation drops close to zero.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC3104331&req=5

RSIF20100524F6: Autocorrelation measures for node and state group properties (p = 1.0; q = r = w = 0.01). Node state (pulses) measures the fraction of nodes that are in the same state at time t + d as they were at time t. Node neighbourhood (circles) measures the fraction of node pairs that are neighbours at time t + d that were also neighbours at time t. Group overlap (crosses) measures the relative overlap in group membership between time t and time t + d. Note that all three measures drop rapidly with initial increases in correlation distance; thereafter, some correlation remains at the group level, while node-level correlation drops close to zero.

Mentions: If we assume such exchanges of nodes between groups of states to occur completely randomly, the probability distribution Pi of groups that have i nodes is given by the Boltzmann distribution (see appendix A.2)3.7Simulations confirm that the state distribution does indeed stabilize (figure 5). However, while the shape of the distribution remains relatively constant, the identity of groups at a particular rank does not. The ongoing dynamics at the node level causes states to grow and shrink in abundance (figure 6).


Stability in flux: community structure in dynamic networks.

Bryden J, Funk S, Geard N, Bullock S, Jansen VA - J R Soc Interface (2010)

Autocorrelation measures for node and state group properties (p = 1.0; q = r = w = 0.01). Node state (pulses) measures the fraction of nodes that are in the same state at time t + d as they were at time t. Node neighbourhood (circles) measures the fraction of node pairs that are neighbours at time t + d that were also neighbours at time t. Group overlap (crosses) measures the relative overlap in group membership between time t and time t + d. Note that all three measures drop rapidly with initial increases in correlation distance; thereafter, some correlation remains at the group level, while node-level correlation drops close to zero.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC3104331&req=5

RSIF20100524F6: Autocorrelation measures for node and state group properties (p = 1.0; q = r = w = 0.01). Node state (pulses) measures the fraction of nodes that are in the same state at time t + d as they were at time t. Node neighbourhood (circles) measures the fraction of node pairs that are neighbours at time t + d that were also neighbours at time t. Group overlap (crosses) measures the relative overlap in group membership between time t and time t + d. Note that all three measures drop rapidly with initial increases in correlation distance; thereafter, some correlation remains at the group level, while node-level correlation drops close to zero.
Mentions: If we assume such exchanges of nodes between groups of states to occur completely randomly, the probability distribution Pi of groups that have i nodes is given by the Boltzmann distribution (see appendix A.2)3.7Simulations confirm that the state distribution does indeed stabilize (figure 5). However, while the shape of the distribution remains relatively constant, the identity of groups at a particular rank does not. The ongoing dynamics at the node level causes states to grow and shrink in abundance (figure 6).

Bottom Line: We show that if nodes rewire their edges based on fixed node states, the network modularity reaches a stable equilibrium which we quantify analytically.Furthermore, if node state is not fixed, but can be adopted from neighbouring nodes, the distribution of group sizes reaches a dynamic equilibrium, which remains stable even as the composition and identity of the groups change.These results show that dynamic networks can maintain the stable community structure that has been observed in many social and biological systems.

View Article: PubMed Central - PubMed

Affiliation: School of Biological Sciences, Royal Holloway, University of London, Egham TW20 0EX, UK. john.bryden@rhul.ac.uk

ABSTRACT
The structure of many biological, social and technological systems can usefully be described in terms of complex networks. Although often portrayed as fixed in time, such networks are inherently dynamic, as the edges that join nodes are cut and rewired, and nodes themselves update their states. Understanding the structure of these networks requires us to understand the dynamic processes that create, maintain and modify them. Here, we build upon existing models of coevolving networks to characterize how dynamic behaviour at the level of individual nodes generates stable aggregate behaviours. We focus particularly on the dynamics of groups of nodes formed endogenously by nodes that share similar properties (represented as node state) and demonstrate that, under certain conditions, network modularity based on state compares well with network modularity based on topology. We show that if nodes rewire their edges based on fixed node states, the network modularity reaches a stable equilibrium which we quantify analytically. Furthermore, if node state is not fixed, but can be adopted from neighbouring nodes, the distribution of group sizes reaches a dynamic equilibrium, which remains stable even as the composition and identity of the groups change. These results show that dynamic networks can maintain the stable community structure that has been observed in many social and biological systems.

Show MeSH
Related in: MedlinePlus