面向复杂有权网络的社区发现方法研究

谭红叶,吴永科,张 虎，刘全明,李 茹,2

(1. 山西大学 计算机与信息技术学院，山西 太原 030006；2. 山西大学 计算智能与中文信息处理教育部重点实验室, 山西 太原 030006)

0 引言

随着以互联网为代表的网络技术的快速发展，人类社会已迈入了复杂网络时代。当前，人们生活在一个充满各种类型网络的复杂网络世界。例如，社会网络、电力与交通网络、经济与金融网络等，在这些网络中充斥着各种不同的关系和结构。随着研究人员对网络性质研究的不断深入，人们发现许多实际网络都有明显的社区结构[1]，每个社区内部的节点之间的连接相对较为紧密，各个社区之间的连接相对比较稀疏。基于这些特征，人们对不同的社会网络探索了很多实用的社区发现算法。典型的算法主要包括: (1)基于网络拓扑结构的算法，主要有Pothen 等人[2]在20世纪90年代提出的基于谱分析方法的社区结构探测算法和Girvan 等人[3]提出的GN层次聚类算法。(2)基于网络动力学的算法，主要包括Reichardt 和 Bornholdt[4-5]将物理学中Potts模型运用到社区发现中的超顺磁聚类算法，Wu等人[6]将网络类比成电路的电流算法。(3)基于模块度优化的算法主要包括贪婪算法[7]和极值优化算法[8-9]等。(4)基于聚类的社区发现算法是寻找社会网络中社团结构的一类传统方法。它基于各个节点之间连接的相似性或者强度，把网络自然地划分为各个子群，根据向网络中添加边或者是从网络中移除边，该类算法可以分为两类: 凝聚方法和分裂方法[10-12]。

显然，这些典型的社区发现方法主要针对无权网络，在这些网络中节点之间的边只有存在或不存在两种情况，两节点之间存在边则连接强度为1，不存在则为0。但在很多实际网络中，节点之间的权值不同，相互的耦合性不同，这些差异对分析复杂网络的社区结构起着至关重要的作用。如科研合作网络中，各个研究者之间的合作论文数量是不同的，合作论文数量多的研究者的紧密性通常更强；复杂交通网络中，一个周期内不同城市间的航班班次和火车车次也相差巨大，来往次数较多的城市更容易形成一体化的经济圈。显然，复杂网络中节点之间的连接强度会在很大程度上影响网络的社区结构，因此利用权重来刻画连接强度的差异性，并将其应用到社区发现研究中具有重要的意义[13-15]。

目前，针对有权网络的社区发现研究已经成为一个重要的研究方向。相关研究主要有: Newman M E J[16]提出了WGN算法，是对GN算法的改进，将边介数用权重的边替换；王坤等人[17]提出了基于相似度的加权复杂网络社区发现；韩华等人[18]基于现有的划分算法提出改进的CNM算法对加权网络进行划分，该方法延续应用了社团结构分级聚类，对Newman贪婪算法[19]进行了改进。

本文结合节点的直接连边权重和基于共同邻节点的连边权重提出了一种改进的节点相关度度量准则。基于这种改进的节点相关度度量准则和团体之间的聚集方法构建了面向有权网络的社区发现模型，分别在有权值的科学家合作网络、全国列车运行网络数据集上进行了社区发现实验。基于列车运行网络数据集的实验结果显示出我国不同城市间的列车分布情况，发现了连接最紧密的城市群、包含较少节点的社区和孤立的城市节点等。

1 加权网络节点相关度度量准则

1.1 节点相关度度量准则

在无权复杂网络中，经典三元闭包原则指出，如果两人A和B拥有一个共同的朋友C，那么这两个人今后也很有可能成为朋友，从而使得三个节点构成一个闭包三角形ABC。对于一般的网络，可以把这一原则推广如下: 两个节点的共同邻居数量越多，这两个节点越相似。本文将该原则应用到无向有权网络中，同时在此基础上将连边权值引入到两个节点间的相关度计算模型，节点相关度准则既考虑了两个节点的共同邻节点，同时又考虑了基于共同邻节点的连边权重。

对于复杂网络，两个节点间的连接强度除了与基于共同邻节点形成的连边相关外，还与直接相连的边有关，因此计算两个节点的相关度需要同时考虑基于共同邻节点的连边权重和直接连边权重。本文通过设置参数α，β来调节直接连边权重和基于共同邻接点的连边权重的关系，节点vi和vj之间的权重可以通过以下式(1)来表示:

(1)

其中，σij表示节点vi和vj本身的直接连边权重，在复杂有权网络中都会直接列出；σh表示节点vi和vj基于共同邻节点的连边权重，需要针对不同类型的复杂网络构造对应的计算模型，针对该问题本文面向复杂有权网络定义了基于共同邻节点的连边权重；n表示节点vi和vj的共同邻节点数；α和β分别为直接连边权重和基于共同邻接点的连边权重的调节参数，需通过实验训练，要求α+β=1。

1.2 基于共同邻节点的连边权重

假设{v1,v2,…,vn}表示节点vi和vj的共同邻节点，{θi1,θi2,…,θin}表示节点vi与共同邻节点的连边权重，{θj1,θj2,…,θjn}表示节点vj与共同邻节点的连边权重。通过图1可以看到节点vi和vj。可以基于它们的公共邻节点产生进一步的联系。那么，对于有权网络该如何通过共同邻节点计算节点vi和vj的连接强度。基于网络流中的最大流理论，每一条路径最大流的流值等于该路径上最小容量的那条边所能承受的流量。图2中节点vi和vj通过公共邻节点v相连，可以看到节点vi到节点v的容量为10，节点v到节点vj的容量为2。那么，按照最大流理论可以得到节点vi和vj间的最大流为2。

图1 两个节点的公共邻节点

图2 两个节点间的最大流

因此，对于基于公共邻节点v的连边权值计算问题，依据最大流理论可以选取两条边的最小权值作为通过该节点v的连边的权重。节点vi和vj的第h个公共邻节点的连边权值计算如式(2)所示。

σh=min(θih,θjh)

(2)

其中，θih和θjh分别表示节点vi和vj的第h个共同邻节点的连边权值, 且0≤h≤n。

1.3 基于两种权值的统一表示框架

复杂网络中的加权方式通常有两种: 相异权和相似权。相异权是指权值越大，节点间的相关度越小，关系越疏远；相似权是指权值越大，节点间的相关度越大，关系越紧密。本文研究的复杂有权网络包括科学合作网络和列车运行网络，两种复杂网络只考虑无向情况。其中科学合作网络的边权赋予采用相似权的方式，列车运行网络的边权赋予采用相异权和相似权的组合方式。由于相异权考虑了节点间的距离，相似权考虑了节点间的关系紧密度，因此在列车运行网络中通过这两种权值的组合可以更准确地反应节点划分的实际情况。本文将这两种权值表示到统一的节点权重度量框架，具体表现形式如式(3)所示。

(3)

其中，σij和ζij分别表示节点vi和vj的相异权和相似权；x，y表示相异权和相似权的权重调节参数，且x+y=1。同时，式(3)分别对相异权的倒数和相似权做了标准化处理，使不同量纲的两个变量都介于0到1之间，一定程度上保证了两个参数的可调节性。式(3)可进一步写成式(4):

σ(vi,vj)=x*min(σij)/σij+y*ζij/max(ζij)

(4)

在本文的实验中，针对科学合作网络数据集的实验令相异权的调节参数x=0，相似权的调节参数y=1。对列车运行网络数据集的实验通过不断调整x和y的取值分析两个权对结果的影响。

2 面向有权网络的社区划分模型

2.1 团体间的连接强度度量准则

通过式(4)可以将单个节点合并成一个个小团体。然后需将这些小团体合并成大的团体直到形成一个个社区。如何合并这些小团体是社区划分研究需要解决的一个关键问题。按照同一社区通常有较强凝聚性的原则，本文研究通过定义团体间的权值来刻画团体间的连接强度。然后，依照权重值的大小来合并各个小团体直到形成合适的社区。两个团体之间的权值基于任意两个不在一个小团体内的节点的相关度的加权平均来计算，如式(5)所示。

(5)

其中，weight(Ci,Cj)表示小团体Ci和Cj之间的权值；σij表示小团体Ci和Cj之间任意两个不在一个小团体内的节点的相关度。

2.2 算法描述

算法思想: 计算各个节点之间的节点相关度，按照设定的阈值合并不同的节点，形成一个个小团体；计算不同团体间的连接强度，不断合并节点或小团体，迭代该过程直到找到合适的社区为止；通过评价指标对社区划分结果进行评价。

算法流程: 假设G(V，E，W)是一个由n个节点m条边组成的复杂网络。其中V是网络节点的集合，E是网络边的集合，W是网络边上权重的集合。

(1) 计算各个节点间的相关度，表示为σ。同时，根据σ的大小设定一个阈值T。

(2) 初始化社区，对于每个节点，将每个节点的社区分别表示为L{i}。

(3) 找到节点间相关度最大且其值大于阈值T的节点对，将其合并为小团体。如果节点vi和vj满足条件，则将节点vj对应社区中节点移到vi对应的社区中，即L{i}=L{i,j}，并将L{j}清空，其相应的连接强度全部归为0。

(4) 重复步骤(3)直到没有找到满足相关度(连接强度)最大和相关度(连接强度)大于阈值T的节点对为止。

(5) 计算由步骤(4)得到的团体L之间的连接强度W，找到最大W值所对应的团体进行合并。

(6) 重复步骤(5)，直到团体社区L的个数等于k时迭代终止，并计算相应的社区划分的评价指标。

(7) 对不同类型的复杂网络分别设定不同的k值，评价不同k值对应的社区划分结果。

3 实验结果与分析3.1 评价指标

为了评价该方法的社区划分效果，本文实验使用了2004年Newman[20]提出的Q函数概念，当模块性Q函数最大时表示网络划分最好。在加权网络中，Q函数通常按式(6)的形式计算。

(6)

其中，aij为网络邻接矩阵的元素，如果vi和vj两节点相连，则aij为边的权重，否则等于0；δ为隶属函数， 当节点vi和vj属于同一个社团时， 隶属函数

为1，否则等于0；M=0.5*∑aij为网络中边的权重之和。在网络划分结构固定，两节点的边随机连接时，节点间存在边的可能性为kikj/(2M)，ki为节点vi的点权，计算方法为对邻接矩阵的第i行求和。

3.2 实验数据

本文使用两个数据集验证所提出的方法，包括: 科学家合作网络和全国列车运行网络数据集。实验所用的科学家合作网络[21]是由Mark Newman于2006年编写的有权网络，网络节点表示网络科学领域的科学家，边表示科学家之间的论文合作关系，权值为作者间的直接合作数量。该版本的科学家合作网络共有1 589名科学家，其中包括由379位科学家组成的最大社区。全国列车运行网络数据收集了我国全部的列车数据和任意车次的途径车站数据，为了消除部分特殊点本文的实验中采用的列车运行网络数据仅保留了五线城市以上的站点，并对一个城市中的所有站点进行了合并，构成了一个由273个节点和12 925条边的加权复杂网络，其中不同城市间的连边权值由来往车次数和实际距离确定。两组实验数据的基本信息如表1所示。

表1 两种实验数据信息

3.3 基于科学家合作网络的社区划分

针对科学合作网络数据集进行的实验使用作者间的合作数据作为相似权，实验表明当参数α，β分布选取0.6和0.4，且阈值T为2时得到最好的社区划分结果，将整个网络划分为397个社区。此时各个子社区之间没有连边，模块度达到0.81，最大的子社区包含节点数为379，表2显示了该实验的社区划分结果。

表2结果显示科学家合作网络中存在很多零散的小社区。本文方法有效的将社区中由379位科学家组成的最大的子社区部分精确的找出来，并将其余的节点也很好的进行了社区划分。其中，节点数在5以下的子社区数量占所有子社区数量的85.6%。该实验表明本文提出的方法在科学家合作网络数据集上会取得模块度较大的社区划分结果。

表2 基于科学家合作网络数据集的社区划分结果统计

3.4 基于列车运行网络的社区划分

(1) 社区发现实验

在列车运行网络数据集的实验中本文分别将站点的来往次数作为相似权，站点间的距离作为相异权，并基于相异权和相似权的不同调节参数分别进行了社区划分实验。α，β采用了科学合作网络实验中结果最好的参数作为初始值，同时使用了其他参数值进行了同类实验，并选择了结果最好的参数值作为后续比较实验的参数。各组实验都选取α=0.6，β=0.4，并在T为0.035时取得较好的实验结果。图3～图6展示了在不同的社区数，不同的x和y时对应的不同效果图。由于节点较多实验选出至少包括10个节点的较大的社区来展示划分结果，并将各个较大社区包含的不同站点按照经纬度在图中显示出来。每个社区用不同的颜色来区分，横坐标表示经度，纵坐标表示纬度。

实验一7个较大社区时，不同相异权和相似权对应的社区划分结果如图3a～3c所示:

图3a 只考虑站点间距离的社区划分

图3b x=0.9 y=0.1

图3c x=0.8 y=0.2

实验中在x=0.7和y=0.3时未找见7个较大社区。

实验二6个较大社区时，不同相异权和相似权对应的社区划分结果如图4a～4d所示。

图4a 只考虑站点间距离的社区划分

图4b x=0.9 y=0.1

图4c x=0.8 y=0.2

图4d x=0.7 y=0.3

实验中，在x=0.6和y=0.4时，未找见6个较大社区。

实验三5个较大社区时，不同相异权和相似权对应的社区划分结果如图5a～5e所示:

图5a 只考虑站点间距离的社区划分

图5b x=0.9 y=0.1

图5c x=0.8 y=0.2

图5d x=0.7 y=0.3

图5e x=0.6 y=0.4

实验中，在x=0.5和y=0.5时，未找到5个较大社区。

实验四4个较大社区时，不同相异权和相似权对应的社区划分结果如图6a～6e所示:

图6a 只考虑站点间距离的社区划分

图6b x=0.9 y=0.1

图6c x=0.8 y=0.2

图6d x=0.7 y=0.3

图6e x=0.6 y=0.4

实验中，在x=0.5和y=0.5时，未找到4个较大社区。

(2) 实验结果分析

图3～图6显示出不同城市之间形成了较明显的社区结构。对于只考虑站点间距离的社区划分形成的图3～图6中的a图，尽管形成了社区，但部分社区将离得较远的节点划分到一起了，出现这种现象的主要有两个原因: ①部分节点只与较远的节点有连边； ②两个节点之间的连边权值，既考虑了直接连边也考虑了共同邻居节点的连边。

对于图3～图6中的b、c、d、e图，针对不同的社区数的社区划分结构都有明显的变化，但从图中可以看出越到后边的图节点越稀疏，社区越清晰，越能看出列车运行网络的骨干线路。出现这种现象主要是因为随着连边权值的调节参数不断加大，节点之间的连边数在社区划分中起的作用越大，而相应的节点距离起的作用就会变小。这将会导致部分地理位置上比较紧密的点，可能由于来往次数比较少而成为了孤立节点或者较小的社区。

图4a中6个大社区时的社区划分对应的部分城市如表3所示，表4为考虑距离与来往次数比值为 7∶3时的社区划分结果对应的城市列表，表5是两者的交集结果。通过对这些数据的分析可以发现三类城市: ①部分城市距离较近，但他们之间的列车运行趟数较少，这些城市会随着连边次数的权值占比加大而逐渐分散； ②部分城市距离较远，会随着连边次数的权值占比加大而逐渐聚合； ③部分城市不仅距离较近，他们之间的列车运行趟数也较多，属于比较稳定的经济体，如表5所示。同时，基于完整的社区发现数据还可进一步发现较小的社区和孤立点。

表3 只考虑距离的社区划分结果对应的城市列表

表4 考虑距离与来往次数比值为7∶3时的社区划分结果对应的城市列表

表5 表3和表4相交的城市列表

针对不同类型数据集上的实验结果表明，本文提出的面向复杂有权网络的社区发现方法具有较好的社区划分效果。面向全国列车运行网络数据集的实验分析了全国列车城市站点的不同类别，挖掘了稳定的经济体、节点较少的社区和孤立点等，可进一步为较大的经济体的建设提供重要的依据。

4 结论

本文结合节点的直接连边权重和基于共同邻居节点的连边权重提出了一种改进的节点相关度度量准则。基于这种改进的节点相关度度量准则和团体之间的聚集方法构建了面向有权网络的社区发现模型。在有权值的科学家合作网络和全国列车运行网络数据集上进行了社区发现实验，验证了本文提出的方法在有权网络的社区划分上的有效性，分析了该方法在全国列车运行城市类别研究中的重要意义。接下来将在本文实验的基础上进一步面向复杂交通网络研究最有影响力的城市节点发现方法和社区的“结构洞”挖掘模型。