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

Network snapshots for different values of a (where a = p/q) when no state update occurs (i.e. r = w = 0). Different colours indicate different states. Three classes of stable system behaviour can be distinguished: (a) when the rate of random rewiring is high with respect to random rewiring (e.g. a = 1), network topology is random; (b) when the rate of random rewiring is low (e.g. a = 0.01), the network fractures into a set of disconnected, homogeneous components; (c) when homophilous and random rewiring are balanced (e.g. a = 0.1), densely connected homogeneous state groups are evident, but the network as a whole also remains connected.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

RSIF20100524F1: Network snapshots for different values of a (where a = p/q) when no state update occurs (i.e. r = w = 0). Different colours indicate different states. Three classes of stable system behaviour can be distinguished: (a) when the rate of random rewiring is high with respect to random rewiring (e.g. a = 1), network topology is random; (b) when the rate of random rewiring is low (e.g. a = 0.01), the network fractures into a set of disconnected, homogeneous components; (c) when homophilous and random rewiring are balanced (e.g. a = 0.1), densely connected homogeneous state groups are evident, but the network as a whole also remains connected.

Mentions: When we run the model global network properties such as clustering coefficient, average shortest path length and modularity stabilize in spite of the ongoing dynamics. Generally, three different scenarios of network topology emerge (see figure 1) depending on the distribution of states and the relative fraction of homophilous versus random rewiring events,3.1If a is small, or most rewiring events connect random nodes, the resulting dynamic networks are of Erdős–Rényi type at any point in time, with the usual characteristics of low clustering, short path lengths and low modularity. If a is large, or most rewiring events connect nodes of the same state, groups of nodes sharing the same state form tight communities with only transient connections to the rest of the network. These transient connections, when they come into place, are quickly rewired to again connect nodes of the same state. In that case, while the communities disconnect and reconnect over time, at any specific point in time the network fractures into components of nodes with the same state, with the size of these components depending on the abundance of the corresponding states. These network snapshots possess strong clustering, but since they are disconnected they cannot be associated with meaningful modularity and average path lengths.


Stability in flux: community structure in dynamic networks.

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

Network snapshots for different values of a (where a = p/q) when no state update occurs (i.e. r = w = 0). Different colours indicate different states. Three classes of stable system behaviour can be distinguished: (a) when the rate of random rewiring is high with respect to random rewiring (e.g. a = 1), network topology is random; (b) when the rate of random rewiring is low (e.g. a = 0.01), the network fractures into a set of disconnected, homogeneous components; (c) when homophilous and random rewiring are balanced (e.g. a = 0.1), densely connected homogeneous state groups are evident, but the network as a whole also remains connected.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

RSIF20100524F1: Network snapshots for different values of a (where a = p/q) when no state update occurs (i.e. r = w = 0). Different colours indicate different states. Three classes of stable system behaviour can be distinguished: (a) when the rate of random rewiring is high with respect to random rewiring (e.g. a = 1), network topology is random; (b) when the rate of random rewiring is low (e.g. a = 0.01), the network fractures into a set of disconnected, homogeneous components; (c) when homophilous and random rewiring are balanced (e.g. a = 0.1), densely connected homogeneous state groups are evident, but the network as a whole also remains connected.
Mentions: When we run the model global network properties such as clustering coefficient, average shortest path length and modularity stabilize in spite of the ongoing dynamics. Generally, three different scenarios of network topology emerge (see figure 1) depending on the distribution of states and the relative fraction of homophilous versus random rewiring events,3.1If a is small, or most rewiring events connect random nodes, the resulting dynamic networks are of Erdős–Rényi type at any point in time, with the usual characteristics of low clustering, short path lengths and low modularity. If a is large, or most rewiring events connect nodes of the same state, groups of nodes sharing the same state form tight communities with only transient connections to the rest of the network. These transient connections, when they come into place, are quickly rewired to again connect nodes of the same state. In that case, while the communities disconnect and reconnect over time, at any specific point in time the network fractures into components of nodes with the same state, with the size of these components depending on the abundance of the corresponding states. These network snapshots possess strong clustering, but since they are disconnected they cannot be associated with meaningful modularity and average path lengths.

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