定义多层社会网络G_m=(V, E, L), 其中V为节点集合, E是一个三元组〈x, y, l〉, 表示不同网络层的节点边集合,这里x, y∈V, l∈L, x≠y, L为层数集合,对于任何两个元组〈x, y, l〉∈E和〈x', y', l'〉∈E. 若x=x',y=y', 则l≠l'. 通过如上定义,〈x₁, x₂, l〉表示第l层中节点x₁与x₂的连边^[12].

在一个网络G=(V, E)中, 其中V为节点集合, E为节点间的边的集合, 若集合C={C₁, C₂, …, C_m}满足①C_iV; ② C_i, C_i≠; ③C_i, C_j,(C_i≠C_j)∧(C_i∩C_j≠); ④∪^m_i=1C_i=V, 则C就是网络G中的一个重叠社团集合^[13].

目前的多层或多维社会网络^{[3- 4,6]}中,重叠社团发现的一般步骤是先检测不同层或不同维度网络的重叠社团,再对检测结果进行融合,最终得到划分结果.

FAN等^[3]提出的基于局部社团的多层在线网络重叠社团发现算法(local community based community detection algorithm, LC-CDA)是一种较新的多层社会网络重叠社团发现算法.该算法步骤为

1)检测每层网络中的局部社团,对于网络中的每个节点,将其与邻居节点划分进局部社团c中, 对于c中的每个节点,计算其社团内和社团外节点连接数的差值,即

x_i=∑_{j∈c, j≠i}a_ij-∑_jca_ij(1)

其中,若节点i与节点j之间有连接,则a_ij=1.

2)求差值总和f=∑_i∈cx_i. 若f>0, 表明社团内的连边数大于社团和网络中其他节点的连边数; 否则,剔除c中差值最小的节点,直到f>0.

3)计算所有局部社团中两两的重叠系数(|c_i∩c_j|)/min{|c_i|, |c_j|}, 与阈值β(0<β<1)进行比较,若大于阈值则对两个局部社团进行合并,得到社团划分结果.

LC-CDA算法将根据数据集中喜好信息所划分的社团结果作为正确结果,并与算法所划分的社团结果进行比较,即通过式(2)计算两种结果的相似度对算法进行评价.

S=1/(2|C'|)∑_ci'∈C'max_cj∈C δ(c_i', c_j)+

1/(2|C|)∑_ci∈Cmax_cj'∈C' δ(c_i', c_j)(2)

其中, δ(c_i', c_j)为c_i'和社团c_j之间的Jaccard相似性,其计算式为

δ(c_i', c_j)=(|c_i'∩c_i|)/(|c_i'∪c_i|)(3)

S的取值范围是[0, 1]. S值越大,表示该算法所划分的社团与使用喜好信息划分的社团越接近,算法性能越好.

该算法中局部社团仅考虑了社团整体与外部的联系,未考虑社团内部节点间的拓扑属性,因此无法发现更多细粒度的小社团,且经本研究实验发现,LC-CDA用于小型多层社会网络时,很难有效地检测出多个重叠社团结构.为此,本研究提出一种基于弱派系的多层社会网络重叠社团发现算法.

在一个网络G=(V, E)中,其中V为节点集合, E为节点间的边集合,假设u和v是G中的两个相邻节点,则由节点u和v所决定的弱派系定义为

G_uv=(V_uv, E_uv)(4)

其中, V_uv={u,v}∪{N_u, N_v}, V_uv分别为节点u和v及其邻居节点构成的节点集合, N_u和N_v为节点u和v的邻居节点集合; E_uv={(x,y)∈E}|x, y∈V_uv}, E_uv为V_uv中节点间属于边集E中的连边所构成的边集合.节点u和v分别通过计算节点优先级与节点相似度得出.

在一个网络G=(V, E)中,其中, V为节点集合, E为节点间的边集合,假设u为G中的一个节点,则节点u的优先级定义为

P_u=(m_u+k)/(k+1)(5)

其中, m_u为节点u的所有邻居节点之间的边数; k为节点u的度.对于有向图,使用节点u的入度计算优先级P_u, 即

P_u=(m_u+k_in)/(k_in+1)(6)

其中, m_u为节点u的所有邻居节点之间的边数; k_in为节点u的入度.

式(5)与式(6)综合了仅考虑节点度的度中心性,与仅考虑邻居节点连接数量的局部聚类系数.两个公式同时利用了度与邻居节点间的连接数,有利于估计节点邻居间连接的紧密程度,优先级越大则表明节点邻居间的连接越紧密.

选择网络中优先级最大的节点作为构建弱派系中的一个节点,另一节点是与优先级最大节点的邻居节点中相似度最大的节点.

在一个网络G=(V, E)中,其中V为节点集合, E为节点间的边集合,假设u和v是G中的两个邻接节点,则这两个节点的相似度定义为

S_Nuv=(|N_u∩N_v|)/((|N_u||N_v| )^1/2)(7)

其中,N_u和N_v分别为节点u和节点v的邻居节点集; |N_u|和|N_v|分别为集合N_u和N_v中的元素数.本算法中计算节点相似度采用的是Slaton指标^[14],在基于共同邻居的相似性指标中,常用的还有Jaccard指标^[15]和Sorenson指标^[16]等.

在一个网络G=(V, E)中,其中, V为节点集合, E为节点间的边集合,假设C₁和C₂是G中的两个弱派系,则定义弱派系C₁和C₂间的相似度为

S_CC1C2=(|V(C₁)∩V(C₂)|)/(min(|V(C₁)|,|V(C₂)|))(8)

对于弱派系C₁和C₂, 有0≤S_CC1C2≤max(|V(C₁)|,|V(C₂)|). 对于一个网络中的弱派系设置相同的阈值β, 若两个弱派系的相似度大于阈值时则合并为一个社团,因此本算法也具有可调重叠社团相似性的特点.文献[10]提出的相似度计算考虑到了两者共同的节点与边,而本算法仅考虑共同的节点以便合并多个网络层的弱派系.

社团划分结果的评价指标一般有归一化互信息(normalized mutual information,NMI)^[17]指标与调整兰德系数(adjusted Rand index,ARI)^[18]指标等.由于大多数真实网络数据集无事先标记好的社团划分结果,因此无法使用这两种指标进行评价.对于未知结果的重叠社团评估,目前主要使用扩展模块化度Q_ov^[19], 即

Q_ov=1/(2m)∑^l_i=1∑_{v∈Ci, w∈Ci}1/(Q_vQ_w)(A_vw-(k_vk_w)/(2m))(9)

其中, A为网络的邻接矩阵; C_i为一个社团(1≤i≤l,l为社团个数); m为网络的边数; Q_v为节点v所属社团个数; k_v为节点v的度. Q_ov越大表明社团划分的效果越好.

式(9)并不适用于多层网络社团的划分,考虑到网络密度与连边数对社团发现的影响,将网络的边数比例作为网络权重,构建新的指标Q_mov, 用于评价多层社会网络重叠社团划分结果. Q_mov值越大表明社团划分结果越好.

定义多层网络重叠社团的评价指标Q_mov为

Q_mov=∑^N_i=1w_iQ_i(10)

其中, Q_i为第i层网络的扩展模块化度; w_i为第i层网络的权重,定义为

w_i=(E_i)/(∑^N_j=1E_j)(11)

其中, E_i为第i层网络的边数.

从式(11)可见,网络边数比例越大,即相对网络密度越大,则模块化度的权重越大.

算法的输入为多层社会网络G_ml和相似度阈值β, 输出为社团集合S, 具体步骤为:

1)初始化S, 设定阈值β, 输入多层网络数据,对每一层网络G执行步骤 2)至步骤 4),得到弱派系结果,然后执行步骤5).

2)初始化弱派系集合WC.

3)根据式(5)或式(6)计算当前网络G中所有节点的优先级, 并选取优先级最大的节点u, 根据式(7)计算节点u的邻居节点中与u相似度最大的节点v, 使用节点u与节点v根据式(4)构建弱派系wc并保存至WC.

4)将步骤 3)中弱派系wc的节点从G中移除,若G中节点非空则回到步骤3);

5)根据每一层的弱派系结果构建弱派系集合WClique,并将所有弱派系标记为未访问,对WClique中的所有弱派系执行步骤 6)至步骤8).

6)若所选的弱派系C₁未被访问,则执行步骤 7),否则选择下一个弱派系执行步骤 6)至步骤8);

7)将C₁标记为已访问,对与弱派系C₁有重合节点的弱派系集合N(C₁)中的弱派系执行步骤8).

8)计算弱派系C₁与邻居弱派系C₂的相似度,将C₂标记为已访问.若大于β则合并为一个社团,保存检测出的社团至社团集合S中,否则,不进行合并.

9)返回社团集合S.

本研究采用tailorshop、AUCS和FF-TW-YT三种真实的多层社会网络数据集进行仿真实验,如表1.其中,tailorshop数据集是由KAPFERER^[20]收集的服装厂内39名员工工作与朋友关系的双层网络数据; AUCS数据集是由ROSSI等^[21]收集的某大学61名雇员不同线上线下关系的网络数据,该数据集分为lunch、facebook、coauthor、leisure和work五层,均为无向无权网络; FF-TW-YT数据集是由MAGNANI等^[22]采集的500名用户在多个在线社交网站上的关系网络数据,每个用户都拥有多个不同社交网站的账号,并在每一层具有不同关系网.该数据集包含FriendFeed、Twitter和YouTube三层,且均为无权网络,其中FriendFeed与Twitter层为有向网络,YouTube层为无向网络.

表1 多层社会网络数据集
Table 1 Multi-layer social network data set

为评估WC-CDA的有效性,将其与LC-CDA比较.两种算法的执行顺序都是先检测单层网络的结果,然后根据β进行社团的合并,通过比较不同相似度下社团发现结果的属性与评价指标来进行评估.由于LC-CDA所用的评估方法只适用于已有结果的数据集,不具有通用性,因此,本研究在仿真过程中使用Q_mov指标对两种算法进行评价.

图1 Tailorshop数据集上的仿真结果
Fig.1 Result of simulation on Tailsorshop data set

图2 AUCS数据集上的仿真结果
Fig.2 Result of simulation on AUCS data set

图3是用于FF-TW-YT数据集的仿真结果.从图3(a)可见,WC-CDA在β≥0.5时可检测出大量社团,而LC-CDA所检测的社团数量缓慢增长,且从图1(b)可见,WC-CDA所检测的社团平均尺寸较小.由图3(c)可见,当0.1≤β<0.5时,WC-CDA的Q_mov优于LC-CDA; 当0.5≤β≤0.9时,LC-CDA的Q_mov优于WC-CDA.

图3 FF-TW-YT数据集上的仿真结果
Fig.3 Result of simulation on FF-TW-YT data set