Abstract
We present a new approach to community discovery. Community discovery usually partitions the graph into communities or clusters. Focused community discovery allows the searcher to specify start points of interest, and find the community of those points. Focused search allows for a much more scalable algorithm in which the time depends only on the size of the community, and not on the number of nodes in the graph, and so is scalable to arbitrarily large graphs. Furthermore, our algorithm is robust to imperfect data, such as extra or missing edges in the graph. We show the effectiveness of our algorithm using both synthetic graphs and on the real-life Livejournal friends graph, a publicly-available social network consisting of over two million users and 13 million edges. © 2005 IEEE.