Islands and Bridges: Making Sense of Marked Nodes in Large Graphs
Leman Akoglu, Jilles Vreeken, Hanghang Tong, Duen H Chau, Christos Faloutsos · 2012
contained in this document are those of the authors and should not be interpreted as repre-senting the official policies, either expressed or implied, of the Army Research Laboratory, of the National Science Foundation, of the U.S. Government, or any other funding parties. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on. This work is also partially supported by an IBM Faculty Award. Jilles Vreeken is supported by a Post-Doctoral Fellowship of the Re-search Foundation – Flanders (FWO). Suppose we are given a large graph in which, by some external process, a handful of nodes are marked. What can we say about these marked nodes? Are they all close-by in the graph, or are they segregated into multiple groups? How can we automatically determine how many, if any, groups they form as well as find simple paths that connect the nodes in each group? We formalize the problem in terms of the Minimum Description Length principle: a set of paths is simple when we need few bits to describe each path from one node to another. For example, we want to avoid high-degree nodes, unless we need to visit many of its spokes. As such, the best partitioning