Phys. Rev. E 93, 012306 (2016) - Structural inference for uncertain networks

Go Mobile »
Access by University of Bath

Structural inference for uncertain networks

Travis Martin, Brian Ball, and M. E. J. Newman

Phys. Rev. E 93, 012306 – Published 15 January 2016

Abstract

In the study of networked systems such as biological, technological, and social networks the available data are often uncertain. Rather than knowing the structure of a network exactly, we know the connections between nodes only with a certain probability. In this paper we develop methods for the analysis of such uncertain data, focusing particularly on the problem of community detection. We give a principled maximum-likelihood method for inferring community structure and demonstrate how the results can be used to make improved estimates of the true structure of the network. Using computer-generated benchmark networks we demonstrate that our methods are able to reconstruct known communities more accurately than previous approaches based on data thresholding. We also give an example application to the detection of communities in a protein-protein interaction network.

Received 7 July 2015

DOI:https://doi.org/10.1103/PhysRevE.93.012306

©2016 American Physical Society

Authors & Affiliations

Travis Martin¹, Brian Ball^2,3, and M. E. J. Newman^2,4

¹Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, Michigan, USA
²Department of Physics, University of Michigan, Ann Arbor, Michigan, USA
³Quicken Loans, Detroit, Michigan, USA
⁴Center for the Study of Complex Systems, University of Michigan, Ann Arbor, Michigan, USA

Article Text

Click to Expand

References

Click to Expand

Issue

Vol. 93, Iss. 1 — January 2016

Reuse & Permissions

Access Options

Article part of CHORUS

Announcement

Physical Review E Scope Description to Include Biological Physics

January 14, 2016

The editors of Physical Review E are pleased to announce that the journal’s stated scope has been expanded to explicitly include the term “Biological Physics.”

Images

Figure 1
The model of uncertain network generation used in our calculations. A community assignment $g$ $g$ and network $A$ $A$ are drawn from a random network model such as the stochastic block model. The experimental uncertainty is represented by giving each pair of nodes $i, j$ $i, j$ a probability $Q_{i j}$ $Q_{i j}$ of being connected by an edge, drawn from different distributions for edges $A_{i j} = 1$ $A_{i j} = 1$ and nonedges $A_{i j} = 0$ $A_{i j} = 0$ .
Reuse & Permissions
Figure 2
Simple example of the generation of two uncertain networks from an initial network with three nodes. The two networks generated (right-hand side) differ only in their noise distributions, $β_{0} (Q)$ $β_{0} (Q)$ and $β_{1} (Q)$ $β_{1} (Q)$ , whose probability density functions (PDFs) are shown in the center. The lower pair of distributions corresponds to a low-noise setting in which the PDFs for edges and nonedges are quite distinct and the resulting probability matrix $Q$ $Q$ retains most of the information from the original adjacency matrix $A$ $A$ . The upper pair of distributions corresponds to a high-noise setting in which the two PDFs are almost the same and the final matrix $Q$ $Q$ retains little of the original network structure.
Reuse & Permissions
Figure 3
Tests of the method described in this paper on synthetic benchmark networks. (a) Fraction of nodes placed in the correct community for uncertain networks generated using a stochastic block model with $n = 4000$ $n = 4000$ nodes, two groups of equal size, edge probabilities $ω_{11} = ω_{22} = 0.02, ω_{12} = ω_{21} = 0.014$ $ω_{11} = ω_{22} = 0.02, ω_{12} = ω_{21} = 0.014$ , and noise parameters $a_{1} = 1.4$ $a_{1} = 1.4$ and $b_{1} = 2$ $b_{1} = 2$ [see Eq. (38)]. The horizontal dashed line shows the performance of the algorithm described in this paper. The points show the performance of a naive algorithm in which the uncertain network is first converted to a binary network by thresholding the edge probabilities and the result then fed into a standard community detection algorithm. The results for each algorithm are averaged over 20 repetitions of the experiment with different networks. Statistical errors are comparable in size to the data points. (b) Fraction of nodes classified into their correct communities for stochastic block model networks with varying amounts of noise in the data. The parameters are the same as for (a) but with the sparsity parameter $c$ $c$ fixed at $1 / 4 n$ $1 / 4 n$ [see Eq. (39) and the ensuing discussion] and varying the parameter $b_{1}$ $b_{1}$ , which controls the level of noise in the data.
Reuse & Permissions
Figure 4
Communities found by (a) the algorithm described in this paper and (b) the thresholding algorithm, in a three-way split of the protein interaction network of the bacterium Borrelia hermsii HS1, taken from the STRING database. Nodes are laid out according to the communities in (a) and the layout is the same in both panels.
Reuse & Permissions
Figure 5
Receiver operating characteristic (ROC) curves for the edge recovery problem on a synthetic network generated using a two-group stochastic block model with $n = 4000$ $n = 4000$ nodes, $ω_{11} = ω_{22} = 0.05, ω_{12} = ω_{21} = 0.001$ $ω_{11} = ω_{22} = 0.05, ω_{12} = ω_{21} = 0.001$ , and noise parameters $b_{1} = 4$ $b_{1} = 4$ and $c = 1 / 4 n$ $c = 1 / 4 n$ . The three curves show the performance of the algorithm of this paper, the naive algorithm based on the raw probabilities $Q_{i j}$ $Q_{i j}$ alone, and a hypothetical “ideal” algorithm that knows the values of the parameters used to generate the model (so that one does not have to run the EM algorithm at all). The diagonal dashed line represents a curve generated by an algorithm that does no better than chance.
Reuse & Permissions

1 of 5

Sign up to receive regular email alerts from Physical Review E