SCHEDULE: NOV 15-20, 2015

When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.

GossipMap: A Distributed Community Detection Algorithm for Billion-Edge Directed Graphs

SESSION: Graph Analytics on HPC systems

EVENT TYPE: Papers

EVENT TAG(S): Architectures, Clouds and Distributed Computing, Analytics

TIME: 4:00PM - 4:30PM

SESSION CHAIR(S): Dilma Da Silva

AUTHOR(S):Seung-Hee Bae, Bill Howe

ROOM:19AB

ABSTRACT:

In this paper, we describe a new distributed community detection algorithm for billion-edge directed graphs that, unlike modularity-based methods, achieves cluster quality on par with the best-known algorithms in the literature. We show that a simple approximation to the best-known serial algorithm dramatically reduces computation and enables distributed evaluation yet incurs only a very small impact on cluster quality.

We present three main results: First, we show that the clustering produced by our scalable approximate algorithm compares favorably with prior results on small synthetic benchmarks and small real-world datasets (70 million edges). Second, we evaluate our algorithm on billion-edge directed graphs (a 1.5B edge social network graph, and a 3.7B edge web crawl), and show that the results exhibit the structural properties predicted by analysis of much smaller graphs from similar sources. Third, we show that our algorithm exhibits over 90% parallel efficiency on massive graphs in weak scaling experiments.

Chair/Author Details:

Dilma Da Silva (Chair) - Texas A&M University|

Seung-Hee Bae - University of Washington

Bill Howe - University of Washington

  Click here to download .ics calendar file

  Click here to download .vcs calendar file

  Click here to add event to your Google Calendar

Paper provided by the ACM Digital Library

Paper also available from IEEE Computer Society