Connection Subgraphs in Social Networks

Abstract

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