近年来, 对各种复杂网络的研究^[1-3]是许多领域的研究热点之一, 如生物网络、社交网络、电子邮件网络、引文网络等已成为众多学者的主要研究对象.复杂网络中的社区发现不仅有助于深入研究整个网络的功能模块及其演化, 而且能够准确地理解并分析复杂系统的拓扑结构及动力学特性, 因此具有十分重要的理论意义和应用价值^{[4, 5]}.

目前, 针对复杂网络中的社区发现问题, 研究较多的是无向无权网络, 包括基于图划分的聚类算法^[6]、基于谱分析的聚类算法^[7]、基于层次的聚类算法^[8]、基于密度的聚类算法^{[9, 10]}等.其中, 基于密度的聚类算法通过搜索网络中稠密子图^[11], 能够较好地发现网络中的功能模块, 在社区发现中得到了广泛应用.2003年Bader等人提出的MCODE算法^[12]、2005年Palla等人^[13]提出的派系过滤算法(clique percolation method, 简称CPM)、2006年Saito等人^[14]提出的k-dense算法、2009年Shen等人提出的EAGLE算法^[15]等将网络拓扑结构作为社区划分的依据, 对无权网络进行社区划分.

然而, 现实复杂网络中的边或顶点中往往包含有一些重要的先验信息, 如, 高通量实验所得到的蛋白质互作用网络中, 边权重往往代表实验可信度; 合作网络中的边权重通常代表合作对象的连接紧密程度.2008年, Blondel等人基于模块性最优化提出了启发式算法BGLL^[16].2009年, Liu等人^[17]提出的CMC算法通过迭代评分的方法给每条边赋予权重, 然后通过搜索网络中的所有极大团并计算其加权密度, 最后依据极大团的加权密度定义极大团之间的相互连接度, 进而合并极大团得到网络中的社区结构.2011年, Lee等人^[18]提出的MDOS算法在加权网络中通过选取种子节点, 并依据子图函数逐步扩展得到稠密子图.Wang等人基于边聚集系数局部度量提出了适用于无权网络和加权网络的HC-PIN算法^[19].2014年, Ren等人^[10]也通过定义边权重将无权网络转化为加权网络, 然后结合子图的密度性和模块性定义适应度函数, 给出了基于局部适应度的LF_PIN算法.但是, 这些学者仅考虑基于拓扑结构定义网络中边的权重或者仅考虑网络中具有现实意义的边权重进行社区发现.如何将具有现实意义的边权重与网络拓扑结构相结合, 作为社区发现算法的依据, 进而发现复杂网络中的重叠社区, 是当今社区发现算法研究热点之一.

针对加权网络的社区发现问题, 提出了一种基于种子扩展策略的重叠社区发现算法(overlapping community detection on weighted networks, 简称OCDW).首先给出了一种综合考虑网络自身边信息和网络拓扑结构信息的边权重定义方式, 并基于此定义节点的加权度, 选择权重最大的节点作为社区种子节点; 进而给出了基于社区评估函数的种子扩展策略和权重更新方式, 迭代得到加权稠密子图; 最后, 将重叠率比较高的稠密子图合并为加权中心社区, 并根据节点对社区的归属度b(v, C)来度量节点和社区的连接倾向程度, 将未聚类节点分配到加权中心社区中, 从而得到最终的社区发现结果.

1 背景知识

通常, 一个复杂网络可以用图G=(V, E)来表示, 其中, 节点集V={v₁, v₂, …, v_n}, n=|V|; 边集E中每条边e_{i, j}对应V中一对顶点(v_i, v_j)之间的连接关系, m=|E|.节点v的邻域N_G(v)={u|(u, v)∈E}, 在不引起混淆的情况下, 简记为N(v). N(v)中的节点称为节点v的相邻点.节点v的度记为k_v.除非特别指明, 本文仅考虑简单无向图, 即k_v=|N(v)|.令U⊆V(G), 用[U]_G表示G的节点子集U的导出子图, 记为[U].令$ {{N}_{G}}(U)=\bigcup\nolimits_{x\in U}{{{N}_{G}}(x)} $表示顶点子集U在图G中的邻域.令$ N_{G}^{-}(U)={{N}_{G}}(U)\backslash U. $图 1给出了两个典型复杂网络实例.

为了合理地对复杂网络中的节点进行社区发现, 将顶点间的相似性作为衡量节点连接紧密程度的重要标准.Jaccard度量^[20]认为:网络图中两节点间的公共邻接点越多, 其在结构上就越相似, 连接也就越紧密, 如公式(1)所示.

$ Jaccard({{v}_{i}}, {{v}_{j}})=\frac{|N({{v}_{i}})\cap N({{v}_{j}})|}{|N({{v}_{i}})\cup N({{v}_{j}})|} $

(1)

Hub Promoted和Hub Depressed度量^[20]考虑偏好连接对连接紧密度的影响, 如公式(2)、公式(3)所示.

$ HP({{v}_{i}}, {{v}_{j}})=\frac{|N({{v}_{i}})\cap N({{v}_{j}})|}{\min \{|N({{v}_{i}})|, |N({{v}_{j}})|\}} $

(2)

$ HD({{v}_{i}}, {{v}_{j}})=\frac{|N({{v}_{i}})\cap N({{v}_{j}})|}{\max \{|N({{v}_{i}})|, |N({{v}_{j}})|\}} $

(3)

由于复杂网络构建过程中实验方法的偏差会导致网络拓扑结构中有大量噪声, 如由高通量实验构建的蛋白质互作用网络中存在大量的假阳性和假阴性数据, 为了更准确地表示网络中边的连接紧密程度, 应该综合考虑网络拓扑结构和复杂网络中的边信息.

2 边权重定义

现实网络中, 边的特性可以通过边权重来体现.如社会网络中, 边权重可以表示个体之间连接的紧密及强弱关系; 科学家合作网络中的边权重, 可以表示科学家之间合作的次数; 而蛋白质互作用网络中, 边权重往往表示由高通量实验所产生的蛋白质互作用边的可信度^[23].在网络中进行社区发现, 不仅需要考虑网络的拓扑结构, 而且也要考虑节点间边连接的现实意义.

为了能够更加准确地度量节点之间的关联强度, 需要先对网络中边的权重进行定义, 如公式(4)所示.

$ {w}'({{v}_{i}}, {{v}_{j}})=\alpha \cdot \frac{|N({{v}_{i}})\cap N({{v}_{j}}){{|}^{2}}}{\min {{\{|N({{v}_{i}})|, |N({{v}_{j}})|\}}^{2}}}+\beta \cdot \frac{|N({{v}_{i}})\cap N({{v}_{j}}){{|}^{2}}}{\max {{\{|N({{v}_{i}})|, |N({{v}_{j}})|\}}^{2}}}+(1-\alpha -\beta )\cdot u({{v}_{i}}, {{v}_{j}}) $

(4)

其中, N(v_i)表示节点v_i邻接节点的集合, N(v_i)∩N(v_j)表示节点v_i和v_j的公共邻接节点集合, u(v_i, v_j)表示节点v_i和v_j在真实网络中边的权重.前两项体现了节点v_i和v_j在网络拓扑结构方面的相似程度, 第3项体现了边的真实网络权重.将图G的边$ {{e}_{{{v}_{i}}{{v}_{j}}}} $的最终权重定义为公式(5).

$ w({{v}_{i}}{{v}_{j}})=\left\{ \begin{array}{*{35}{l}} \varepsilon +\tfrac{1-\varepsilon }{{{{{w}'}}_{avg}}}\cdot {w}'({{v}_{i}}{{v}_{j}}),&{{v}_{i}}{{v}_{j}}\in E(G) \\ 0,&{{v}_{i}}{{v}_{j}}\notin E(G) \\ \end{array} \right. $

(5)

其中, $ {{{w}'}_{avg}}=\frac{\sum\nolimits_{{{v}_{i}}{{v}_{j}}\in E(G)}{{w}'({{v}_{i}}{{v}_{j}})}}{|E(G)|}, $常量ε(∈[0, 1])用以区分网络中一对顶点之间是否存在边, 此处取ε=0.2.

3 加权网络的重叠社区发现算法OCDW

基于上一节给出的边权重定义, 本文给出一种基于“种子节点扩展策略”的社区发现算法OCDW, 其中包括种子节点的选取、种子扩展过程和社区合并与后处理这3个基本过程.

●  首先, 根据与节点关联的边权重计算节点权重, 选择权重较大的节点作为种子节点;

●  其次, 以种子节点为初始点, 根据节点对子图的适应度函数将种子节点扩展成局部稠密子图;

●  当所有局部稠密子图构造结束后, 将这些子图进行合并处理, 得到最终的社区发现结果.

3.1 种子节点的选取

种子节点应该位于最终社区对应子图的拓扑中心位置, 通常, 这类节点在网络中重要性比较高且位于网络中相对稠密的区域中.种子节点的选择要有足够的代表性, 能够使得社区发现算法在尽可能少的迭代过程中给出网络中大多数节点的社区归属, 因此, 种子节点之间在网络结构上应该相距较远.基于这些原则, 将网络中节点v_i∈V(G)的加权度作为其权重定义, 如公式(6)所示:

$ wd({{v}_{i}})=\sum\nolimits_{{{v}_{j}}\in N({{v}_{i}})}{w({{v}_{i}}{{v}_{j}})\cdot {{k}_{j}}} $

(6)

其中, N(v_i)表示节点v_i的邻接点集合, k_j表示节点v_j的度.节点v_i的加权度wd(v_i)与其邻点的度数以及连边的权重成正相关, 反映了v_i在网络中的重要程度.此处选择权重最大的节点作为第1个种子节点.

为使网络中尽可能多的节点有社区归属, 在选择下一个社区的种子节点时, 应该降低那些已经成为种子的节点选择概率.因此, 本算法在找到一个稠密子图之后, 减少该子图中的边权重, 并重新计算相关节点的加权度.若某节点的加权度变化过大, 则不应选作其他社区的种子节点.因此定义节点的加权度变化率, 如公式(7)所示.

$ cr(v)=1-\frac{w{d}'({{v}_{i}})}{wd({{v}_{i}})} $

(7)

其中, wd(v)表示节点v在原始网络中的加权度, wd'(v)表示节点v在更新子图边权重之后的加权度.如果节点v的加权度变化率cr(v) > θ, 则节点v不能再次被选为种子节点, 本文设定θ=0.3.

图 2为空手道俱乐部和海豚社交网络在算法执行完之后的所有种子节点, 用黑色节点表示.可以看出, 图中种子节点选择数量适中且具有较好的代表性.

3.2 种子扩展策略

为了得到当前种子节点附近的一个稠密子图, 首先给出子图的适应度函数以评价其稠密程度.假设S是图G的一个连通子图, V_S表示子图S的顶点集, E_S表示S的边集, 令n_s=|V_S|, m_s=|E_S|.在S中添加$ \frac{{{n}_{s}}({{n}_{s}}-1)}{2}-{{m}_{s}} $条边, 可以得到一个完全图S', 把新添加的权重设定为图G中边的平均权重.通过考虑S中已有边与新添边权重的差异来评价S的稠密程度.公式(8)给出了子图S的社区评估函数f(S).

$ f(S)=\sum\nolimits_{{{v}_{i}}{{v}_{j}}\in E(S)}{w({{v}_{i}}{{v}_{j}})}-\frac{1}{2|E(G)|}[{{n}_{s}}({{n}_{s}}-1)-2{{m}_{s}}]\cdot \sum\nolimits_{{{v}_{i}}{{v}_{j}}\in E(G)}{w({{v}_{i}}{{v}_{j}})} $

(8)

显然, f(S)越大, 子图S在给定权重意义下越稠密.根据定义可知, 若S中只有1个节点, 则f(S)=0.

对节点v∉V_s, 定义v对S的适应度函数δ_S(v)=f(S∪{v})-f(S).在种子节点扩展步骤, 将满足δ_S(v) > 0且适应度函数最大的节点扩展到当前子图S中, 此过程迭代进行, 直至找不到满足条件的节点, 从而得到一个当前稠密子图.图 3为空手道俱乐部和海豚社交网络通过算法依据子图适应度函数将种子节点扩展得到的稠密子图, 不同形状的灰色节点表示不用的稠密子图.

3.3 合并优化社区与未聚类节点处理

通过上述步骤之后, 我们可以找到很多稠密子图, 但是存在一些稠密子图之间重叠节点较多的情况, 需要将重叠节点较多的稠密子图进行合并, 得到最终社区发现结果.如图 3(a)所示, 节点{9, 31, 33, 34}(图中六边形节点)构成的稠密子图与由节点{24, 30, 33, 34}(图中三角形节点)构成的稠密子图之间有一半节点重合, 需要进行合并.本文中判断两个稠密子图合并的条件为两个子图间重叠节点数不小于较小稠密子图节点数一半时, 将二者合并得到中心社区, 称为加权中心社区.图 4(a)和图 4(b)分别给出了空手道俱乐部和海豚社交网络合并后所得到的加权中心社区.

OCDW算法得到的加权中心社区包括了原始网络中的一些局部稠密子图, 但并未完全覆盖整个网络, 仍然存在一些未聚类节点(如图 4中的空白节点所示).理想的社区发现结果应该使网络中尽量多的节点有最终的社区归属, 因此, 根据节点与中心社区连接紧密程度定义未聚类对中心社区的归属度, 如公式(9)所示.

$ b(v, C)=\gamma \cdot \frac{\sum\nolimits_{x\in N(v)\cap C}{w(x, v)}}{\sum\nolimits_{x\in C}{w(x, v)}}+(1-\gamma )\cdot \frac{\sum\nolimits_{x\in N(v)\cap C}{wd(x)}}{\sum\nolimits_{x\in C}{wd(x)}} $

(9)

基于公式(9)给出的节点对社区归属度的定义, 迭代地将未聚类节点划分到已有的中心社区中, 对中心社区进行扩展, 得到更加合理的聚类结果(详细的中心社区扩展策略见算法1的步骤7和步骤8).图 5给出了空手道俱乐部数据和海豚社交网络的最终聚类结果.

3.4 算法描述

算法1.加权网络重叠社区发现算法.

输入:网络G=(V, E, U), 其中, V和E分别表示G的节点集和边集, U是G的权重矩阵.

输出:社区集合C={C₁, C₂, …, C_k}.

过程:

步骤1.令n=|V|, m=|E|, t=0, F=V, $ \alpha =\frac{2m}{n(n-1)} $.

步骤2.如果α < 0, 则转步骤9.令C=∅, β=0.7-α.

      根据公式(4)、公式(5)计算图G中每条边的综合权重矩阵W_n×n(G).

步骤3.根据公式(6)计算V中节点的加权度wd(v), 假设wd(v₁)≥wd(v₂)≥…≥wd(v_n).

步骤4.如果F为空集, 则转步骤5;否则, 令t=t+1, C_t=∅.

      步骤4.1.选择集合F中权重最大的一个节点v, 令F=F-{v}, 且C_t=C_t∪{v}.

      步骤4.2.令N(C_t)表示当前集合C_t的邻接点集合, 对N(C_t)中的每个节点u, 计算u对C_t的影响度$ {{\delta }_{{{C}_{t}}}}(v)=f({{C}_{t}}\cup \{u\})-f({{C}_{t}}) $, 其中, f(⋅)由公式(8)给出.

      步骤4.3.令节点x是N(C_t)中对C_t影响度最大的节点且满足$ {{\delta }_{{{C}_{t}}}}(x)>0 $, 即$ {{\delta }_{{{C}_{t}}}}(x)={{\max }_{v\in N({{C}_{t}})}}{{\delta }_{{{C}_{t}}}}(v). $

      步骤4.4.若节点x存在, 则令C_t=C_t∪{x}, 则转步骤4.3.

      步骤4.5.若|C_t|≤3, 令t=t-1, 转步骤4.

      步骤4.6.将C_t的导出子图[C_t]识别为稠密子图.对[C_t]中的每条边xy∈E([C_t]), 使得$ w(xy)=\frac{w(xy)}{\sqrt{|{{C}_{t}}|}}. $

      步骤4.7.对每个节点x∈C_t, 令$ w{d}'(x)=\sum\nolimits_{v\in N(x)}{w(vx)\cdot {{k}_{v}}}, $根据公式(7)计算节点加权度变化率, 若cr(x)≤θ, 则令F=F-{x}; 转步骤4.

步骤5.对每一个稠密子图C_i∈{C₁, …, C_t}, 计算C_i与其他子图的重叠度.若C_i与子图C_j(i < j)节点的重叠度|C_i∩C_j|/min{|C_i|, |C_j|}≥0.5, 则令C_i=C_i∪C_j.

步骤6.对合并后的稠密子图重新编号, 得到中心社区集合为$ \{C_{1}^{(0)}, ..., C_{S}^{(0)}\}. $若s < 1, 则令α=α-0.03, 转步骤2.

步骤7.令集合$ {{T}^{(0)}}=V-\bigcup\nolimits_{i=1}^{S}{{{C}_{i}}}, $μ₀=0.7, t=0.

步骤8.令t=t+1, 对每个社区$ C_{1}^{(t-1)}, ..., C_{S}^{(t-1)}, $执行以下操作.

      步骤8.1. $ C_{i}^{(t)}=C_{i}^{(t-1)}(1\le i\le s), $对任意元素$ v\in N(C_{i}^{(t-1)})\cap {{T}^{(t-1)}}, $根据公式(9)计算b(v, C).如果b(v, C)≥μ_t-1, 则$ C_{i}^{(t)}=C_{i}^{(t)}\cup \{v\}. $

      步骤8.2.令μ_t=μ_t-1-0.1, $ {{T}^{(t)}}=V-\bigcup\nolimits_{i=1}^{S}{C_{i}^{(t-1)}}, $若μ_t≥0.3且T^(t)≠∅, 则返回步骤8.

步骤9.结束, 输出社区集合$ \{C_{1}^{(t)}, ..., C_{S}^{(t)}\}. $

加权网络重叠社区发现算法OCDW给出了基于贪心搜索策略的社区发现算法, 其中, 步骤1~步骤3实现了对网络中节点和边权重赋初值, 平均时间复杂度与网络中的总边数成正比, 即O(c|E|).步骤4迭代实现了种子节点的选择与获得中心社区, 每次迭代会遍历网络中的所有边, 代价为O(|E|).中心社区扩展迭代次数与中心点的选择密切相关, 假设迭代次数为t, 则步骤4的总代价为O(t|E|).步骤5实现了中心社区合并操作, 假设有s(通常s < < |V|)个中心社区, 则时间代价为O(s²).步骤7、步骤8实现了未聚类点分配过程, 时间代价至多为O(|V|).综合以上分析, 算法OCDW的总平均时间复杂度为O(ct|E|+|V|), 其中, c和t是常数.

4 实验与结果分析

在空手道俱乐部(zachary’s karate club)^[24]、海豚社交网络(dolphins social network)^[25]、大学生足球网络(American college football network)^[26]、Polbooks(books about US politics dataset, http://www.orgnet.com/)、Adjnoun^[26]和Email^[27]这6个无权网络数据集以及Les Misėrables^[28]、合作网络(NetScience)^[28]和Hep-th^[29]这3个加权网络数据集上对算法OCDW进行评测, 数据基本情况见表 1.

4.1 评价指标

设OCDW算法的社区发现结果为C={C₁, …, C_s}, 有标签数据集上的原始划分结果为O={O₁, …, O_t}.对集合C_i和O_j(1≤i≤s, 1≤j≤t), 令T_{i, j}=|C_i∩O_j|, $ {{b}_{i}}=\sum\nolimits_{j=1}^{t}{{{T}_{i, j}}}, {{d}_{j}}=\sum\nolimits_{i=1}^{s}{{{T}_{i, j}}}. $本文采用以下指标对算法性能进行度量.

(1) 准确度(Acc)^[30]用来度量两个参照集的匹配程度, 其定义如公式(10)所示.

$ Acc=\sqrt{\frac{\sum\nolimits_{i=1}^{S}{{{\max }_{j}}\{{{T}_{i}}_{, j}\}}}{\sum\nolimits_{i=1}^{S}{{{b}_{i}}}}\cdot \frac{\sum\nolimits_{j=1}^{t}{{{\max }_{i}}\{{{T}_{i}}_{, j}\}}}{\sum\nolimits_{j=1}^{t}{|{{O}_{j}}|}}} $

(10)

(2) 分离度(Sep)^[31]用来度量社区发现结果与原始数据划分的一致性, 其定义如公式(11)所示.

$ Sep=\sqrt{\frac{{{\left( \sum\nolimits_{i=1}^{S}{\sum\nolimits_{j=1}^{t}{Se{{p}_{i, j}}}} \right)}^{2}}}{s\times t}} $

(11)

其中, $ Se{{p}_{i, j}}=\frac{T_{i, j}^{2}}{{{b}_{i}}\cdot {{d}_{j}}} $表示已发现社区C_i与原始社区O_j的一致度.

(3) 度量(F-measure)^[32]通过精度(precision)和召回率(recall)的调和平均值来度量社区发现结果与原始社区的匹配程度, 其定义如公式(12)所示(此处θ=0.25).

$ F-measure=\frac{2\cdot Precision\cdot Recall}{Precision+Recall} $

(12)

其中,

$ \begin{matrix} Precision=\frac{|\{{{C}_{i}}\in C:\, \exists {{O}_{j}}\in O\wedge NA({{C}_{i}}, {{O}_{j}})\ge \theta \}|}{|C|}, \\ Recall=\frac{|\{{{C}_{j}}\in C:\, \exists {{O}_{i}}\in O\wedge NA({{C}_{i}}, {{O}_{j}})\ge \theta \}|}{|O|}, \\ NA({{C}_{i}}, {{O}_{j}})=\frac{{{({{T}_{i, j}})}^{2}}}{|{{C}_{i}}|\cdot |{{O}_{j}}|}. \\ \end{matrix} $

(4) 标准互信息(NMI)通过熵来度量两个数据分布的吻合程度, 此处用来度量社区发现的结果与原始社区划分的吻合程度, 其定义如公式(13)所示.

$ NMI=\frac{2\sum\nolimits_{i=1}^{S}{\sum\nolimits_{j=1}^{t}{{{T}_{i}}_{, j}\log \frac{n{{T}_{i, j}}}{{{b}_{i}}{{d}_{j}}}}}}{-\sum\nolimits_{i=1}^{s}{{{b}_{i}}\log \frac{{{b}_{i}}}{n}}\sum\nolimits_{j=1}^{t}{{{d}_{j}}\log \frac{{{d}_{j}}}{n}}} $

(13)

(5) 调整兰德系数(ARI)是由Hubert and Arabie提出的, 通过统计划分正确的社区中元素的对数来度量算法社区发现结果和原始社区的一致性, 定义如公式(14)所示.

$ ARI = \frac{{\sum\nolimits_{i = 1}^s {\sum\nolimits_{j = 1}^t {\left( \begin{array}{l} {T_{i,j}}\\ 2 \end{array} \right)} } - \frac{{\sum\nolimits_{i = 1}^s {\left( {\begin{array}{*{20}{c}} {{b_i}}\\ 2 \end{array}} \right)\sum\nolimits_{j = 1}^t {\left( \begin{array}{l} {d_j}\\ 2 \end{array} \right)} } }}{{\left( {\begin{array}{*{20}{c}} n\\ 2 \end{array}} \right)}}}}{{\frac{1}{2}\left[ {\sum\nolimits_{i = 1}^s {\left( \begin{array}{l} {b_i}\\ 2 \end{array} \right) + \sum\nolimits_{j = 1}^t {\left( \begin{array}{l} {d_j}\\ 2 \end{array} \right)} } } \right] - \frac{{\sum\nolimits_{i = 1}^s {\left( \begin{array}{l} {b_i}\\ 2 \end{array} \right)\sum\nolimits_{j = 1}^t {\left( \begin{array}{l} {d_j}\\ 2 \end{array} \right)} } }}{{\left( {\begin{array}{*{20}{c}} n\\ 2 \end{array}} \right)}}}} $

(14)

其中, n为网络总节点数.ARI∈[-1, 1], 其值越大, 说明社区发现结果与原始社区越吻合.

(6) 模块性(EQ).本文用Shen等人提出的重叠社区模块性^[15]度量算法在无标签数据集上的社区发现质量, 如公式(15)所示.

$ EQ=\frac{1}{2}\sum\nolimits_{i=1}^{s}{\left( \sum\nolimits_{x\in {{C}_{i}}}{\sum\nolimits_{y(\ne x)\in {{C}_{i}}}{\frac{1}{{{O}_{x}}{{O}_{y}}}\left[{{A}_{xy}}-\frac{{{k}_{x}}{{k}_{y}}}{2m} \right]}} \right)} $

(15)

其中, o_x表示在最终社区发现结果中节点x属于的社区数, A_xy是原始网络邻接矩阵, k_x表示节点x的度数, m是原始网络总边数.

4.2 实验结果与分析

在5个带社区标签的数据集空手道俱乐部(karate)、海豚社交网络(dolphins)、大学生足球网络(football)、Polbooks和Adjnoun上, 将本文算法OCDW与经典的社区发现算法k-dense^[14], CPM^[13], MCODE^[12], HC-PIN^[19], MDOS^[18]和BGLL^[16], 从F度量、准确度(ACC)、分离度(Sep)、标准互信息(NMI)、调整兰德系数ARI这些方面进行比较, 结果如表 2和图 6所示.

尽管k-dense算法和CPM算法在一些指标中表现突出, 然而其运行结果中存在大量的未聚类节点.本文算法OCDW能够将网络中的绝大部分节点进行社区指派, 在5个带标签数据集实验中, 各项指标均名列前茅, 表明其聚类结果与网络原始社区最为接近, 具有较高的综合性能.

在4个无标签数据集Email, Les Misérables, NetScience和Hep-th上, 将本文OCDW算法在模块性及运行时间方面与其他算法进行比较, 结果见表 3.由于算法OCDW在不影响聚类效果的前提下对种子节点的选择范围进行了控制, 因此算法的运行时间也得到了很好的改进.综合考虑模块性和时间性能, 本文算法OCDW算法表现良好.

总体而言, 本文提出的OCDW算法在社区发现过程中综合考虑了网络的拓扑结构和原始权重信息, 能够给出贴近现实网络的社区发现结果, 并且具有较好的时间性能和模块性.

5 总结

本文提出了一种基于种子-扩展策略的面向复杂网络中加权稠密子图的社区发现算法OCDW, 综合考虑网络拓扑结构和现实网络权重, 对网络中的边权重进行定义; 通过搜索网络中的在加权意义下的相对稠密子图得到加权中心社区; 评估未聚类节点与加权中心社区的归属度, 对未聚类节点进行社区指派.通过与经典的社区发现算法k-dense, CPM, MCODE, HC-PIN, MDOS, BGLL等算法在9个真实网络数据集上进行分析比较, 结果表明, 本文提出的算法OCDW能够将网络中的绝大部分节点进行社区指派, 并在F度量、准确度、分离度、标准互信息、调整兰德系数、模块性及运行时间等方面均表现出较好的性能.