前言
这学期开始看社团检测的东西，了解了一些经典算法。比如GN算法，BGLL算法(又叫Louvain，
因为该算法是作者在Louvain大学时提出的)，LPA算法，等等。
我先看的LPA（毕竟算法思想最简单,hhh，怪我太笨了），又看了Louvain。
Louvain算法的代码，作者在文章里给了网址，是C++写的，我下到本地运行并认真研究了一下，写的真挺好的。
然后昨天突发奇想，干脆自己仿照Louvain的代码风格，用C++把LPA实现一下，
因为在网上只看到过Python和Java实现的LPA算法，还没见过C++实现的。
然后昨天把框架写好，今天把细节补全，最后又从Louvain的代码里搬来了模块度的计算部分。
最后调试好，就OK啦。
1.LPA基本思想
给每一个节点添加标签，初始时可以以各自的nodeid作为标签，标签传播过程中将一个节点的邻居节点的标签中
数量最多的标签作为该节点的标签。标签即代表所属社区。
- 1 初始时，给每个节点一个标签，通常以其id作为初始标签。
- 2 每个节点使用其邻居节点的标签中数量最多的标签更新自身标签。
- 3 反复执行步骤2，直到满足终止条件。(至于终止条件是什么，这个可以自己设置,
比如我就直接设定迭代5次结束，也可以根据每次迭代模块度的增加程度来设定，
网上有说直到每个节点的标签不再变化为止，其实这比较难判定，
而且据研究，大部分网络经过5次迭代，其95%的节点标签都不再变化，
后面每次迭代虽部分标签还在变化，但相比来说性价比不高了)
LPA算法的优点是收敛周期很短，而且不需要任何先验知识。时间复杂度接近线性：对节点分配标签为O(n)，
每次迭代需要遍历所有的边两次，也就是O(2m)，所以时间复杂度为O(n+2m)，其中n为节点数，m为边数。
同步更新和异步更新还没搞懂，回头看看再说。
缺点
- 1 由于迭代过程中可能会出现随机选择的情况，所以LPA算法具有不稳定性，也就是同一个网络每次执行的结果可能都不一样。
- 2 可能出现巨型社区。
算法改进思路
- 目前还没
2.数据集
dolphins
3.代码
代码都在我的github上, 下面仅列出main函数代码.
#include "lpa.h"
using namespace std;
void display_time(const char *str){
time_t rawtime;
time ( &rawtime );
cerr << str << " : " << ctime (&rawtime);
}
int main(int argc, char **argv){
srand(time(NULL));
//parse_args(argc, argv);
if(argc != 2){
cerr << "argc not 2" << endl;
}
string filename = argv[1];
cout << "filename = " << filename << endl;
time_t time_begin, time_end;
time(&time_begin);
display_time("start");
//sleep(3);
LPA lpa(filename);
cout << "初始模块度 = " << lpa.modularity() << endl;
for(int i = 0; i < 5; i++){
lpa.labeled();
lpa.display();
}
display_time("end");
time(&time_end);
return 0;
}
4.运行结果
