Introduction
Dynamics are simple stochastic processes on graphs in which nodes update their
own state according to a symmetric function of the state of their neighbors
and of their current state, with no dependency on time or on the topology of
the graph [
27,26
]. In previous decades the computational power of this kind
of systems has been investigated by computer scientists, mathematicians, and
physicists. Recently it got a renewed interest from the theoretical computer
science community, as new algorithmic techniques make it possible to analyze
dynamics as distributed algorithms [
15,3,10,11,5,4
].
In the context of distributed computing one fundamental task is that of
reaching a consensus, i.e., a con guration where all nodes have the same state. In
this regard, the \trivial" example of dynamics is the so-called Voter dynamics,
in which in each round each node copies the opinion of a random neighbor.
Despite its apparent simplicity, some properties of this model have been proven
only recently [
23,20,7
]. The Voter dynamics is characterized by the property of
reaching a proportionate consensus 1 in polynomial time independently from the
network topology [
25
]. However, the convergence time is (n) even on networks
with small diameter such as expander and complete graphs.
1 The probability to converge to a state is proportional to the initial volume of that
state, i.e., to the sum of the degrees of the nodes supporting that state [
20
].
The simplest non-trivial example of dynamics is arguably the 2-Choices
dynamics, where at each discrete time step each node samples two random
neighbors with replacement and, if they have the same state, the node adopts that
state. Prior to our works [
13,14
], the 2-Choices dynamics has been only
analyzed on networks with good expansion properties, where it exhibits the same
emergent behavior of the Voter dynamics, but converges very quickly [
10,11
].
Phase Transition on Core-Periphery Networks
We study the behavior of the 2-Choices dynamics theoretically and empirically
on core-periphery networks [
13
]. These networks, well-known in social network
analysis, sociology, and economics [
9,17
], are characterized by a bipartition of
the nodes into a core, a small dense set of nodes that dominates the network, and
a periphery, the loosely connected remaining nodes. We consider an axiomatic
framework [
1
] which is based on two parameters only, dominance and robustness,
to express the in uence of the core on the periphery.2 We consider a natural
scenario, where agents in core and periphery initially have di erent states, and
show the following phase transition phenomenon:
Theorem 1. There exists a universal constant c? such that: if the dominance
is greater than c? and the core is robust enough, then a con guration of
almostconsensus is reached in O(log n) rounds, with high probability;3 if the dominance
is less than c?, then a metastable phase takes place where most of the nodes
retain their initial opinion for n!(1) rounds, with high probability.
We validate our theoretical results with experiments on real-world networks.
The experiments show some weaknesses in the heuristic used to identify the
core in [
1
]. We design a new heuristic able top identify a core with a volume
approximately equal to that of the periphery by repeatedly calculating
densestsubgraph approximations; with the Voter dynamics this is su cient to have
equal probability of consensus for both states and prior results on the 2-Choices
dynamics [
10,11
] require an initial biased con guration of the states to give
results on the consensus; our experiments show that the consensus is almost
always reached on the core's state. We believe these results may be useful for
understanding the principles that drive social and economic agents into forming
core-periphery networks.
Metastablility on Clustered Graphs and its Biological Implications
The long metastable phase that often occurs can be exploited in the context
of Label Propagation Algorithms (LPAs, started by [
28
]), a widely used class of
heuristics for graph clustering that matches the following general pattern:
1. Initially, each node is assigned a label, typically independent from the others
and uniformly at random.
2. Then, each node starts updating its current label according to a simple local
majority-based rule based on the labels of its neighbors.
2 We refer the reader to [
13
] for a formal de nition of these parameters.
3 Our analysis shows that the process does not deviate signi cantly from its expected
evolution with high probability, i.e., with probability at least 1 O(n c).
3. After a relatively short number of rounds, the labeling of the graph is
expected to stabilize and is declared to be the clustering of the graph.
Most of the work on label propagation algorithms has been empirical,
lacking formal arguments that show their ability in the detection of clusters. The
only rigorous analysis present in literature is the one of Max-LPA [
21
], where
each node updates its label to the most frequent label among all its neighbors.
Compared to the 2-Choices dynamics, Max-LPA has a higher cost in the
total number of messages exchanged in each round. For the rst time we analyze
a sparsi ed LPA, where every node chooses a random initial state out of two
possible ones and executes the 2-Choices dynamics [
14
]. In the following we
report the de nition of the class of graphs considered for the analysis and our
main theorem.
De nition 1 ([
6
]). A (2n; d; b)-clustered regular graph is de ned as a graph
G = (V1 [_ V2; E) such that: jV1j = jV2j = n; every node has degree d; every node
in V1 has b neighbors in V2 and every node in V2 has b neighbors in V1.
Theorem 2. If the 2-Choices dynamics is initialized in a slightly asymmetric
way w.r.t. the clusters,4 then with constant probability the network rapidly
converges to a metastable phase in which almost all nodes within each cluster share
the same state and the predominant states of the clusters are di erent.
The states of the nodes in the metastable phase constitute a labeling which
reveals the clustered structure of the network. The probability to converge to such
a phase can be ampli ed via Community-Sensitive Labeling [
2
]. Our analysis
exploits some spectral properties of the transition matrices of simple random walks
on clustered regular graphs and, compared to that of Max-LPA, it considers
much sparser communities at the price of a stricter condition on the cut.
Evolutionary Biology. From our theoretical results in [
14
], it is possible
to derive some biological implications. Evolutionary dynamics is the branch of
genetics which studies how populations evolve genetically as a result of the
individuals' interactions [
16
]. Lieberman et al. initiated the study of evolutionary
dynamics on graphs by investigating the xation probability of the Moran process,
namely the probability that a new mutation with increased tness eventually
spreads across all individuals in the population [
22
]. However, no simple
dynamics has been proposed in the context of evolutionary graph theory to explain one
of evolution's fundamental phenomena, namely speciation [
12
].
Two fundamental classes of driving forces for speciation can be distinguished:
allopatric speciation and sympatric/parapatric speciation. The former, which
refers to the divergence of species resulting from geographical isolation, is well
understood [
29
]; the latter, namely divergence of species without complete
geographical isolation, is still controversial [
29,8
]. In several evolutionary settings,
the spread of a mutation appears nonlinear w.r.t. the number of interacting
individuals carrying the mutation, exhibiting a drift towards the most frequent
4 For example, if every node choose the initial state according to the ip of a fair coin.
phenotypes [
19,12
]. We look at the 2-Choices dynamics on clustered graphs as
a quadratic evolutionary dynamics on sympatric and parapatric scenarios. The
random initialization of the 2-Choices dynamics can be regarded as two
intermixed populations of individuals with di erent genetic pools. The interactions for
reproduction between the two populations can be categorized in frequent
interactions among individuals within an equal-size bipartition of the populations (the
clusters) and less frequent interactions between the two populations. This can
be interpreted as genetic admixture, i.e., interbreeding between two
geneticallydiverging populations [
24
]. Within such framework, our theorem provides an
analytical evolutionary graph-theoretic proof of concept on how speciation can
emerge from the simple nonlinear underlying dynamics of the evolutionary
process on the population level.
Neuroscience. During mammalian development, neuromuscular junctions
and some other postsynaptic cells transition from having multiple neurons
innervating onto them into having a single neuron only [
18,30
]. This process takes
place as synaptic sites are exchanged between di erent axons: Locations on the
surface of the cell on which neurons innervate transition from being freed by
the current innervating neuron to be occupied again by a new one [
30
]. In [
30
],
a simplistic model for the aforementioned process has been provided, which is
equivalent to the Voter when the underlying graph is regular. In [
14
], we argue
that our analysis provides evidence for the fact that, in order for a model based
on dynamics to comply with experimental evidence on the outcome of the
innervation process, either the innervation sites do not exhibit spatial bottlenecks
or the dynamics cannot be based on majority-like mechanisms.