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

Modularity based on maximal topological modularity as given by the Girvan–Newman algorithm (Qt) as measured in simulations (crosses), and as given by our algorithm identifying modules based on state (Qs), as predicted analytically (solid line) and measured in simulations (circles), in terms of the fraction of rewiring events that are homophilous, a = p/q.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

RSIF20100524F2: Modularity based on maximal topological modularity as given by the Girvan–Newman algorithm (Qt) as measured in simulations (crosses), and as given by our algorithm identifying modules based on state (Qs), as predicted analytically (solid line) and measured in simulations (circles), in terms of the fraction of rewiring events that are homophilous, a = p/q.

Mentions: If each node is initialized randomly with one of y states (0 ≪ y ≪ n), the value of ɛ is given by summing over a Poisson distribution,3.3In a similar way ɛ can be calculated for other state distributions. Over a period of time where every link is rewired at least once (which is of the order of (p + q)−1), the proportion of within-state edges will converge to x ≈ (p + ɛq)/(p + q), giving the modularity for the state partition as3.4The two processes can thus be used to generate a network that has a partition with modularity given by Qs. This can be compared with the modularity Qt of the partition of the same network that uses topological analysis to maximize modularity (e.g. [9]). When community structure has been introduced by homophilously increasing the numbers of links between nodes of the same state, with all other links placed randomly, it is unlikely that any topological partition that splits up or combines groups of nodes of the same state could achieve a greater level of modularity than that found in the state partition. This intuition is confirmed in figure 2, which shows how the topologically generated partition corresponds to the state partition when the network has topological community structure (Qt > 0.4).


Stability in flux: community structure in dynamic networks.

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

Modularity based on maximal topological modularity as given by the Girvan–Newman algorithm (Qt) as measured in simulations (crosses), and as given by our algorithm identifying modules based on state (Qs), as predicted analytically (solid line) and measured in simulations (circles), in terms of the fraction of rewiring events that are homophilous, a = p/q.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

RSIF20100524F2: Modularity based on maximal topological modularity as given by the Girvan–Newman algorithm (Qt) as measured in simulations (crosses), and as given by our algorithm identifying modules based on state (Qs), as predicted analytically (solid line) and measured in simulations (circles), in terms of the fraction of rewiring events that are homophilous, a = p/q.
Mentions: If each node is initialized randomly with one of y states (0 ≪ y ≪ n), the value of ɛ is given by summing over a Poisson distribution,3.3In a similar way ɛ can be calculated for other state distributions. Over a period of time where every link is rewired at least once (which is of the order of (p + q)−1), the proportion of within-state edges will converge to x ≈ (p + ɛq)/(p + q), giving the modularity for the state partition as3.4The two processes can thus be used to generate a network that has a partition with modularity given by Qs. This can be compared with the modularity Qt of the partition of the same network that uses topological analysis to maximize modularity (e.g. [9]). When community structure has been introduced by homophilously increasing the numbers of links between nodes of the same state, with all other links placed randomly, it is unlikely that any topological partition that splits up or combines groups of nodes of the same state could achieve a greater level of modularity than that found in the state partition. This intuition is confirmed in figure 2, which shows how the topologically generated partition corresponds to the state partition when the network has topological community structure (Qt > 0.4).

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