Share Email Print

Proceedings Paper

Network reconstruction via graph blending
Author(s): Rolando Estrada
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

Graphs estimated from empirical data are often noisy and incomplete due to the difficulty of faithfully observing all the components (nodes and edges) of the true graph. This problem is particularly acute for large networks where the number of components may far exceed available surveillance capabilities. Errors in the observed graph can render subsequent analyses invalid, so it is vital to develop robust methods that can minimize these observational errors. Errors in the observed graph may include missing and spurious components, as well fused (multiple nodes are merged into one) and split (a single node is misinterpreted as many) nodes. Traditional graph reconstruction methods are only able to identify missing or spurious components (primarily edges, and to a lesser degree nodes), so we developed a novel graph blending framework that allows us to cast the full estimation problem as a simple edge addition/deletion problem. Armed with this framework, we systematically investigate the viability of various topological graph features, such as the degree distribution or the clustering coefficients, and existing graph reconstruction methods for tackling the full estimation problem. Our experimental results suggest that incorporating any topological feature as a source of information actually hinders reconstruction accuracy. We provide a theoretical analysis of this phenomenon and suggest several avenues for improving this estimation problem.

Paper Details

Date Published: 12 May 2016
PDF: 20 pages
Proc. SPIE 9826, Cyber Sensing 2016, 982605 (12 May 2016); doi: 10.1117/12.2223864
Show Author Affiliations
Rolando Estrada, Teledyne Scientific Co. (United States)

Published in SPIE Proceedings Vol. 9826:
Cyber Sensing 2016
Igor V. Ternovskiy; Peter Chin, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?