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 rates of state spread (r) and random rewiring (q) (p = 1 and w = 0.001). Snapshots were taken at t = 5 × 106, to ensure that any transient dynamics had passed. Different colours indicate different states. Again, three classes of stable system behaviour can be distinguished. (i) Random network topologies result not only when the rate of random rewiring is high (q = 1), but also when the rate of state spread is either very low or very high. In the former case, the absence of state spread inhibits the organizing tendencies of homophilous rewiring; in the latter case, a single group rapidly establishes itself and dominates the population, in which case homophilous rewiring becomes effectively equivalent to random rewiring. (ii) When the rate of random rewiring is low and there is a moderate level of state spread (e.g. r = 0.001; q = 0.1), the network fractures into a set of disconnected, homogeneous components. (iii) With intermediate levels of both state spread and random rewiring (e.g. r = 0.01; q = 0.01), 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

RSIF20100524F3: Network snapshots for different rates of state spread (r) and random rewiring (q) (p = 1 and w = 0.001). Snapshots were taken at t = 5 × 106, to ensure that any transient dynamics had passed. Different colours indicate different states. Again, three classes of stable system behaviour can be distinguished. (i) Random network topologies result not only when the rate of random rewiring is high (q = 1), but also when the rate of state spread is either very low or very high. In the former case, the absence of state spread inhibits the organizing tendencies of homophilous rewiring; in the latter case, a single group rapidly establishes itself and dominates the population, in which case homophilous rewiring becomes effectively equivalent to random rewiring. (ii) When the rate of random rewiring is low and there is a moderate level of state spread (e.g. r = 0.001; q = 0.1), the network fractures into a set of disconnected, homogeneous components. (iii) With intermediate levels of both state spread and random rewiring (e.g. r = 0.01; q = 0.01), densely connected homogeneous state groups are evident, but the network as a whole also remains connected.

Mentions: We find that, under appropriate parameters, the model shows community structure with several concurrent groups, many of which have relatively long lifetimes (figure 3). The sizes of the groups, as well as their composition, are dynamic as nodes join and leave them in the close interplay of state changes and edge rewiring (figure 4). Again, we see that, under a wide range of parameters, some global properties, such as clustering coefficient or network modularity, stabilize as the network keeps evolving. Mathematical analysis (see appendix A.1) also predicts stability of network modularity and gives a good approximation of the corresponding topological network modularity (as with figure 2) when the state spread parameters maintain a moderate number of groups (between n/50 and n/3).


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 rates of state spread (r) and random rewiring (q) (p = 1 and w = 0.001). Snapshots were taken at t = 5 × 106, to ensure that any transient dynamics had passed. Different colours indicate different states. Again, three classes of stable system behaviour can be distinguished. (i) Random network topologies result not only when the rate of random rewiring is high (q = 1), but also when the rate of state spread is either very low or very high. In the former case, the absence of state spread inhibits the organizing tendencies of homophilous rewiring; in the latter case, a single group rapidly establishes itself and dominates the population, in which case homophilous rewiring becomes effectively equivalent to random rewiring. (ii) When the rate of random rewiring is low and there is a moderate level of state spread (e.g. r = 0.001; q = 0.1), the network fractures into a set of disconnected, homogeneous components. (iii) With intermediate levels of both state spread and random rewiring (e.g. r = 0.01; q = 0.01), 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

RSIF20100524F3: Network snapshots for different rates of state spread (r) and random rewiring (q) (p = 1 and w = 0.001). Snapshots were taken at t = 5 × 106, to ensure that any transient dynamics had passed. Different colours indicate different states. Again, three classes of stable system behaviour can be distinguished. (i) Random network topologies result not only when the rate of random rewiring is high (q = 1), but also when the rate of state spread is either very low or very high. In the former case, the absence of state spread inhibits the organizing tendencies of homophilous rewiring; in the latter case, a single group rapidly establishes itself and dominates the population, in which case homophilous rewiring becomes effectively equivalent to random rewiring. (ii) When the rate of random rewiring is low and there is a moderate level of state spread (e.g. r = 0.001; q = 0.1), the network fractures into a set of disconnected, homogeneous components. (iii) With intermediate levels of both state spread and random rewiring (e.g. r = 0.01; q = 0.01), densely connected homogeneous state groups are evident, but the network as a whole also remains connected.
Mentions: We find that, under appropriate parameters, the model shows community structure with several concurrent groups, many of which have relatively long lifetimes (figure 3). The sizes of the groups, as well as their composition, are dynamic as nodes join and leave them in the close interplay of state changes and edge rewiring (figure 4). Again, we see that, under a wide range of parameters, some global properties, such as clustering coefficient or network modularity, stabilize as the network keeps evolving. Mathematical analysis (see appendix A.1) also predicts stability of network modularity and gives a good approximation of the corresponding topological network modularity (as with figure 2) when the state spread parameters maintain a moderate number of groups (between n/50 and n/3).

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