SC12 Home > SC12 Schedule > SC12 Presentation - Parallel Algorithms for Counting Triangles and Computing Clustering Coefficients

SCHEDULE: NOV 10-16, 2012

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.

Parallel Algorithms for Counting Triangles and Computing Clustering Coefficients

SESSION: Research Poster Reception

EVENT TYPE: Posters and Electronic Posters

TIME: 5:15PM - 7:00PM

SESSION CHAIR: Torsten Hoefler

AUTHOR(S):S. M. Arifuzzaman, Maleq Khan, Madhav V. Marathe

ROOM:East Entrance

ABSTRACT:
We present MPI-based parallel algorithms for counting triangles and computing clustering coefficients in massive networks. Counting triangles is important in the analysis of various networks, e.g., social, biological, web etc. Emerging massive networks do not fit in the main memory of a single machine and are very challenging to work with. Our distributed-memory parallel algorithm allows us to deal with such massive networks in a time- and space-efficient manner. We were able to count triangles in a graph with 2 billions of nodes and 50 billions of edges in 10 minutes. Our parallel algorithm for computing clustering coefficients uses efficient external memory aggregation. We also show how edge sparsification technique can be used with our parallel algorithm to find approximate number of triangles without sacrificing the accuracy of estimation. In addition, we propose a simple modification of a state-of-the-art sequential algorithm that improves both runtime and space requirement.

Chair/Author Details:

Torsten Hoefler (Chair) - ETH Zurich

S. M. Arifuzzaman - Virginia Tech

Maleq Khan - Virginia Tech

Madhav V. Marathe - Virginia Tech

Add to iCal  Click here to download .ics calendar file

Add to Outlook  Click here to download .vcs calendar file

Add to Google Calendarss  Click here to add event to your Google Calendar

Parallel Algorithms for Counting Triangles and Computing Clustering Coefficients

SESSION: Research Poster Reception

EVENT TYPE:

TIME: 5:15PM - 7:00PM

SESSION CHAIR: Torsten Hoefler

AUTHOR(S):S. M. Arifuzzaman, Maleq Khan, Madhav V. Marathe

ROOM:East Entrance

ABSTRACT:
We present MPI-based parallel algorithms for counting triangles and computing clustering coefficients in massive networks. Counting triangles is important in the analysis of various networks, e.g., social, biological, web etc. Emerging massive networks do not fit in the main memory of a single machine and are very challenging to work with. Our distributed-memory parallel algorithm allows us to deal with such massive networks in a time- and space-efficient manner. We were able to count triangles in a graph with 2 billions of nodes and 50 billions of edges in 10 minutes. Our parallel algorithm for computing clustering coefficients uses efficient external memory aggregation. We also show how edge sparsification technique can be used with our parallel algorithm to find approximate number of triangles without sacrificing the accuracy of estimation. In addition, we propose a simple modification of a state-of-the-art sequential algorithm that improves both runtime and space requirement.

Chair/Author Details:

Torsten Hoefler (Chair) - ETH Zurich

S. M. Arifuzzaman - Virginia Tech

Maleq Khan - Virginia Tech

Madhav V. Marathe - Virginia Tech

Add to iCal  Click here to download .ics calendar file

Add to Outlook  Click here to download .vcs calendar file

Add to Google Calendarss  Click here to add event to your Google Calendar