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

Distribution of the times it takes until a node changes its state (dashed line), and distribution of the total lifetimes of states from first innovation until they go extinct (solid line) for three different sets of parameters representing different relative time scales of state spread and homophilous rewiring: (a) fast state spread (n = 102; b = 10−3; c = 10−3), (b) similar time scales (n = 102; b = 10−3; c = 10−1.5), (c) fast rewiring (n = 101.5; b = 10−3; c = 103).
© Copyright Policy - open-access
Related In: Results  -  Collection

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

RSIF20100524F7: Distribution of the times it takes until a node changes its state (dashed line), and distribution of the total lifetimes of states from first innovation until they go extinct (solid line) for three different sets of parameters representing different relative time scales of state spread and homophilous rewiring: (a) fast state spread (n = 102; b = 10−3; c = 10−3), (b) similar time scales (n = 102; b = 10−3; c = 10−1.5), (c) fast rewiring (n = 101.5; b = 10−3; c = 103).

Mentions: In fact, every state that appears in the network via the innovation process will eventually go extinct due to the inherent stochasticity of the model. This becomes clear when we consider the lifetime distribution of states. In figure 7, we compare the distribution of change of states in nodes (i.e. the time it takes until the state of a given node changes) with the distribution of lifetimes of states in all nodes (i.e. the time between a state being introduced through innovation and its extinction) where state spread and homophilous rewiring are much more frequent than the randomizing processes of innovation and random rewiring. When state spread happens on time scales faster than homophilous rewiring, the changes in network structure resulting from rewiring will be too slow to create a modular structure—one dominant group forms and persists for a long time, while most newly innovated states go extinct quickly. Thus the distribution of node state changes and states largely coincide.


Stability in flux: community structure in dynamic networks.

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

Distribution of the times it takes until a node changes its state (dashed line), and distribution of the total lifetimes of states from first innovation until they go extinct (solid line) for three different sets of parameters representing different relative time scales of state spread and homophilous rewiring: (a) fast state spread (n = 102; b = 10−3; c = 10−3), (b) similar time scales (n = 102; b = 10−3; c = 10−1.5), (c) fast rewiring (n = 101.5; b = 10−3; c = 103).
© Copyright Policy - open-access
Related In: Results  -  Collection

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

RSIF20100524F7: Distribution of the times it takes until a node changes its state (dashed line), and distribution of the total lifetimes of states from first innovation until they go extinct (solid line) for three different sets of parameters representing different relative time scales of state spread and homophilous rewiring: (a) fast state spread (n = 102; b = 10−3; c = 10−3), (b) similar time scales (n = 102; b = 10−3; c = 10−1.5), (c) fast rewiring (n = 101.5; b = 10−3; c = 103).
Mentions: In fact, every state that appears in the network via the innovation process will eventually go extinct due to the inherent stochasticity of the model. This becomes clear when we consider the lifetime distribution of states. In figure 7, we compare the distribution of change of states in nodes (i.e. the time it takes until the state of a given node changes) with the distribution of lifetimes of states in all nodes (i.e. the time between a state being introduced through innovation and its extinction) where state spread and homophilous rewiring are much more frequent than the randomizing processes of innovation and random rewiring. When state spread happens on time scales faster than homophilous rewiring, the changes in network structure resulting from rewiring will be too slow to create a modular structure—one dominant group forms and persists for a long time, while most newly innovated states go extinct quickly. Thus the distribution of node state changes and states largely coincide.

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