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
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.