/CommunityDetectionCodes

some overlapping community detection algorithms. Major contents are survey, algorithms' implementations, submodules, graph dataset benchmarks, evaluation metrics, scripts, some visualizations in Presentation folder.

Primary LanguageC++GNU General Public License v2.0GPL-2.0

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)

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.