Fast Discovery of Connection Subgraphs
Christos Faloutsos,
Kevin S. McCurley, and Andrew Tomkins
We define a connection subgraph as a small subgraph of a
large graph that best captures the relationship between two nodes. The
primary motivation for this work is to provide a paradigm for exploration
and knowledge discovery in large social network graphs. We present a
formal definition of this problem, and an ideal solution based on electricity
analogues. We then show how to accelerate the computations,
to produce approximate but high-quality connection subgraphs on very
large (disk-resident) graphs.
The full paper on
connection subgraphs is available.