基于节点重要性和模块度优化的社团划分算法

张梦园,李玲娟

(南京邮电大学 计算机学院,江苏 南京 210023)

0 引 言

对复杂网络的深入研究发现,现实世界中许多系统都能抽象为网络,如人与人之间的社交网络、自然界的食物链网络、蛋白质相互作用网络等。这些网络由具有一定组织性和极大随机性的节点构成[1]。根据网络节点之间的连边是否存在权值,复杂网络可以分为无权网络和加权网络,加权网络相比无权网络能够反映更加丰富的信息,同时赋予复杂网络更加明确的物理意义。

社团是复杂网络的一个重要特征,社团内各个节点间连接紧密,而社团之间只有一些稀疏的连接[2]。发现复杂网络中的社团结构能为进一步理解网络所代表的真实世界系统的结构和功能提供捷径。经典的社团划分算法有基于模块度优化的、基于标签传播的、基于局部扩展的、基于深度学习的等等[3-5]。针对加权网络的社团划分算法还相对较少,通常考虑引入边的权值来对已有的经典的无权网络划分算法进行改进。典型的基于模块度优化的加权复杂网络的社团划分算法有WGN[6]、WFN[7-8]、CNM[9]、BGLL等。

其中的BGLL[10]算法分为两个阶段,第一阶段不断将节点移入(即并入)使模块度增益最大的社团,直至节点的移动不会再导致模块度增加;第二阶段将得到的社团作为新的节点对网络进行重构,在重构的网络上重复第一阶段。BGLL算法在第二阶段对网络重构,极大地缩小了网络规模,算法的迭代会越来越快,因此具有很好的时间效率,但由于第一阶段迭代遍历节点是无序的,没有考虑节点自身在网络中的地位,因此可能会使最终划分结果的准确度不佳,仍有改进的空间。

该文考虑在无向加权网络的社团划分算法BGLL中引入节点重要性来调整其遍历次序,以提高算法划分结果的准确度。首先,设计了一种基于节点自身信息及其邻居节点信息的加权网络节点重要性计算方法WNI (weighted network node importance);然后,融合WNI和BGLL算法,设计了一种基于节点重要性和模块度优化的加权网络社团划分算法(weighted network community division algorithm based on node importance and modularity optimization),命名为IMWCD。IMWCD算法将BGLL算法每轮合并后重构的网络中的所有节点按照重要性升序排序,并作为下一轮遍历的顺序,以此为基础实现加权网络的社团划分。

1 相关知识

1.1 网络的图表示

一个真实的加权网络可以抽象表示为图G=(V,E,W)的形式,其中V表示节点集,E表示边集,W表示边的权值,节点数n=|V|,边数m=|E|,E中每一条边都有V中的一对点与之对应,wij表示任意有边相连的节点i和节点j之间的权值。对于无向网络而言,任意点对(i,j)和(j,i)表示同一条边,对应边的权值wij=wji;对于有向网络,节点之间的连边具有方向性,如(i,j)唯一表示由节点i指向节点j的边。与网络中某个节点v直接相连的边的数目称为该节点的度dv。

1.2 节点重要性

有研究表明,网络中重要性较大的节点相比其他节点更能影响网络的结构和功能[11],重要性越大的节点越倾向于成为社团的中心。因此,节点重要性度量方法对于发现网络的社团结构具有重要的意义。评价网络中节点重要性的方法有很多,如介数中心性、度中心性、PageRank等。基于网络全局属性的介数中心性评价方法认为:经过某个节点的最短路径数量越多,则该节点越重要[12],这种评价方法需要计算所有节点对之间的距离,时间复杂度过高。度中心性是最简单的节点重要性评价指标,直接反映与当前节点相连的邻居数量(即节点的度),节点的度越大,与之直接相连的邻居节点越多,该节点越重要[13];这种评价方法具有计算复杂度低的优点,但只考虑了待评估节点的局部信息,没有考虑邻居节点的信息或节点在网络中所处环境等因素,可能导致计算结果误差较大。PageRank[14]是谷歌搜索引擎的核心算法,考虑的是待评估页面的邻居页面信息对待评估页面重要性的影响,认为如果一个页面被大量其他页面所指向,则此页面是重要的。

1.3 BGLL算法

BGLL算法是一种层次性贪婪算法,基于模块度优化的思想,自底向上地不断合并网络中的社团,取模块度最大时的划分状态作为最终的划分结果。BGLL算法首先将网络中每个节点初始化为一个社团,社团编号为节点编号。之后的工作分为两个阶段。

第一阶段:对于每个节点,考察其所有邻居节点,尝试将此节点移入其邻居节点所在社团,并计算移入后的模块度增益,如果计算得出的所有增益为负,则节点仍处于原始社团,否则选择将节点移入模块度增益最大的社团内。遍历网络中所有节点,直到没有节点移动,即移动任意节点都不会再导致模块度的增加,此时第一阶段结束。其中,模块度增益定义如下:

(1)

其中,∑in表示社团内部所有边的权值之和,ki,in表示节点i与所在社团内的节点的连边的权值之和,ki为节点i在网络中的所有连边的权值之和,∑tot表示节点i所在社团内的各个节点与网络中所有节点连边的权值之和,m为网络中所有边的权值之和。

第二阶段:将网络图进行重构,规则如下:将第一阶段划分出的社团作为新的节点,社团编号作为新的节点编号。新的节点之间连边的权值为两个原社团之间连边的权值之和,处在同一个社团内的节点使得新形成的节点有指向自己的自环边,且权值为社团内所有连边的权值之和。将第二阶段重构的网络图作为第一阶段的输入重新进行迭代,直至网络不再改变即模块度最大时算法停止。

2 加权网络节点重要性计算方法WNI设计

如前文所述,节点重要性能反映节点在网络中的地位,重要性越大的节点越有可能成为社团的中心。合理使用节点重要性可以使社团划分算法的划分过程更具有方向性和目的性,从而获得更准确的划分结果。

该文借鉴度中心性和PageRank的评价思想,对加权网络中的节点重要性做出如下的量化定义:

Ip=Ip'+IN

(2)

其中,Ip表示节点p的重要性,Ip'表示根据节点p自身权值信息计算得到的重要性,IN表示根据节点p的邻居节点信息计算得到的重要性。

Ip'的定义如下:

(3)

(4)

其中,wmin表示网络中边的最小权值,wmax表示网络中边的最大权值。归一化可以防止网络规模过大时,直接计算边的权值之和可能导致的数据溢出问题。

IN的定义如下:

(5)

其中,wjp表示节点j和节点p之间的权值,‖N(j)‖表示节点j的邻居节点数目,wk表示节点j的邻边中第k条边的权值。

以图1所示的简单加权网络为例,其中节点v1拥有最多的连边且与之相连的边的权值在整个网络中占比最大,该节点应该是网络中最重要的节点。对于节点v2和v3,除了考察其自身的Iv',它们的共同邻居v1对节点v3的重要性贡献较大,则v3应比v2拥有更高的重要性值。

图1 简单加权网络

可见,节点v1的重要性Iv1最大,计算结果与实际相符,说明该文设计的加权网络的节点重要性计算方法WNI是合理有效的。

3 IMWCD算法设计与分析

如前文所述,BGLL算法第一阶段节点的遍历次序随机,没有考虑节点自身属性信息及其所处环境信息,从而可能使最终的社团划分结果的准确度不够高。为了解决这个问题,该文设计了基于节点重要性和模块度优化的加权网络社团划分算法IMWCD。

3.1 设计思路

IMWCD采用WNI方法计算节点重要性,将BGLL算法每次迭代中第一阶段的节点遍历顺序由随机遍历调整为按节点重要性的升序遍历,以便综合利用全局和局部信息来提升算法的准确度。

3.2 IMWCD算法总体流程

算法总体流程可描述如下:

输入:网络图G=(V,E,W);

输出:加权网络社团。

算法步骤:

Step1:初始化网络中每个节点i∈V为一个社团,社团编号为节点编号;

Step2:根据式(2)至式(5)计算每个节点的重要性,并将所有节点按照重要性升序排列成节点序列list;

//迭代更新阶段:

Step3:考察list中的首个节点;

Step4:遍历当前节点的邻居节点,计算当前节点移入其邻居节点所在社团后的模块度增益,记录模块度增益的最大值和对应的社团编号;

Step5:若最大模块度增益大于零,将当前节点移入模块度增益最大的社团;否则当前节点仍留在原始社团。继续考察list中的下一个节点;

Step6:重复Step4、Step5,直至当前网络中没有节点需要移动;

Step7:计算Step6结束后整个网络的模块度,并与上一轮的网络模块度对比,如果网络模块度未增大,则当前的划分结果为最终划分结果,算法终止;否则,执行Step8;

//网络重构阶段:

Step8:将Step6中检测出的每个社团分别作为一个节点,对网络进行重构,将社团内的所有边的权值之和作为新节点指向自身的自环边的权值,新节点之间的权值为两个原社团之间连边的权值之和。将重构网络作为输入,重复Step2至Step7进行新一轮迭代。

IMWCD算法的具体流程如图2所示。

图2 IMWCD算法的具体流程

3.3 IMWCD算法分析

(1)实例分析。

在加权网络图中,权值代表了不同节点间联系的紧密程度,而根据社团结构的定义,社团内部节点间联系紧密,社团之间联系稀疏。以图3所示的简单加权网络为例来模拟IMWCD算法对加权网络社团结构的划分过程,检验其社团划分效果。

图3 加权网络

用公式(2)至公式(5)计算每个节点的重要性,得到I1=2.266,I2=3.312,I3=1.753,I4=3.373,I5=1.942,I6=2.306,I7=2.066,按照节点重要性升序排列得到节点序列L={3,5,7,1,6,2,4}。

将网络中的7个节点初始化为7个单独的社团,编号与节点序号对应,分别为C1至C7。

迭代更新阶段:首先考察节点序列L中的节点3(称为目标节点),其邻居节点所在社团集合为{1,2,4},根据公式(1)分别计算将节点3移入其邻居节点所在社团Ci前后的模块度增益ΔQi,分别为:ΔQ1=0.020 2,ΔQ2=0.061 8,ΔQ4=0.025 5,则选择将节点3移入社团C2。同理,依次遍历剩下的节点,以模块度增益最大且为正值为原则,将节点移入相应社团,具体情况如表1所示。

表1 第一次遍历的情况

由表1可知,第一次遍历产生了三个社团,分别为C2(3),C4(1,2,4),C6(5,6,7)。因为有节点移动,所以再次从节点序列L的节点3开始新的遍历,其当前所属社团为C2,邻居社团只有C4,将其移入C4的模块度增益ΔQ4=0.107 4,因为ΔQ4>0,所以将其移入社团C4;继续依次遍历L中其余节点,计算得出这些节点的移动不会使模块度增加(具体计算过程不再赘述),因此在本轮遍历过程中节点3移入C4,C2消失,C6不变。即结果有2个社团,分别是C4(1,2,3,4),C6(5,6,7)。

因为有节点移动,所以要继续从节点序列L的节点3开始新的遍历,再次执行迭代更新,计算得出所有节点变动后的模块度增益均小于零(具体计算过程不再赘述),即所有节点不需再移动,迭代更新阶段结束,划分出的社团结构如图4所示。此时的网络模块度Q=0.428 2。

图4 迭代更新结果

网络重构阶段:将迭代更新检测出的社团作为节点,对网络进行重构,重构的网络如图5所示。为了便于理解,新网络的节点号用对应的社团号表示,两个节点分别是C4和C6。

图5 网络重构结果

对重构后的网络,用公式(2)至公式(5)计算每个节点的重要性得到IC4=2.026,IC6=1.460,升序排列的节点序列为L={C6,C4},重复迭代更新阶段,此时两个节点互为邻居,C6移动到C4所在社团后的模块度增益是ΔQC6=-0.428 3,C4移动到C6所在社团后的模块度增益是ΔQC4=-0.428 3,都小于零,即都不需再移动,迭代更新结束,此时网络模块度为Q'=0.428 2,与上一轮迭代更新结束时的网络模块度Q相同,算法终止。最终划分出的两个社团编号分别为C4和C6。不难看出节点4和节点6在最初的节点重要性升序序列中确实处于高位,因此最终划分的社团以节点4和6为中心,符合实际情况,验证了WNI和IMWCD的有效性。

(2)时间复杂度分析。

在节点重要性计算过程中,根据节点自身权值信息计算重要性的时间复杂度为O(dn);d为网络的平均度值,n为网络中的节点数;基于邻居节点信息计算重要性的时间复杂度为O(dn),按节点重要性升序排序节点的时间复杂度为O(n),因此对于节点重要性计算以及节点重要性排序的算法复杂度为O(dn+dn+n),即O((2d+1)n);传统BGLL算法考察每个节点的邻居节点,时间复杂度为O(dn),计算节点移动的模块度变化的时间复杂度为O(n),移动节点的复杂度为O(n),网络重构阶段的时间复杂度为O(m),m为网络中的边数。因此BGLL算法的时间复杂度为O(dn+n+n+m),即O((d+2)n+m)。实际大规模网络图为稀疏图,因此BGLL的时间复杂度近似O((d+2)n)。综上,IMWCD算法的总复杂度为O((2d+1)n+(d+2)n+m),近似为O(3(d+1)n),算法总的时间复杂度仍然是接近线性的。

4 性能测试实验及结果分析

该文分别在LFR人工基准网络数据集和三个真实加权网络数据集上对所设计的IMWCD算法的性能进行测试,并与BGLL算法和CNM算法做对比。其中,CNM算法首先将有N个节点的网络初始化为n个社团,然后计算社团两两合并前后的模块度增益,用堆结构来构造模块度增量矩阵,选择模块度增益最大的社团进行合并,并更新模块度增量矩阵,直至网络中所有的节点都归到一个社团。该算法针对稀疏网络的时间复杂度为O(mlogn),其中m为边数,n为节点数。

(1)实验数据集。

(a)LFR人工基准网络数据集。

实验使用的LFR人工基准网络数据集参数见表2。

表2 LFR基准网络数据集参数

表中,N表示网络中的节点数量;k表示节点的平均度;maxk表示节点的最大度值;maxc表示最大社团规模;minc表示最小社团规模;u表示混合系数,u越大,社团结构越不明显。为了能够对加权社团划分算法做验证,在数据集生成过程中,对于同一个社团内的连边随机生成[0.5,1]的权值,不同社团之间的边随机生成(0,0.5)的权值。

(b)真实网络数据集。

实验使用的三个较大规模真实网络数据集分别是1995至1999年间高能物理研究领域(High-energy theory)和天体物理研究领域(Astrophysics)的科学家合作网络,以及1995至2005年间凝聚态(Condensedmatter)研究领域的科学家合作网络。以下分别简称H-th、A-ph、C-mat。边的权值表示科学家们的合作次数。数据集的统计特征如表3所示。

表3 数据集统计情况

(2)评价指标。

用标准化互信息NMI[15]来衡量算法对LFR人工基准网络的社团划分准确度,NMI值越大,表明算法划分精度越高;用模块度Q来衡量算法对真实加权网络的社团划分质量,Q值越大,表明社团划分的模块化越强,划分效果越好。

(3)结果分析。

(a)基于LFR人工基准网络数据集的实验结果。

使用三种算法分别对网络N1和N2进行划分,NMI的计算结果如表4所示。

表4 三种算法的NMI值

从表4可以看出,相同混合系数下,随着节点数增多,各算法的NMI值略有下降。相同节点数的情况下,随着混合系数的增加,网络的社团结构越来越模糊,三个算法的表现也逐渐变差,但所设计的IMWCD算法的NMI值始终高于其他两个算法,社团划分的准确性优于其他对比算法。

(b)基于真实加权网络数据集的实验。

表5给出了三种加权网络社团划分算法在真实网络数据集H-th、A-ph、C-mat上分别运行十次得到的平均模块度Q值。

表5 真实加权网络数据集社团划分结果

从表5可以看出,IMWCD算法在三个较大规模的真实加权网络数据集上的模块度Q值都大于其他两个算法,验证了IMWCD算法在划分准确度方面的优势。

5 结束语

考虑到节点重要性对社团划分过程具有更明确的指示作用,以及BGLL算法迭代更新过程中的节点遍历顺序会影响算法划分结果的准确度,设计了一种基于节点重要性和模块度优化的加权网络社团划分算法。综合节点自身权值信息和其邻居节点信息计算节点的重要性,以节点重要性的升序为BGLL算法的节点遍历顺序。理论分析和在人工网络及真实加权网络数据集上的实验结果证明了IMWCD算法在保持线性时间复杂度的同时,克服了BGLL算法节点顺序敏感问题,划分结果的准确度有所提升,能够对加权复杂网络进行有效的社团划分。