雅乐网

测试文件 graph.txt，内容为：

0	1
0	2
0	3
1	2
1	3
2	4
4	5
4	7
5	6
5	7
5	8
6	8
7	8
7	10
8	9
9	10
9	12
9	13
10	11
10	12
11	12
11	13
12	13

网络如下图所示：

Louvain Modularity

该方法paper: [0803.0476] Fast unfolding of communities in large networks

代码下载地址：louvain / Code / [f7ab0f]

该算法的结果有随机性

Linux编译

使用make编译，这个版本会提示main_community.cpp:125:27: error: ‘getpid’ was not declared in this scope srand(time(NULL)+getpid());

只要在前面加上头文件#include <unistd.h> 就可以了。

MinGW编译

需要修改的地方：

1. graph_binary.cpp 中第30行的 #include <sys/mman.h> 注释掉。

2. main_community.cpp 的第29行添加#include <ctime>

3. 由于代码中默认long类型是8字节大小，而我的windows中long大小是4字节，导致出错。需修改的地方：

graph.cpp文件 142行 long tot=0; 改为 long long tot=0;

graph.cpp文件 144行 tot+=(long)links[i].size(); 改为 tot+=(long long)links[i].size();

graph_binary.cpp 第57行 改为finput.read((char *)(&links[0]), (long)nb_links*4);

graph_binary.cpp 第161 162行改为 foutput.write((char *)(&degrees[0]),8*nb_nodes); foutput.write((char *)(&links[0]),4*nb_links);

修改graph_binary.h文件 约55行   vector<unsigned long> degrees; 改为 vector<unsigned long long> degrees;

之后可以编译

使用方法：

无权图：

./convert -i graph.txt -o graph.bin
./community graph.bin -l -1 -v > graph.tree

有权图：

./convert -i graph.txt -o graph.bin -w graph.weights
./community graph.bin -l -1 -w graph.weights > graph.tree

结果如下：

0 0
1 0
2 0
3 0
4 1
5 1
6 1
7 1
8 1
9 2
10 2
11 2
12 2
13 2
0 0
1 1
2 2

这个算法的结果有层次结构的，第一个0到13行 是叶子层，后面还有的话就是更高的level

Link Communities

bagrow/linkcomm: Programs to identify link communities in complex networks

对于相同的图，该算法的结果是固定的。

cpp版本：

编译（Linux，MinGW）

g++ -O5 -o calcJaccards calcAndWrite_Jaccards.cpp
g++ -O5 -o clusterJaccards clusterJaccsFile.cpp

使用：

./calcJaccards net.pairs net.jaccs
./clusterJaccards net.pairs net.jaccs net.clusters net.mc_nc THRESHOLD

THRESHOLD是一个小数（例如0.2）

输出net.clusters文件：

0,1 0,2 0,3 1,2 1,3 
2,4 
4,5 4,7 5,6 5,7 5,8 6,8 7,8 7,10 8,9 9,10 9,12 9,13 10,11 10,12 11,12 11,13 12,13

OSLOM

网址：OSLOM

Linux编译

下载代码后，执行目录中的 compile_all.sh 进行编译。

编译后，会生成可执行文件oslom_dir和oslom_undir，分别适用于有向图和无向图

MinGW编译

编译出exe但是运行会段错误，暂未调通。

使用方法

./oslom_undir -f graph.txt -uw

-f 指定图文件， -uw表示不带权，-w表示带权

会在当前目录生成结果文件夹：graph.txt_oslo_files，其中 tp ,tp1, tp2…就是社团文件。oslom的社团检测是分层级的，tp是最顶层社团，tp1是下面一层…

运行结果：

#module 0 size: 4 bs: 0.0932256
0 1 2 3 
#module 1 size: 10 bs: 0.0578294
4 5 6 7 8 9 10 11 12 13

Infomap

mapequation.org – code

linux下，执行make进行编译。

MinGW中编译

没有安装OMP的情况下使用make noomp编译 。

若报错undefined reference to `_Unwind_Resume’，修改makefile，在第17行加入 CXXFLAGS += -Wl,-Bdynamic -lgcc_s

使用方法

Infomap中结点的起始编号默认从1开始，如果有0结点，要使用-z选项

Infomap/Infomap graph.txt . -z -i link-list --clu

输出文件graph.clu

# 'graph.txt . -z -i link-list --clu' -> 14 nodes partitioned in 0s from codelength 3.772924456 in one level to codelength 2.986246713 in 2 levels.
# node cluster flow:
9 1 0.0869565
10 1 0.0869565
12 1 0.0869565
11 1 0.0652174
13 1 0.0652174
5 2 0.0869565
7 2 0.0869565
8 2 0.0869565
4 2 0.0652174
6 2 0.0434783
0 3 0.0652174
1 3 0.0652174
2 3 0.0652174
3 3 0.0434783

Greedy Clique Expansion（GCE）

代码下载地址：GCE

linux编译

linux上代码直接编译会有错误，对 graph_loading 文件作如下修改：

1. 注释掉语句 close(graphFD);

2. 把整个 const char *readEdge(const char *cur, int &l, int &r) 函数 移动到文件前面namespace graph_loading { 后，（14行）

3. 找到 struct readEdgeInvalidLineInDataException : public exception { }; 这一行，把它移动到文件前面namespace graph_loading { 后，（14行）

windows上编译

需要sys/mman.h 可以在这里下载witwall/mman-win32: mman library for Windows. 

把mman.h放到GCECommunityFinder目录，修改graph_loading.cpp中的 #include <sys/mman.h> 改为 #include “mman.h”

g++ -c mman.cpp可以生成一个mman.o文件

把mman.o文件放到GCECommunityFinder\build目录，修改makefile，在第9行后面加入 ./mman.o

g++  -o "GCECommunityFinder"  ./Community_Finder.o ./Seed.o ./aaron_utils.o ./cliques.o ./find_communities.o ./graph_loading.o ./graph_representation.o ./mman.o

编译时提示mkdir函数没有声明，在cliques.cpp第2行加入

#include <io.h>

编译时提示

../graph_loading.cpp:340:17: error: aggregate 'graph_loading::mmapFile(const char*)::stat64 buf' has incomplete type and cannot be defined
   struct stat64 buf;
                 ^
../graph_loading.cpp:341:24: error: 'fstat64' was not declared in this scope
   fstat64(graphFD, &buf) == 0 || Die("fstat64 failed");

在#include <sys/stat.h>这一行上面加入下面的代码

#if __MINGW32__
#define __MSVCRT_VERSION__ 0x0601
#endif
struct __stat64
{
    _dev_t st_dev;
    _ino_t st_ino;
    _mode_t st_mode;
    short st_nlink;
    short st_uid;
    short st_gid;
    _dev_t st_rdev;
    __int64 st_size;
    __time64_t st_atime;
    __time64_t st_mtime;
    __time64_t st_ctime;
};

进入build文件执行make就可以编译了

使用方法

GCECommunityFinder/build/GCECommunityFinder graph.txt 3 0.6 1.0 0.75 2> LC_output.txt  | tee GCE.gen

注意2>是一个整体 2不是参数

GCE.gen

0 1 3 2 
4 5 7 8 6 
9 12 13 11 10 

DEMON

Democratic Estimate of the Modular Organization of a Network

网址：Michele Coscia | DEMON

需要安装networkx 安装命令

sudo pip install networkx

运行命令

python demon_py/launch.py graph.txt

产生文件communities，内容为

0	4,5,6,7,8
1	9,10,11,12,13
2	0,1,2,3

CFinder

网址：[CFinder] Clusters and Communities: Overlapping dense groups in networks

下载后直接提供了可执行文件 ，使用下面的命令给予运行权限

chmod +x CFinder/CFinder_commandline
chmod +x CFinder/CFinder_commandline64

使用方法

CFinder/CFinder_commandline64  -i graph.txt -l CFinder/licence.txt -o CFinderOutput

-o后面是输出目录，这个目录必须之前不存在

输出文件在 指定的目录中的k=3中的communities文件

# The communities at k=3
# from /home/yalewoo/CommunityDetectionAlgorithm/graph.txt
# at no lower link weight threshold,
# and at no upper link weight threshold.
# Links were treated as undirected.
# No time limit was set for the clique search.

0: 0 1 2 3 
1: 4 5 7 6 8 
2: 10 11 12 13 9 

BigClam

代码下载地址：snap/examples/bigclam at master · snap-stanford/snap

下载时需要下载整个snap的代码：snap-stanford/snap: Stanford Network Analysis Platform (SNAP) is a general purpose network analysis and graph mining library.

Linux编译

使用 make all 编译整个 snap

MinGw编译

未成功。

使用方法

snap-master/examples/bigclam/bigclam -i:graph.txt

结果在当前目录生成的 cmtyvv.txt 文件中：

13	12	9	
13	11	12	
3	0	1	
2	0	1	
9	13	12	
13	11	12	
6	5	8	
13	11	12	
2	1	0	
5	7	4	
1	3	0	
0	3	1	
5	7	8	
6	8	5	
7	5	8	
7	5	8	
7	8	5	
6	8	5	
7	8	5	
5	7	8	
6	8	5	
6	8	5