Network Inference from Co-Occurrences

Details Network Inference from Co-Occurrences Network Inference from Co-Occurrences

2006-05-23

arxiv.org/abs/cs/0605100v1

Computer Science

Information Theory

Submitted to IEEE Transactions on Information Theory. An extended version is available as University of Wisconsin Technical Re

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Network Inference from Co-Occurrences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Network Inference from Co-Occurrences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network Inference from Co-Occurrences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-181796