1 Network Inference from Co-Occurrences
Michael Rabbat, Mário A. T. Figueiredo, Senior Member, Robert D. Nowak, Senior Member · 2006
The discovery of network structures is a fundamental problem in arising in numerous fields of science and technology, communication systems, biology, sociology and neuroscience. Unfortunately, it is often difficult to obtain data that directly reveals network structure, and so one must infer a network from incomplete data. This paper considers inferring network structure from “co-occurrence ” data; observations that identify which network components (e.g., switches, routers, genes) carry each transmission but does not indicate the order in which they handle the transmissions. Without order information, there is an exponential number of feasible networks that are compatible with the observed data. Yet, the basic physical principles underlying most networks strongly suggest that all feasible networks are not equally likely. In particular, network elements that co-occur in many observations are probably closely connected. We model the co-occurrence observations as independent realizations of a random walk on the underlying graph, subjected to a random permutation which accounts for the lack of order information. Treating the permutations as missing data, we derive an exact expectation-maximization (EM) algorithm for estimating the random walk parameters. The model and EM algorithm significantly simplify the problem, but the computational complexity of the reconstruction process does grow exponentially in the length of the longest transmission path. For large networks the exact E-step may be computationally intractable, and so we also propose an efficient Monte Carlo EM (MCEM) algorithm, based on importance sampling, and derive conditions which ensure convergence of the algorithm with high probability. Remarkably, the MCEM maintains the desirable properties of the exact EM algorithm and reduces the complexity of each iteration