Page 170 - 《软件学报》2020年第11期

3486 Journal of Software 软件学报 Vol.31, No.11, November 2020

R(1,4)=0.333,R(3,4)=0.333,均大于阈值 q,选择隶属度最大的节点 2 加入到 D 中,即 D={1,3,2}.以此类推,可将节
点 4 加入到 D 中,即 D={1,3,2,4}.然后计算社区 D 与其邻居节点的模糊关系隶属度 R(4,5)=0.25,R(4,6)=0.25,由
于没有大于阈值 q 的邻居节点,因此算法结束,返回 D={1,2,3,4}作为寻找到的局部社区.该结果与真实社区结果
相同.
3 5
8
4
1 9
7
2 6
Fig.2 Small social network with 9 nodes and 14 edges
图 2 一个具有 9 个节点和 14 条边的小型社会网络

3 实验与结果

3.1 相关算法及评价指标
为了测试本文算法的有效性,与以下 4 种算法进行了比较分析.
(1) Clauset 算法 [16] 是第一个局部社区发现算法,通过最大化社区模块度 R 构建局部社区.
(2) LWP 算法 [17] 是一种著名的局部社区发现算法,通过优化社区模块度 M 寻找具有最大社区模块度的子
图,从而发现一个节点所属的社区.
(3) GMAC 算法 [19] 是马连航等人提出的一种利用 d 层邻居节点采用相似度方法寻找与查询节点相似度
最大的节点集合.对于参数 d 设置为作者推荐的 3.
(4) FlowPro 算法 [22] 是一种基于流传播的局部社区发现算法,起始节点发射一定数量的流在网络中传播,
根据与起始节点在同一个社区中的节点获得的流多于社区外节点的原则确立起始节点所在的局部
社区.
我们使用查准率 Precision、查全率 Recall、查准率和查全率的调和均值 F-score [19] 来衡量局部社区发现算
法的有效性.对于节点 v,假设节点 v 所在的真实社区的节点集合为 C i ;从节点 v 出发,局部社区发现算法找到的
社区中的节点集合为 D,那么,
| D ∩ C |
Precision = i (2)
| D |
| D ∩ C |
Recall = i (3)
| C i |
×
Precision Recall
-
Fscore =× (4)
2
Precision + Recall
单一的查准率 Precision 或查全率 Recall 指标取值高低,反映不了算法有效性的高低.在很多场景下,随着
Precision 的降低,Recall 指标会升高;反之,随着 Precision 的升高,Recall 指标也会降低.因此,我们采用综合了这
两个指标的调和均值 F-score 来衡量算法有效性的高低.
3.2 仿真网络数据集实验
首先,在 LFR 基准网络上测试本文算法的有效性.LFR 基准网络是由 Lancichinetti [24] 提出,被广泛应用于社
区发现算法测试中 [18−20] .LFR 基准网络节点度和社区规模均服从幂率分布,更接近于现实世界的真实网络.LFR
网络生成程序的常用参数见表 1.
本次实验中,参数设置为:n=5000,k=10,k max =50,mu 取值为 0.1,0.15,...,0.5 共计 10 个值,相邻的两个取值之间
间隔 0.05,其他参数使用默认值.混合参数 mu 为每个节点与社区外节点链接数目占该节点度的比例,例如,
mu=0.1 表示社区中节点出发的边 90%在社区内部,10%连接社区外的节点.所以,随着 mu 值的增大,每个社区内