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

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

1 相关工作

局部社区发现是复杂网络社区发现问题的子问题,得到的是单一节点所在的社区,而不是网络中的所有社
区,因此不要求知道网络的整个结构.一般定义为:对于网络 G=(V,E),V 为节点的集合,E 为边的集合,给定任一个
节点 v(v∈V),找出节点 v 在网络中所属的社区 D [15] .图 1 给出了一个网络的局部社区示意.

U
N
D

Fig.1 Division of a network into local community D (black nodes and green nodes),
D’s shell nodes set N (white nodes) and unknown nodes set U (grey nodes)
图 1 网络分为局部社区 D(黑色节点和绿色节点)、D 的外壳节点集合 N(白色节点)
以及未知节点集合 U(灰色节点)

针对图 1 所示的网络图,在局部社区发现过程中,网络 G 中的节点主要分为 3 部分:局部社区 D、外壳节点
集 N 和未知节点集 U.局部社区 D 中节点及其连接都是已知的,D 中节点可以分为核心节点集 C 和边界节点集
B,其中,C 中节点的邻居节点全都在 D 中,而 B 中节点至少有一个邻居节点不在 D 中.外壳节点集 N={y|y∉D,
(x,y)∈E,x∈D},通过寻找 D 中节点的邻居节点可以找出 N.未知节点集 U=G−D−N,在局部社区发现过程中,假设 U
中节点是未知的,即不利用 U 中节点及其连接等信息进行局部社区发现.
Clauset 首次提出局部社区发现问题,并定义了一个社区的局部模块度度量指标 R [16] .R 为边界节点集 B 内
节点分别与社区 D 和外壳节点集 N 形成边数的比值.计算 R 不需要使用网络的全局信息,该算法通过最大化社
区的局部模块度度量指标 R 选取邻近节点的原则构建局部社区.Luo 等人从子图的内度与外度的视角,定义了
另一个社区的局部模块度度量指标 M [17] ,M 为 D 内节点分别与 D 内节点和 N 内节点形成边数的比值.通过迭代
选择能使 M 增大的 N 内节点,或者删除能使 M 增大的 D 内的节点的原则,构建局部社区.
以上 R 和 M 这两个指标只考虑与局部社区 D 相关的边的数目,而忽略了不同边的两个节点之间的相似程
度是不一样的.Huang 等人首先提出了基于节点间相似度的局部社区发现算法 LTE [18] ,用社区 D 内形成边的节
点对之间的相似度之和与社区 D 内节点和外壳节点集 N 形成边的节点对之间的相似度之和的比值来度量社区
的质量,从 N 中选取与社区 D 内节点相似度最大的节点的原则构建局部社区.不同于 LTE 算法,只考虑节点自身
及其邻居来度量两个节点间的相似性,Ma 等人还考虑了不直接相连的 d 层邻居(d≥1),提出了基于 d 层邻居的
局部社区发现算法 GMAC [19] .Liu 等人采用节点向量模型来表示网络中的节点,在考虑两个节点的共同邻居的
同时,还将邻居节点与它们各自的相似度纳入计算,实现了一种新的局部社区发现算法 [20] .赵卫绩等人提出了一
种加权邻居节点的共同邻居相似度 CNWNN 指标,通过优先考虑与当前局部社区嵌入度最大的节点,逐步找到
给定节点所在的社区 [21] .此外,Panagiotakis 等人提出了基于流传播的局部社区发现算法 FlowPro [22] ,通过在起始
节点发射一定数量的流在网络中传播,流经的节点存储接收到流的 1/2,将另外 1/2 继续传播给自己的邻居节点,
最后,以每个节点保存的流的多少来度量与起始节点连接的紧密度,选取流多的节点作为起始节点所在的局部
社区.
基于社区质量度量优化类方法,都是基于判断一个节点是不是应该属于当前社区.与之不同的是,本文从关
系的视角定义社区,认为社区是具有一定强度的关系构成的.为此,本文采用模糊关系来描述两个节点之间的相
似关系,然后证明了该关系是一种模糊相似关系,将局部社区定义为给定节点关于该模糊相似关系 q 水平的等
价类,进而采用最大连通子图算法求得给定节点所在的局部社区.