Configuration model

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Figure 1. Degree sequence and different network realizations in the configuration model[1]

In network science, the configuration model is a method for generating random networks from given degree sequence. It is widely used as a reference model for real-life social networks, because it allows the user to incorporate arbitrary degree distributions.

Rationale for the model[edit]

In the configuration model, the degree of each vertex is pre-defined, rather than having a probability distribution from which the given degree is chosen.[2] As opposed to the Erdös-Rényi model, the degree sequence of the configuration model is not restricted to have a Poisson-distribution, the model allows the user to give the network any desired degree distribution.

Algorithm[edit]

The following algorithm describes the generation of the model:

  1. Take a degree sequence, i. e. assign a degree to each vertex. The degrees of the vertices are represented as half-links or stubs. The sum of stubs must be even in order to be able to construct a graph (). The degree sequence can be drawn from a theoretical distribution or it can represent a real network (determined from the adjacency matrix of the network).
  2. Choose two vertices uniformly at random. Connect them with an edge using up one of each node's stubs. Choose another pair from the remaining stubs and connect them. Continue until you run out of stubs. The result is a network with the pre-defined degree sequence. The realization of the network changes with the order in which the stubs are chosen, they might include cycles (b), self-loops (c) or multi-links (d) (Figure 1).[1]

Self-loops, multi-edges and implications[edit]

The algorithm described above matches any stubs with the same probability. The uniform distribution of the matching is an important property in terms of calculating other features of the generated networks. The network generation process does not exclude the event of generating a self-loop or a multi-link. If we designed the process where self-loops and multi-edges are not allowed, the matching of the stubs would not follow a uniform distribution. However, the average number of self-loops and multi-edges is a constant for large networks, so the density of self-loops and multi-links goes to zero as [2] (see the cited book for details).

A further consequence of self-loops and multi-edges is that not all possible networks are generated with the same probability. In general, all possible realizations can be generated by permuting the stubs of all vertices in every possible way. The number of permutation of the stubs of node is , so the number of realizations of a degree sequence is . This would mean that each realization occurs with the same probability. However, self-loops and multi-edges can change the number of realizations, since permuting self-edges can result an unchanged realization. Given that the number of self-loops and multi-links vanishes as , the variation in probabilities of different realization will be small but present.[2]

Properties[edit]

Edge probability[edit]

A stub of node can be connected to other stubs (there are stubs altogether, and we have to exclude the one we are currently observing). The vertex has stubs to which node can be connected with the same probability (because of the uniform distribution). The probability of a stub of node being connected to one of these stubs is . Since node has stubs, the probability of being connected to is ( for sufficiently large ). The probability of self-edges cannot be described by this formula, but as the density of self-edges goes to zero as , it usually gives a good estimate.[2]

Given a configuration model with a degree distribution , the probability of a randomly chosen node having degree is . But if we took one of the vertices to which we can arrive following one of edges of i, the probability of having degree k is . (The probability of reaching a node with degree k is , and there are such nodes.) This fraction depends on as opposed to the degree of the typical node with . Thus, a neighbor of a typical node is expected to have higher degree than the typical node itself. This feature of the configuration model describes well the phenomenon of "my friends having more friends than I do".

Clustering coefficient[edit]

The global clustering coefficient (the average probability that the neighbors of a node are connected) is computed as follows:

,

where denotes the probabilistic distributions of vertices and having edges, respectively.

After transforming the equation above, we get approximately

, where is the number of vertices, and the size of the constant depends on .[2] Thus, the global clustering coefficient becomes small at large n limit.

Giant component[edit]

In the configuration model, the existence of a giant component is bound to the Molloy-Reed criterion.[3] The intuition behind this criterium is that if the giant component exists, then the average degree of a randomly chosen vertex in a connected component should be at least 2. Using this assumption, the following formula can be derived:

where and are the first and second moments of the degree distribution. (see also: robustness of complex networks). That means that according to Molloy-Reed, the critical threshold solely depends on quantities which are uniquely determined by the degree distribution .

Components of finite size[edit]

As total number of vertices tends to infinity, the probability to find two giant components is vanishing. This means that in the sparse regime, the model consist of one giant component (if any) and multiple connected components of finite size. The sizes of the connected components are characterised by their size distribution - the probability that a randomly sampled vertex belongs to a connected component of size There is a correspondence between the degree distribution and the size distribution When total number of vertices tends to infinity, , the following relation takes place:[4]

where and denotes the -fold convolution power. Moreover, explicit asymptotes for are known when and is close to zero.[4] The analytical expressions for these asymptotes depend on finiteness of the moments of the degree distribution tail exponent (when features a heavy tail), and the sign of Molloy-Reed criterium. The following table summarises these relationships (the constants are provided in[4]).

Moments of Tail of
light tail -1 or 1
0
heavy tail, -1
0
1

heavy tail, -1
0
1
heavy tail, -1
0
1

heavy tail, 1
heavy tail, 1

Modelling[edit]

Comparison to real-world networks[edit]

The three general properties of complex networks are broad degree distribution, short average path length and high clustering.[1][5][6] Having the opportunity to define any arbitrary degree sequence, the first condition can be satisfied by design, but as shown above, the global clustering coefficient is an inverse function of the network size, so for large configuration networks, clustering tends to be small. This feature of the baseline model contradicts the known properties of empirical networks, but extensions of the model can solve this issue (see [7]).

Application: modularity calculation[edit]

The configuration model is applied as benchmark in the calculation of network modularity. Modularity measures the degree of division of the network into modules. It is computed as follows:

[8]

in which the adjacency matrix of the network is compared to the probability of having an edge between node and (depending on their degrees) in the configuration model (see the page modularity for details).

References[edit]

  1. ^ a b c Network Science by Albert-László Barabási.
  2. ^ a b c d e Newman, Mark (2010-03-25). Networks: An Introduction - Oxford Scholarship. Oxford University Press. doi:10.1093/acprof:oso/9780199206650.001.0001. ISBN 9780191594175.
  3. ^ Molloy, Michael; Reed, Bruce (1995-03-01). "A critical point for random graphs with a given degree sequence". Random Structures & Algorithms. 6 (2–3): 161–180. CiteSeerX 10.1.1.24.6195. doi:10.1002/rsa.3240060204. ISSN 1098-2418.
  4. ^ a b c Kryven, I (2017). "General expression for the component size distribution in infinite configuration networks". Physical Review E. 95 (5): 052303. doi:10.1103/PhysRevE.95.052303.
  5. ^ Barabási, Albert-László; Albert, Réka (1999-10-15). "Emergence of Scaling in Random Networks". Science. 286 (5439): 509–512. arXiv:cond-mat/9910332. Bibcode:1999Sci...286..509B. doi:10.1126/science.286.5439.509. ISSN 0036-8075. PMID 10521342.
  6. ^ Watts, Duncan J.; Strogatz, Steven H. (1998). "Collective dynamics of 'small-world' networks". Nature. 393 (6684): 440–442. Bibcode:1998Natur.393..440W. doi:10.1038/30918. ISSN 1476-4687. PMID 9623998.
  7. ^ Newman, M. E. J. (2009). "Random Graphs with Clustering". Physical Review Letters. 103 (5): 058701. arXiv:0903.4009. Bibcode:2009PhRvL.103e8701N. doi:10.1103/physrevlett.103.058701. PMID 19792540.
  8. ^ Newman, M. E. J. (2004). "Finding and evaluating community structure in networks". Physical Review E. 69 (2): 026113. arXiv:cond-mat/0308217. Bibcode:2004PhRvE..69b6113N. doi:10.1103/physreve.69.026113. PMID 14995526.