Analytical approach to network inference: Investigating degree distribution

When the network is reconstructed, two types of errors can occur: false positive and false negative errors about the presence or absence of links. In this paper, the influence of these two errors on the vertex degree distribution is analytically analyzed. Moreover, an analytic formula of the density of the biased vertex degree distribution is found. In the inverse problem, we find a reliable procedure to reconstruct analytically the density of the vertex degree distribution of any network based on the inferred network and estimates for the false positive and false negative errors based on, e.g., simulation studies.

Figure 1

Density histogram of the original vertex degrees, blue bars; detected density vertex degree distribution, gray dotted line; the result of network reconstruction using Eq. (9) knowing $A$ and ${\mathcal{P}}^{\prime }$, solid red line; and the result when a non-negative constraint is applied to the truncated singular value decomposition, black dashed line. The original network is a random network with 100 nodes and probability of connection 0.2.

Figure 2

Density histogram of the original vertex degrees, blue bars; detected density vertex degree distribution, gray dotted line; the result of network reconstruction using Eq. (9) knowing $A$ and ${\mathcal{P}}^{\prime }$, solid red line; and the result when a non-negative constraint is applied to the truncated singular value decomposition, black dashed line. The original network is a small world network with 100 nodes and probability of rewiring 0.4.

Figure 3

Density histogram of the original vertex degrees, blue bars; detected density vertex degree distribution, gray dotted line; the result of network reconstruction using Eq.(9) knowing $A$ and ${\mathcal{P}}^{\prime }$, solid red line; and the result when a non-negative constraint is applied to the truncated singular value decomposition, black dashed line. The original network is a scale-free network with 100 nodes.

Figure 4

Density histogram of the original vertex degrees, blue bars; detected density vertex degree distribution, gray dotted line; the result of network reconstruction using Eq. (9) knowing $A$ and ${\mathcal{P}}^{\prime }$, solid red line; and the result when a non-negative constraint is applied to the truncated singular value decomposition, black dashed line. The original network is a $4\times 5\times 5$ grid.

Figure 5

Density histogram of the original vertex degrees, blue bars; detected density vertex degree distribution, gray dotted line; the result of network reconstruction using Eq.(9) knowing $A$ and ${\mathcal{P}}^{\prime }$, solid red line; and the result when a non-negative constraint is applied to the truncated singular value decomposition, black dashed line. A network of three randomly connected communities is used as original network.

Figure 6

Reconstruction of the degree of a single node with original degree $k=75$.

Figure 7

Reconstructions of the degree of single nodes with original degrees $k$ from 10 to 90 in steps of 10.

Figure 8

Density histogram of the original vertex degrees, blue bars; detected density vertex degree distribution, gray dotted line; and the results when a non-negative constraint is applied to the truncated singular value decomposition using the true $\beta$, black dashed line; and perturbations from the true $\beta$, red, blue, green, and yellow solid lines. The original network is a scale-free network with 100 nodes.

Figure 9

Density histogram of the original vertex degrees, blue bars; detected density vertex degree distribution, gray dotted line; and the results when a non-negative constraint is applied to the truncated singular value decomposition using the true $\beta$, black dashed line; and perturbations from the true $\beta$, red, blue, green, and yellow solid lines. The original network is a random network with 100 nodes and probability of connection 0.2.

Figure 10

Density histogram of the original vertex degrees, blue bars; detected density vertex degree distribution, gray dotted line; and the results when a non-negative constraint is applied to the truncated singular value decomposition using the true $\beta$, black dashed line; and perturbations from the true $\beta$, red, blue, green, and yellow solid lines. The original network is a random network with 100 nodes and probability of connection 0.2.

Figure 11

Density histogram of the original vertex degrees, blue bars; detected density vertex degree distribution, gray dotted line; and the results when a non-negative constraint is applied to the truncated singular value decomposition using the true $\beta$, black dashed line; and perturbations from the true $\beta$, red, blue, green, and yellow solid lines. The original network is a random network with 100 nodes and probability of connection 0.8.