社团是复杂网络科学中一种重要的拓扑结构,也是物以类聚,人以群分自然现象在网络中的一种反映。因此对复杂网络进行社团发现是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})