Paper Info
Title
Network Topology Mapping From Partial Virtual Coordinates and Graph Geodesics
Abstract
For many important network types, physical coordinate systems and physical distances are either difficult to discern or inapplicable. Accordingly, coordinate systems and characterizations based on hop-distance measurements, such as Topology Preserving Maps (TPMs) and Virtual-Coordinate (VC) systems are attractive alternatives to geographic coordinates for many network algorithms. We present an approach to recover geometric and topological properties of a network with a small set of distance measurements. The approach is a combination of shortest path (often called geodesic) recovery concepts and low-rank matrix completion, generalized to the case of hop-distances in graphs. Results for sensor networks embedded in 2-D and 3-D spaces as well as for social networks indicate that the method can accurately capture the network connectivity with a small set of measurements. TPM generation can now be based on various context appropriate measurements or VC systems instead of distances to a set of global anchors. The proposed method is a significant generalization that allows the topology to be extracted from a random set of graph shortest paths, making it applicable in contexts such as social networks where VC generation may not be possible.
Year
DOI
Venue
2019
10.1109/TNET.2019.2953921
IEEE/ACM Transactions on Networking
Keywords
Field
DocType
Network topology,Topology,Social network services,Layout,Level measurement,Atmospheric measurements,Particle measurements
Coordinate system,Topology,Matrix completion,Shortest path problem,Computer science,Geographic coordinate system,Network topology,Small set,Wireless sensor network,Geodesic,Distributed computing
Journal
Volume
Issue
ISSN
27
6
1063-6692
Citations 
PageRank 
References 
0
0.34
0
Authors
5
Name
Order
Citations
PageRank
A. Jayasumana193.57
Randy Paffenroth29914.17
Gunjan Mahindre301.35
Sridhar Ramasamy400.34
Gajamannage Kelum521.73