Combinatorial Network Abstraction by Trees and Distances

We draw attention to network abstraction as a fundamental problem within network analysis and visualization. A combinatorial network abstraction problem is specified by a class P of pattern graphs and a real-valued similarity measure rho based on certain graph properties. For fixed P and rho, the optimization task on any graph G is finding a subgraph G' which belongs to P such that rho(G,G') is minimal. In this work, we consider this problem for the natural case of trees (as the class of pattern graphs) and similarity-measures based on distances. In particular -with respect to the most standard vector and matrix norms- we systematically study sub-trees of graphs that minimize distances, approximate distances, and approximate closeness-centrality. Although these similarity measures lead to reasonable results, the complexity analysis of finding optimal trees is discouraging: we prove that all problems are NP-complete independent of the norms used, except for the case of minimizing distances with respect to the L_infinity matrix-norm which was already known to have a polynomial algorithm.     «

We draw attention to network abstraction as a fundamental problem within network analysis and visualization. A combinatorial network abstraction problem is specified by a class P of pattern graphs and a real-valued similarity measure rho based on certain graph properties. For fixed P and rho, the optimization task on any graph G is finding a subgraph G' which belongs to P such that rho(G,G') is minimal. In this work, we consider this problem for the natural case of trees (as the class of pattern...     »