Saturday, July 12, 2014

Emergence and Persistence of Communities in Coevolutionary Networks

Here is some serious geekery for your Saturday entertainment. This is a fairly complex and computational model of how social communities emerge and survive over time through a process called "adaptive rewiring."

Here is a brief overview of how these coevolutionary networks might exist in different realms:
In a social network, communities might indicate factions, interest groups, or social divisions [1]; in biological networks, they encompass entities having the same biological function [5–7]; in the WorldWideWeb they may correspond to groups of pages dealing with the same or related topics [8]; in food webs they may identify compartments [9]; and a community in a metabolic or genetic network might be related to a specific functional task [10].
And for those of us who are not familiar with this field or its terminology, here is a glossary of network terminology, taken from Gross and Blasius (2008).
A brief network glossary.

Degree. The degree of a node is the number of nearest neighbours to which a node is connected. The mean degree of the network is the mean of the individual degrees of all nodes in the network.
Dynamics. Depending on the context, the term dynamics is used in the literature to refer to a temporal change of either the state or the topology of a network. In this paper, we use the term dynamics exclusively to describe a change in the state, while the term evolution is used to describe a change in the topology.
Evolution. Depending on the context the term evolution is used in the literature to refer to a temporal change of either the state or the topology of a network. In this paper, we use the term evolution exclusively to describe a change in the topology, while the term dynamics is used to describe a change in the state.
Frozen nodes. A node is said to be frozen if its state does not change over in the long-term behaviour of the network. In certain systems discussed here, the state of frozen nodes can change nevertheless on an even longer (topological) time scale.
Link. A link is a connection between two nodes in the networks. Links are also sometimes called edges or simply network connections.
Neighbours. Two nodes are said to be neighbours if they are connected by a link.
Node. The node is the principal unit of the network. A network consists of a number of nodes connected by links. Nodes are sometimes also called vertices.
Scale-free network. In scale-free networks, the distribution of node degrees follows a power law.
State of the network. Depending on the context, the state of a network is used either to describe the state of the network nodes or the state of the whole network including the nodes and the topology. In this review, we use the term state to refer exclusively to the collective state of the nodes. Thus, the state is a priori independent of the network topology.
Topology of the network. The topology of a network defines a specific pattern of connections between the network nodes.
And from the same authors (citation at the bottom of the post), here is a visual representation of how adaptive rewiring might look:


This is interesting stuff and it seems very relevant to emerging coevolutionary networks in P2P communities and other cooperative networks that emerging in the post-capitalist world.

Full Citation:
González-Avella, JC, Cosenza, MG, Herrera, JL, & Tucci, K. (2014, Jul 1). Emergence and persistence of communities in coevolutionary networks. arXiv:1407.0388v1

Emergence and persistence of communities in coevolutionary networks

J. C. González-Avella, M. G. Cosenza, J. L. Herrera, K. Tucci
ABSTRACT
We investigate the emergence and persistence of communities through a recently proposed mechanism of adaptive rewiring in coevolutionary networks. We characterize the topological structures arising in a coevolutionary network subject to an adaptive rewiring process and a node dynamics given by a simple voterlike rule. We find that, for some values of the parameters describing the adaptive rewiring process, a community structure emerges on a connected network. We show that the emergence of communities is associated to a decrease in the number of active links in the system, i.e. links that connect two nodes in different states. The lifetime of the community structure state scales exponentially with the size of the system. Additionally, we find that a small noise in the node dynamics can sustain a diversity of states and a community structure in time in a finite size system. Thus, large system size and/or local noise can explain the persistence of communities and diversity in many real systems.

I. INTRODUCTION

Many social, biological, and technological systems possess a characteristic network structure consisting of communities or modules, which are groups of nodes distinguished by having a high density of links between nodes of the same group and a comparatively low density of links between nodes of different groups [1–4]. Such a network structure is expected to play an important functional role in many systems. In a social network, communities might indicate factions, interest groups, or social divisions [1]; in biological networks, they encompass entities having the same biological function [5–7]; in the WorldWideWeb they may correspond to groups of pages dealing with the same or related topics [8]; in food webs they may identify compartments [9]; and a community in a metabolic or genetic network might be related to a specific functional task [10].

Since community structure constitutes a fundamental feature of many networks, the development of methods and techniques for the detection of communities represents one of the most active research areas in network science [2, 11–17]. In comparison, much less work has been done to address a fundamental question: how do communities arise in networks? [18].

Clearly, the emergence of characteristic topological structures, including communities, from a random or featureless network requires some dynamical process that modifies the properties of the links representing the interactions between nodes. We refer to such link dynamics as a rewiring process. Links can vary their strength, or they can appear and disappear as a consequence of a rewiring process. In our view, two classes of rewiring processes leading to the formation of structures in networks can be distinguished: (i) rewirings based on local connectivity properties regardless of the values of the state variables of the nodes, which we denote as topological rewirings; and (ii) rewirings that depend on the state variables of the nodes, where the link dynamics is coupled to the node state dynamics and which we call adaptive rewirings.

Topological rewiring processes have been employed to explain the origin of small-world and scale-free networks [19, 20]. These rewirings can lead to the appearance of community structures in networks with weighted links [21] or by preferential attachment driven by local clustering [22]. On the other hand, there is currently much interest in the study of networks that exhibit a coupling between topology and states, since many systems observed in nature can be described as dynamical networks of interacting nodes where the connections and the states of the nodes affect each other and evolve simultaneously [23–29]. These systems have been denoted as coevolutionary dynamical systems or adaptive networks and, according to our classification above, they are subject to adaptive rewiring processes. The collective behavior of coevolutionary systems is determined by the competition of the time scales of the node dynamics and the rewiring process. Most works that employ coevolutionary dynamics have focused on the characterization of the phenomenon of network fragmentation arising from this competition. Although community structures have been found in some coevolutionary systems [30–33], investigating the mechanisms for the formation of perdurable communities remains an open problem.

In this paper we investigate the emergence and the persistence of communities in networks induced by a process of adaptive rewiring. Our work is based on a recently proposed general framework for coevolutionary dynamics in networks [29]. We characterize the topological structures forming in a coevolutionary network having a simple node dynamics. We unveil a region of parameters where the formation of a supertransient modular structure on the network occurs. We study the stability of the community configuration under small perturbations of the node dynamics, as well as for different initial conditions of the system.

Reference:
Gross, T, and Blasius, B. (2008, Mar). Adaptive coevolutionary networks: A review. Journal of the Royal Society Interface; 5(20): 259-271. doi: 10.1098/​rsif.2007.1229
Post a Comment