Community Detection Survey

Introduction

The repository collects and refactors some overlapping Community detection algorithms. Major content is survey, algorithms' implementations, graph input benchmarks, submodules, scripts.

Recommend ide are from jetbrains, namely clion, pycharm and intellij for c++, python and java.

Some Non-Overlapping Community Detections Algorithms could be found in NonOverlappingCodes.

A community-detection survey in Survey, you can have a look, if interested.

Graph Benchmarks

Synthetic Tool

Content | Detail | Status --- | --- | --- 2009-LFR-Benchmark | LFR Benchmark to generate five types of graphs | build success, some files unused

Real-World DataSets(Edge List)

Detailed information is in Datasets.

Newly occurring useful links(Websites for downloading)

• http://networkrepository.com/soc.php
• http://konect.uni-koblenz.de/
• http://law.di.unimi.it/datasets.php

Old links

• http://vlado.fmf.uni-lj.si/pub/networks/data/
• https://snap.stanford.edu/data/

Quality-Evaluation Metrics

Without-Ground-Truth

Evaluation Metric Name | Implementation | Heuristic --- | --- | --- Link-Belonging-Based Modularity | link_belong_modularity.py | compare to random graph

With-Ground-Truth

Evaluation Metric Name | Implementation | Heuristic --- | --- | --- Overlap-NMI | overlap_nmi.py | info-theory entropy-measure Omega-Idx | omega_idx.py | unadjusted compared to expected

Algorithms

In each algorithm, there is a ReadMe.md, which gives brief introduction of corresponding information of the algorithm and current refactoring status. Category information are extracted, based on Xie's 2013 Survey paper Overlapping Community Detection in Networks: The State-of-the-Art and Comparative Study.

All c++ projects are built with cmake, java projects are built with maven, python projects are not specified how to build.

Algorithm | Category | Language | Dependency | Status --- | --- | --- | --- | --- 2008-CPM | clique percolation | c++, python | lcelib | build success 2009-CIS | seed expansion | c++ | | build success 2009-EAGLE | seed expansion | c++ | igraph, boost | build success 2010-LinkComm | link partition | python| optparse | python okay 2010-iLCD | seed expansion | java | args4j, trove4j | build success 2010-CONGA | dynamics | java | | build success 2010-TopGC | statistical inference | java | | build success 2011-GCE | seed expansion | c++ | boost | build success 2011-OSLOM | seed expansion | c++ | | 2011-MOSES | fuzzy detection | c++ | boost | build success 2011-SLPA | dynamics | c++, java, python | networkx, numpy | build success for java 2012-FastCPM | clique percolation | python, c++ | networkx | build success 2012-ParCPM | clique percolation | c | igraph | build success 2012-DEMON | seed expansion | python | networkx | python okay 2013-SVINET | statistical inference | c++ | gsl, pthread | build success 2013-SeedExpansion | page-rank | c++, matlab | graclus, matlab-bgl | 2014-HRGrow | matrix-exponential | c++, matlab, python | pylibbvg | python okay 2015-LEMON | seed expansion | python | pulp | python okay

Presentation Files

survey-presentation-slides-yche.pdf is available.

Some files for my survey presentation is in Presentation, including algorithm visualization scripts, graph serialization related scripts and social network visualization scripts and corresponding figures.

Submodules(Dependencies)

Detailed information is in SubModules.

Submodule | Implementation Language | Detail --- | --- | --- igraph | c | also provide python wrapper, graph utilities matlab-bgl | c++, matlab | matlab implementation with bgl dependency graclus | c++ | graph partition algorithm lcelib | c++ | graph utilities by CxAalto

Scripts

Some file processing utility python scripts are put in Scripts.

Attention

These codes are all research codes, which I found through the internet. Please do not use them in production environment.