- Home
- Register
- Attend
- Conference Program
- SC15 Schedule
- Technical Program
- Awards
- Students@SC
- Research with SCinet
- HPC Impact Showcase
- HPC Matters Plenary
- Keynote Address
- Support SC
- SC15 Archive
- Exhibits
- Media
- SCinet
- HPC Matters
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