Graph reconstruction from path correlation data

DOI10.1088/1361-6420/AAE798MaRDI QIDQ4646414zbMATH OpenOpenAlexWikidataFDO

Authors Gregory Berkolaiko, N. G. Duffield, Mahmood Ettehad, Kyriakos Manousakis

Publication date 14 January 2019

Published in Inverse Problems (Search for Journal in Brave)

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

zbMATH Keywords

asymmetric routingcovarianceend-to-end measurementlogical treesnetwork tomographyunicast probing

Mathematics Subject Classification ID

Distance in graphs (05C12) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Communication networks in operations research (90B18)

Abstract: A communication network can be modeled as a directed connected graph with edge weights that characterize performance metrics such as loss and delay. Network tomography aims to infer these edge weights from their pathwise versions measured on a set of intersecting paths between a subset of boundary vertices, and even the underlying graph when this is not known. In particular, temporal correlations between path metrics have been used infer composite weights on the subpath formed by the path intersection. We call these subpath weights the Path Correlation Data. In this paper we ask the following question: when can the underlying weighted graph be recovered knowing only the boundary vertices and the Path Correlation Data? We establish necessary and sufficient conditions for a graph to be reconstructible from this information, and describe an algorithm to perform the reconstruction. Subject to our conditions, the result applies to directed graphs with asymmetric edge weights, and accommodates paths arising from asymmetric routing in the underlying communication network. We also describe the relationship between the graph produced by our algorithm and the true graph in the case that our conditions are not satisfied.

Recommendations

• Distance realization problems with applications to internet tomography
• Network tomography: recent developments
• Network tomography: a review and recent developments
• Reconstruction of graphs based on random walks
• Reconstructing cactus graphs from shortest path information (extended abstract)

Cites work

• Combinatorial reconstruction problems
• Electrical Impedance Tomography
• Identifiability of flow distributions from link measurements with applications to computer networks
• Multicast topology inference from measured end-to-end loss
• Multicast-based inference of network-internal loss characteristics
• Network Tomography of Binary Network Performance Characteristics
• Network Tomography: Estimating Source-Destination Traffic Intensities from Link Data
• On revealing graph cycles via boundary measurements
• Optical tomography on graphs
• Pyramidal resistor networks for electrical impedance tomography with partial boundary measurements
• Recent progress in the boundary control method
• Recovering a tree from the lengths of subtrees spanned by a randomly chosen sequence of leaves
• Time-Varying Network Tomography: Router Link Data

Cited in

(6)

• On the interpretation of inflated correlation path weights in concentration graphs
• Data-driven network analysis and applications
• Reconstructing cactus graphs from shortest path information (extended abstract)
• scientific article; zbMATH DE number 5504379 (Why is no real title available?)
• Reconstructing undirected graphs from eigenspaces
• Reconstruction of graphs based on random walks

This page was built for publication: Graph reconstruction from path correlation data

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