利用spark进行层次社团发现(louvain算法测试)

社团是复杂网络科学中一种重要的拓扑结构，也是物以类聚，人以群分自然现象在网络中的一种反映。因此对复杂网络进行社团发现是SNA(社会网络分析)中重要的内容之一。

现在的社团发现算法层出不穷，有非常多非常优秀有社团发现算法。其中louvain的快速社团发现算法是一种高效的层次社团发现算法。按照其主页上的原理英文就是：

“First, it looks for "small" communities by optimizingmodularity in a local way. Second, it aggregates nodes of the same communityand builds a new network whose nodes are the communities. These steps arerepeated iteratively until a maximum of modularity is attained.”

从字面意思中，主要包括两个步骤：

·     1st Pass: 包含步骤1至3，用于设定各节点的归属社区，直到不再发生变化

·     2nd Pass: 由步骤4组成，用于构建新图，并重新执行1stPass的操作，直到Modularity值不再增加

根据这个思路，网上找了相关的资料，进行算法在spark环境的测试，效果还是不错的。

如针对空手道网络，得到了三层的层次结构，最终得到四个社团，具体结果如下所示：

第一层效果如下所示：

(2,{社团编号:2,社团模块度增益:33,内部权重:0,节点权重:9}) (13,{社团编号:4,社团模块度增益:29,内部权重:0,节点权重:2}) (19,{社团编号:23,社团模块度增益:43,内部权重:0,节点权重:2}) (34,{社团编号:23,社团模块度增益:43,内部权重:0,节点权重:17}) (15,{社团编号:23,社团模块度增益:43,内部权重:0,节点权重:2}) (4,{社团编号:4,社团模块度增益:29,内部权重:0,节点权重:6}) (21,{社团编号:23,社团模块度增益:43,内部权重:0,节点权重:2}) (16,{社团编号:23,社团模块度增益:43,内部权重:0,节点权重:2}) (22,{社团编号:2,社团模块度增益:33,内部权重:0,节点权重:2}) (28,{社团编号:25,社团模块度增益:21,内部权重:0,节点权重:4}) (29,{社团编号:29,社团模块度增益:3,内部权重:0,节点权重:3}) (25,{社团编号:25,社团模块度增益:21,内部权重:0,节点权重:3}) (11,{社团编号:5,社团模块度增益:6,内部权重:0,节点权重:3}) (14,{社团编号:4,社团模块度增益:29,内部权重:0,节点权重:5}) (32,{社团编号:25,社团模块度增益:21,内部权重:0,节点权重:6}) (30,{社团编号:27,社团模块度增益:6,内部权重:0,节点权重:4}) (24,{社团编号:25,社团模块度增益:21,内部权重:0,节点权重:5}) (27,{社团编号:27,社团模块度增益:6,内部权重:0,节点权重:2}) (33,{社团编号:23,社团模块度增益:43,内部权重:0,节点权重:12}) (23,{社团编号:23,社团模块度增益:43,内部权重:0,节点权重:2}) (1,{社团编号:2,社团模块度增益:33,内部权重:0,节点权重:16}) (6,{社团编号:7,社团模块度增益:10,内部权重:0,节点权重:4}) (17,{社团编号:7,社团模块度增益:10,内部权重:0,节点权重:2}) (3,{社团编号:4,社团模块度增益:29,内部权重:0,节点权重:10}) (7,{社团编号:7,社团模块度增益:10,内部权重:0,节点权重:4}) (9,{社团编号:9,社团模块度增益:5,内部权重:0,节点权重:5}) (8,{社团编号:4,社团模块度增益:29,内部权重:0,节点权重:4}) (12,{社团编号:2,社团模块度增益:33,内部权重:0,节点权重:1}) (18,{社团编号:2,社团模块度增益:33,内部权重:0,节点权重:2}) (20,{社团编号:2,社团模块度增益:33,内部权重:0,节点权重:3}) (26,{社团编号:25,社团模块度增益:21,内部权重:0,节点权重:3}) (10,{社团编号:4,社团模块度增益:29,内部权重:0,节点权重:2}) (31,{社团编号:23,社团模块度增益:43,内部权重:0,节点权重:4}) (5,{社团编号:5,社团模块度增益:6,内部权重:0,节点权重:3})

第二层效果如下：

(4,{社团编号:2,社团模块度增益:62,内部权重:14,节点权重:15}) (25,{社团编号:25,社团模块度增益:24,内部权重:12,节点权重:9}) (29,{社团编号:25,社团模块度增益:24,内部权重:0,节点权重:3}) (27,{社团编号:9,社团模块度增益:54,内部权重:2,节点权重:4}) (23,{社团编号:9,社团模块度增益:54,内部权重:26,节点权重:17}) (7,{社团编号:5,社团模块度增益:16,内部权重:6,节点权重:4}) (9,{社团编号:9,社团模块度增益:54,内部权重:0,节点权重:5}) (5,{社团编号:5,社团模块度增益:16,内部权重:2,节点权重:4}) (2,{社团编号:2,社团模块度增益:62,内部权重:16,节点权重:17})

第三层效果如下：

(25,{社团编号:25,社团模块度增益:24,内部权重:14,节点权重:10}) (9,{社团编号:9,社团模块度增益:54,内部权重:40,节点权重:14}) (5,{社团编号:5,社团模块度增益:16,内部权重:12,节点权重:4}) (2,{社团编号:2,社团模块度增益:62,内部权重:48,节点权重:14})

针对wiki-vote网络(SNAP的大规模网络数据集：https://snap.stanford.edu/data/wiki-Vote.html，7115个节点，10万多条边)，仅花了一分钟就实现了5个层次28个社团的划分，速度非常快。其最终结果如下：

(7494,{社团编号:7494,社团模块度增益:2,内部权重:2,节点权重:0}) (3244,{社团编号:3244,社团模块度增益:2,内部权重:2,节点权重:0}) (5766,{社团编号:5766,社团模块度增益:2,内部权重:2,节点权重:0}) (6266,{社团编号:6266,社团模块度增益:2,内部权重:2,节点权重:0}) (8075,{社团编号:8075,社团模块度增益:4,内部权重:4,节点权重:0}) (5596,{社团编号:5596,社团模块度增益:55643,内部权重:40678,节点权重:14965}) (7032,{社团编号:7032,社团模块度增益:4,内部权重:4,节点权重:0}) (7190,{社团编号:7190,社团模块度增益:2,内部权重:2,节点权重:0}) (28,{社团编号:28,社团模块度增益:58937,内部权重:44186,节点权重:14751}) (6089,{社团编号:6089,社团模块度增益:2,内部权重:2,节点权重:0}) (6100,{社团编号:6100,社团模块度增益:2,内部权重:2,节点权重:0}) (6258,{社团编号:6258,社团模块度增益:2,内部权重:2,节点权重:0}) (7466,{社团编号:7466,社团模块度增益:4,内部权重:4,节点权重:0}) (2304,{社团编号:2304,社团模块度增益:2,内部权重:2,节点权重:0}) (8014,{社团编号:8014,社团模块度增益:2,内部权重:2,节点权重:0}) (7981,{社团编号:7981,社团模块度增益:2,内部权重:2,节点权重:0}) (2932,{社团编号:2932,社团模块度增益:60332,内部权重:36672,节点权重:23660}) (5678,{社团编号:5678,社团模块度增益:2,内部权重:2,节点权重:0}) (5970,{社团编号:5970,社团模块度增益:2,内部权重:2,节点权重:0}) (5413,{社团编号:5413,社团模块度增益:2,内部权重:2,节点权重:0}) (4167,{社团编号:4167,社团模块度增益:2,内部权重:2,节点权重:0}) (975,{社团编号:975,社团模块度增益:32406,内部权重:15458,节点权重:16948}) (7194,{社团编号:7194,社团模块度增益:2,内部权重:2,节点权重:0}) (3194,{社团编号:3194,社团模块度增益:2,内部权重:2,节点权重:0}) (2134,{社团编号:2134,社团模块度增益:8,内部权重:4,节点权重:4}) (7972,{社团编号:7972,社团模块度增益:2,内部权重:2,节点权重:0}) (6002,{社团编号:6002,社团模块度增益:2,内部权重:2,节点权重:0}) (4540,{社团编号:4540,社团模块度增益:2,内部权重:2,节点权重:0})