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

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

2 基于模糊相似关系的局部社区发现算法

2.1 预备定义
本小节先给出网络、模糊关系 R 等定义,然后给出模糊相似关系视角下的局部社区发现问题的定义.
定义 1(网络 [18] ). 用图 G=(V,E)来表示网络,其中,V 是节点集合,E 是边集合,|V|表示节点集合 V 中节点的个
数.对于节点 v(v∈V),Γ(v)表示节点 v 的邻居节点的集合.
(x,y)∈E,表示节点 x 和 y 之间存在边;(x,y)∉E,表示节点 x 和 y 之间没有边.x 和 y 之间是否有边相连,这是明
确的,可以用“1”或者“0”来刻画.在边的基础上,我们定义一个关系 R,用来表示一条边的两个节点的相似关系.显
然,两个节点的相似关系,用“1”或者“0”来刻画是不合适的.为此,我们引入模糊关系,用节点间的相似度作为隶
属函数来刻画两个节点的相似关系.
定义 2(模糊关系 R). 设 R 是 V 上的模糊关系,对于任意的节点对(x,y)∈(V×V),隶属度 R(x,y)定义为
( ) |
Γ
⎧ |( ) x ∩ Γ y
x
⎪ ⎪ min(| ( ) |,| ( ) |) ,( , ) y ∈ E
Γ y
Γ x
Rx (1)
(, ) y = ⎨
x
⎪ 0, ( , ) y ∉ E
⎪ ⎩ 1, x = y
采用度小的节点的邻居节点集嵌入在度大的节点的邻居节点集中的程度,作为两个节点在同一个社区的
隶属度 R(x,y).从公式(1)可得,R(x,x)=1,R(x,y)=R(y,x).即模糊关系 R 满足自反性、对称性,所以关系 R 是模糊相似
关系.
定义 3(节点关于模糊相似关系 R 的 q 水平的相似类 [23] ). 节点集合 V 上的模糊相似关系 R,对任意节点 a∈V,
集合[a] Rq ={x|x∈V,R(a,x)≥q},称为元素 a 关于模糊关系 R 的 q 水平的相似类.
设 B 1 ,B 2 是节点集合 V 上的模糊相似关系 R 上的 q 水平上的 2 个相似类,若 B 1 ∩B 2 ≠∅,则称它们是相似类.
将所有与[a] Rq 相似的类合并成一类,就是包含节点 a 的等价类.
基于以上定义,可以得出模糊相似关系视角下的局部社区发现问题可以定义为:设 R 是 V 上的模糊关系,a
是 V 中的任意一个节点,给定阈值 q,a 所在的社区可以看作是节点 a 关于关系 R 的 q 水平上的等价类.从图论的
角度,节点 a 所在的社区可以看作是包含节点 a,由隶属度大于等于 q 的边构成的最大连通子图.
2.2 算法描述
传统的模糊聚类算法需要知道网络的全局结构,通过构造模糊相似矩阵,得到网络节点的一个划分,计算量
大.而在局部社区发现中,我们的目标只是寻找给定节点所在的社区,而不需要得到网络中所有节点的一个划
分.因此,本文采用最大连通子图的方法来进行局部社区发现.将给定节点 v 加入到社区 D,在保证隶属度大于等
于 q 的前提下,选择与 D 内节点构成隶属度最大的节点加入到社区 D.重复该过程,直到 D 内节点与 D 外节点的
隶属度都小于 q 为止.此时所形成的连通子图即为从节点 v 出发由隶属度大于等于 q 的节点构成的最大连通子
图.我们将该最大连通子图看作给定节点 v 的局部社区.本算法的时间复杂度仅取决于所寻找社区的大小,而不
取决于整个网络的大小.
算法思路如下.
(1) 初始化:D={v},N=Γ(v).
(2) 在保证隶属度大于等于 q 的前提下,从 D 中节点出发,在 N 中寻找与 D 中节点相连且隶属度最大的节
点 y,将 y 加入到 D 中.
(3) 将 y 的邻居节点集中不在 D 中的节点加入到 N 中.
(4) 重复步骤(2)和步骤(3),直到 N 为空或 N 中节点与 D 中节点的隶属度都小于阈值 q 为止.
算法描述如算法 1 所示.
算法 1. 基于模糊相似关系的局部社区发现算法.
输入:网络 G=(V,E),初始节点 v,模糊关系 R,阈值 q.