Fast discovery of connection subgraphs

Christos Faloutsos, Kevin S. McCurley, Andrew Tomkins

Abstract

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 networks 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 in real time on very large (disk resident) graphs.We describe our operational prototype, and we demonstrate results on a social network graph derived from the World Wide Web. Our graph contains 15 million nodes and 96 million edges, and our system still produces quality responses within seconds.
BibTeX
@inproceedings{faloutsos2004fast,
  author = {Christos Faloutsos and Kevin S. McCurley and Andrew Tomkins},
  title = {{Fast discovery of connection subgraphs}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2004},
  doi = {10.1145/1014052.1014068},
}

Loading related content...

Figure