Relaxation dynamics of maximally clustered networks
Janis Klaise Samuel Johnson







 J.Klaise@warwick.ac.uk
 Centre for Complexity Science, University of Warwick, Coventry CV4 7AL, United Kingdom

 S.Johnson.2@warwick.ac.uk
Warwick Mathematics Institute, University of Warwick, Coventry CV4 7AL, United Kingdom



             


We study the relaxation dynamics of fully clustered networks (maximal number of triangles) to an unclustered state under two different edge dynamics—the double-edge swap, corresponding to degree-preserving randomization of the configuration model, and single edge replacement, corresponding to full randomization of the Erdős–Rényi random graph. We derive expressions for the time evolution of the degree distribution, edge multiplicity distribution and clustering coefficient. We show that under both dynamics networks undergo a continuous phase transition in which a giant connected component is formed. We calculate the position of the phase transition analytically using the Erdős–Rényi phenomenology.


89.75.Hc, 64.60.aq
                             

                              
Relaxation dynamics of maximally clustered networks
    Samuel Johnson
    December 30, 2023
===================================================







§ INTRODUCTION

Network science has enjoyed an unprecedented popularity in the last two decades as a paradigm for studying complex, interacting systems such as the Internet <cit.>, World Wide Web <cit.>, food webs <cit.>, scientific collaboration networks <cit.>, social and biological networks <cit.>, contact networks <cit.> and many others <cit.>. Many of these empirical networks exhibit a high degree of clustering or transitivity, i.e. a significant number of short, closed loops forming triangles <cit.>. This phenomenon is most commonly quantified by the clustering coefficient, defined as the proportion of connected triads that are also triangles in a network <cit.>.

The classical random network models, the Erdős–Rényi random graph <cit.> and the configuration model <cit.>, both suffer from being unable to generate networks with significant values of the clustering coefficient thus making them unsuitable for modelling many real networks. High values of the clustering coefficient observed in empirical networks have lead to a surge of random network models that are capable of generating significant numbers of triangles <cit.>. The relationship between clustering and other network properties has also been studied extensively <cit.>. However, despite the large body of research, the inherent violation of edge independence in highly clustered networks has made it difficult to understand the full implications of clustering. Common issues encountered when dealing with highly clustered networks include difficulties of network sampling <cit.>, inability to use edge independence to derive accurate results <cit.> and potentially overstated inferences of causality <cit.>. This points to a need for more fundamental research in clustered networks.

In this paper we explore simple dynamics of highly clustered networks relaxing to an unclustered equilibrium state. Specificaly, we study the evolution of the clustering coefficient under two edge rewiring schemes starting with fully clustered, degree-regular networks, i.e. networks in which all nodes have the same number of neighbours and a maximal number of triangles. We find that under both dynamics whose equilibrium distributions correspond to the Erdős–Rényi random graph and the configuration model respectively, a giant connected component emerges via a continuous phase transition. We provide an analytical prediction of the critical point for this transition as well as derive time evolution equations for various network properties.



§ METHODS



 §.§ Network metrics

We consider undirected graphs with N nodes and L edges described by a symmetric N× N adjacency matrix 𝐀 with binary edge variables A_ij∈{ 0,1} for i,j∈{ 1,…,N} with A_ij=1, i≠ j indicating an edge between nodes i and j so that L=∑_i,jA_ij. The degree distribution of a network is defined as p_k=N_k/N, where N_k is the number of nodes with degree k. We denote the nth moment of the degree distribution by k^n.

We define the multiplicity m_ij of an edge ij to be the number of triangles it participates in <cit.>. Similarly to the degree distribution, we define the edge multiplicity (or simply multiplicity) distribution as q_m=L_m/L, where L_m is the number of edges with multiplicity m. We denote the nth moment of the multiplicity distribution by m^n.

The clustering coefficient of a network is defined as three times the number of triangles divided by the number of connected triples, i.e. C=3N_/N_∧ <cit.>. This measure of clustering is properly normalized so that C∈[0,1]. It also admits a probabilistic interpretation—it is the probability that a randomly chosen triple of nodes is closed.

We can express the clustering coefficient in terms of the degree and multiplicity distributions. For any network we have

    N_∧ = ∑_kk2N_k = N∑_kk2p_k = Nk^2-k/2

and

    3N_ = ∑_mL_m = L∑_mmq_m = Lm.

Putting the above results together and noting that in any network L=Nk/2, we obtain the following general expression for the clustering coefficient:

    C = km/k^2-k.




 §.§ Random network ensembles

We study relaxation dynamics of k-regular networks under edge rewiring in two random network ensembles—the configuration model (CM) and the Erdős–Rényi random graph (ER).

The CM <cit.> is defined by drawing a valid degree sequence 𝐤={ k_i}_i=1^N from a degree distribution p_k and producing a network realization uniformly at random from all possible networks with that degree sequence <cit.>. Provided the second moment of the degree distribution remains finite, it can be shown that the clustering coefficient scales as C∼ 1/N so that in the thermodynamic limit (N→∞) the resulting networks are tree-like <cit.>.

The ER random graph <cit.> is defined by placing L edges uniformly at random between N nodes [Another common definition leading to a slightly different model is to place each of the possible N2 edges with equal probability p, but this does not enforce a fixed number of edges.]. If we require that the mean degree k=2L/N be fixed, the degree distribution of the ER model in the thermodynamic limit is Poisson with mean k <cit.>. The ER model is thus a special case of the CM and has the same scaling behaviour of the clustering coefficient.

Given that both the CM and ER random graphs are asymptotically triangle-free, it is natural to consider them as equilibrium ensembles for relaxation dynamics of highly clustered networks into an unclustered state. To this end we describe two edge rewiring mechanisms that have the CM and the ER random graphs as equilibrium distributions (see <ref> for a graphical demonstration).






  
*Double edge swap (CM).
The double-edge swap <cit.> is defined by choosing two existing edges in the network at random and rewiring their ends to produce two new edges while deleting the original two. This is also known as degree-preserving randomization and so naturally produces network realizations in the CM ensemble with a fixed degree sequence. The double-edge swap defines a Markov chain whose equilibrium distribution is the CM <cit.>.



  
*Edge replacement (ER).
Alternatively, one can fully randomize a network by picking an edge at random and placing it anywhere in the network where there is no edge already <cit.>. In this scheme the number of edges is preserved but the degrees of the nodes are not. Edge replacement defines a Markov chain whose equilibrium distribution is the ER ensemble.

A double-edge swap or an edge replacement constitutes an elementary rewiring step.



§ RESULTS

To assess the evolution of network measures over time, we take into account the network size and the rewiring scheme (either CM or ER) to normalize the number of elementary rewiring steps per number of edges. If r_CM and r_ER are the number of elementary rewiring steps in the CM and ER ensembles respectively, we define the corresponding time variables as

    t_ER   = r_ER/L
    
        t_CM   = 2r_CM/L.

These definitions have the useful interpretation that when t_scheme=1, the rewiring scheme has, on average, modified each edge in the network.



 §.§ Multiplicity distribution

The multiplicity distribution evolves over time as edges are rewired and triangles are destroyed. The initial configuration of a k-regular network is a disjoint union of N/(k+1) cliques of size k+1 which ensures maximal clustering C=1. In other words, at time t=0, the multiplicity distribution is

    q_k-1   = 1 
    
        q_m    =0  if m≠k-1.


Consider the smallest informative time step Δ t_CM=2/L or Δ t_ER=1/L corresponding to exactly one elementary rewiring step. At t=0 a clique of size k+1 has exactly k+12 edges all of which have maximal multiplicity k-1. Rewiring any single edge will destroy k-1 triangles leading to a decrease of 2(k-1)+1 edges with maximal multiplicity, one for the rewired edge and an additional two for each destroyed triangle. Assuming that no new triangles are created, the single rewired edge will have multiplicity zero. <Ref> shows the transition rates in the multiplicity distribution of a single clique.




We now make the ansatz that this is the main way the multiplicity distribution changes over time—multiplicity is predominantly decreased by rewiring single edges from cliques and all such rewirings are independent. In this case, we can write down the full transition rate diagram between multiplicity classes as shown in <ref>. This gives the following time evolution equations for q_m:

    dq_m/dt   = -(2m+1)q_m+2(m+1)q_m+1, [   for m=; k-1,…, 1 ]
    dq_0/dt   = 3q_1+∑_m=2^k-1q_m.


<Ref> shows the numerical solution of these ODEs which is in excellent agreement with simulation results. The calculations are valid both in the ER and the CM case.





  
*Average multiplicity.
Using the time evolution equations for the multiplicity distribution, we can derive exact expressions of its moments. Specifically we are interested in the average multiplicity m as it features in the expression for the clustering coefficient. We have

    dm/dt = ∑_m=1^k-1mdq_m/dt.

Inserting <ref> we obtain the simple expression

    dm/dt = -3m.

Using the initial condition m(0)=k-1, this has solution

    m = (k-1)e^-3t.

<Ref> shows the analytic solution of the average multiplicity which is in perfect agreement with simulation results.




 §.§ Degree distribution

In the case of the ER model, the degree distribution is also changing over time. Consider the degree distribution p_k(t) as a function of time and a time step Δ t_ER. We can calculate the rate at which p_k(t) changes.

An edge replacement event in the ER model consists of two steps. First, a random edge is selected. Second, a random pair of nodes that are not linked by an edge (let us call this pair a non-edge) is selected and the edge selected in the first step is deleted while the non-edge becomes an edge.

When a random edge is selected, p_k can decrease if at least one end of the edge has degree k. Alternatively, p_k can increase if at least one end of the edge has degree k+1. The probability of reaching a node of degree k by following a randomly chosen edge is given by the so called excess degree distribution <cit.> which reads s_k=kp_k/k. Given this and the fact that a randomly chosen edge can have 0,1 or 2 nodes of degree k, we can calculate the expected number of nodes of degree k at the ends of a random edge:

    𝔼(k→ k-1)=2s_k^2+2s_k(1-s_k)=2s_k=2kp_k/k.

This is the expected number of nodes whose degree would decrease from k to k-1 during a single edge selection step. Note that at the beginning of the process the degree distribution is regular so 𝔼(k→ k-1)=2 as expected.

Similarly, the expected number of nodes whose degree would decrease from k+1 to k leading to an increase in p_k is:

    𝔼(k+1→ k)=2s_k+1=2(k+1)p_k+1/k.


Now consider the second step in the edge replacement event, the selection of a non-edge. When a random non-edge is selected, p_k can also change in two ways. It can increase if at least one of the selected nodes has degree k-1 and it can decrease if at least one of the nodes has degree k. The calculation of the expected number of nodes changed as a result of this is similar to the previous case, but we must consider the distribution of non-degrees instead. To this end we study the graph complement of the original network defined as a network in which two nodes are linked if and only if they are not linked in the original network. From here on we denote by an overbar quantities in the graph complement.

It is easy to see that the degrees of nodes in the complement are given by k=N-1-k where k is the degree of a node in the original network and we have p_k=p_k. Thus, the non-edges are selected proportionally to k not k as in the case of edge selection so we must work with the excess non-degree distribution given by s_k=kp_k/k. Note that the mean non-degree is given by

    k = ∑_kkp_k = N-1-k.

As in the case of edge selection, the expected number of nodes whose degree would increase from k to k+1 thus reducing p_k during a single non-edge selection step is

    𝔼(k→ k+1)=2q_k=2kp_k/k = 2(N-1-k)/N-1-kp_k.

When N is large we can approximate this by

    𝔼(k→ k+1)≃ 2p_k.


Similarly, p_k can increase if we select a non-edge with at least one node with degree k-1. The expected number of such nodes in a single non-edge selection is

    𝔼(k-1→ k)≃ 2p_k-1.




<Ref> describes pictorially the transition rates between degree classes as derived here. This allows us to write down the time evolution equations for p_k:

    dp_k/dt = 2p_k-1-2(1+k/k)p_k+2k+1/kp_k+1,

for k=0,1,…. This system of ODEs is not closed, so in order to solve it numerically, we must truncate the system at some p_k^* setting p_k=0 for all k>k^*. The value of k^* should be set high enough so the probability mass unaccounted for is minimal for accurate predictions. We test our predictions by numerically solving the ODEs for a network with average degree k=2 and setting the cut-off k^*=8. The results are shown in <ref>. The numerical solution of the ODE system is in excellent agreement with simulation results. We also note that the cut-off is appropriate for this level of approximation as the total probability mass does not diverge from unity noticeably over the time period considered.






  
*Second moment of the degree distribution.
Using the time evolution equations for the degree distribution, we can derive exact expressions of its moments. Specifically, we are interested in the second moment k^2. We have

    dk^2/dt = ∑_kk^2dp_k/dt.

Inserting <ref> we obtain the simple expression

    dk^2/dt = -4k^2/k+4k+4.

Using the initial condition k^2(0) = k^2 and recalling that the average degree k is constant, this has solution

    k^2 = k(k+1-e^-4t/k).




 §.§ Clustering coefficient

Putting together the results for the multiplicity and degree distributions, and using <ref>, we obtain exact expressions for the clustering coefficient as a function of time in both the CM and ER ensembles:

    C_CM   = e^-3t
    
        C_ER   = (k-1)e^-3t/k-e^-4t/k.


We note that in the CM ensemble, the clustering coefficient has no dependence on the average degree while this is not the case for the ER ensemble. This is because the number of connected triples N_∧ in the CM ensemble is constant by virtue of having a fixed degree sequence while it is dependent on the evolving degree sequence in the ER ensemble.



 §.§ Giant connected component

We find that under both rewiring schemes there is an emergence of global connectivity via the appearance of a giant connected component (GCC) at some critical time t^c (equivalently, critical clustering coefficient C^c). We confirm from simulation results that a GCC emerges in a continuous phase transition (<ref> for the CM and <ref> for the ER ensembles). Note that the large fluctuations in the 2-regular case is due to the fact that 2-regular networks are exactly at the poing of criticality in the unclustered CM case (C=0). This phenomenon has been studied in the context of reversible polymerization of rings <cit.>.












We can calculate the critical point analytically by using the known result that a GCC in an ER random graph emerges when k=1 <cit.>. We conjecture that a GCC induced by edge rewiring emerges when the average number of external edges between the original N/(k+1) cliques of size k+1 exceeds one. If this is the case, the critical number of elementary rewiring steps is

    r^c = N/2(k+1).

Expressing this in terms of the time variable, we obtain the critical time for both the CM and the ER rewiring schemes:

    t^c_CM   = 2/k(k+1)
    
        t^c_ER   = 1/k(k+1).

Note that these differ by a factor of two. This is because in the CM rewiring scheme, even though every elementary rewiring step involves two edges, the two rewirings are not independent—during one rewiring step it is possible to connect at most two disconnected components.

Expressed in terms of the clustering coefficient, the critical thresholds read:

    C^c_CM   = e^-6/k(k+1)
    
        C^c_ER   = (k-1)e^-3/k(k+1)/k-e^-4/k^2(k+1).


<ref> confirm that these are in excellent agreement with simulations in the CM case and <ref> confirm a good agreement in the ER case which improves as the mean degree increases.

What is the cause of the discrepancy of the analytical result for the critical point and the numerical simulations, particularly for low mean degree ER networks? We conjecture that this is due to some edges being rewired multiple times while others are not rewired at all. This would have the effect of increasing the critical time because we have to wait slightly longer until the average number of rewired edges discouting edges rewired multiple times reaches the point where long range connectedness emerges. <Ref> seems to confirm this to be the case. Let us calculate this revised critical time in the ER case.

During an edge replacement step, the probability of any edge being chosen for rewiring is 1/L. So after r rewiring events the probability that a specific edge has not been rewired is

    ℙ(not rewired) = (1-1/L)^r.

Substituting r=Lt since we are in the ER case and taking the limit as L→∞, we get

    ℙ(not rewired) = e^-t.

The new revised time for ethe mergence of the GC, call it t^r, is then the time at which point this probability drops below a certain threshold. What is this threshold? It should be when the proportion of edges that have been rewired gives rise to a GCC which is precisely given by t^c. We can then write

    e^-t^r = 1-t^c.

Note that by Taylor expansion we have t^r≃ t^c if this time is small as in the case when the average degree k→∞. This explains why the t^c value becomes a better predictor for the critical threshold as the mean degree increases as seen in <ref>.

The revised critical point in the ER case is thus

    t^r = -log(1-t^c) = log(k(k+1)/k(k+1)-1).

<Ref> confirms that t^r is a better predictor of the location of the phase transition. The difference between t^c and t^r becomes negligible as the mean degree increases.



Another aspect that could influence the position of the critical point is the possibility of having rewired more edges that needed to connect previously disconnected components. We show in the <ref> that this should have no bearing on the critical point in large networks.



§ DISCUSSION

In this paper we studied the evolution of highly clustered networks under random edge rewiring dynamics. Our main result is showing the existence of a phase transition in which a giant connected component emerges. <cit.> showed that equilibrium ensembles of degree-regular networks with prescribed clustering always admit a giant connected component. As a consequence, spreading processes such as infectious diseases in contact networks could always become endemic regardless of the level of clustering. By contrast, our work implies that this need not be the case in non-equilibrium systems. Depending on the precise mechanisms of time evolution of real networks and the level of clustering maintained, a giant connected component facilitating spreading processes may or may not exist. We have studied a model in which highly clustered populations undergo fully random connectivity changes and even in this simple scenario we observe two different modes of global connectivity.

Another interesting aspect of our work is from the perspective of statistical mechanics. A maximally clustered network is essentially the lowest entropy microstate in the context of the random network ensembles studied here. This is because such a network, under relabelling of nodes, is unique and least likely to be produced by chance at equilibrium. By using this configuration as a starting state for network dynamics, we have shown that the emergence of global connectivity is effectively delayed. This raises several other research questions, for example, is random rewiring the most or least effective method of delaying the onset of global connectivity? It is probable that more sophisticated rewiring methods involving choice, such as those studied in explosive percolation <cit.>, would lead to different critical thresholds. We have also limited ourselves to studying rewiring that consistently destroys triangles, but what about rewiring with a view to increase the number of triangles? A number of greedy as well as equilibrium algorithms exist and are widely applied to model highly clustered networks <cit.>, but it is unclear how they cover the space of all networks and can lead to interesting behaviour such as hysteresis loops <cit.>. Indeed, clustering in networks still leaves much to be explored.


J.K. was supported by the EPSRC under grant EP/IO1358X/1. S.J. is grateful for support from Spanish MINECO Grant No. FIS2013-43201-P (FEDER funds).


*


§ EXTRANEOUS EDGES

Another mechanism that could change the location of the critical point t^c is the number of extraneous edges between already connected components. A GCC is formed when there are enough external edges between the initial cliques. Only one external edge is needed to connect two cliques, but there are multiple ways to do it and sometimes multiple edges end up linking together the same cliques. For example, we need only one edge two join two disconnected triangles, but there are a total of 9 ways to do it, moreover there is no guarantee that we will not end up with multiple edges between these triangles.

More generally, let the average degree k be fixed, then at t=0 there are n=N/(k+1) cliques of size k+1. Any two cliques can therefore be connected in (k+1)^2 ways.

Suppose we never want to make more than one external edge to connect disconnected components. Then at t=0 the number of choices for placing an external edge is given by

    (k+1)n2 = N(N-k-1)/2.

After each rewiring event, the number of choices decreases by (k+1)^2, so after r-1 rewires, the probability of placing an extraneous edge on the next rewire, r, is

    ℙ(extra edge on step r) = 2(k+1)^2r/N(N-k-1).

Thus, the expected number of extraneous edges after r rewiring events is

    𝔼(extra edges by step r) = ∑_r^'=0^r2(k+1)^2r^'/N(N-k-1).

In particular, setting r=r^c=N/2(k+1) we get


    𝔼(extra edges by step r^c) 
     =2(k+1)^2/N(N-k-1)·N/4(k+1)(N/2(k+1)+1) 
    
      = N+2k+2/4(N-k-1).


Taking the limit N→∞, we get

    𝔼(extra edges by step r_c) ≃1/4,

which is fixed and independent of network size. Therefore, the formation of extraneous edges does not affect the location of the critical point in the large network limit.



