新型双模式加权机制及其对网络计算的影响*

李慧嘉 黄照词 王文璇 夏承遗

1) (北京邮电大学理学院, 北京 100876)

2) (天津理工大学计算机与通信工程学院, 天津 300384)

高效率的网络分析方法对于分析、预测和优化现实群体行为具有重要的作用, 而加权机制作为网络重构化的重要方式, 在生物、工程和社会等各个领域都有极高的应用价值.虽然已经得到越来越多的关注, 但是现有加权方法数量还很少, 而且在不同拓扑类型和结构特性现实网络中的效果和性能有待继续提高.本文提出了一种新型的双模式加权机制, 该方法充分利用网络的全局和局部的重要拓扑属性(例如节点度、介数中心性和紧密中心性), 并构建了两种新型的运行模式: 一种是在原始模式中通过增加桥边的权重来提高同步能力; 另一种是在逆模式中通过弱化桥边的权重来提高聚类检测.此外, 该加权机制仅受单一参数 α 的影响, 非常便于调控.在人工基准网络和现实世界网络中的实验结果均验证了该模型的有效性, 可以广泛应用于大规模的现实世界网络中.

1 引 言

复杂网络理论[1−3]是一种分析大规模复杂系统的有力工具, 在过去十年里已经涌现出一系列相关研究成果, 例如聚类划分技术、疾病传播和免疫策略、交通驱动模型、同步分析、级联失效、异常值搜索算法等等.在这些成果中, 拓扑计算和结构分析是研究复杂网络内在特性的最有效途径, 并使得理解网络功能特征成为可能.其中, 最重要的拓扑特征之一是聚类结构[3−8].它在探测聚类时将节点分成若干子集, 子集之间应有清晰的边界约束,同一组成员之间比不同组成员拥有更多的关联.聚类信息有助于理解和分析网络的结构特征和功能特性.

既有研究已提出了许多网络聚类探测算法, 其中Newman等[9,10]提出的模块度函数Q是最为常用的一种探测指标, 用以评价聚类划分[2]的好坏.给定一个划分Pk=(G1,G2,···,GK)=((V1,E1),(V2,E2),···,(VK,EK)), K是聚类的数目, 模块度函数Q[9]定义如下:

其中, L是网络中边的总数目, l (Vs,Vs) 和分别代表聚类s内部以及s与网络中剩余部分之间的边的数目.通常来说, Q值较大意味着该聚类结构较好[11−16].此外, Boccaletti等[17]根据网络中的同步局域化理论提出了一种新的动态聚类检测方法(opinion changing rate model, OCR).他们将改进的Kuramoto同步模型应用到网络的每个节点中, 利用社团内部连接紧密而同步速度快的特征, 利用权重技术使得网络聚类之间的边权逐渐降低, 直到网络聚类划分获得最大的模块度Q值.复杂网络中另一个广泛存在的现象是同步[18−24].在连通网络中, 每个节点通过网络连接, 在动力系统的演化下, 与网络其他节点进行耦合.在足够强的耦合作用下, 节点的状态会随着时间的延长达到同步(状态一致).在许多加权网络中, 可以调整网络的结构和权重, 以提升节点状态获得达到同步的能力.事实上, 已有研究结果表明, 在许多社会和生物网络研究中, 同步行为会在调节系统和组织功能中发挥重要作用.

随着数据收集技术的进步, 诸如互联网、国际贸易网络等现实网络的规模极速增长, 如何处理这些大规模网络已经成为巨大挑战.传统的指数型算法, 甚至是多项式时间算法, 也已难以适用于大规模网络的计算与分析.为此, 研究人员可以尝试另辟蹊径, 如通过改变拓扑性质来提升网络的计算效率.但是在许多实际应用中, 网络结构通常是固定的, 一般不可能对边进行重连.为了克服这一困难,可以为网络连边分配合适的权重, 用来异化不同属性的边, 以达到提升计算性能的目的, 如弱化类间边的权重可以提高聚类探测的效率; 而在信息传播研究中提高重负荷边的流通负载(通常用权重表示)可以降低网络拥塞.

当前, 加权方法已经得到越来越多的关注[21−30],但是总体来说数量还很少, 而且对于不同拓扑类型和结构特性的现实网络, 特定加权算法的效果和性能仍不清楚, 还有待继续分析和验证.而且现有方法(在第2节详细说明)通常仅利用一种节点中心度来定义网络边权, 对于结构相对均匀的网络, 效果不理想; 而且对于相对稀疏的现实网络, 调控参数的影响不明显.另外, 目前加权之后的动态网络中的各种隐藏特征, 如聚类结构和同步能力之间的相互关系, 仍未能得到很好的解释和分析.

本文提出一种新型的双模式加权机制, 用来解决上述问题.从一个简单的无权无向网络开始, 通过加权算法, 利用网络的全局和多种局部信息(包括节点的介数、度、紧密中心度等), 将网络转化为能够提高聚类和同步能力的加权有向网络.这里的加权机制包括两种模式: 在原始模式下, 它通过增加桥边的权重以提高网络的同步能力; 而在逆模式中, 则通过弱化桥边权重以提高聚类的检测效率.该加权机制只受一个参数 α 的控制, 可以很方便地进行调控.对于聚类探测, 通过在人工基准网络(包括GN基准和LFR基准), 以及若干现实网上进行测试, 验证了本文提出的加权机制不仅有助于提高探测精度, 而且还能缓解模块度优化的分辨率限制问题.关于同步性, 通过在具有不同结构特性的无标度网络和Watts-Strogatz网络上进行测试,验证了加权机制在提升网络同步性能上的高效表现.通过比较, 本文提出的加权机制在提高网络计算能力方面要优于其他以往发表的加权方法.

本文第1节和第2节分别梳理复杂网络的基本理论及国内外相关的工作; 第3节引入本文使用的加权机制并提出对应的双模式加权算法; 第4节对加权机制如何增强网络同步性能及其对聚类结构探测的影响进行详细分析; 第5节对加权机制分别运用于人工网络和大量现实世界网络进行试验;第6节对全文进行总结, 并提出一些未来研究中值得深入考虑的问题.

2 相关工作

基于现实数据重构复杂网络是了解和控制复杂系统的基本方式, 而作为网络重构的重要组成部分, 网络加权已经开始得到越来越多的关注.Chavez等[21]提出了一种通过拉普拉斯矩阵的非对角线元素 lij来增强同步能力的加权方案, 其加权后的元素定义如下:

其中, α 为调控参数, Bij是节点i和j之间的边介数中心度, α ≈1 相当于最优的同步能力.与之相似, Wang等[22]提出网络可以被视为是加权无向网络和加权有向网络的叠加.基于现实网络的特征, 他们假设了一个合适的梯度场, 并定义权重

如下:

Charvez等和Wang等提出方法具有一定程度的相似性, 但后者利用的不是介数中心度, 而是基于节点的度.随着 α 值的增大, 网络同步化总是会随之提升.然而, 同时应当注意避免 α 值过高, 否则会导致网络断开和分裂.为了解决这个问题, Jalili等[23]在节点介数中心度方法的基础上提出了一种新的加权方法, 其中权重定义如下:

其中, BjB 和 BijB 分别代表节点j与边 eij之间的介数中心度.该加权机制被用来提高网络的同步性能.但是上述加权算法仅仅利用一种节点中心度来定义网络边权, 对于结构相对均匀的网络, 效果不理想.而且对于相对稀疏的现实网络, 调控参数的影响不明显.

最近, Khadivi等[31]讨论了一种新型加权机制, 用以缓解网络聚类中的模块度缺陷, 即分辨率极限[32]和极端限制[33]等问题.该加权机制利用了网络的局部和全局信息, 其中每条边的权重定义如下:

其中, cij定义为共同邻居比例, Bij是边介数中心度.利用Clauset-Newman-Moore方法[10]进行试验, 验证了该加权机制能够显著地优化社团探测的速度与精度.但是仿真分析也表明, 当网络规模较小时, 其加权效果不明显.而且虽然该方法可以用来加强社团内部的团内边, 但是却无法明显降低团间边的权重, 从而阻碍了该加权算法的进一步应用.另外现有的网络加权方法还包括模拟退火算法[25]、文献计量方法[26]、随机游走算法[27]、级联动力学方法[28]、变分贝叶斯方法[29]和概率推断方法[30]等.但总体来说, 当前加权算法的数量还很少, 而且对于不同拓扑类型和结构特性的现实网络, 特定加权算法的效果和性能仍不清楚, 还有待继续分析和验证.

3 复杂网络基本理论

3.1 基本定义

假设 G (V,E) 是一个无向连通图, V为节点集,E为边界集.这里考虑三个最常用的衡量拓扑结构和信息流通的中心度指标.

节点度节点度 ki[34]表示节点i相连的边的数量, 根据邻接矩阵 A =(aij) 将其定义为

其中, aij是节点i和节点j之间的邻接矩阵值.还可以将节点度扩展到加权网络得到节点强度的概念.

节点强度节点强度 si[35]是节点i相关联的边的权重总和, 定义如下:

其中, wij为节点i和节点j之间的边的权重值.

介数中心度一个节点在信息传播中的重要性可以通过其介数中心度[36]来计算, 定义为

其中, σij(u) 为节点i和节点j之间的通过节点u的最短路径的数量, σij是节点i和节点j之间的最短路径的总数量.介数中心度的概念还可以拓展到边.边 eij的介数中心度 Bij表示通过该边的最短路径的数量, 在信息传播研究中常用来表示流通负载.

紧密中心度(closeness)节点i的紧密中心度[36]定义为一个网络中其他节点到节点i的平均距离的倒数

其中, Dij是节点i和节点j之间最短路径的长度;Ci用来测量一个节点与其他节点的(平均)紧密程度.为了定义该中心性与最短路径的直接(正比例)关系, 还可以将其定义为 Ci的倒数:

k-邻域图k-邻域图[37,38]定义为将节点i和节点j连接起来的最短路径上的点的集合, 其中i和j之间的最短距离值小于等于k.由于邻域关系是不对称的( i →j ), 因此根据k-邻域图的定义得到的可能是一个有向子图.在特定网络中, 节点i的k-邻域图被构造为特定的相似性度量(这里指最短路径距离)下显示与i最相似的子图.然而在大多数应用中, k的值难以直接给定, 以致其应用领域受到限制.

3.2 双模式加权算法

1)通信邻域图

受到k-邻域图定义的启发, 为了增强网络信息流, 本文提出了一个新的拓扑定义——通信邻域图(communication neighbor graph, CNG), 并进一步提出一种新的加权算法.通信邻域图的具体定义如下.

通讯邻域图假设 G (V,E) 是一个无自循环的无向网络, 其中节点的数量 | |V||=N.对于G中的节点来说, ζij是节点i与节点j之间的最短路径(路径为节点序列集合).节点i通过节点j的通信邻域图用 Πi→j表示, 其定义为: 给定节点u, 如果满足通过节点i与u之间的最短路径长度大于节点j与u之间的最短路径长度, 即 l (ζiu)> l (ζju) ,那么节点u属于 Πi→j.如果节点i和节点u之间存在一条以上的最短路径, 那么就认为 ζiu是其中任意一条.根据通信邻域图CNG的定义, 对于特定节点u, 假定节点i与节点u之间有边相连, 如果 ζiu经过节点j, 那么节点u就属于 Πi→j.

注意到通信邻域图CNG是非对称的, 即一般情况下 Πi→j与 Πj→i是不同的.对于任意一对相邻的节点i和j来说, 节点j一定属于 Πi→j.另外, 任一节点属于且仅属于节点i的一个通讯邻域图.图1(a)给出了两个相邻节点的通信邻域图的例子.当网络是稠密且规模不大时, 该定义是非常直观的.

图1 (a)节点4和节点5之间边对应的通讯邻域图; (b)网络中的桥边Fig.1.(a) Communication neighborhood graph corresponding to the edge between node 4 and node 5; (b) bridge side in the network.

2) 加权算法

如果边权与流量成正比, 那么为了增强连边上的信息流, 需要研究最有可能出现瓶颈的桥点和桥边.因为桥点和桥边数目较少且处于两个类之间,它们往往无法承载端点需要发送的全部信息, 如图1(b)所示.如果节点具有大的度、介数中心性和紧密中心性, 那么它更有可能具有高信息吞吐量,因此这些节点及其所连的边更可能成为瓶颈.在本文模型中, 这种可能性被假设为与单一实数成正比, 即定义图中每个节点的 γ 值.

在给定通信邻域图CNG的定义后, 接下来介绍一种新型的加权机制.令 γ (u)∈R 表示属于Πi→j中节点u的一个特定指标,Γ(Πi→j)={γ(u1),γ(u2),···,γ(uk)} 且 是 Πi→j中 所 有 节 点 的 γ 值集合, 其中 u ∈Πi→j.那么, 本文的加权机制定义如下:

其中, ψ 为任意实数集中的单一实数相关的函数.这是一种具有代表性的加权方法, 可以用来加强与网络通信相关的多种计算与应用.

本文加权算法旨在重点增强瓶颈节点的各种中心性值, 使其与加权权重成正比, 以便增强网络的整体通信能力.定义 ψ 为一个集合所有元素的加和, 即如果 X ={x1,x2,···,xN} , 那么ψ(X)=定义节点u的加权参数为

其中, α ∈R , 且 ku, Bu和分别为网络G中节点的度、介数中心性和紧密中心度 Cu的倒数.ε 设定为0.01, 以避免 γ 值为0.设计加权参数 γ 是为了反映瓶颈节点u的各项参数, 包括度 ku, 介数中心性 Bu和紧密中心度 Cu, 如果各项参数比较大, 则γ也比较大, 节点u成为瓶颈节点的概率也会很大.那么, 节点j到节点i的权重为

其中 Πi→j表示节点i通过节点j的通信邻域图.(12) 式表示的加权机制的原理为当传输线路i→j 比较重要时, 其通信邻域图 Πi→j的规模也会 相 应 比 较 大.则 当 α >0 时, (12)式 的 分 子 项和相应的权重 Wij也会相应比较大,从而实现了加权机制增强重要通信边的权重的目的.这里, 分母项的设置是为了实现标准化, 权重矩阵的对角线元素被设置具有零行和属性, 即

在加权策略((12)式)中, 分母的标准化项使得入度更加均匀.另外, γ 函数((11)式)增强了以高 γ 值节点为起点的路径, 并且进一步使得网络流量更加趋向于流向这类节点.这个过程使节点的负载分配更加倾向于平均.总而言之, 本文提出的加权策略使负载分布更加均匀化, 同时降低了平均路径长度.本文加权算法具体流程如算法1所示.本算法由于需要计算节点的介数、度、紧密度三种中心性度量, 时间复杂度分别为O(n3), O(n2)和O(n3), 因此总的时间复杂度为O(n3).

算法1网络加权算法流程

输入: 网络G, 其节点数为n, 边数为m; 加权参数α.

输出: 网络加权矩阵W.

1） 根据“通讯邻域图”的定义计算网络中每条边的通讯邻域图;

2） 计算 ku, Bu和 C ～u, 分别为网络G中节点的度、介数中心性和紧密中心度 Cu的倒数;

3） 根据(6)式和(11)式计算节点u的加权值γ(u);

4）根据(12)式更新网络中边的加权值wij.

需要说明的是, 本文提出的加权机制是使用虚拟方式改变拓扑结构, 但是仅通过加权来达到网络重连的效果是不大可能的.例如, 在环形规则网络中, 所有节点的 γ 值是相等的, 加权机制并不能增强网络的传输容量.因此, 本文的加权机制旨在通过降低瓶颈节点的限制, 使网络层次结构趋于平坦以提高传输容量.这种加权机制对具有非均匀层次结构和瓶颈节点的网络(如无标度网络)来说很有效率.反之, 均匀网络或无瓶颈节点的网络则不具备这种加权机制的优势.此外, 本文的加权策略还有一个重要优点: 只受一个参数调控, 即参数 α , 可以用来控制加权权重的异质程度(即非均匀性).这里有三种典型的情况:

当 α >0(α<0) , 在通信邻域图中, 具有高ξ值的节点对信息传输会有更多(更少)的贡献.特别地, 在同质(均匀)网络中, 节点呈现出均匀的负载和度分布, 那么节点的 ξ 值和随之得到的加权值也会变得均匀.在这种情况下, 改变 α 不会导致权重和网络传输效率发生显著变化.类似地, 当网络负载分布和度分布是异质(非均匀)时, 不同的 α 会导致权重和网络传输效率发生显著变化.因此, 在异质(同质)网络中, α 会有更多(更少)的影响.

当 α =0 时, γ 值将退化为对所有节点u都有γ(u)=1.值得注意的是, 这种情况与无权网络或者标准化仅仅应用于节点度的情况不同.在这种情况下, 仅考虑每个通信邻域图的节点数量, 它在γ值分布的方差较小的网络中将会相当有效, 即 γ 值的同质性.

由于受标准化因子和通信邻域图节点数目的影响, α <0 并不会产生负值, 但是会使得信息传输能力下降(即具有高 ξ 值的节点对信息传输会有更少的贡献).根据本文框架, 我们提出了利用转置权重矩阵以降低传输能力的逆加权方案.为了能够更方便地转换, 权重矩阵被定义为

其中, 参数 0 ≤ρ≤1 , 表示传输程度.例如, 当ρ=1 意味着高传输流量, 而 ρ =0 意味着低传输流量.

逆模式加权机制在(12)式的加权机制中,设定参数 α <0 , 定义为逆模式加权机制.根据(12)式, 在逆模式加权机制中, 即具有高 ξ 值的节点对信息传输会有更少的贡献, 从而会使得网络流量更加趋向于避开这类节点, 使得信息传输能力下降.为了能够更方便地转换, 权重矩阵被定义为(13)式.逆模式加权算法如算法2所示.

算法2逆模式加权算法流程

输入: 网络G, 其节点数为n, 边数为m; 加权参数 α <0 ; 传输程度参数0≤ρ≤1.

输出: 网络加权矩阵W.

1) 根据“通讯邻域图”的定义计算网络中每条边的通讯邻域图;

2) 根据(11)式计算节点u的加权值 γ (u) ;

为了测试参数 α 的影响, 将其应用到著名的BA网络中, 分别考虑 α =2 和 α =6 两种情况, 结果如图2所示.可以看出, 受加权机制的影响, 节点强度和节点度会出现明显异化.此外, 当α=6时, 节点强度和节点度的关系的分布相较于α=2时更加分散.这是因为 α 的值越大, 更多的边会得到较大的权重值.该结果与前面加权机制的分析相符合.因此, 通过本文的加权策略, 权重分布、节点强度以及度的关系均依赖于参数 α 的值, 该加权网络比相应的二进制无权网络提供了更多的信息.

图2 参数α取不同值时BA模型中节点强度s和节点度k之间的关系(N = 5000) (a) α =2 ; (b)α=6Fig.2.Relationship between node strength s and node degree k in BA model (N = 5000) with different values of parameter α: (a) α =2 ; (b) α =6.

4 复杂网络的属性分析

许多研究[20,39,40]发现, 网络中信息传输的难易程度可以解释为同步能力, 并且它们都被网络拓扑矩阵的特征值所限制.由此直接引出本文提出的加权方案, 它可以试图通过改善信息流以增强同步能力.然而, 并不是所有的应用都需要提高同步能力,有些反而需要降低, 比如降低网络的同步性有助于辨别网络中的聚类结构[17].本节将分析加权机制对网络同步能力的作用, 并进一步分析其对聚类探测及其效率的影响, 从而有效验证加权机制的高效性.除了同步和聚类分析, 本文加权机制还可以有效应用于网络流行病传播关键路径识别、免疫策略分析、演化博弈分析、路由策略设计、交通拥塞预防等多个方面.

4.1 同步性分析

首先说明加权机制增强网络同步性能的原因.设 λ1≤λ2≤,···,≤λN为加权矩阵W的N个特征值.根据文献[41], 矩阵W的特征值比 λN/λ2越小, 则意味着该网络具有更大的同步能力.如上所述, 网络通信的能力可以被解释为在网络中信息流动的难易程度.更确切地说, 可以将动态方程写作:

通过网络加权, 总是可以将W的对角线元素标准化为1, 从而防止任意大或者任意小的耦合值.权重矩阵W是不对称的, 并且一般而言非对称矩阵的特征值非常复杂.下面的推论证明了非对称矩阵W具有有界的实数特征值.

推论1加权机制((12)式)得到的权重矩阵的所有特征值是实数, 且值介于0—2之间.

证明权重矩阵W对应的拉普拉斯矩阵 Lw,写作 Lw=MQ , 其中

Q是一个零行和矩阵, 具有负非对角项, 即Qij=−ψ(Γ(Πi→j)).容易看出, W的特征值λi(i=1,···,N) 与 M1/2QM1/2的特征值相等, 即是实数且非负的, 且最小特征值 λ1=0.另一方面,Gerschgorin循环定理[42]证明了 Lw的每个特征值都在一个半径为1的圆的内部, 因此0=λ1≤λ2≤,···,≤λN≤2.证明完毕.

接下来引入超中心节点的定义.

超中心节点网络中具有最大 γ 值的节点被称为网络的超中心节点.

定理1令 G (V,E) 为一个无向网络, 对于每一对节点u和v, 选择它们之间的最短路径 S Puv, 并根据通信邻域图的定义确定通信邻域图运用加权机制((12)式).如果该邻域图具有唯一的超中心节点, 那么当 α →+∞ 时, 通过移除超中心节点的输入边, 剩余网络将会退化到一个以超中心节点为根节点的有向生成树, 因此总有一条有向路径可以从超中心节点通向其他所有节点.

证明根据(12)式, 当 α →+∞ 时, 可以得到ψ(Γ(Πi→j))≈max{Γ(Πi→j)} , 从而有现在, 假设节点 u∗是唯一的超中心节点, 即网络中具有最大的 γ 值的节点.当 α →+∞ 时, 如果 u∗∈Πi→j并收敛于0, 权重 Wij将收敛于1.换言之, 每个节点∗只保持一条边连接网络中具有最大 γ 值的那个节点.由于 u∗的输入边被删除了, 也就是所有到u∗的输入边的权重都等于0, 仅保留N – 1条有向边.因此, 从节点 u∗到网络中所有其他节点都有一条有向路径, 且仅保留有N – 1条边, 由此得到的网络结构是一个有向生成树, 其中具有最大 γ 值的节点是根节点.证明完毕.

推论2根据参考文献[41], 定理1中得到的有向生成树的特征值比 λN/λ2=1 , 意味着该网络具有最大的同步能力.简单来说, 由于生成树的根拥有最大的 γ 值, 因此在所得的生成树中, 大多数节点都在树的较低层次上, 也就是说大多数节点与根节点的平均距离较短.值得一提的是, 当α→+∞时, 如果不移除根节点的输入边, 那么特征 值 比 λN/λ2=2 , 也就是说,0=λ1<λ2=λ3,···,=λN−1<λN=2.如果超中心节点并不唯一, 当 α →+∞ 时, 网络将退化为有向图, 其中所有超中心节点都属于边权重相等的团.此外, 该团中的任意节点都能与图中的所有其他节点相连, 即对于网络中的每个节点来说, 都有一条有向路径通向每个超中心节点.基于上述可以发现, 只有参与这些路径的边被留下来, 而其他的边都将会消失.

4.2 聚类结构分析

前文已经提到, 在一些应用中, 有时候还需要降低同步能力, 如辨别网络中的聚类结构[17].本文提出的加权策略对聚类结构探测也有很强的影响,并且可以进一步发现聚类结构与同步性之间的隐藏关系.首先给出聚类结构的弱定义:

聚类结构的弱定义Radicchi等[43]分别从弱定义和强定义这两方面给出了衡量聚类结构的量化标准, 其中弱定义被认为是一个子图集合能够成为聚类结构的最弱标准, 即聚类是网络的子图集合, 子图内部的边的密度高于子图之间的边的密度.给定一个网络 G =(V,E) , 其中V是节点集,E是边界集, A =(aij) 为 其邻接矩阵, 令Vs⊂V为一个特定子图, Vs=VVs为网络其余的节点集,那么在弱灵敏度条件下 Vs能够成为一个聚类的条件是:

推论3如果 eij是一个类间边, 那么邻域图Πi→j和 Πj→i很可能是两个相邻的聚类.此外, 在极端情况下, 如果网络是二划分且 eij是唯一的类间边, 根据聚类结构的弱定义, Πi→j和 Πj→i将是严格的网络聚类.

证明:根据弱定义, 如果一个网络拥有聚类结构, 由于存在高密度的类内边, 一个随机游走者将会在一个聚类中停留很多的时间.这意味着一个节点到同一聚类内的节点的路径长度通常比到不同聚类的节点的路径长度短.如图2中 α =2 时,Πi→j中的节点到节点j的路径长度比到节点i的路径长度都要长.相反, Πj→i中的节点到节点i的路径长度比到节点j的路径长度长.因此可以得出结论: Πi→j和 Πj→i很可能是两个不同的聚类.此外, 如果 eij是唯一的类间界, 根据聚类结构的弱定义, 这个结论是严格的.证明完毕.

为了阐明加权机制对聚类结构的影响, 逐步增大 α 的值并在示例网络中删除 Wij<0.5 的 边.如图3所示, 当 α 值从2增加到4, 聚类结构会显著增强.

图3 应用加权机制后网络的动态演化示例图Fig.3.Example of dynamic evolution of network after applying weighting mechanism.

根据弱定义, 比率 R =lout/lin在解决模块度优化问题上发挥着十分重要的作用.为了满足弱定义的标准, 这个比率的区间应该为[0, 2].

定理2令 lout为类间边的数量, lin为类内边的数量, 那么比率 R =lout/lin可以用来有效量化网络中的聚类结构.

证明对于特定的网络G, 其相对的超图G∗定义为一个有向加权的C团结构, 其中的每个节点对应于G的一个聚类.在 G∗中, 节点r和节点s之间的边用来加权, 其中代表G中聚类r和聚类s之间的团间边数量,代表聚类r内部边的数量.G∗对应的 C ×C 拉普拉斯矩阵F={Frs} 是不对称的, 但是可以变换为 F =∆Θ , 其中∆={∆rs}是一个对称的零行和矩阵, 其非对角元素为对角元素为且那么可以将F写成:

因为F是零行和的, 所以F的谱元素都是非负实数, 其中F的最小特征值, 次小特征值

根据谱方法和信息论[42,44−46],能够量化超图的连通性, 从而衡量不同聚类的性质和互相关联的程度.应该注意到,已经过标准化, 所以它应该是一维的.这里, 可以得出.特殊情况下, 如果C个聚类都具有相等规模 Nc=N/C ,那么类内边数量和类间边数量对所有聚类来说都是一样的.此时, 由和可以得到由∆=CI/lin, 可以得到证明完毕.

接下来将展示本文的加权策略如何化解聚类探测中的分辨率限制问题, 以使优化方法更加有效.Fortunato和Barthelemy[32]发现了聚类探测的分辨率限制问题, 表明对于优化模块度Q((1)式)的算法, 如果的取值区间不在[0, L]内, 那么模块度优化算法将无法检测到这些聚类.直观地看, 如果引入一种加权策略, 能够有效扩大这个限制区间, 那么许多优化算法就能够在一个较大的限制范围内探测到准确聚类.为了分析简便, 假设权重之和边的个数L保持相等.这里, 加权网络中所有的量都以上尖号为区分, 即.首先, 回顾一个关于聚类规模边界的定理[32].

定理3聚类规模对模块度函数Q的影响有如下限制:

其中, R =lout/lin.如果合并聚类i和聚类j不能提高模块度函数Q的值, 那么对于聚类i和聚类j的规模有如下约束条件[31]:

对所有j, 有

对所有i, 有

总结来说, 如果将本文的加权策略应用于网络中, 那么能够通过优化算法探测出更大或更小的聚类, 从而可以有效地降低分辨率限制的问题.

5 实 验

本节将上述加权机制运用在人工网络和大量现实世界网络中.结果表明, 这种加权机制可以分别利用原模式和逆模式来提高网络同步能力以及增强聚类结构检测能力.

5.1 同步性

在本文提出的加权策略中, 唯一的调整参数是α.通过改变 α 参数, 可以控制权重值的异质性和特征值比 λN/λ2.

1)人工基准网络

这里利用无标度网络[2]和Watts-Strogatz小世界网络[1]作为基准模型网络, 并将本文加权机制应用其中.无标度网络的节点度分布服从幂律特性, 即该模型有两个参数, 其中节点初始边数 k0控制平均度, 即 〈 k〉≈2k0.另外, 参数 β 调整控制网络度分布的异质性, 当 β 增加时, 网络的异质性会减少到特定程度.

图4给出了在无标度网络上的实验结果, 其中数据点为50次实验结果的平均值.图4(a)为特征值比 λN/λ2和参数( α , 〈 k〉 )的对应关系, 这里网络的平均度用 〈 k〉 表示.设 α =1 , 对于所有的平均度〈k〉 , 可以得到 λN/λ2<2 , 这比文献[23]的最优情况还要好, 而又优于文献[21, 22, 39]的研究结果.对于较大的平均度 〈 k〉 , 权重分布和度分布的同质性增加, 这表示 γ 值将更加均匀, 而 α 的影响也会较弱.所以, 无论 α 的大小, 加权过程都将显著提高网络同步能力.对于平均度 〈 k〉 较低的网络, 由于网络中异质性较高, 因此较大的 α 将会得到更好的结果.接下来研究网络的异质性(非均匀性), 该性质可以用参数 β 来衡量.已有研究表明, 网络度分布的异质性是影响同步性能最重要的因素之一.无标度网络中特征值比 λN/λ2和参数 α , β 的关系如图4(b)所示.对于不同的 β , 因为无标度特征导致节点度的非均匀性, 参数 α 的影响作用会更加显著.此外可以看出, 随着 β 值增加, 网络非均匀性降低,得到的加权网络的同步性会逐渐变差.

图4 (a) 无标度网络中 λ N/λ2 与( α , 〈 k〉 )的对应关系(N = 500, β =0 ); (b)无标度网络中 λ N/λ2 与( α , β )的对应关系(N = 500, 〈 k〉=4 )Fig.4.(a) Corresponding relationship (N = 500, β =0 ) in scale-free networks between λ N/λ2 and ( α , 〈 k〉 ); (b) Corresponding relationship (N = 500, 〈 k〉=4 ) in scale-free networks between λ N/λ2 and ( α , β ).

接下来将加权机制应用到Watts-Strogatz网络中, 相对于无标度网络来说, Watts-Strogatz网络的节点度分布是均匀的.该网络受两个参数控制, 即平均度 〈 k〉=2k0, 和重连概率P.图5给出了在Watts-Strogatz网络中应用本文加权算法的结果, 图中数据点为50次实验结果的平均值.其中, 图5(a)为特征值比 λN/λ2随参数 α 和网络平均度 〈 k〉 的变化情况.和无标度网络相似, 当平均度〈k〉 增加时, 网络的异构程度随之降低 α , 从而降低α的贡献程度.可以看出, 当平均度 〈 k〉 非常高时,α对特征值比 λN/λ2几乎没有影响.图5(b)为特征值比 λN/λ2随参数 α 和重连概率P的变化情况.当P较小时, 网络度分布几乎是均匀的, 但是节点的负载分布却是极度非均匀的.这是由于极少数的重连边可以被视作捷径, 它们承担着很高的负载,导致负载的分布具有高度的不均匀性.随着重连概率P的增加, 网络重连边的数量会逐渐增加, 负载分布会因此变得越来越均匀.在这种情况下, 虽然度分布的方差会逐渐增加, 但仍不足以提升 γ 值的异质程度.因此, 增加P会使 γ 值分布更加均匀,从而降低加权机制的贡献程度.特别地, 当P = 1时, Watts-Strogatz网络等同于完全随机图.

图5 (a) Watts-Strogatz网 络 中 λ N/λ2 与( α , 〈 k〉 )的 对 应 关 系(N = 500, P = 0.1); (b) Watts-Strogatz网 络 中λN/λ2与( α , P)的对应关系(N = 500, 〈 k〉=4 )Fig.5.(a) Corresponding relationship (N = 500, P = 0.1) in Watts-Strogatz networks between λ N/λ2 and ( α , 〈 k〉 ); (b) corresponding relationship (N = 500, 〈 k〉=4 ) in Watts-Strogatz networks between λ N/λ2 and ( α , P).

2) 现实世界网络

虽然现实世界极其复杂以致无法获取全部信息, 但是为了充分地进行验证, 我们将9个不同的加权机制应用到大量现实世界网络中并进行对比,包括Chavez方法[21]、Wang方法[22]、Jalili方法[23]、Khadivi方法[31]、模拟退火(SA)算法[25]、随机游走(RW)算法[27]、变分贝叶斯(VB)算法[29]、概率推断(PL)方法[30]和本文方法, 结果列在表1中,其中设定 α =4.可以看出, 本文使用的加权机制的性能超过了其他所有的加权方法.值得一提的是, 对于所有的现实世界网络, 随着 α 的增加, 特征值 λN/λ2比都将收敛于2.

表1 在现实世界网络中使用8种不同加权策略的实验结果对比, 其中RW代表随机游走方法, SA代表模拟退火方法,VB代表变分贝叶斯方法, PL代表概率推断方法Table 1.Comparison of experimental results using eight different weighting strategies in real world networks, in which RW represents random walk method, SA stands for simulated annealing method, VB stands for variational Bayesian method, PL stands for probability inference method.

5.2 聚类探测

1)人工基准网络

本文采用两个著名的人工基准网络, 即Girvan-Newman (GN)基准网络和Lancichinetti-Fortunato-Radicchi (LFR)基准网络, 用以评估加权机制对社区探测效率的影响.其中, GN基准测试[9,11]已经广泛应用于对不同聚类算法的效率评估.GN网络共包括128个节点, 这些节点被分配到4个聚类中, 每个聚类包含32个节点, 每个聚类内部点之间连边和与类外节点连边的概率分别为 pin和 pout.因此, 对于每个节点, 它们在聚类内部的边的个数和与其他类节点关联的边的期望分别为 zin=31pin和 zout=96pout, 可以看出 zin+zout=16.

更进一步地, Lancichinetti等[47]提出了LFR基准网络, 它可以通过调整相关参数来符合现实网络中的无标度特征.在该基准网络中, 节点的度分布和聚类规模遵循幂律分布.此外, 还需要设定一些其他参数, 包括节点最大度、节点平均度、节点总数、聚类最大规模和最小规模以及最重要的混合参数 µ.混合参数 µ 的取值区间为[0, 1], 决定了LFR基准图的聚类模糊性程度: µ 越大, 聚类就越难被正确划分.可以看出, GN基准网络是LFR基准网络的一个特例.由于GN基准网络和LFR基准网络的社团都是预先给定的, 而不同划分算法得到的结果是不同的, 因此这里利用正确率R(正确划分的节点和全部节点的比值)衡量划分的正确性.

首先, 将加权策略将应用于GN基准网络.在图6(a)的原加权网络中, α 取2和4, 在逆加权网络中, α 取–2和–4, 数据点为50次实验结果的平均值.图6(a)给出了在GN基准网络上应用加权策略前后的平均正确率R的对比.可以看出, 当α=4 和 α =2 时, 加权策略的原模式都提高了平均正确率R, 而相应的两个逆模式 ( α =−4 和α=−2 )都会降低平均正确率R.与 α =4 的情况相比, 在 α =2 的情况下, 平均正确率R会下降约2—3倍.而且在逆模式中, 当 zout≤6.5 时,α=−4的情况与 α =−2 相比, 平均正确率R会降低2倍以上.

其次, 在LFR基准网络上进行分析, 其中参数设置如下: 节点数量为1000、平均度为20、最大节点度为50、幂律分布指数为2、混合参数 µ 在区间[0, 0.5]内变化.从图6(b)可以看出, 加权策略的原模式会显著提高平均正确率R, 而相应的逆模式会降低平均正确率R.与 α =4 的情况相比, 在α=2的情况下, 平均正确率R会下降约4—5倍.另外, 在逆加权模式也会得到相似的结果.比较两种基准网络, 对于提高平均正确率R, 加权策略在LFR基准网络中会取得更好的效果.

图6 (a) GN基准网络中使用加权机制(逆加权机制)前后平均比率R的对比; (b) LFR基准网络中使用加权机制(逆加权机制)前后平均比率R的对比Fig.6.(a) Comparison of average ratio R before and after using weighting mechanism (inverse weighting mechanism)in GN benchmark network; (b) comparison of average ratio R before and after using weighting mechanism (inverse weighting mechanism) in LFR benchmark network.

再次, 为了展示加权机制对聚类探测的影响,首先利用具有不同 α 值的加权机制对网络赋权, 然后利用一些著名的聚类算法运行并测试其准确性.这里使用在信息论中被广泛研究的标准化互信息(normalized mutual information, NMI)来衡量聚类结果的准确性[40].NMI位于区间[0, 1]内, 其值的大小表明真实聚类和模型结果之间重叠的比例.特别地, 当NMI的值为1时, 算法结果与真实聚类完全相同, 具有最高的划分效率.真实划分X和模型结果Y之间的标准化互信息NMI的数学定义为

其中, cX和 cY分别表示真实划分X和模型结果Y中的聚类数量.在(21)式, Nij代表真实划分中聚类i和实验结果中聚类j之间重叠的节点数量,Ni和 Nj分别表示矩阵N中第i行和第j列值的总和.

图7 (a)和图7(b)给出了利用两种著名算法,即模拟退火法(SA)[48]和Duch-Arenas法(DA)[49],在运用加权机制的网络上的实验结果, 图中数据点为50次实验结果的平均值.其中, SA算法被证明是效果最好的聚类算法之一, 然而其计算复杂性也较高.与SA相比, DA不仅在模块化优化方面具备一定可靠性, 而且计算过程也相对简单.从图7(a)和图7(b)可以看到, 当 α 值从–2降低到–4,逆加权模式对应的NMI值越来越高, 要优于无权网络.相反, 在原加权模式中, 当 α 值从2增加到4,加权网络的NMI相对于无权网络的NMI却越来越少.这些结果均验证了本文的加权策略的有效性.此外, 通过比较两种方法发现, 图7(a)中α=4( α =−4 )和 α =2 ( α =−2 )两 种 情 况 的NMI差异区间小于图7(b).这可能是因为, 即使是在无权网络中, SA都拥有更高的精确度, 难以通过加权策略提高它的表现.但是对于DA来说, 通过提高α, 加权机制能够大幅提高它的计算精度.

图7 在LFR网络中运用加权机制(逆加权机制), 当取不同的 α 值时, 利用(a) SA算法和(b) DA算法后NMI的计算值Fig.7.Weighted mechanism (inverse weighted mechanism)is used in LFR network.When the α value is different, the NMI value is calculated by using (a) SA algorithm and (b) DA algorithm.

此外, 本文还考虑了聚类规模的影响, 验证结果如图8所示, 图中数据点为50次实验结果的平均值.考虑两种不同聚类规模条件下的LFR基准网络, 其中, 每个聚类的节点数量在10—50之间为小聚类网络, 在20—100之间为大聚类网络.为了增强这两种LFR基准网络的可比性, 规定它们的区别仅限于聚类的规模大小, 其他方面的性质则完全相同.图8验证了在逆加权网络中, SA和DA算法的准确性都得到提升.此外, 通过比较不同规模LFR网络的聚类结果可以看出, 大聚类网络中两种算法的精确度更低, 这可能是因为小聚类网络中具有更多的类间边, 而类间边更可能是被加权的.并且通过比较两种方法, 图8(a)显示的小聚类和大聚类LFR网络(无论是逆加权网络还是加权网络)之间的NMI区间差距小于图8(b), 原因与图7相同, 完美证明了本文加权机制的有效性.

图8 在LFR网络中运用加权机制(逆加权机制), 当α=4( α =−4 )并考虑聚类规模时, 利用(a) SA算法和(b) DA算法后NMI的计算值Fig.8.The weighted mechanism (inverse weighted mechanism) is used in LFR network.When α = 4 (α = –4) and considering the cluster size, the NMI calculated by (a) SA algorithm and (b) DA algorithm.

2) 现实世界网络

进一步将加权策略应用到现实世界网络中, 结果在表2中列出.这里使用了7种广泛使用的网络, 并标识了相应的文献出处.为了便于比较,提供了关于7种网络已发表方法中的最优模块度Q值[56].本文计算了当 α =4 时三种代表性算法,即SA[48], DA[49]和CNM[10]的加权前后模块度Q值, 其中“/”左右表示加权后和加权前的模块度Q值, 结果如表2所列.这三种算法的精确度虽然并不处于最顶级的行列, 然而正如表2所列, 在应用加权策略后, 结果非常接近已发表的最优值, 并且计算过程更加简便.

表2 在不同现实网络使用加权策略得到的实验结果, 其中“/”左右表示加权后和加权前的模块度Q值Table 2.Experimental results are obtained by using weighting strategy in different real networks, where /’s left or right represents the modularity Q value after or before weighting.

进一步将9种加权策略应用到现实世界网络中, 包括Chavez方法[21]、Wang方法[22]、Jalili方法[23]、Khadivi方法[31]、模拟退火(SA)算法[25]、随机游走(RW)算法[27]、变分贝叶斯(VB)算法[29]、概率推断方法[30]和本文方法, 用以对比不同加权方法的聚类效果.聚类算法统一使用CNM方法[10],并计算当 α =4 时的模块度Q值.结果列在表3中, 可以看出, 本文所使用的加权机制的性能超过了其他所有的加权方法, 从而验证了本文加权算法的高效性.

表3 在现实世界网络中使用不同加权策略的实验结果对比, 这里网络聚类算法利用CNM算法, 其中RW代表随机游走方法, SA代表模拟退火方法, VB代表变分贝叶斯方法, PL代表概率推断方法Table 3.Comparison of experimental results using different weighting strategies in the real world network.CNM algorithm is used as the network clustering algorithm, in which RW represents the random walk method, SA represents the simulated annealing method, VB represents the variable dB method, and PL represents the probability inference method.

6 结 论

随着“大数据”技术的不断涌现和发展, 如何处理大规模网络已经成为了巨大的现实挑战[57,58].同时, 作为一个开放性问题, 提高网络同步性能或聚类探测的算法效率往往非常困难.为此, 本文提出一个新型双模式加权机制, 通过加权改变网络拓扑结构来提高同步性能或聚类探测的算法效率.该加权机制包括两种模式: 一是通过提高桥点的权重以增强同步能力的原始模式: 二是通过减少桥点的权重以提高聚类探测效率的逆模式.这种加权机制仅受一个参数 α 的影响, 因此非常便于实施.通过在人工基准网络和现实世界网络上的实验分析, 检验了模型的有效性和高效性.特别地, 通过比较发现,本文提出的加权策略在效率上优于以往发表的提升网络计算效率的加权方法.

在今后的研究工作中, 仍有一些问题值得深入探讨.比如工程、信息领域应用中的群体演化博弈和平均一致性问题, 可能在无向网络中更容易分析和理解, 加权有向网络并不一定是最佳选择.另外,如何在拥有数百万甚至更多节点的超大规模网络中进行研究分析, 也需要进一步深入探索.

感谢吉林大学刘大有教授、中国科学院数学与系统科学研究院章祥荪研究员、中央财经大学刘志东教授对本文提出的建设性建议.