deric / fast-community

A graph clustering algorithm

FastCommunity Clustering Algorithm

Slightly modified version of fastmodularity that works on Linux.

Usage

This program is rather complicated and requires a specific kind of input, so some notes on how to use it are in order. Mainly, the program requires a specific structure input file (.pairs) that has the following characteristics:

1. pairs is a list of tab-delimited pairs of numeric indices, e.g.,

		54\t91\n

2. the network described is a SINGLE COMPONENT
3. there are NO SELF-LOOPS or MULTI-EDGES in the file; you can use the 'netstats' utility to extract the giantcomponent (-gcomp.pairs) and then use that file as input to this program
4. the MINIMUM NODE ID = 0 in the input file; the maximum can be anything (the program will infer it from the input file)

Description of command line arguments:

• -f <filename> give the target .pairs file to be processed
• -l <text>the text label for this run; used to build output filenames
• -t <int> timer period for reporting progress of file input to screen
• -s calculate and record the support of the dQ matrix
• -v --v ---v differing levels of screen output verbosity
• -o <directory> directory for file output
• -c <int> record the agglomerated network at step <int>

Algorithm

See http://www.arxiv.org/abs/cond-mat/0408187 for more information

• read network structure from data file (see below for constraints)
• builds dQ, H and a data structures
• runs new fast community structure inference algorithm
• records Q(t) function to file
• (optional) records community structure (at t==cutstep)
• (optional) records the list of members in each community (at t==cutstep)

Compiling

On Debian install:

$ sudo apt-get install build-essential

And compile using make:

$ make

License

GNU GPLv2

Authors

• Aaron Clauset ([email protected])

Collaborators

• Dr. Cris Moore ([email protected])
• Dr. Mark Newman ([email protected])

fast-community's Issues

Conflict with C++ 11

I try to build this repo on my ubuntu 18.04. After run make, I get errors, like:

g++     -O3 -fomit-frame-pointer -funroll-loops -fforce-addr -fexpensive-optimizations -o fastcommunity fastcommunity_mh.cc 
In file included from fastcommunity_mh.cc:82:0:
maxheap.h:54:16: error: reference to ‘tuple’ is ambiguous
 struct hnode { tuple     *d; };
                ^~~~~
maxheap.h:32:8: note: candidates are: struct tuple
 struct tuple {
        ^~~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/nested_exception.h:40,
                 from /usr/include/c++/7/exception:143,
                 from /usr/include/c++/7/ios:39,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from fastcommunity_mh.cc:74:

After seeing and searching, I think that tuple are conflict with tuple in c++ 11, So I change the GCCFLAGS in makefile, add -std=gnu++98 and it work again.

#CCFLAGS = -O3 -fomit-frame-pointer -funroll-loops -fforce-mem -fforce-addr -fexpensive-optimizations
CCFLAGS = -std=gnu++98 -O3 -fomit-frame-pointer -funroll-loops -fforce-addr -fexpensive-optimizations

So I you can change the makefile for this reason.

By the way, I want to use community detection alg to deal with candidate microservice identification from legacy system.
After about 15 years, you think i can use which kind of community detection alg to deal with my problem, which better have code like this one and work on weight graph, directed graph is better. Because I am confused in so many clustering algorithms, look forward your reply.