社团检测常用算法调用总结

yalewoo 最后修改于 2019-05-12 发表于 2017-05-12 5,740 views 7

社团检测社团检测

测试文件 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;

之后可以编译

使用方法：

无权图：

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

有权图：

1 2	./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）

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

使用：

1 2	./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但是运行会段错误，暂未调通。

使用方法

1	./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选项

1	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

1	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就可以编译了

使用方法

1	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 安装命令

1	sudo pip install networkx

运行命令

1	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

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

1 2	chmod +x CFinder/CFinder_commandline chmod +x CFinder/CFinder_commandline64

使用方法

1	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 8 5

6 8 5

7 8 5

5 7 8

6 8 5

文章《社团检测常用算法调用总结》共有7条评论：

罗永平

GCE的代码照着你的方法在windows改不成攻呢？可否给出改好的？
我修改到最后一步也就是①添加__MSVCRT_VERSION__（提示重定义了，然后我就把它删了）
②添加struct __stat64（提示重定义，然后我就把graph_loading.cpp中的mmapFile函数中的stat64改为_stati64、fstat64改为_fstati64），通过上面我改的之后，编译提示readEdge未定义，无论是我把它放到RangeOfEdges前还是RangeOfEdges里面都没法解决

2018年1月15日上午11:06 回复
- yalewoo 作者
  
  https://u3962903.ctfile.com/fs/3962903-234201795
  
  2018年1月15日下午2:16 回复
  - 罗永平
    
    谢谢，如果直接使用你编译好的执行文件执行是可以的，但是如果我再make的话还是会出错，部分错误信息如下：
    g++ -O3 -g3 -Wall -c -fmessage-length=0 -MMD -MP -MF”graph_loading.d” -MT”graph_loading.d” -o”graph_loading.o” “../graph_loading.cpp”
    ../graph_loading.cpp:11:0: warning: “__MSVCRT_VERSION__” redefined
    #define __MSVCRT_VERSION__ 0x0601
    
    In file included from d:\mingw\include\_mingw.h:66:0,
    from d:\mingw\include\errno.h:41,
    from d:\mingw\lib\gcc\mingw32\6.3.0\include\c++\cerrno:42,
    from ../graph_loading.cpp:1:
    d:\mingw\include\msvcrtver.h:68:0: note: this is the location of the previous definition
    # define __MSVCRT_VERSION__ __MSVCR60_DLL
    
    ../graph_loading.cpp:13:8: error: redefinition of ‘struct __stat64’
    struct __stat64
    ^~~~~~~~
    In file included from d:\mingw\include\wchar.h:212:0,
    from d:\mingw\lib\gcc\mingw32\6.3.0\include\c++\cwchar:44,
    from d:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\postypes.h:40,
    from d:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\char_traits.h:40,
    from d:\mingw\lib\gcc\mingw32\6.3.0\include\c++\string:40,
    from d:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bitset:47,
    from ../graph_loading.cpp:2:
    d:\mingw\include\sys/stat.h:195:8: error: previous definition of ‘struct __stat64’
    struct __stat64 __struct_stat_defined( __off64_t, __time64_t );
    不知道是否是因为我使用win10的原因，还是我自己的系统出了问题。
    
    2018年1月15日下午2:36 回复
    - yalewoo 作者
      
      可能是MinGW版本不一致，我的貌似是4.9.2，可能新的版本里__stat64已经有了所以会提示重定义
      
      2018年1月15日下午4:00 回复
      - 罗永平
        
        有可能就是新版MinGW的问题，我在win7里面试过了也是提示一样的错误，谢谢你！
        
        2018年1月15日下午9:38
CTer

楼主给力

2017年8月8日下午4:51 回复
- yalewoo 作者
  
  哟罗胖
  
  2017年8月8日下午4:52 回复

雅乐网

计算机技术、学习成长