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

刘井莲 等:一种基于模糊相似关系的局部社区发现方法 3485

输出:节点 v 所在的社区 D.
方法:
1) initialize D={v},N=Γ(v);
2) while (N!=NULL)
3) dic={⋅};
4) for any node a∈D
5) for any node b∈N
6) if R(a,b)≥q then
7) dic[(a,b)]=R(a,b);
8) End If
9) End For
10) End For
11) if (dic==NULL)
12) break;
13) else
14) find (x,y) such that R(x,y) is maximum;
15) D=D∪{y};
16) update N;
17) End If
18) End While
19) return D;
第 1 行初始化局部社区 D 和外壳节点集 N.第 2 行~第 18 行通过最大连通子图的方法寻找局部社区,其中,
第 3 行~第 10 行计算 D 中节点与 N 中节点形成边的节点对的隶属度,将隶属度大于等于 q 的边以及该边的隶
属度保存到字典类型变量 dic 中;第 11 行~第 17 行选择隶属度最大的边并入连通子图,并更新外壳节点集 N.第
19 行返回找到的局部社区 D.
2.3 时间复杂度分析
本文算法采用整型数据类型来表示网络 G 中的节点,每个节点被赋予一个唯一的整型序号来表示,采用关
于节点的哈希表来存储整个网络,每个节点关联了一个向量,向量中存储按照由小到大排序好的邻居节点集.假
定网络中节点度的平均值为 k,那么查找任一节点的邻居节点集的时间复杂度为 O(1).计算两个节点 a 和 b 的共
同邻居时,采用两个“指针”分别指向 Γ(a)和 Γ(b)遍历求交集的方法,该操作的时间复杂度为 O(2k).
由于局部社区发现是在网络中给定节点的周围区域计算,不是建立在整个网络结构的基础上,因此算法的
时间复杂度与所得到的社区的规模有直接关系,而不依赖于网络 G 中节点数|V|、边数|E|的大小.算法 1 中,最频
繁的操作是第 6 行,计算节点 a,b 的隶属度 R(a,b),该操作的时间复杂度为 O(2k).假定最后得到的社区中节点个
数为|D|,则算法在执行过程中需要计算|D|⋅k 条边的隶属度,即第 6 行在整个算法中重复的次数为|D|⋅k.因此,算法
2
的时间复杂度为 O(2k ⋅|D|).
2.4 实例分析

[3]
为了更加直观地理解本文提出的局部社区发现算法,采用了由 9 个节点和 14 条边组成的小型网络 ,来说
明本文算法的计算过程.网络连接情况如图 2 所示,真实社区划分{1,2,3,4}和{5,6,7,8,9}.
计算流程:设置阈值 q=0.3,节点 1 作为初始节点,首先将节点 1 加入到局部社区 D 中,即 D={1},节点 1 与其
邻居节点 2~节点 4 的模糊关系隶属度 R(1,2)=0.5,R(1,3)=0.667,R(1,4)=0.333,均大于阈值 q,选择隶属度最大的节
点 3 加入到 D 中,即 D={1,3}.计算 D 内节点与其邻居节点 2、节点 4 的模糊关系隶属度 R(1,2)=0.5,R(3,2)=0.5,