Robert R. McCormick School of Engineering and Applied Science Electrical Engineering and Computer Science Department Center for Ultra-scale Computing and Information Security at Northwestern University

Project Team Members:

Northwestern University


Parallel MEP (PMEP)


Description:

Detecting communities is of great importance in sociology, biology and computer science disciplines where systems are often represented as graphs. Community detection for large graphs is extremely challenging due to a lack of a priori information of the graph structure and a high degree of data dependency. The scalability and quality of a parallel algorithm is significantly impacted by the data partitioning scheme it employs.

We have devised a distributed-memory based parallel algorithm called PMEP which parallelizes MEP, a community detection algorithm based on the idea of maximizing equilibrium and purity of communities. MEP has been demonstrated to produce high quality of results for medium to large graphs. To parallelize MEP, we use a data partitioning strategy that duplicates a portion of computational workload in exchange for a lower communication cost required in the later stage when combing local results into a global one. This strategy is motivated by the fact that graph problems are highly data dependent and it is unlikely for a data partitioner to produce subgraphs that can be processed independently on multiple processes without incurring a high cost of synchronization and communication. The experimental results on both synthetic and real dataset show that PMEP successfully achieves scalability while maintaining high qualities of clustering results.

PMEP is a publicly available code that implements distributed-memory based parallel community detection algorithm using MPI.

Publications:

Software Download:

CONTACT:

Most files in the suite are self explanatory and include comments. In case you have unresolvable issues or if you would like to give suggestions or contribute software, please email us.

Northwestern University EECS Home | McCormick Home | Northwestern Home | Calendar: Plan-It Purple
© 2011 Robert R. McCormick School of Engineering and Applied Science, Northwestern University
"Tech": 2145 Sheridan Rd, Tech L359, Evanston IL 60208-3118  |  Phone: (847) 491-5410  |  Fax: (847) 491-4455
"Ford": 2133 Sheridan Rd, Ford Building, Rm 3-320, Evanston, IL 60208  |  Fax: (847) 491-5258
Email Director

Last Updated: $LastChangedDate: 2015-03-06 21:41:36 -0600 (Fri, 06 Mar 2015) $