Finite connected components in infinite directed and multiplex networks with arbitrary degree distributions

This work presents exact expressions for size distributions of weak and multilayer connected components in two generalizations of the configuration model: networks with directed edges and multiplex networks with an arbitrary number of layers. The expressions are computable in a polynomial time and, under some restrictions, are tractable from the asymptotic theory point of view. If first partial moments of the degree distribution are finite, the size distribution for two-layer connected components in multiplex networks exhibits an exponent $-\frac{3}{2}$ in the critical regime, whereas the size distribution of weakly connected components in directed networks exhibits two critical exponents $-\frac{1}{2}$ and $-\frac{3}{2}$.

Figure 1

Example of multiplex network with three layers. Each edge belongs to only one layer, whereas each node has one copy in each layer. Even though in each separate layer the nodes can be partitioned into different sets of connected components, the network is fully connected in the weak sense, when the connectivity information from all layers is combined.

Figure 2

An oscillatory example of the size distribution of connected components in the two-layer configuration model as predicted by the analytical expression (40) (black solid line) is compared against the data obtained from simulations (scattered points linked with a dashed line that indicates the trend). Low probabilities are naturally underrepresented in simulated data due to the limited size of the Monte Carlo sample. The theory, as given by Eqs. (32) and (45), predicts the asymptote with a transient slope $-\frac{3}{2}$ (yellow solid line).

Figure 3

An example of the size distribution of weakly connected components in a directed configuration model as predicted by the analytical expression (15) (solid line) is compared against the data obtained from simulations (scattered points). The theory, as given by Eq. (32), predicts the asymptote with a transient slope $-\frac{3}{2}$ (dashed line).

Figure 4

An example of the size distribution of weakly connected components in a directed configuration model as predicted by the analytical expression (15) (solid line) is compared against the data obtained from simulations (scattered points). The theory, as given by Eq. (36), predicts the asymptote with a transient slope $-\frac{1}{2}$ (dashed line).

Figure 5

Comparisons of respective theoretical size distributions of finite components against the empirical data. Three cases of directed networks containing $N$ nodes in total are considered: (a) the network of retweets in the Higgs-Twitter data set, $N=425008$ [24]; (b) the graph of the sparse statistical matrix Chem97ZtZ, $N=2541$ [25]; and (c) the network of communications on Wikipedia until January 2008, $N=2394385$ [26].