参数自适应重叠社群发现算法之ASLPAw

社群发现也叫社区发现，是用来发掘分离出网络中子网内聚较高关系密切的一组组子网结构。

原始SLPA有个阈值“r”设定过滤掉频次低的社群标签，默认处理是用从0.01到0.5间十种“r”分别筛选一次，然后人工检视十种结果，人工选一个觉得合适的结果。

既麻烦不自动化，还又太主观。

在此用自动化的iForest（孤立森林）算法去除离群的低频标签，代替了人为阈值过滤方式。iForest属于Non-parametric和unsupervised的方法，即不用定义数学模型也不需要有标记的训练。

SLPA中有个对节点顺序洗牌的步骤，实际实现都用了伪随机函数。而伪随机函数是有周期的。节点数很多时，节点排列数会大于伪随机函数周期。为了洗牌完全性，所以节点规模越大，一轮洗牌需要的次数也越大。洗牌的恰当次数通过节点数代入Stirling公式算出。

我用Py来写个ASLPAw易于理解的参考实现。全面支持用于无权重/有权重、无向/有向及多重图结构数据。没有做效率优化，但健壮性有保证。作为基础的NetworkX包效率本就不高，也是不适宜大型网络上应用。下一版将扩展支持多种高效包，如SNAP、graph-tool、igraph。

源码放在GitHub上，GitHub - fsssosei/ASLPAw: Adaptive overlapping community discovery algorithm package in python.

欢迎一起写。

已经发布到了PyPI上，可以很方便的安装分发：

pip install ASLPAw

ASLPAw包是很易用的。

先在程序里导入：

from ASLPAw_package import ASLPAw

ASLPAw函数接受NetworkX图数据，计算后出各节点所属社群标签节点后以带权有向图格式返回

例如：

>>> ASLPAw(data_graph, seed=65535).adj

AdjacencyView({0: {1: {'weight': 30}}, 1: {6: {'weight': 15}, 1: {'weight': 14}}, 6: {6: {'weight': 31}}, 2: {1: {'weight': 30}}, 3: {1: {'weight': 29}}, 4: {1: {'weight': 30}}, 5: {1: {'weight': 30}}, 7: {6: {'weight': 30}}, 8: {6: {'weight': 29}}, 9: {6: {'weight': 29}}, 10: {6: {'weight': 25}}, 11: {6: {'weight': 28}}, 12: {15: {'weight': 19}}, 15: {15: {'weight': 24}}, 13: {15: {'weight': 22}}, 14: {15: {'weight': 22}}, 16: {15: {'weight': 19}}, 17: {15: {'weight': 19}}})

0: {1: {'weight': 30}}含义是，节点0所属的社群标签节点是1，权重30意思是0节点跟所属的社群标签间权重。其他节点格式含义相同。