War pact model of shrinking networks

Summary

Many real systems can be described by a set of interacting entities forming a complex network. To some surprise, these have been shown to share a number of structural properties regardless of their type or origin. It is thus of vital importance to design simple and intuitive models that can explain their intrinsic structure and dynamics. These can, for instance, be used to study networks analytically or to construct networks not observed in real life. Most models proposed in the literature are of two types. A model can be either static, where edges are added between a fixed set of nodes according to some predefined rule, or evolving, where the number of nodes or edges increases over time. However, some real networks do not grow but rather shrink, meaning that the number of nodes or edges decreases over time. We here propose a simple model of shrinking networks called the war pact model. We show that networks generated in such a way exhibit common structural properties of real networks. Furthermore, compared to classical models, these resemble international trade, correlates of war, Bitcoin transactions and other networks more closely. Network shrinking may therefore represent a reasonable explanation of the evolution of some networks and greater emphasis should be put on such models in the future.

Keywords:

Network analysis – Community structure – Clustering coefficients – International trade – Random graphs – Scale-free networks – Small world networks – Mesoscopic physics

Introduction

The most natural representation of many real complex systems is a network of nodes connected by edges also called a graph in discrete mathematics. Despite being a very simplistic representation, networks have given us a better understanding of complex real-world phenomena such as epidemic spreading of diseases [1, 2], small-worlds of human society [3, 4], mobility and navigation [5, 6], emergence of complex organization [7, 8], robustness and controllability of manmade technology [9, 10], and the structure of science [11], to name just a few examples. Indeed, the networks have proven to be an invaluable tool for data analysis in the last two decades [12].

One of the key reasons for the successes mentioned above is the realization that real networks share a number of structural properties regardless of their type or origin. For instance, most real networks exhibit a scale-free structure like power-law node degree distribution [7, 13], short distances between the nodes called the small-world structure [3, 4], resilience or robustness to targeted attacks [9], pronounced mixing between the nodes [14, 15], a distinctive mesoscopic network structure [16, 17], characteristic node connection patterns [18, 19] and a key position or centrality of a small number of nodes [20, 21]. It is therefore a common belief that real networks form according to some shared rules or principles giving rise to these complex structures.

The network science literature is abundant with generative models of network formation that try to explain their intrinsic structure and dynamics. Most network models are static, meaning that edges are added between a fixed set of nodes according to some predefined rule. These include the simplest Erdős-Rényi random graphs [22], and somewhat more realistic configuration [23], hierarchical [24], geometric [19] and optimization [25] graphs that can already explain some non-trivial properties of real networks. Moreover, stochastic block models [26] can generate networks with an arbitrary mesoscopic structure. However, greater insights into the structure and dynamics of real networks were actually obtained with evolving network models where the number of nodes or edges increases over time. Most well-known examples of evolving models are undoubtedly the Price cumulative advantage model [13], the Barabási-Albert scale-free networks [7] and the copying network model [27].

On the other hand, some real networks do not grow but rather shrink, meaning that the number of nodes or edges decreases over time. Apart from a few exceptions, such as [28], shrinking network models have been largely neglected in the literature [29]. To fill this gap, we here propose a simple model of shrinking networks called the war pact model. The model starts with some fixed number of edges and the maximal possible number of nodes, hence the initial seed network is a perfect matching. The nodes are then iteratively merged until the desired number of nodes is obtained. We show that networks generated by the war pact model match the most common properties of real networks. More importantly, the model provides an intuitive explanation of the evolution of diverse real networks. The paper therefore puts forth an intriguing question whether growing or shrinking models explain the evolution of real networks better.

Materials and methods

The present section describes networks, models and methods used in the paper. We start with a detailed description of the war pact model and its implementation. Next, we introduce four real networks used for empirical validation of the model and alternative random graph models used for comparison. Finally, we review two information-theoretic measures used for comparing networks or graphs.

War pact model

The top row in Fig 1 shows a diagram of a particular realization of the war pact model. The model starts with an initial seed network which is a perfect matching of nodes with some predefined number of edges. The model then iteratively merges the nodes until one obtains a network with the desired number of nodes. Note that the number of edges stays fixed during the evolution of the model, while the number of nodes decreases by one in each step. The nodes to be merged in each step can be selected uniformly at random, preferentially according to their degrees or using some other selection rule.

More formally, let n and m be the desired number of nodes and edges, where 2m ≥ n. The model starts with m edges connecting 2m nodes as in Fig 1. In each step, the model merges two nodes i and j into a newly added node k by first replacing nodes i and j with node k and then connecting the neighbors of nodes i and j to node k. The model proceeds for 2m − n steps when the number of nodes equals n.

As shown in the bottom row in Fig 1, the model can generate a rich local structure depending on the distance d between the nodes being merged. Merging nodes at distance d = 1 (i.e. an edge) creates a self-edge, which is not allowed, merging nodes at distance d = 2 creates parallel edges and thus a multigraph, while merging nodes at distance d = 3 creates a triangle resulting in non-trivial network clustering [4]. In general, merging nodes at distance d creates a cycle on d nodes.

The war pact model is free from parameters. Nevertheless, one can still freely choose the strategy of selecting the nodes to be merged in each step and also the initial state of the model. In the letter case, initializing the model with a perfect matching as above is somewhat artificial and not realistic in practice. However, as we show in the Results and discussion section, the particular choice of the model initialization has no apparent effect on the final structure of the generated networks. For this reason, the model is initialized with a perfect matching unless explicitly stated otherwise.

On the other hand, the particular choice of the node selection rule can have a profound effect on the structure of the generated networks. Therefore, we consider four different node selection rules that proved reasonable in practice. In particular, the two nodes to be merged can be selected uniformly at random among all nodes (denoted RR model) or preferentially according to their degrees (KK model). Hence, a node is selected with the probability proportional to k, where k is the current degree of the node. Finally, we also consider two mixed rules where the first node is selected with the probability proportional to its degree k, while the second node is selected uniformly at random (KR model) or with the probability proportional to its inverse degree k⁻¹ (KI model). Other possible rules either do not generate realistic networks or we could not find an intuitive explanation for such a model.

For a visual representation, Fig 2 shows layouts of three particular realizations of the war pact model networks. In all three cases, the first node is selected with the probability proportional to its degree k, whereas the second node is selected with the probability proportional to its degree k, inverse degree k⁻¹ or uniformly at random (KK, KI and KR models, respectively). Notice that clusters revealed with Bayesian stochastic blockmodeling [30] show diverse mesoscopic structures of these networks ranging from hub and spokes arrangements to a community and core-periphery structure.

The implementation of the war pact model is relatively straightforward using the hash map H as shown in Algorithm 1. Each node of graph G is represented by its hash value h ∈ H initialized as H(i) = i for each node index i = 1, …, 2m (lines 4-5). Note that each hash value h ∈ H corresponds to a unique node in graph G and each node has a unique hash value. Merging two nodes H(i) and H(j) then merely requires unifying their hash values as H(i) = H(j) and updating graph G accordingly (lines 12-13). For choosing a node uniformly at random, one selects a random hash value h ∈ H (line 9), while if choosing a node with the probability proportional to its degree, one selects the hash value H(i) of a randomly selected node index i ∈ [1, 2m] (line 10). The pseudocode in Algorithm 1 assumes that graph G is initialized with a perfect matching of nodes (line 6) and ensures that no self-edges are created during the evolution of the model (line 11). Note that, in practice, one should use a disjoint-set data structure instead of a hash map to ensure a near-constant time complexity of all operations.

Algorithm 1 War pact model

Input: nodes n and edges m

Output: graph G

1: H ← empty map         {Define empty map representing nodes.}

2: G ← empty graph         {Define empty war pact model graph.}

3: for i ∈ [1, m] do

4:  H(i) ← i and H(m + i) ← m + i    {Map nodes’ indices to their hashes.}

5:  add nodes H(i) and H(m + i) to G    {Add nodes (i.e. hashes) to graph.}

6:  add edge {H(i), H(m + i)} to G    {Create perfect matching of nodes.}

7: end for

8: white G has > n nodes do

9:  h ← Random(H)        {Select random hash (i.e. random node).}

10:  i ← Random([1, 2m])    {Select random index (i.e. node by degree).}

11:  if h ≠ H(i) and edge {h, H(i)} ∉ G then

12:   merge nodes h and H(i) in G {Merge selected nodes by rewiring edges.}

13:   H(i) ← h             {Unify hashes of selected nodes.}

14:  end if

15: end while

16: return G

Networks and models

For empirical validation of the war pact model, we consider four real networks of different types and origins. The networks represent international trade consisting of the strongest food import and export relations between countries from the Food and Agricultural Organization of the United Nations [32], historical records of international wars, non-military conflicts, border disputes and other disagreements between national alliances during 1996 collected by the Correlates of War project [33], Bitcoin transactions between the most active users (i.e. clusters of coappearing input addresses) between 2012 and 2013 parsed from the public ledger [34], and the Internet map at the level of autonomous systems on the first day of 1998 reconstructed from the University of Oregon Route Views project [35]. Networks are represented with undirected graphs with self-edges and isolated nodes removed.

Table 1 shows the standard statistics of the analysed networks. These are the number of nodes n and edges m, the average node degree 〈k〉 = 2m/n, the fraction of nodes in the largest connected component LCC, the average node clustering coefficient 〈C〉=1n∑iCi [4] with the clustering coefficient of node i defined as Ci=2tiki(ki−1), where t_i is the number of triangles including node i and k_i > 1 is its degree, the average distance between the nodes 〈d〉=2n(n−1)∑i<jdij, where d_ij is the number of edges in the shortest paths between nodes i and j, the maximal distance or diameter d_max = max_i<j d_ij, the node degree mixing coefficient r [14] defined as the Pearson’s correlation coefficient of the degrees of connected nodes and the modularity of network community structure Q=12m∑ij(Aij−kikj2m)δ(ci,cj) [36], where A is the network adjacency matrix, c_i is the community label of node i and δ is the Kronecker delta. The modularity Q is reported as the average over 100 runs of the Leiden algorithm [37].

The war pact model is compared against three classical random graph models. The first is the Erdős-Rényi random graph model [22], where an edge is put between each pair of n nodes with a probability of 〈k〉/(n − 1). Next is the Barabási-Albert scale-free model [7], where n nodes are added one at a time and each forms 〈k〉/2 edges while preferentially linking to high degree nodes. The model generates networks with a scale-free degree distribution p_k ∼ k^−γ [7, 38], where γ is the power-law exponent. Finally, we consider the Watts-Strogatz small-world model [4], where a fraction of edges of a regular ring lattice is randomly rewired. The model generates networks with a high clustering coefficient 〈C〉 ≫ 0 and a short average distance between the nodes 〈d〉 ≃ log_〈k〉 n.

Network comparison

We adopt two recently proposed measures for comparing networks or graphs. These are the simplified D-measure [39] and the portrait divergence [40, 41]. Both are principled information-theoretic measures that can be used to compare arbitrary graphs and do not require that the two graphs being compared are defined on the same set of nodes. Both measures compare graphs by quantifying differences among the distances between the nodes of the graphs as defined below.

Let d_ij(G) denote the distance between nodes i and j in an undirected graph G and d_max(G) the maximal distance or diameter, d_max(G) = max_i<j d_ij(G). Next, let D_id(G) be the fraction of nodes at distance d from node i, d = 0, …, d_max(G),

The first term of Eq (1) compares graphs through averaged distances between the nodes and thus captures global differences between the graphs. The second term further compares graphs through the heterogeneity of the nodes and how each particular node is connected throughout the graph. It thus captures local differences between the graphs. It was empirically shown that the measure returns non-zero values only for non-isomorphic graphs [39].

In the case of the complete D-measure, Eq (1) also includes the third term measuring the dissimilarity between node centralities in graphs G and G′, and their complements. Since the latter are computationally prohibitive for sparse graphs, and only strictly necessary to distinguish highly regular graphs, we here avoid the additional term without significant precision loss [39].

Furthermore, let P_kd(G) be the number of nodes that have k nodes at distance d, d = 0, …, d_max(G),

Results and discussion

This section presents an empirical validation of the war pact model. First, we characterize the statistical properties of the networks generated by different variants of the model. Next, we study the model evolution by analyzing networks with growing number of nodes or edges. Finally, we compare the war pact model against classical random graph models and clarify the intuition behind the model for various real networks.

War pact networks

Fig 3 shows distributions of various node statistics of particular realizations of the war pact model networks. We consider four variants of the node selection rule introduced in the Materials and methods section and three different choices of model initialization. The top row in Fig 3 shows the distributions for networks initialized with a perfect matching of nodes as in Algorithm 1, the networks in the middle row are initialized with Erdős-Rényi random graphs [22] with the same number of nodes and edges, while the networks in the bottom row are initialized with randomly grown tree graphs.

Notice that the distributions in the top, middle and bottom rows are almost indistinguishable. Hence, the particular choice of the model initialization has no apparent effect on the structure of the generated networks. In the remainder, we therefore always initialize the model with a perfect matching of nodes.

In contrast, the choice of the node selection rule does indeed shape the structure of the generated networks as already observed in Fig 2. For instance, consider the node degree distributions p_k shown in the first column in Fig 3. When both nodes to be merged are selected preferentially according to their degree k (KK model), the degree distribution p_k seems to follow a power-law for low degrees k ≲ 10, whereas high degree nodes k ≳ 1 000 form a rich club [44]. Actually, the subgraph induced by the nodes with degree k ≥ 1 000 is a clique. Next, when selecting the second node uniformly at random (KR model), the degree distribution has a shape close to the power-law p_k ∼ k^−γ with γ ≈ 1.6 throughout the entire range of node degrees. The war pact model can therefore generate scale-free networks as is commonly observed in social and information domains [45, 46]. Finally, the other two node selection rules (KI and RR models) generate networks with a peak in the degree distribution characteristic of technological networks and random graphs. Hence, depending on the particular real network being modeled, different node selection rules prove appropriate.

The middle column in Fig 3 shows the distributions of the average node clustering coefficient C(k) for nodes with degree k. These largely resemble the node degree distributions p_k. In the case of the KR model networks with a seemingly power-law degree distribution p_k ∼ k^−γ, C(k) distributions also seem to follow a power-law [47]. More importantly, in all cases considered, the war pact model generates networks with a non-trivial node clustering coefficient 〈C〉 ≫ 0 characteristic of small-world networks [4].

The small-world networks are further characterized by short distances between the nodes [4]. The last column in Fig 3 shows the distributions of node distances p_d for d > 2. Most pairs of nodes are at distance d = 4 or 5 regardless of the particular variant of the model. Thus, in summary, the war pact model generates networks with a scale-free and small-world structure as commonly observed in practice.

Fig 4 shows different properties of the war pact model networks with a growing number of nodes or edges. These are the fractions of nodes in the largest connected component LCC, the average node clustering coefficient 〈C〉 and the node degree mixing coefficients r. As predicted by the percolation theory for random graphs [48], a large connected component LCC ≈ 100% emerges when the average node degree 〈k〉 exceeds a certain threshold, which depends on the particular variant of the model (top left plot in Fig 4). Nevertheless, when the average node degree equals 〈k〉 ≈ 10, the largest connected component includes LCC > 90% of the nodes regardless of the model considered. Notice that this is independent of the number of nodes n (bottom left plot in Fig 4).

As expected, the average node clustering coefficient 〈C〉 increases with the average node degree 〈k〉 (top middle plot in Fig 4). Networks with the highest clustering coefficient 〈C〉 are generated by the KR model with values similar to those observed in real networks (see Table 1). In contrast, networks generated by the KK model show an increasing clustering coefficient 〈C〉 only up to a certain point when the average node degree equals 〈k〉 ≈ 5, after which 〈C〉 starts to decrease. The reason for this is that the networks start forming a well-pronounced rich club of a few high-degree nodes with C = 1, whereas most of the nodes are pendant nodes with C = 0. Finally, when fixing the average node degree to 〈k〉 = 10 and increasing the number of nodes n, the clustering coefficient 〈C〉 decreases for all variants of the war pact model since the generated networks are becoming increasingly more sparse (bottom middle plot in Fig 4).

The last column in Fig 4 shows the evolution of the node degree mixing coefficient r for the growing war pact model networks. Notice that the values of r are largely independent of the number of nodes n and the average node degree 〈k〉. All variants of the war pact model except maybe the KK model generate networks with no pronounced degree mixing r ≈ 0. On the other hand, the KK model networks are very mildly degree disassortative with r ≈ −0.05, due to the reasons already mentioned above.

Comparison and discussion

The previous subsection shows that the choice of the war pact model initialization does not have any apparent effect on the generated networks. On the contrary, different node selection rules do indeed generate networks with a different topological structure. Most realistic networks matching the properties of connected scale-free and small-world networks with a core-periphery structure [4, 7, 16] seem to be generated by the model that selects the first node preferentially according to its current degree and the second node uniformly at random (the KR model). This model is also theoretically the most sound, since it incorporates the important realism of real networks known as preferential attachment [7], where new nodes preferentially link to well-connected nodes. Here the nodes are not added but merged, while the former are modeled by randomly selected nodes and the latter are modeled by high-degree nodes. In the present subsection, we also evaluate this hypothesis empirically using four real networks from diverse domains.

The first two plots in Fig 5 compare different variants of the war pact model with an international trade network [32]. The plots show distributions of the simplified D-measure p_D in Eq (1) [39] and the portrait divergence p_P in Eq (2) [40]. For both measures, the KR model clearly provides the best fit to the real network. Almost any network generated by the KR model reproduces the real network better than any realization of any alternative model. This also applies to other real networks analysed in the paper (exact results are omitted). In the remainder, we therefore compare other random graph models only with the KR model.

The remaining four plots in Fig 5 compare networks generated by different random graph models with the international trade network as above, and correlates of the war network [33], the Bitcoin transactions network [34] and the autonomous systems graph [35]. The plots show the distributions of the portrait divergence p_P, while the models include the war pact networks, Erdős-Rényi random graphs [22], Barabási-Albert scale-free networks [7] and Watts-Strogatz small-world networks [4]. The latter are without doubt the most fundamental and commonly analysed models in network science literature.

All real networks considered, the war pact model reproduces the structure of the networks better than any other model. Again, almost any network generated by the war pact model fits the real network better than any realization of any alternative model. We stress that all these models are either static or models with a growing number of nodes and edges. In contrast, the war pact model networks shrink over time and possibly provide a better explanation of the evolution of the considered real networks.

Table 2 further shows the standard statistics of the war pact model networks that best reproduce real networks according to the portrait divergence. Comparing the values with those in Table 1, these match the statistics of real networks well with a few exceptions shown in bold in Table 2. In particular, the war pact model underestimates the average node clustering coefficient 〈C〉 and overestimates the node degree mixing coefficient r in correlates of war and Bitcoin transaction networks, and the autonomous systems graph, while the model underestimates the modularity Q of the community structure in international trade and Bitcoin transactions networks, and the autonomous systems graph. On the other hand, the model almost precisely reproduces the fraction of nodes in the largest connected component LCC, the average distance between the nodes 〈d〉 and network diameter d_max. Overall, the war pact model replicates the structure of these real networks better than any other model considered.

Besides, the war pact model also provides an intuitive explanation of the evolution of many real networks. For instance, the nodes in the correlates of war network represent alliances between world nations and the edges represent different military or non-military conflicts between them. When nations of two alliances form a pact, or nations in one alliance occupy the nations of another, the enemies of both become common enemies, which can be modeled by simply merging the corresponding nodes. Furthermore, the node selection rule that proved most suitable above suggests that larger alliances with larger number of enemies form a pact with or conquer other alliances. This intuition has motivated the name war pact model.

The evolution of other real networks analysed in the paper can be explained in a similar manner. The trading relations between countries or companies are shared after an alliance between two countries or a merger of two companies. Next, when a single user controls multiple Bitcoin addresses, these are likely to coappear in future transactions. Finally, when two entities that have governed their Internet traffic independently unite for whatever reason, their traffic is merged from an external point of view. Indeed, one can come up with a similar intuitive explanation of the evolution of other real networks not considered here.

As already mentioned before, the initialization of the war pact model with pairs of connected nodes is somewhat artificial in the scenarios considered. However, as we show in the empirical evaluation of the model, the particular choice of model initialization has no apparent effect on the resulting structure of the generated networks.

Conclusion

In this paper, we propose a simple model of shrinking networks called the war pact model. The model starts with some fixed number of edges forming a perfect matching, and then iteratively merges the nodes until the desired number of nodes is obtained. In contrast to most network models in literature that are either static, representing a snapshot of a network [4, 22, 23], or generate networks with a growing number of nodes and edges [7, 13, 27], the war pact model networks shrink and thus represent a shift in the perspective of the evolution of real networks that has been largely neglected in the past [28, 29].

We show that networks generated by the war pact model match the common properties of real networks. These include the emergence of a large connected component [22], a scale-free node degree distribution [7], a small-world network structure [4], a disassortative node degree mixing [14], a distinctive network mesoscopic structure [16] and selected other properties. Even more importantly, the model provides an intuitive explanation of the evolution of diverse real networks representing the worldwide trade, international wars or non-military conflicts and other disputes, cryptocurrency transactions, Internet traffic and likely many other networks not considered here. In summary, compared to classical growing network models, network shrinking possibly provides a more reasonable explanation of the evolution of at least some real networks and greater emphasis should be put on such models in the future.

There are various directions for further research. Firstly, due to the algorithmic simplicity of the war pact model, different network properties might be derived analytically, thus rendering numerical simulations unnecessary. Secondly, the model could be extended to other types of networks like weighted or valued and also signed networks. Similarly, the node selection rule could be easily adjusted for multimode and multiplex networks. Finally, a thorough comparison of different network models could be conducted, possibly giving a more conclusive answer whether growing or shrinking models, or some reasonable combination of them, explain the evolution of real networks better.