Weighted hypersoft configuration model

Maximum entropy null models of networks come in different flavors that depend on the type of constraints under which entropy is maximized. If the constraints are on degree sequences or distributions, we are dealing with configuration models. If the degree sequence is constrained exactly, the corresponding microcanonical ensemble of random graphs with a given degree sequence is the configuration model per se. If the degree sequence is constrained only on average, the corresponding grand-canonical ensemble of random graphs with a given expected degree sequence is the soft configuration model. If the degree sequence is not fixed at all but randomly drawn from a fixed distribution, the corresponding hypercanonical ensemble of random graphs with a given degree distribution is the hypersoft configuration model, a more adequate description of dynamic real-world networks in which degree sequences are never fixed but degree distributions often stay stable. Here, we introduce the hypersoft configuration model of weighted networks. The main contribution is a particular version of the model with power-law degree and strength distributions, and superlinear scaling of strengths with degrees, mimicking the properties of some real-world networks. As a byproduct, we generalize the notions of sparse graphons and their entropy to weighted networks.

Figure 1

The nested hierarchy of the configuration models. Sampling a graph $G$ from the hypercanonical HSCM ensemble can be done in three steps: (1) sample a sequence $\mathit{\kappa }=\left\{{\kappa }_i\right\}$ of expected degrees independently from the distribution $\rho \left(\kappa \right)$, i.e., from $P_{\mathrm{HSCM}}\left(\mathit{\kappa }\right|\rho )={\prod }_i\rho \left({\kappa }_i\right)$; (2) sample a degree sequence $\mathit{k}=\left\{k_i\right\}$ from the SCM degree sequence distribution $P_{\mathrm{SCM}}\left(\mathit{k}\right|\mathit{\kappa })$; and (3) sample graph $G$ from the uniform CM distribution $P_{\mathrm{CM}}\left(G\right|\mathit{k})$. The HSCM probability distribution can thus be written as a chain $P_{\mathrm{HSCM}}\left(G\right|\rho )={\int }_{\mathit{\kappa }}{\sum }_{\mathit{k}}{P}_{\mathrm{CM}}\left(G\right|\mathit{k})P_{\mathrm{SCM}}\left(\mathit{k}\right|\mathit{\kappa })P_{\mathrm{HSCM}}\left(\mathit{\kappa }\right|\rho )d\mathit{\kappa }$ showing that the ensemble at the next level of the hierarchy is a probabilistic mixture of the ensembles at the previous level. In the graphon theory [60], one has to consider the fourth highest level (not shown) where $\rho$ is also random. Moving up in the hierarchy adds new sources of randomness, thus increasing entropy. Since $P_{\mathrm{SCM}}\left(\mathit{k}\right|\mathit{\kappa })$ is intractable—it is a mixture of mixed Poisson distributions—in practice it is much easier to sample graphs as described in the text. The same picture applies to the weighted case upon the addition of strengths $\mathit{s}$ and their expectations $\mathit{\sigma }$.

Figure 2

Basic structural properties of networks in the WHSCM with power-law hidden-variable distributions in Eqs. (64, 65, 66). Ten networks of size $n=20000$ are generated with $\alpha =2.5,\beta =2.0,a=1.0,\text{and}R=6.0$. The resulting average degree is about 20. (a) and (b) show the complementary cumulative distribution functions (CCDF) of degrees and strengths, while (c) shows the average strengths of nodes of degree $k$.

Figure 3

Maximum likelihood estimation of the latent parameters in the WSCM with power-law degree and strength sequences. Degree sequences of length $n=3000$ are sampled from the Pareto distribution with varying power-law exponent $\gamma$, and then rounded to the closest integer. The corresponding strengths are set to $s_i={\sigma }_0{k}_i^{\eta }$. The expected average degree is set to $\overline{k}=10$ and ${\sigma }_0=0.1$. (a)–(c) show scatter plots of the inferred parameters $\lambda ,\mu$ for varying values of $\eta$ and $\gamma =2.2,2.6,\text{and}3.0$. The inset in (a) shows the $\lambda -\mu$ scatter plot for $\eta =1.7, \gamma =2.2$ along with the power-law fit lines for small-$\lambda$ and large-$\lambda$ regions. (d)–(f) show the complementary CDFs of the $\lambda$ parameter for varying values of $\eta$ and $\gamma =2.2,2.6,\text{and}3.0$. The inset in (d) shows the complementary CDF of the $\lambda$ parameter for $\eta =1.7, \gamma =2.2$ along with the power-law fit lines for small-$\lambda$ and large-$\lambda$ regions.

Figure 4

Structural properties of synthetic networks in the power-law WHSCM model defined in Sec. 5. The parameters used to generate the networks are $n={10}^5, \overline{k}=10, {\sigma }_0=0.1, \gamma \in \{2.2,2.6,3.0\}$, and $\eta \in \{1.0,1.1,1.3,1.5,1.7,1.9\}$. For each combination of the parameters, 20 network instances are generated. (a), (d), and (g) show the empirical complementary CDFs (CCDFs) of node degrees for $\gamma =2.2,2.6,\text{and}3.0$. Each panel shows 20 degree CCDF curves corresponding to the 20 network instances. The curves with the same value of exponent $\eta$ are of the same color. The black dashed lines show the imposed values of the power-law exponent $\gamma$. Panels (b), (e), and (h) show the empirical CCDFs of node strengths for $\gamma =2.2,2.6,3.0$. The black lines denote the power laws with the imposed values of $\delta -1$ where the strength power-law exponent $\delta$ is related to $\gamma$ and $\eta$ via $\delta -1=(\gamma -1)/\eta$. Panels (c), (f), (i) show the strength-degree correlations for $\gamma =2.2,2.6,3.0$. The average strength $\overline{s}\left(k\right)$ of nodes of degree $k$ is shown for all the 20 network instances. The curves with the same $\eta$ are of the same color. The black lines show the functions $s\left(k\right)={\sigma }_0{k}^{\eta }$ with the imposed values of $\eta$. For clarity, the strength CCDFs are shown for $s\ge {10}^{-2}$.

Figure 5

Inferred power-law exponents of the degree and strength distributions in synthetic WHSCM networks. Synthetic networks of varying sizes $n\in [{10}^2,{10}^5]$ are generated using the power-law WHSCM from Sec. 5 with the shown matrix of values of parameters $\gamma ,\eta$. All networks have $\overline{k}=10$ and ${\sigma }_0=0.1$. For each combination of parameters and sizes $n$, 20 random networks are generated. The degree distribution power-law exponent $\gamma$ and the strength distribution power-law exponent $\delta$ are then inferred using the power-law exponent estimation software from [32]. The box plots show the distributions of the inferred values of $\gamma ,\delta$. The box plot settings are standard: the whiskers are the 5th and 95th percentiles, and the box boundaries are the 25th and 75th percentiles of the distributions; the black lines within the boxes are the medians. The dashed and dotted lines show the target values of $\gamma$ and $\delta$ used to generate the networks.

Figure 6

Weight disparity as a function of node degree in the power-law WHSCM. The figure shows the log-binned average weight disparity $\overline{Y}\left(k\right)$ of nodes of degree $k$ in the power-law WHSCM networks with $\gamma =2.2,2.6,3.0$ and $\eta =1.0,1.1,1.3,1.9$. The black dashed lines show the $1/k$ scaling. In all the generated networks, the other parameters are set to $n={10}^5, \overline{k}=10$, and ${\sigma }_0=0.1$.

Figure 7

Real networks vs their WHSCM counterparts. Each row in the figure corresponds to one of the three real weighted networks described in Sec. 7, as indicated by the network names at the top of each row. Each column in the figure shows different structural properties of the real networks: (a), (f), and (k) show the degree CCDFs, with the dashed blacked lines indicating the pure power-law scalings with the exponents $\gamma$ listed in Table 2; (b), (g), and (l) show the average strength as a function of node degree, $\overline{s}\left(k\right)$, with the black dashed lines indicating the pure scalings with the exponents $\eta$ shown in Table 2, and the gray dashed lines indicating the linear scaling; (c), (h), and (m) show the average weight disparity, defined in Eq. (89), as a function of node degree, with the gray dashed lines indicating the $1/k$ scaling of the weight disparity corresponding to the perfectly homogeneous distribution of local weights; (d), (i), and (n) show the average local clustering coefficient as a function of node degree; (e), (j), and (o) show the average weighted local clustering coefficient, defined in Eq. (90), as a function of node strength. The data for the real networks are shown in the orange color, while the data for the synthetic WHSCM networks are in blue. For each real networks, ten random WHSCM graphs are generated using the power-law WHSCM with the parameters listed in Table 2.

Figure 8

Correlation of the expected and actual degrees/strengths in the WHSCM. Each row corresponds to the WHSCM input parameter $\gamma$ indicated on the top. Each color-coded plot corresponds to an $\eta$ parameter indicated in the legend. The rest of the WHSCM input parameters are $n=10,000, \overline{k}=10$, and ${\sigma }_0=0.1$. Data is log-binned. Error bars show standard deviation from the bin mean. Black dashed line shows perfect linear correlation.

Figure 9

Scaling of the $R$ and $a$ parameters as a function of network size $n$ for various values of $\gamma , \eta$, and fixed values of $\overline{k}=10$ and ${\sigma }_0=0.1$.

Figure 10

Illustration of the approximation used to find expression for $\kappa$ and $\sigma$. The scheme is plotted on the log-log scale.