基于信息传播影响因素的边重要性度量方法*

徐 曼，鲁富荣，马国帅，钱宇华

(1.山西大学大数据科学与产业研究院,山西 太原 030006; 2.计算智能与中文信息处理教育部重点实验室(山西大学),山西 太原 030006; 3.山西大学计算机与信息技术学院,山西 太原 030006)

1 引言

复杂网络的结构和功能在科学网络的许多分支中引起了极大的关注，它影响着网络的拓扑和信息的传播。网络是信息传播的媒介，有时，少量的节点或边就能使整个网络发生巨大变化。这种信息级联的现象在很多情况下都存在，如电网的级联故障、通过社交网络传播的消息和谣言，以及微博消息影响最大化等。如何找到关键节点和边是一项重要而有意义的研究。

复杂网络中的重要节点能够在很大程度上影响网络的结构与功能。近年来，网络中节点重要性的度量方法有很多，半局部中心性[1]、k-壳分解法[2]等都是基于节点近邻的方法；离心中心性[3]、接近中心性[4]、Katz中心性[5]等都是基于路径的方法；节点删除的生成树法[6]以及节点收缩法[7]则是基于节点移除和收缩的方法。相比之下，边的重要性的研究虽然尚未成体系，但边在信息扩散过程中也起着重要作用。在能量受限的大规模工业无线传感器网络中，睡眠调度是在满足网络连通性和可靠性的前提下，节约无线节点剩余能量的方法之一。在复杂网络中，有时禁止一个节点的所有通信是不切实际的，因此有必要截断一些重要的通信链路。重要边分析将有助于从全局角度引导或控制信息的传播。

边的重要性研究主要集中在从网络拓扑结构中去寻找关键边。从其研究意义来看，大多数是从维持网络连通性的角度出发的。Ouyang等人[8]通过移除边后网络连通性的变化，推导出了一个计算边重要性的方程。Girvan等人[9]提出了边介数中心性，边介数越大说明该条边在网络中越重要。Hamers等人[10]指出Jaccard系数考虑到如果节点i和节点j有较少的共同邻居，则边更重要。Cheng等人[11]则在Bridgeness中假设删除1条边，信息就会在包含删除边的小社团中传播到其他边。直观地说，较小的社团中的边更重要。最近，Yu等人[12]考虑到派系对刻画边重要性的影响，提出了一种基于网络中的派系和路径的边排序算法BCCMOD(Betweenness Centrality and Clique MODel)。

此外，少量关于边的重要性研究则是从信息传播角度出发的。de Meo等人[13]在对K-path边中心性的描述中指出,如果将多个消息合并在1个社交网络中生成和传播，那么如果1条边被频繁地用来传播信息，它就被看作是重要的。Liu等人[14]将局部传播的异质性考虑在内找出网络中的冗余边。

以上2种方法仅仅考虑到传播过程中的一种特性。而在实际信息传播过程中，影响信息传播的因素往往不只1个。因此，本文尝试综合考虑影响信息传播的因素，即传播者、受传者的作用，传播渠道以及传播环境这3方面因素对边的重要性进行度量。现有的4个经典的度量边重要性的方法为Jaccard系数、Bridgeness、介数中心性和可达性指数[15]。通过与它们进行比较，验证了本文方法在网络连通性和扩散动态过程中识别重要边这2方面均优于其他常用方法。

2 相关工作

在本节中，首先给出用到的几类节点定义，然后总结回顾已有边中心性度量的相关工作。

2.1 基本概念

定义1(重叠节点) 许多真实的网络中具有重叠的社团，其中，一些属于多个社团的节点则被称为重叠节点。

定义2(桥节点) 桥节点连接多个组或社团，一旦去掉这些桥节点之间的连接，一些真实的网络就会被分成2个社团。

定义3(孤立节点) 除了检测出来的社团、重叠节点和桥节点外，一些度较低的节点不属于任何一个社团，这些节点在本文中称为孤立节点。

2.2 网络连通性中的边重要性

大多数边重要性排序方法仅考虑了单一的网络拓扑，且都是基于网络连通性去寻找重要边，下面是这些方法具体的定义。

定义4(边介数中心性) 边介数中心性[9]是通过计算每条边e(u,v)的2个端点u和v之间的最短路径来表示。其值越大表明边e(u,v)越重要。介数中心性定义如下：

(1)

其中,σst为节点s到节点t的最短路径数，而σst(e)则表示从s到t通过边e的最短路径数。值得注意的是，它计算的是每对节点之间的最短路径，因此时间复杂度非常高。此外，它的问题在于对于有些边，甚至关键边的值可能相对较低。

定义5(桥中心性) 2个派系之间的边称为桥，其中，1个大小为k的派系是有着k个节点的全连接子图。桥中心性[11]被定义为：

(2)

其中,x和y是1条边e的2个端点。1个节点x或1条边e的派系大小被定义为包含这个节点或这条边的最大派系的大小。该指标仅适用于密集网络，网络中类似或相关的节点易于连接并形成局部派系，如社交网络和文档网络。此外，寻找每个节点和每条边的最大派系也很费时。

定义6(可达性指数) 边e(u,v)的可达性[15]指数被定义为：

(3)

其中，|V|是网络中节点的个数，Ge(u,v)是从原始网络中移除1条边e(u,v)得到的子网。而R(s;Ge(u,v))是子网Ge(u,v)中从1个节点s可达的节点数量。

定义7(Jaccard系数) 边e(u,v)的Jaccard系数[10]被定义为：

(4)

其中，u和v是1条边e(u,v)相连的2个节点,而Γu是节点u的邻居集合。

2.3 信息传播中的边重要性

定义8(k-path 中心性[13]) 该指标不同于边介数中心性，k-path中心性对信息的传递进行随机游走过程模拟，信息的传递至多k步，表示形式如下所示：

(5)

定义9(扩散重要性[14]) 该指标将局部传播的异质性考虑在内，也就是从边的2个方向出发，分别计算除去2个端点的公共邻居后的端点邻居节点个数总和，定义如下：

(6)

其中，nx→y是从节点x向y方向传播的时候，可以将信息扩散到除去x和y的公共邻居节点之外的y的邻居节点数量。

可以看出，基于网络连通性的边介数中心性、桥中心性、可达性指数以及Jaccard系数这4种指标分别从网络的最短路径、派系、最大连通片以及节点的邻居这4种角度出发，考虑到网络的拓扑结构，刻画了边的重要性。基于信息传播的边重要性度量方法中k-path 中心性以每条边所经过的路径数的多少刻画其重要性。另一个方法扩散重要性仅考虑了从节点x向y方向传播或从节点y向x方向传播的2个方向。以上2种方法都只考虑到传播过程中的一种特性。而在实际信息传播过程中，影响信息传播的因素往往不只1个。因此，下节将综合考虑影响网络中信息传播的3个因素对边的重要性进行度量。

3 ISM方法

3.1 模型描述

影响信息传播活动涉及4个因素：信源、信宿、信道和信息。由此对信息传播效果产生影响的因素主要有4个方面，即传播者、受传者、传播渠道和传播环境[16]。

(1)传播者和受传者。

信息传播过程中的主体包括2部分：传播者和受传者。在邮件网络中，假定最简单的“发送或接收1封邮件”是1条消息。1个人既可以接收消息，也可以向通讯录中出现的其他联系人发送消息。当传播者发送重要邮件时，从信息扩散先后顺序来看，他会根据联系人的重要程度，选择想要告诉的联系人(即受传者)并进行转发。其中，传播者和受传者用节点表示，他们之间的信息传递关系用节点间的连边表示。从信息传播的角度来看，与边相连的2个节点越重要，边就越重要[12]。可以发现，在信息传播的过程中1条边的重要性取决于其2个端点的重要程度。本文采用节点中心性指标，即节点度k去刻画传播者和受传者的重要程度。无向网络中节点i的度ki定义为与其直接相连的边的数目。

(2)传播渠道。

传播渠道是信息传播的媒介，传播的路径越多，传播的效果越好。而且，具有不同强度的边在维持网络连接、信息过滤、信息传播等方面发挥着不同的作用[17]。在邮件网络中，如果1条边(即表示2个联系人是否有邮件传送的过程)被频繁地用来传播多个邮件信息，则这条边连接的2个节点的紧密程度越大，即连接强度较大。同时，这条边所承载的信息量就比较多，对信息传播的影响也就比较大。本文则通过计算边的介数中心性去描述信息传播过程中的传播渠道。

(3)传播环境。

在信息传递过程中，真实的传播方向不单单与其传播者、受传者和传播渠道有关，而且还与他们所处的环境有关。传播环境包括群体规范、人际关系等。而在社交网络中，传播环境即节点和边所处的社团结构。网络的社团结构如图1所示，每个社团内部的节点之间的连接相对较为紧密，各个社团之间的连接相对来说比较稀疏。在图1中，社团划分较为明显，此时，处于社团之间的边则比较重要。

Figure 1 Structure of non-overlapping community图1 非重叠社团结构

但现实生活中，大多数网络社团划分并不像上述情况那样有较为明显的社团边界。而是如图2所示，划分的社团之间出现了较多的重叠部分，有不少的重叠节点和边。为了使应用场景更接近真实场景，本文在传播者、受传者和传播渠道这3个因素的基础上，还考虑了传播环境(即重叠社团[18])对边的重要性的影响。

Figure 2 Structure of overlapping community图2 重叠社团结构

在信息传播的过程中，2个联系人之间的共同联系人越多，那么这2个联系人之间的联系越容易被其他联系所替代，即这2个联系人之间的边越不重要。从图2中可以看出，这个网络结构中存在2个社团，分别为实线和虚线连接的2部分。这2个社团之间有着较多的重叠节点(如32，9，3，20，14等)。

为了更加详细地描述重叠部分对边重要性的影响，看图3所示结构，其中，假设1，2为图2所示的2个社团中的节点。3，4，5，6则对应于图2中的那些重叠节点。可以发现，重叠节点是比较多的，那么这2个社团之间的边即e(1,2)则特别容易被1-3-2这类路径所取代。这就证明了之前的猜想，与重叠节点相连的边是不重要的。所以，本文考虑传播环境中重叠社区的影响去衡量边的重要性是比较合理的。

Figure 3 Influence of overlapping nodes on the edges图3 重叠节点对边的影响

在接下来的小节中，将讨论ISM方法如何考虑到以上描述的几种因素来刻画边的重要性。

3.2 形式化定义

综上所述，考虑到信息传播的3个影响因素，下面来讨论具体的方法。其形式化定义如定义10所示。

定义10(ISM(Information Spreading Model)方法) 对一个图G=(V,E)的每条边e，ISM的计算如下:

(7)

其中，ki和kj是1条边e的2个端点的度，Betweeness(e)是通过这条边的最短路径的数目占所有最短路径的比例，occur_time(e)则是与重叠节点i和j相连的边e在重叠社团中出现的次数，如果与重叠节点不相连，则此值为1。

occur_time(e)的计算过程主要包括以下3个步骤：

(1)提取最大社团。

将网络表示为G(V,E)，其中V表示网络中n个节点的集合，E表示m条边的集合。基于深度和广度遍历，提取所有的最大社团，初始过程如下所示：

①初始化。计算每个节点的度，并移除度为1的孤立节点。

②然后选择1个度最大的节点[V0]，并找到它的相邻节点。

③将[V0]作为初始节点,搜索所有标签“DV=1”的邻居节点[N1],然后搜索所有[N1]的邻居节点[N2]和有着标签“DV=1”的节点[V0]；搜索所有[N2]的邻居节点[N3]和有着标签“DV=1”节点[V0]，直到搜索到[V0]所有邻居节点并回到初始节点[V0]。

④上一步之后会得到1个环{V0,V1,V2,…,Vj,V0}，如果节点{N1,N2,…,Nj}为顶点[V0]的邻居节点，令顶点[N1]为起始节点，搜索其邻居节点{N3,N4,…,Nj}并让[N2]为起始节点，搜索其邻居节点{N4,N5,…,Nj}直到顶点[Nj-2]是点[Nj]的邻居节点。

⑤将“Ms”(s=1,2,…)最大社团作为输出，并在给定网络的邻接矩阵中用标签“DV=1”修改节点的度。

⑥如果一些节点的度不为零转到步骤②;否则转到步骤⑦。

⑦如果每个节点的度为零，停止循环，最终得到所有的最大社团。

(2) 扩展最大的社团。

以下规则用来扩展最大社团。首先检测社团结构，找到属于多个具有“DV”标签的最大社团中的重叠节点。然后，找到连接2个以上的不属于任何1个最大社团的桥节点，和一些不属于任何1个最大社团的、度较低的孤立节点。

其次，NM是2个最大社团中节点的总数，N0是2个最大社团中公共节点的总数。在无权网络中，当NM/2≤N0时，这2个最大社团可以合并成1个更大的子图。否则，这2个最大社团就不能合并成更大的子图。最后，孤立节点不属于任何最大社团。如果1个孤立节点只连接1个非重叠顶点,这种孤立节点可与它连接的非重叠节点分为同一社团。

(3) 计算重叠节点在同一社团中出现的次数。

根据上述步骤所得结果，统计出节点i与节点j同时出现在1个最大社团中的次数，即occur_time(e)。

根据式(7)，给出本文的ISM方法流程如下：

Step1初始化每条边的得分为0;

Step2根据模型描述中的(1)计算与每条边相连的节点的度的乘积;

Step3根据式(1)计算所有边的边介数中心性;

Step4根据形式化定义中的具体步骤找到重叠社团;

Step5计算与重叠节点相连的边在重叠社团中出现的次数occur_time(e);

Step6按照式(10)计算所有边的得分;

Step7将所有边的分数从大到小进行排序;

Step8结束。

4 实验与结果

本节将在9个真实网络的数据集上验证ISM的有效性。

4.1 度量标准

一般地，将易感指数S和最大连通片σ作为评估排序重要边性能的标准。

在网络连通性度量中，常用易感指数S[19]来评价方法的性能。定义易感指数S如下所示：

(8)

其中，n为整个网络的大小，ns表示大小为s的连通片的数目，而Smax是最大连通片的大小。至于细节部分，先根据排序算法的分数降序排边，然后从网络中一条一条地按照分数降序移除边，并计算易感指数S。在这个过程中，定义移除边的比例参数p为：

(9)

其中，mr表示移除的边的条数，m表示整个网络的边数。

除了易感指数S，另一个常用于评估方法性能的指标是最大连通片的大小σ[20]。具体是根据分数降序排边，然后按照从高到低的排序分数，一条一条地移除边，同时计算移除边后的最大连通片的大小σ。

4.2 数据集

本文将在9个有着不同信息传播的无权无向网络数据集上进行实验。除了TRN-Yeast-1[21]和TRN-Yeast-2[20]，其余数据均可从芝加哥网络数据集[22]上下载。

(1)Football网络是2000年秋季美国甲级联赛各学院之间的美式足球比赛网络。(2)Grasslands和Seagrass是来自水生和陆地系统的小规模食物网络。(3)TRN-Yeast-1和TRN-Yeast-2是酵母的2个转录网络。(4)Euroroad是国际性的电子道路网，主要位于欧洲。网络是无向的，节点表示城市，2个节点之间的边表示它们由1条e路连接。(5)Power是1个包含美国西部各州电网信息的网络。(6)Netscience是1个由Newman在2006年收集的网络，其中网络的节点表示科学家，连边表示科学家之间的合作关系。(7)Router是1个包含相互连接的自治系统的网络。

网络的基本统计信息如表1所示。为保证网络的多样性，每个网络在节点数目N和边的数量|E|、平均度〈k〉、最大度kmax、平均聚类系数H和度异质性C等方面都存在着差异。其中，平均度为所有节点的度的和的平均值，最大度即网络中所有节点的度值的最大值，而节点的度则定义为与该节点连接的其他节点的数目；在简单图中，假设节点相邻的节点有ki个，节点的聚类系数Ci定义则为ki个节点间存在的边数与图中总的可能边数之比，而网络的平均聚类系数H则为所有节点聚类系数Ci的平均值，体现了网络的凝聚力；最后，度异质性C=1-P(K),其中P(K)为网络的度分布。

Table 1 Basic information of the nine networks 表1 9个网络的基本统计信息

4.3 信息传播因素对边重要性的影响

影响信息传播的因素包括：传播者、受传者的作用，传播渠道和传播环境[17]。接下来将具体分析每种因素对边重要性的影响。以图3所示的网络数据为例，分别计算影响传播的每种因素的值，得到的结果如表2所示。虽然图3中最重要的边较难识别和判断，但直观上来看，节点1与2之间的边承载着较多的信息传播，较其他边来说更为重要。表2中传播者、受传者的作用(即1条边Edged的2节点的度值乘积ki*kj)和传播渠道(即经过这条边的最短路径的个数B)都与边的重要性成正比。而与传播环境(即边在重叠社区中出现的次数Occur_time(e))成反比，其意义为若一条边位于多个社团中，则这条边的重要程度较小。以上结果均与图3观察到的结果相符。

Table 2 Influence of information dissemination factors on each edge表2 信息传播因素对每条边的影响

4.4 实验和结果

图4表示边排序分数与最大连通片大小σ相对差异的Spearman相关系数。Spearman相关系数的大小反映了变量间相关程度。网络中移除的边越重要，则对网络的最大连通片造成的影响最大，即边排序分数与最大连通片大小的差异越大(呈现负相关)，相关系数越大，找出的边越重要。从图4能够看出，这些方法的排序分数都与最大连通片的大小相关。边排序分数与从颜色深浅与其相关系数的值来看，Reachability指标的边排序分数与最大连通片大小σ相对差异的相关性值最小；接下来，Jaccard和Bridgeness的相关性居中，而Betweeness和ISM的相关性的值基本上都接近1，相关程度都比较大。总体上来看，ISM中有5个值都高于Betweeness的，这表明与其它方法相比，ISM的排序结果与最大连通片的变化最相关，故其排序性能最好。以上比较直观地探讨了ISM方法与边重要性的相关性。稍后将分别叙述最大连通片σ的变化和易感指数S如何能够反映出边重要性方法性能的好坏。

Figure 4 Spearman correlation coefficients between the ranking scores and the relative differences of σ图4 边排序分数和σ的相对差异的Spearman相关系数

Figure 5 Susceptibility index S over different values of p图5 不同p值对应的易感指数S

9个代表性的网络在不同p下的易感指数S变化情况如图5所示。从图5可以看出，ISM方法在统计上优于其它方法。例如，ISM在Football、TRN-Yeast-1、TRN-Yeast-2、Euroroad、Netscience这5个数据集上，敏感指数S最大时，其对应的移除边的比例p最小。在Grasslands、Router和Power中，ISM中最大的S出现得较早，其对应的p值非常接近最小值。因此，与其他方法相比，ISM的最大S值在大多数情况下出现得都早，表明ISM可以快速地破坏网络，使网络瓦解。注意到，ISM适用于除Seagrass外的网络，ISM方法在对网络的控制和抑制信息传播方面具有更好的效果。以上分析结果表明，ISM综合考虑了信息传播过程中的3个因素来度量边的重要性是合理的。

Figure 6 Size of giant component σ over different value of p图6 不同p值对应的最大连通片大小σ

网络在不同p下的最大连通片的大小σ比较结果如图6所示。该曲线下降得越快，表明方法的效果越好。从图6可以看出，ISM方法优于其它方法。例如，对于Football、Grasslands、Euroroad、Router、Netscience数据集，ISM的曲线下降最快，这意味着该方法可以快速地分解网络。在数据集TRN-Yeast-2和Power上曲线的下降速度接近于最好的Betweeness的曲线。在图6中，Seagrass网络的最大连通片的大小总体上来看，随着移除边的比例增加，下降得最快。以上分析结果表明，ISM在大多数情况下可以快速分解网络，可以有效地度量边的重要性。

5 结束语

分析真实网络的结构是理解和控制网络动态行为的重要思路。本文通过综合考虑影响信息传播的3个因素：传播者、受传者作用，传播渠道和传播环境，提出了一种基于信息传播影响因素的边重要性度量方法ISM(信息传播模型)。与4个基于拓扑的经典边重要性度量方法相比：(1)ISM在边渗流过程中网络衰减的速度更快，也就是说，移除同样数量的边后，最大连通片的大小要小得多；(2)最大连通片的大小变化越明显，则表明网络能较快地被分解。实证分析表明，该方法在网络连通性意义下识别重要边优于其他经典方法。综上所述，ISM在现实生活中有很大的意义，例如控制疾病或谣言的传播，特别是由大量重叠社团组成的网络中，对目标攻击进行防御。值得注意的是，ISM综合考虑了较多的影响信息传播的因素，导致了其时间复杂度较高，使其很难在特大规模网络中应用。此外，对更大规模网络的研究也将是未来工作的一部分。