Network Inference From Co-Occurrences

DOI10.1109/TIT.2008.926315zbMATH Open1322.68170arXivcs/0605100OpenAlexW3100458749MaRDI QIDQ3604833FDOQ3604833

Authors: Michael G. Rabbat, Mário A. T. Figueiredo, Robert D. Nowak 

Publication date: 24 February 2009

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: The recovery of network structure from experimental data is a basic and fundamental problem. Unfortunately, experimental data often do not directly reveal structure due to inherent limitations such as imprecision in timing or other observation mechanisms. We consider the problem of inferring network structure in the form of a directed graph from co-occurrence observations. Each observation arises from a transmission made over the network and indicates which vertices carry the transmission without explicitly conveying their order in the path. Without order information, there are an exponential number of feasible graphs which agree with the observed data equally well. Yet, the basic physical principles underlying most networks strongly suggest that all feasible graphs are not equally likely. In particular, vertices that co-occur in many observations are probably closely connected. Previous approaches to this problem are based on ad hoc heuristics. We model the experimental 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. For long transmission paths the exact E-step may be computationally intractable, so we also describe an efficient Monte Carlo EM (MCEM) algorithm and derive conditions which ensure convergence of the MCEM algorithm with high probability. Simulations and experiments with Internet measurements demonstrate the promise of this approach.

Full work available at URL: https://arxiv.org/abs/cs/0605100

Recommendations

• Inferential Network Analysis
• Towards structural network analysis.
• Hypergraph modeling and visualisation of complex co-occurence networks
• Detecting direct associations in a network by information theoretic approaches
• Structure-oriented prediction in complex networks
• Network inference and community detection, based on covariance matrices, correlations, and test statistics from arbitrary distributions
• Inferring network topology from complex dynamics
• A framework for imperfectly observed networks

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Applications of Markov renewal processes (reliability, queueing networks, etc.) (60K20) Computing methodologies for information systems (hypertext navigation, interfaces, decision support, etc.) (68U35)

Cited In (4)

• Estimating diffusion networks: recovery conditions, sample complexity and soft-thresholding algorithm
• Iterative procedure for network inference
• Data-driven network analysis and applications
• Reconstructing Markov processes from independent and anonymous experiments

This page was built for publication: Network Inference From Co-Occurrences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3604833)