lizhen0909/communitydetectioncodes

Some overlapping community detection algorithms (Until 2016). by Yulin Che (https://github.com/CheYulin) for the PhD qualification exam (survey on community detection algorithms)

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.