Connection Subgraphs in Social Networks

Full textClick to download.
CitationWorkshop on Link Analysis, Counter terrorism, and Privacy SIAM International Conference on Data Mining, 2004
AuthorsChristos Faloutsos
Kevin S. McCurley
Andrew Tomkins


A connection subgraph is a small (ie, viewable) subgraph of a social network that best captures the relationship between two people. We present a formal definition of this problem, and an ideal solution based on computation of current in electrical networks, or equivalently, based on random walks on weighted graphs. We then give a series of approximations to the ideal solution that produce high-quality connection subgraphs in real time on very large (out of core) social network graphs. We describe a working prototype, and we demonstrate results on a social network graph derived from the World Wide Web containing 15 million nodes and 96 million edges, for which our prototype produces good quality responses within a few seconds.

Back to publications
Back to previous page