0 概述

企业社会化网络(Enterprise Social Network, ESN)是企业个体间为适应市场需求, 通过交互合作而形成的关系体系。在ESN中, 企业节点基于关系特性产生聚集效应, 呈现出模块化的社区结构。社区发现有助于分析网络中企业团体的拓扑属性、模式以及功能特性, 挖掘隐藏的企业关系与合作规律并优化供应链需求, 对探究ESN的结构特征具有重要意义。

传统的社区发现算法按照网络节点内在拓扑结构的连接紧密程度, 将节点划分成若干互不相连的社区, 其典型代表有层次聚类算法^[1]、GA算法^[2]、基于信息论算法^[3]以及模块度优化算法^[4]。然而, 在现实网络中, 有些节点的隶属关系并不唯一, 其可能同时隶属于多个社区, 社区间存在明显的重叠与嵌套特征。因此, 挖掘重叠社区结构往往更有实际意义。近年来, 重叠社区发现引起了研究者的广泛关注, 一些代表性算法相继被提出, 这些算法主要分为3类:

第1类是基于局部信息的算法, 这类算法主要依靠节点或边的局部信息来扩展探测社区的重叠结构。其中代表性算法有OSLOM^[5]、LFM^[6]、GCE^[7]以及LLCM^[8]等。

第2类是基于标签传播的算法, 这类算法根据每个节点及其邻居节点的标签与隶属度, 更新划分每个节点的社区归属并进行重叠社区发现。其中代表性算法有BMLPA^[9]、LPPB^[10]以及FNCS-LPA^[11]等。

第3类是基于链接聚类的算法, 这类算法以网络中的边为对象划分每条边的社区归属, 再将划分得到的链接社区转化成相应的节点社区。其中代表性算法有LINK^[12]、Link-Comm^[13]以及DBLINK^[14]等。

其他相关算法还包括基于非负矩阵分解模型的LANMF^[15]、MCMOEA^[16]、NMF^[17]等。在现实的ESN中, 企业个体间的竞争力与地位往往不同, 核心企业与配套企业间存在明显差异^[18], 从而导致派系聚簇现象产生。本文结合局部信息的特点, 通过种子派系来研究ESN中社区局部扩张的过程, 提出一种基于贪婪派系扩张的社区发现算法GFE。利用种子派系信息不断扩张、合并周围新的企业节点, 得到一个理想规模的派系社区结构。重复迭代上述过程, 以得到覆盖ESN中多个派系的重叠社区。

1 基于派系的社区结构

给定一个企业社会化网络G=(V, E), 其中, V={v₁, v₂, …, v_N}表示企业节点的集合, N表示节点数目, E={(v_i, v_j)|v_i, v_j∈V, i≠j}表示企业节点间合作关系边的集合。企业社区发现的目的是在ESN中找到符合一定条件的企业节点集合, 这是典型的NP-hard问题。

1.1 企业社区的基本定义

因合作、联盟等原因聚在一起的企业集群, 具有高度的互动性, 他们以整体利益最大化为目标形成社区结构。企业社区结构通常可以被描述为企业社会化网络节点集合的若干子集, 每个子集内部节点之间的连接相对稠密, 而不同子集节点之间的连接相对稀疏。基于文献[19]对有关社区的描述, 本文作如下定义。

定义1 (结构相对度)   给定一个企业社会化网络图G=(V, E), A=[A_ij]_N×N为图G中的邻接矩阵。子图$ S \subset G$, 对于$\forall v_{i} \in S $, 企业节点v_i的内部度与外部度可以用邻接矩阵元素分别表示为:

$ d_S^{{\rm{in}}}\left( {{v_i}} \right) = \sum\limits_{{v_i},{v_j} \in S} {{A_{ij}}} $

$ d_S^{{\rm{out}}}\left( {{v_i}} \right) = \sum\limits_{{v_i} \in S,{v_j} \notin S} {{A_{ij}}} $

则企业节点v_i的结构相对度d_S(v_i)表示为:

$ {d_S}\left( {{v_i}} \right) = d_S^{{\rm{in}}}\left( {{v_i}} \right) + d_S^{{\rm{out}}}\left( {{v_i}} \right) $

定义2 (企业社区)   给定一个企业社会化网络图G=(V, E), 子图$S \subset G, \forall v_{i} \in S $, 如果满足$ d_{S}^{\mathrm{in}}\left(v_{i}\right)>d_{S}^{\mathrm{out}}\left(v_{i}\right)$, 则称S为强连接企业社区。若S仅满足$\sum\limits_{v_{i} \in S} d_{S}^{\mathrm{in}}\left(v_{i}\right)>\sum\limits_{v_{i} \in S} d_{S}^{\mathrm{out}}\left(v_{i}\right) $, 则称其为弱连接企业社区。

在强连接企业社区中, 每个节点的内部链接都多于其外部链接。在弱连接企业社区中, 所有节点的内部链接之和多于其外部链接之和。

1.2 派系社区

ESN中存在一种企业节点间两两完全互连的特殊企业子团, 该子团被称为派系。k派系指该子团中存在k个企业节点, 极大派系则表示企业子团规模k已达到最大, 无法通过添加其他企业节点来扩展该派系规模。

定义3 (极大派系)   给定一个企业社会化网络图G=(V, E), $S \subset G $。F是S中的局部结构, 若F中所有企业节点v_i的个数为k, 且F的内部链接总数满足$\sum\limits_{v_{i} \in F} d_{F}^{\mathrm{in}}\left(v_{i}\right)=\frac{k(k-1)}{2} $, 则称F是S中的派系。如果有$\forall v_{u} \in S $且$v_{u} \notin F $, 满足$\sum {d_F^{{\rm{in}}}} \left( {{v_i} \cup {v_u}} \right) < \frac{{k(k - 1)}}{2} $, 则称F是S中的极大派系。

如图 1所示, 三角形节点表示已加入社区的邻居企业节点, 圆形节点表示待加入的候选企业节点。方形节点v₁、v₂和v₃两两互连构成规模为3的派系, 但该派系并非极大派系, 可通过添加节点v₄将其扩展到规模为4的极大派系。极大派系是一种相对稳固的局部结构, 派系中的企业合作关系较为紧密, 且其中的节点难以被替换。

派系社区是基于极大派系的一种社区结构, 其包含极大派系以及周围一定区域内的邻居企业节点, 该区域范围由适应度函数f决定。一个派系社区S中所包含的企业节点v_si必须满足f(v_si)>0。

1.3 重叠派系社区

在实际中, 一个企业节点可能隶属于多个企业社区, 派系社区间可能存在重叠、嵌套等现象。例如, 某企业同时参与手机零件制造和空调零件供应, 且在这2个领域都发挥着一定的作用, 则该企业视为加入了2个派系社区。在现实的ESN中, 重叠派系社区与普通社区在描述上存在一定区别, 稠密的重叠派系社区之间也可能存在很多外部链接。如图 2所示, 派系社区S₁与S₂相交, 存在v₁与v₂ 2个重叠节点。对于社区S₁内部节点v₁来说, 其与S₁中其他节点间有3个链接, 而与S₂存在4个链接, 即外部链接多于内部链接。此外, 重叠派系社区还体现了企业社区重叠性与层次性的双重特征。

定义4 (社区重叠度)  给定2个派系社区S₁和S₂, 社区重叠度定义为:

$ {O_v}\left( {{S_1},{S_2}} \right) = \frac{{\left| {{S_1} \cap {S_2}} \right|}}{{\min \left( {\left| {{S_1}} \right|,\left| {{S_2}} \right|} \right)}} $

若ESN中2个派系社区S₁和S₂共享了$Q_{S_{1}, S_{2}}^{O_{v}} $个企业节点, 则S₁和S₂称为重叠派系社区。此外, 在派系社区发现过程中可能会出现高度重叠、近似重复的社区对, 这就需要对社区的重叠度O_v进行限定。当社区对间的重叠度O_v超过一定范围时, 则表明这2个社区相似度较大, 可进行合并。

2 GFE算法

为避免在企业社区发现过程中2个社区高度重叠现象的发生, 提高社区发现的效率, 本文提出一种基于贪婪派系扩张的重叠社区发现算法GFE。

2.1 种子派系选择

GFE算法需要选择合适的种子派系, 利用种子派系信息挖掘ESN中的社区结构。将图G=(V, E)转换为最大派系图$ G^{c}=\left(V^{c}, E^{c}\right)$, 其中, $ {V^c} = \left\{ {v_1^c} \right., v_2^c, \cdots , v_m^c\} $是派系集合, ${E^c} = \left\{ {\left( {v_m^c, v_n^c} \right)|v_m^c, v_n^c \in {v^c}} \right., m \ne n\} $是派系间连接关系边的集合。在图的转换过程中, 需先确认每个派系中的企业节点, 然后利用派系之间的结构计算其链接强度。

2.1.1 派系节点确定

为找出极大派系, 首先需要确定派系中的每个企业节点。由于每个极大派系均是图G中企业节点所隶属的派系之一, 因此本文将派系中的节点确认过程转化成找出G中每个节点所隶属的所有极大派系的过程, 如算法1所示。

算法1  确定G^c中的派系节点

输入  初始图G=(V, E)

输出  派系节点集合V^c

1.V^c←φ

2.Calculate the degree k(v_i) of each node v_i∈V;

3.$ {{\rm{k}}_{\max }} \leftarrow \mathop {\max }\limits_{{{\rm{v}}_{\rm{i}}} \in {\rm{V}}} {\rm{k}}\left( {{{\rm{v}}_{\rm{i}}}} \right)$

4.Sort the nodes in descending order of the degree;

5.for k = k_max+1 to 1 do

//节点度不小于(k－1)

6.for each node v_i∈V do

7.if k(v_i) < k－1

8.no more k-factions exist and goto Outer loop;

9.end if

//该节点没有被分配给任何派系

10.if v_i has been assigned to one faction node

11.goto Inner loop;

12.end if

//至少(k－1)个相邻节点的度数不小于(k－1)

13.Neigh(v_i) ← {v_j|(v_j is adjacent to v_i and k(v_i)≥k－1};

14.if |Neigh(v_i)| < k－1

15.v_i cannot constitute k-faction and goto Inner loop;

16.end if

//转换为搜索由该节点邻居构成的(k－1)派系问题

17.if the nodes in Neigh(v_i) can constitute q(k－1)－faction(q≥1)

//将所有发现的k派系添加到派系节点集合中

18.V^c←V^c∪{v_i, ((k－1)－faction)₁}∪…∪{v_i, ((k－1)－faction)_q};

19.end if

20.Inner loop;

21.end for

22.Outer loop;

23.end for

在算法1中, 派系中的节点根据其所在派系大小以降序排列。企业节点的“择优连接”偏好性表明企业更愿意与关系连接数目较多的企业节点建立联系, 即2个企业节点建立链接关系的边越多, 其构成极大派系的机率越大。因此, 本文首先计算G中每个节点的度数, 然后按度数的降序将节点进行排序。

假设G中的节点数为N, 最大节点度为k_max, 则G中的派系规模不大于k_max+1。随着派系规模k的值从k_max+1下降到1, 搜索每个节点所隶属的k派系。因为派系中的节点两两完全互连, 所以k派系中所有节点的度数必须大于k－1。此外, 若一个节点已经被分配给较大的派系, 则该节点寻找到相对较小的子团后停止搜索过程。因此, 搜索节点所隶属的k派系需满足以下3个条件:

1) 该节点度数不小于k－1。

2) 该节点没有被分配给任何派系。

3) 该节点至少有k－1个相邻节点的度数不小于k－1。

若满足上述所有条件, 查找该节点的所有k派系的问题, 可转换为确认其与邻居节点是否具有k－1个连接关系的问题, 最后将发现的所有k派系添加到派系集合中。

图 3(a)所示为一个具有9个节点和14条连接边的ESN原始图, 图 3(b)给出了相应的派系节点, 其中, 包括一个规模为4的派系和3个规模为3的派系。由图 3可以看出, 节点v₇、v₈和v₉属于派系v₄^c, 而节点v₄和v₅同时属于派系v₂^c和v₃^c。原始图的每个节点至少被分配给对应的最大派系图中的一个派系。

2.1.2 派系间的链接强度

2个派系之间的链接强度大小取决于重叠节点、重叠边以及联通边的比例。给定2个派系, 重叠节点为这2个派系的共同节点, 其连接边被称为重叠边, 联通边指2个派系中不同节点间的连接边。如图 4所示, 图 4(a)中的v₃为重叠节点, 图 4(b)中节点v₂与v₃间的边为重叠边, 图 4(c)中节点v₃与v₄间的边为联通边。

定义5 (重叠节点比率)  给定2个派系v_m^c和v_n^c(m≠n), 其之间的重叠节点比率l_on(v_m^c, v_n^c)记为:

$ {l_{{\rm{on}}}}\left( {v_m^c,v_n^c} \right) = \frac{{N\left( {v_m^c \cap v_n^c} \right)}}{{N\left( {v_m^c} \right) + N\left( {v_n^c} \right) - N\left( {v_m^c \cap v_n^c} \right)}} $

其中, N(v_m^c)、N(v_n^c)分别表示派系v_m^c、v_n^c的节点数目, N(v_m^c∩v_n^c)表示派系v_m^c与v_n^c间的重叠节点数目。

定义6 (重叠边、联通边比率)  设A=[A_ij]_N×N为原始图G中的相邻矩阵, 若(v_i, v_j)∈E, 则A_ij=1, 否则A_ij=0。重叠边比率l_oe(v_m^c, v_n^c)、联通边比率l_je(v_m^c, v_n^c)分别表示为:

$ {l_{{\rm{oe}}}}\left( {v_m^c,v_n^c} \right) = \frac{{\sum\limits_{{v_i},{v_j} \in \left( {v_m^c \cap v_n^c} \right)} {{A_{ij}}} }}{{\sum\limits_{{v_i},{v_j} \in V} {{A_{ij}}} }} $

$ {l_{{\rm{je}}}}\left( {v_m^c,v_n^c} \right) = \frac{{\sum\limits_{{v_i} \in \left( {v_m^c - v_n^c} \right),{v_j} \in \left( {v_n^c - v_m^c} \right)} {{A_{ij}}} }}{{\sum\limits_{{v_i},{v_j} \in V} {{A_{ij}}} }} $

定义7 (派系间链接强度)   基于l_on、l_oe、l_je, 派系v_m^c和v_n^c间的链接强度为:

$ \begin{array}{*{20}{c}} {L\left( {v_m^c,v_n^c} \right) = \beta {l_{{\rm{on}}}}\left( {v_m^c,v_n^c} \right) + \gamma {l_{{\rm{oe}}}}\left( {v_m^c,v_n^c} \right) + }\\ {\omega {l_{{\rm{je}}}}\left( {v_m^c,v_n^c} \right)} \end{array} $

其中, β、γ、ω∈[0, 1]且β+γ+ω=1, β、γ、ω分别控制重叠节点、重叠边和联通边的权重。L(v_m^c, v_n^c)∈[0, 1), 当2个派系v_m^c和v_n^c完全独立时, L(v_m^c, v_n^c)=0。

如图 3(c)所示, 派系v₁^c和v₂^c间有2个重叠节点和1条重叠边, 没有联通边, 这2个派系的总节点数为5, 总边数为14, 则l_on=2/5, l_oe=1/14, l_je=0。故派系v₁^c和v₂^c间的链接强度为:

$ L\left( {v_1^c,v_2^c} \right) = \frac{1}{3}\left( {\frac{2}{5} + \frac{1}{{14}} + 0} \right) $

派系间的链接强度有强有弱, 有些甚至为0。在派系扩张的过程中, 链接相对紧密的派系间极有可能发展成近似重复的企业社区, 这不仅会造成计算的浪费, 还对社区层次结构的划分产生不利影响。为避免上述问题, 可以设置一个链接强度阈值Δ, 当派系间链接强度超过Δ时, 这些派系被认为是“可疑种子”。采用一个简单优化方法合并这类“可疑种子”, 然后进行扩张并发现企业社区, 从而避免近似重复种子的膨胀现象, 且不会影响社区发现的结果。

2.2 贪婪扩张

在选取了适当的种子派系后, 通过贪婪算法不断扩张种子派系, 选择、合并其邻居节点, 最终得到一个候选企业社区C′。在该过程中, 需要定义一个适应度函数^[6]来指导种子派系的发展, 使其扩张成理想的社区。

定义8 (结构适应度)   给定图G=(V, E), 子图$S \subset G, d_{\mathrm{in}}^{s}、d_{\mathrm{out}}^{s}$分别表示S的内部度、外部度, 其中, d_in^S是2个S内部节点的链接数。则社区结构适应度函数定义为:

$ {f_S} = \frac{{d_{{\rm{in}}}^S}}{{{{\left( {d_{{\rm{out}}}^S + d_{{\rm{in}}}^S} \right)}^\alpha }}} $

其中, α是控制社区规模大小的参数, 其在一定程度上避免了扩张过程落入局部稠密的现象。

定义9 (节点适应度)   给定图G=(V, E), 子图$ S \subset G$, 给定候选企业节点v_μ∈V, 则节点v_μ对于S的结构适应度(即节点适应度)为:

$ f_{\left( {S,{v_u}} \right)}^{{v_u}} = {f_{S \cup \left\{ {{v_u}} \right\}}} - {f_{S - \left\{ {{v_u}} \right\}}} $

其中, $f_{S \cup\left\{v_{u}\right\}} $与$ f_{S-| v_{u} \}}$分别表示S中包含节点v_u和不包含节点v_u的结构适应度。

适应度函数返回的值反映了S内部及S与外部之间的连接紧密程度, 增加不同的企业节点可能会引起适应度函数值的增大或缩小, 函数值越高, 则表明增加节点后社区结构越好。在2.1节提供的初始种子派系的基础上, 利用适应度函数不断选取合适的成员节点, 贪婪扩张种子派系, 直到添加任何企业节点都不能增大适应度函数值为止。

2.3 社区差异度

通过适应度函数贪婪扩张可以有效挖掘ESN中社区的重叠结构, 且通过种子派系的贪婪扩张过程, 也在一定程度上展现了社区的良好层次结构。但在此过程中, 可能产生高度重叠的社区, 同一种社区结构被高度相似的社区重复发现了多次, 这不仅会造成计算成本的浪费, 而且不符合ESN的社区结构特征。为避免上述问题, 本文在不影响社区发现结果的前提下, 采用基于社区重叠度的阈值合并方法进行过程优化。

定义10 (社区差异度)  给定2个企业社区S₁和S₂, 通过社区重叠度的定义, S₁和S₂间的差异度δ为:

$ {\delta _E}\left( {{S_1},{S_2}} \right) = 1 - \frac{{\left| {{S_1} \cap {S_2}} \right|}}{{\min \left( {\left| {{S_1}} \right|,\left| {{S_2}} \right|} \right)}} $

社区差异度表示较小社区未嵌入较大社区中的节点所占的比率, 比率越低, 这2个社区的相似性越高。本文引入一个社区差异度阈值ε, 当δ_E(S₁, S₂)≤ε时, 表明社区对的相似性过高, 可将这2个社区进行合并。

给定一组已被接受的企业社区W和一个候选企业社区C′, 将C′的近似重复社区定义为W中与C′的差异度不超过ε的所有社区。通常设置ε的默认值为0.25, 但是如果在输出过程中发现太多近似重复的社区, 应适当增大ε的值。

2.4 算法实现

GFE算法的整体步骤如下:

步骤1  根据种子派系选择策略, 将ESN原始图G=(V, E)转换为极大派系图G^c=(V^c, E^c), 选择未扩张的种子派系F₀作为初始社区C_i。

步骤2  计算种子派系所有邻接节点对其的节点适应度, 利用社区适应度函数贪婪扩张, 直到没有节点可以增加适应度函数值, 得到一个候选企业社区C′。

步骤3  计算候选企业社区C′与已经被接受的社区C的差异度, 若差异度不超过阈值ε, 则C′与C近似重复, 将C′与C进行合并; 否则, 接受C′。

步骤4  返回步骤1, 进行新的社区扩张。若没有未扩张的种子派系, 则算法终止, 最后输出社区。

GFE算法描述如下:

算法2   GFE算法

输入  初始图G=(V, E), 种子派系F₀

输出  生成的社区C_i

1.for all v_u∈F₀ neighbors

2.calculate v_u′s node fitness ${\rm{f}}_{\left(\mathrm{S}, \mathrm{v}_{\mathrm{u}}\right)}^{\mathrm{v}_{\mathrm{u}}} $;

3.if ${\rm{f}}_{\left(\mathrm{S}, \mathrm{v}_{\mathrm{u}}\right)}^{\mathrm{v}_{\mathrm{u}}} $>0 then

4.add v_u to C_i;

5.end if

6.end for

7.create a candidate community C′;

8.for candidate community C′

Calculate the δ_E for C′ with already accepted community C

9.if C′ within ε of any already accepted community C then

10.C′ and C are near-duplicates;

11.merge the candidate community C′

12.else

13.Accept C′;

14.end if

15.end for

3 实验结果与分析

为验证GFE算法的性能, 将其与CPM算法^[20]、LFM算法、基于层次聚类的HC-PIN算法^[21]以及基于标签传播的COPRA算法和SLPA算法^[22]进行比较。实验环境为Lenovo PC Intel(R) Core(TM) i5-2520M CPU @ 2.50 GHz, 内存为8 GB, Windows操作系统, 编程语言为Python。实验将在模拟ESN的LFR基准网络^[23]以及公开的社会网络数据集上进行算法比较。

3.1 评价指标

不同算法在同一网络上可能会划分出不同的社区结构, 需要对划分出的社区质量进行评估。本文采用目前重叠社区研究中比较惯用的4种评价指标:标准化互信息(Normalized Mutual Information, NMI), 相对标准化互信息(relative Normalized Mutual Information, rNMI), F₁值, 扩展模块度EQ。

3.1.1 NMI和rNMI

NMI利用信息熵来衡量算法划分的社区结构与预先已知社区结构之间的差异, 其是基于混合矩阵N进行计算的数字指标, 定义为:

$ NMI = \frac{{ - 2\sum\limits_{i,j} {{N_{ij}}{\rm{lb}}\left[ {\frac{{{N_{ij}}n}}{{{N_i}.N{._j}}}} \right]} }}{{\sum\limits_i {{N_i}.{\rm{lb}}\left[ {\frac{{{N_i}.}}{n}} \right]} + \sum\limits_j {N{._j}{\rm{lb}}\left[ {\frac{{N{._j}}}{n}} \right]} }} $

其中, n表示网络节点的数量, N_ij表示社区i、j中公共的节点数, N_i·(N_·j)表示混合矩阵N中第i行(第j列)之和。若算法发现的社区结构与预先已知的社区结构完全一致, 则NMI值为1;如果两者完全独立, 则NMI值为0。NMI值越接近1, 则表明算法发现的社区质量越好。

当网络规模有限时, NMI易受到系统误差的影响。rNMI能够克服网络规模的影响, 其通过将NMI与随机分区的预期NMI进行比较来考虑统计的显著性^[24]。rNMI定义为:

$ rNMI\left( {A,B} \right) = NMI\left( {A,B} \right) - \left\langle {NMI\left( {A,C} \right)} \right\rangle $

其中, C是与检测的分区大小相同的空模型。

3.1.2 F₁值

F₁值通过召回率(recall)和精确度(precision)的调和平均值, 度量算法划分的社区与预先已知社区结构间的匹配程度。F₁值定义为:

$ {F_1} = \frac{{2recall \times precision}}{{recall \times precision}} $

其中, recall、precision在网络二分后进行定义。

3.1.3 扩展模块度EQ

扩展模块度EQ是建立在模块度Q基础上的评价指标。模块度指标Q用于衡量网络社区划分结果的优劣, 其思想是社区内的节点间连接边越多, 与社区外部连接边越少, Q值越大, 社区结构划分效果越好。但在重叠社区研究中发现, 重叠节点可能与外部连接较多, 这会降低Q的值。EQ在此基础上进行改进, 其在处理重叠节点时, 会考虑这类节点的“重叠度”, 将“重叠度”对Q的影响值除以该节点所隶属社区的个数, 以减少这类节点对模块度值的影响, 使其可用于对重叠社区进行度量。EQ定义为:

$ E Q=\frac{1}{2 m} \sum\limits_{c} \sum\limits_{i, j \in c} \frac{1}{Q_{i} Q_{j}}\left[A_{i j}-\frac{k_{i} k_{j}}{2 m}\right] $

其中, Q_i表示节点i所属的社区数, k_i为与节点i建立链接关系的边数, A_ij是整个网络对应的邻接矩阵的元素, 若节点i与节点j间存在连接, 则A_ij=1, 否则A_ij=0, m表示网络中节点间的连接边总数。

3.2 结果分析 3.2.1 LFR基准网络

本文利用LFR基准网络模拟生成ESN。LFR基准网络具有如下2个优点:

1) 可以模拟ESN中的节点度和社区大小无标度特性。

2) 具有预先已知企业社区的结构, 可将其与算法发现的社区进行比较, 以评估算法的性能。

构建LFR基准网络图, 须定义一些参数。其中, N表示企业节点的个数, k表示企业节点的平均度数, k_max表示企业节点的最大度, O_n表示网络图中重叠企业节点的数量, O_m表示每个重叠节点所隶属的企业社区个数, τ₁、τ₂分别表示节点度和社区大小所遵循的分布参数, C_min、C_max分别表示最小社区规模和最大社区规模所包含的节点数量, 混合参数μ控制企业社区内的节点与外部连接的比率, 随着μ值的增大, 企业社区的结构减弱, 社区发现的难度越大。本文根据实验需要设置不同的参数, 以生成不同类型的企业社会化网络。下文实验结果图 5~图 8中对应的参数配置如表 1所示。

各算法在LFR基准网络上运行效率与节点数、节点平均度间的关系分别如图 5、图 6所示。从图 5可以看出, GFE算法运行效率不仅与结构适应度参数α有关, 还与网络中的企业节点数成正比。CPM算法由于要对网络中的全局极大子团进行定位, 因此其时间复杂度相对较高。LFM算法采用局部贪婪优化策略, 与GFE算法相似, 但是LFM算法随机选择种子节点, 所以其时间复杂度也较高。SLPA算法改进了原始标签传播算法COPRA, 效率相对较高, 但仍低于GFE算法(α=0.9)。从图 5还可以看出, 随着节点数量的增加, 与其他重叠社区发现算法相比, GFE算法运行效率的优势呈增长趋势。在图 6所示的一系列实验中, 企业节点的数量保持固定值5 000。从图 6可以看出, 与本实验中运行效率较快的SLPA和COPRA算法相比, 随着平均度的增加, GFE算法的运行时间增长很快, 即使在规模较小的图上, 节点平均度对GFE算法运行时间的影响也很大。但综合观察可以看出, GFE算法在重叠社区发现的运行效率方面整体表现良好。

在社区重叠程度较高的情况下进一步比较各算法所发现社区的质量, 分别用指标NMI和rNMI评价算法的性能。本次实验分别生成5个模拟网络。在第1个网络图中, 每个节点隶属于唯一社区, 设置节点平均度为k=18。为让企业节点更有可能同时隶属多个社区, 本文设置更高的节点度。在第2个网络图中, 每个重叠节点隶属于2个社区, 节点平均度设置为k=36。以此类推, 在第5个网络图中, 每个重叠节点隶属于5个社区, 设置节点平均度为k=90。其他参数设置情况如表 1所示, 实验结果如图 7、图 8所示。

从图 7、图 8可以看出, 即使社区的重叠程度保持在中等水平, CPM算法和COPRA算法也不能有效地挖掘重叠企业社区结构。随着社区重叠程度的增加, SLPA算法和HC-PIN算法表现较好, 而GFE算法表现最佳。虽然LFM算法和GFE算法使用相同的适应度函数和相似的贪婪扩张方式, 但它们的测试结果差别很大。随着社区重叠程度的加深, LFM算法的性能下降, 原因是随机选择种子可能会导致其过早地放弃尝试扩张未被识别出的社区的图区域。

基于GFE算法(α=0.6)发现的ESN重叠社区的可视化结果如图 9所示。由图 9可以看出, GFE算法在ESN中发现了3个很明显的不同社区结构, 图中用圆圈进行标注。尽管存在一些其他节点的干扰, 但并未影响社区的结构。圆圈交叉部分内的企业节点就是社区间的重叠部分, 可以看出, 有些节点隶属于2个社区, 而有些节点同时隶属于3个社区, 社区间存在交叉重叠现象。虽然本次实验是利用LFR基准网络模拟ESN, 但从重叠社区的挖掘效果来看, 这种做法具有一定的实际意义。

综上, 在运行效率与挖掘效果方面, 相比SLPA、LFM等算法, GFE算法具有一定优势。

3.2.2 真实社会网络

本节利用5个公开的标准社会网络数据集对算法进行测试。社会网络数据集包括3个已知社区结构的常用真实网络:空手道俱乐部网络(Zachary’s Karate Club, 简称Karate)^[25], 海豚网络(Dolphin’s Associations, 简称Dolphin)^[26], NCAA大学橄榄球联盟比赛网络(College Football League, 简称Football)^[25], 以及2个大规模网络:科学合作者网络(Netscience)^[27], 单词关联网络(Word Association)^[28]。这些社会网络的详细描述如表 2所示, 使用F₁值和扩展模块度EQ作为评价标准, 以衡量各算法所划分社区的质量以及合理性。

图 10所示为采用GFE算法发现的Karate的重叠社区。2个社区分别以节点1、2、4和节点24、33、34为种子派系进行贪婪扩张, 中间的节点3、9、10、14、31是2个社区的重叠部分。由图 10可以看出, GFE算法在真实网络中同样能有效地发现较为理想的社区。

表 3所示为6种算法的性能比较结果。由表 3可以看出, 本文GFE算法在3个数据集上都能找到较理想的社区, 且精度较高, 同时F₁值最优。从社区发现的角度看, GFE算法将3个数据集进行准确地划分, 尤其是在Karate数据集中, GFE算法始终保持正确。因此, GFE算法总体上呈现出较高的平均准确度。

在Word Association网络中, 以bright为例划分出其所属的社区, 如图 11所示。bright单词涉及emotion、color和light 3个社区, 每个社区代表bright的一种含义。除bright外, GFE算法还成功检测到color和light之间的其他重叠节点, 即pale和gray。实验结果表明, GFE算法在Word Association中能够合理并有效地发现社区。

6种算法在5个真实网络上的EQ值结果对比如表 4所示。由表 4可以看出, 在Karate和Dolphin中, GFE算法的EQ值相对偏低, 但准确率较高, 而在Football、Netscience和Word Association中, GFE算法的EQ值都偏高。原因是GFE算法采用种子派系作为初始社区, 具有良好的邻域鲁棒性, 且在一定程度上避免了由初始节点落入稀疏边界所带来的计算冗余与误差。综上, GFE算法在真实数据集的社区发现中表现良好, 在规模较大的网络中优势更为明显。

4 结束语

本文提出一种基于贪婪派系扩张的重叠社区发现算法GFE。采用种子派系选择策略, 利用社区适应度函数贪婪扩张种子派系以得到一个候选社区, 将候选社区与已接受社区进行差异度比较, 判断是否接受该候选社区。在种子派系的选择过程中, GFE算法将链接强度过高的派系进行合并, 能够在一定程度上避免网络社区的过度重叠情况, 降低计算复杂度。实验结果表明, 在运行效率与社区划分质量方面, GFE算法相对LFM、CPM等算法具有一定的优势。利用GFE算法在ESN中发现具有重叠性的社区结构, 能够为企业分析相互间的合作关系、优化供应链需求提供一种新的方法和途径。但本文主要以静态网络为研究对象, 忽略了网络以及社区结构的动态变化, 下一步将分析动态网络中的社区演化模式。