COMMUNITY DETECTION
VIA CONSTRAINED FRACTIONAL SET PROGRAMMING

by Thomas Bühler, Syama Sundar Rangapuram, Simon Setzer and Matthias Hein

Finding community structure in a network is an important problem with applications in social network analysis, bioinformatics, spam detection and many more. There are several ways how to define a community in a network. In [1], we presented an approach based on the constrained generalized maximum density subgraph problem. Here, given a set of seed vertices, one is interested in finding a densely connected subset containing the given seed set and satisfying a lower and upper bound on the size of the returned subset. As we have shown in the paper [1], there exists an equivalent continuous relaxation of this NP hard constrained fractional set program. Going over from the combinatorial problem to an unconstrained optimization problem on the Euclidean space now enables us to apply the method RatioDCA [2] to the resulting ratio problem. An implementation of the resulting algorithm can be downloaded from this webpage.

DOWNLOAD AND LICENSE

The CFSP algorithm for community detection has been developed by Thomas Bühler, Syama Sundar Rangapuram, Simon Setzer and Matthias Hein, Department of Computer Science, Saarland University, Germany. The code is published as free software under the terms of the GNU GPL v3.0. Please include a reference to the paper Constrained fractional set programs and their application in local clustering and community detection and include the original documentation and copyright notice.

Download cfsp_community_detection.zip       (Version: 1.0)

Unzip the file and check README for information on how to setup and run the code. If there is any problem, please contact Thomas Bühler.

REFERENCES

[1] T. Bühler, S. Rangapuram, S. Setzer and M. Hein,
Constrained fractional set programs and their application in local clustering and community detection
ICML 2013, 624-632. PDF  (Extended version: PDF )

[2] M. Hein and S. Setzer,
Beyond Spectral Clustering - Tight Relaxations of Balanced Graph Cuts,
In Advances in Neural Information Processing Systems 24 (NIPS 2011), 2366--2374, 2011. PDF  (Extended version: PDF )