Detecting Community Structure in Directed Networks Via Multiple Eigenvectors

现实世界中许多复杂系统都可以用网络^[1]来刻画与描述，如社会网络^[2]、信息和技术网络^[3]及生物网络^[4]等。这些网络大都为有向网络，并且通常呈现出明显的社团结构。探索有向网络的社团结构^[5-9]对于理解网络的结构^[10-11]和其所代表系统的动力学机制有着重要的意义。近年来，很多研究学者提出了不同的算法^[12-15]探索有向网络的社团结构。其中一个重要并且广泛应用的算法为谱聚类算法^[16-19]。该方法利用一个能表示数据集特征矩阵的谱信息划分无向网络的社团结构。这些矩阵包括邻接矩阵^[20]、模块度矩阵^[15]和拉普拉斯矩阵(包括标准的拉普拉斯矩阵^[21]和规范的拉普拉斯矩阵^[22])等。文献[23]比较了这些不同矩阵在社团结构探测中的效果，发现利用规范拉普拉斯矩阵的谱聚类算法所划分的社团结构效果最优，说明利用谱聚类划分社团结构时考虑节点度的异质分布特性是很重要的。根据在不同无向网络上拉普拉斯矩阵的基本性质，文献[24]提出了通用的谱聚类算法，总结了在无向网络上如何利用拉普拉斯矩阵划分社团结构。而对于有向网络，文献[25]基于随机游走过程提出了强连通有向网络的拉普拉斯矩阵，推导了其在有向网络中的性质及其在网络分割中的作用。这些工作为利用拉普拉斯矩阵对有向网络社团划分提供了理论基础。基于文献[25]的理论，文献[26]提出了有向网络拉普拉斯矩阵的扩展形式，用分层有向网络谱分割算法对网络社团结构进行划分。该方法仅仅基于拉普拉斯矩阵次小特征值所对应的特征向量进行社团结构划分。然而，拉普拉斯矩阵的其他特征向量也包含了社团结构的信息。图 1给出了一个包含128个节点，c=6个社团结构(分别记为 ${C_1},{C_2}, \cdots ,{C_6}$ ，c为网络中实际存在的社团结构的个数)的人工网络^[27]上拉普拉斯矩阵前6个较小的特征值所对应的特征向量xi(i=1, 2, …, 6)。从图 1b可以发现节点编号从84~110的特征分量明显跟其他特征分量的值差距较大，即网络中的社团结构C₅可以由第2个特征向量的特征分量体现。同理，从图中可知拉普拉斯矩阵前c个较小特征值所对应的特征向量都包含了社团结构信息，这些特征向量对应节点上的分量反映了网络中真实社团结构(图中虚线分割部分)。

基于上述思想，本文利用多个拉普拉斯矩阵的特征向量(multiple eigenvectors of Laplacian, MEL)识别有向网络的社团结构。首先，给出了有向网络拉普拉斯矩阵的形式。然后，针对不同情况下的有向网络修正了转移概率矩阵使其具有唯一的稳态分布，详细描述了MEL算法的步骤。最后，通过实验将该算法与模块度的谱优化算法^[15](spectral optimization method, SOM)和模拟退火算法^[28](simulated annealing, SA)做了对比分析。实验结果表明本文的算法能更加准确地探索有向网络的社团结构。

假设网络 $G = (V;E)$ 是由 $\left| V \right| = n$ 个节点和 $\left| E \right| = m$ 条边所组成的一个有向网络， $V = \{ {v_1},{v_2}, \cdots ,{v_n}\} $ ， $E = \{ {e_1},{e_2}, \cdots ,{e_m}\} $ 。矩阵A是网络G的邻接矩阵， $d_i^{{\rm{in}}}$ 和 $d_i^{{\rm{out}}}$ 分别表示节点i的入度与出度。出度矩阵 ${\mathit{\boldsymbol{D}}^{{\rm{out}}}}$是对角线对应每个节点出度的对角矩阵。由随机游走理论^[29]可知，网络G的转移概率矩阵P为：

如果有向网络G是强连通网络(即网络中任意两个节点都能相互到达)，那么根据Perron-Frobenius定理^[30]0可知转移概率矩阵P至少有一个左特征向量，它所对应的特征值为1。如果转移概率矩阵P有唯一一个特征值为1，那么网络G是非周期的。为了探索网络G的社团结构，分情况讨论。

首先，假定网络G是强连通并且是非周期的，则对应的转移概率矩阵P有唯一的左特征向量π满足：πP=π，其中特征向量π为随机游走的稳态分布。定义对角矩阵Π对角线元素的值为π的每个分量，即 $\mathit{\boldsymbol{\Pi }} = {\rm{diag}}({\pi _1},{\pi _2}, \cdots ,{\pi _n})$ 。那么，有向网络的拉普拉斯矩阵L有如下形式：

式中，矩阵I为单位矩阵。

其次，如果网络G为强连通但不是非周期的，转移概率矩阵P没有唯一的稳态分布。引入另外一个矩阵P_lazy^[26]来解决这个问题。给定一个强连通不是非周期的网络转移概率矩阵P， ${\mathit{\boldsymbol{P}}_{{\rm{lazy}}}} = \frac{{\mathit{\boldsymbol{I}} + \mathit{\boldsymbol{P}}}}{2}$ 。对于矩阵P_lazy所对应的网络每个节点都带有自环并且又是强连通的，因此该网络是非周期的^[26]。当有向网络G不是非周期时用P_lazy代替P，此时网络具有唯一的稳态分布。

最后，如果网络G不是强连通的, 本文引入PageRank转移概率矩阵P_PR：

式中，向量e为n维的单位向量；1−α是网络中的节点随机转移到任意节点的概率，本文设α=0.99。当网络不是强连通网络时，用P_PR代替P，再计算该网络的拉普拉斯矩阵。

通过上面的转化，可以得到不同情况下有向网络G的拉普拉斯矩阵形式，从而利用拉普拉斯矩阵前c个特征值对应的特征向量进行社团划分。

利用拉普拉斯矩阵的多个特征向量所包含的社团结构信息，本文提出了基于拉普拉斯矩阵多重特征向量划分社团结构的算法，算法具体步骤描述如下。

1) 计算转移概率矩阵： $\mathit{\boldsymbol{P}} = {({\mathit{\boldsymbol{D}}^{{\rm{out}}}})^{ - 1}}\mathit{\boldsymbol{A}}$ 。

2) 根据矩阵P特征值1的个数判断网络G的类型, 下面分3种情况讨论：

① 如果网络G是强连通并且是非周期的，令 $\mathit{\boldsymbol{P'}} = \mathit{\boldsymbol{P}} = {({\mathit{\boldsymbol{D}}^{{\rm{out}}}})^{ - 1}}\mathit{\boldsymbol{A}}$ ；

② 如果网络G是强连通但不是非周期的， $\mathit{\boldsymbol{P'}} = {\mathit{\boldsymbol{P}}_{{\rm{lazy}}}} = \frac{{\mathit{\boldsymbol{I}} + \mathit{\boldsymbol{P}}}}{2}$ ；

③ 如果网络G不是强连通，有：

3) 计算转移概率的稳态分布π： $\pi \mathit{\boldsymbol{P'}} = \pi $ 。

4) 计算网络G的拉普拉斯矩阵：

5) 计算拉普拉斯矩阵的特征值λ及其对应的特征向量矩阵X： $\mathit{\boldsymbol{LX}} = \lambda \mathit{\boldsymbol{X}}$ 。

6) 对特征值从小到大进行排序取前c个特征值所对应的特征向量 $\mathit{\boldsymbol{X'}} = ({\mathit{\boldsymbol{x}}_1},{\mathit{\boldsymbol{x}}_2}, \cdots ,{\mathit{\boldsymbol{x}}_c})$ ，这里c为网络中社团结构的个数。对矩阵 $\mathit{\boldsymbol{X'}}$ 用k-means算法聚类得到每个节点的社团结构标号矩阵M。

本文采用归一化互信息^[31-32](normalized mutual information, NMI)来评价算法对网络社团结构划分的准确性。NMI计算公式如下：

式中， ${M_1}$ 是网络的真实的社团结构； ${M_2}$ 是用算法得到的社团结构； ${N_c}$ 是社团结构的数量；n是网络的节点数； ${n_{st}}$ 表示真实社团s中的节点划分在算法得到的社团t中的数量； $n_s^{(1)}$ 表示在真实社团结构s中节点的数量； $n_t^{(2)}$ 表示在算法得到的社团t中节点的数量。对于该评价标准，如果算法划分所得到的社团结构与网络中真实存在的社团结构完全一致的话，则NMI取最大值1；而当划分结果最差，即划分出来的社团结构与网络中真实存在的社团结构完全不一样，也就说二者没有重叠，这时NMI取最小值0。

使用NMI指标评价社团结构算法性能时必须知道网络的真实社团结构信息，对于网络社团结构信息未知的这种情况，采用模块度指标Q来衡量算法的优劣。模块度^[33]是用于刻画社团特性强弱的参数，是应用广泛的评判社团结构强弱的指标。文献[15]将其扩展到了有向网络，其公式如下：

式中， ${C_i}$ 是节点i所属的社团，当 ${C_i} = {C_j}$ 时 ${\delta _{{c_i},{c_j}}} = 1$ ，否则为0；Q值在0和1之间，Q值越大说明该算法对于划分社团结构越有效。一般以Q=0.3作为网络具有明显社团结构的下界。

为了测试MEL算法的性能，分别利用人工网络和真实网络进行社团划分实验。在实验中，与常见典型社团划分算法进行了比较，参与对比的算法如下。

1) 模块度矩阵谱聚类^[15]：以模块度矩阵最大特征值对应的特征向量来逐次将网络节点进行二分，记为SOM (spectral optimization method)；

2) 基于模块度的模拟退火算法^[28]：首先随机生成一个初始解；在每次迭代中，在当前解的基础上产生一个新的候选解，由模块度函数判断其优劣，并采用模拟退火策略中的Metropolis准则决定是否接受该候选解，记为SA (simulated annealing)。

人工网络按照已知的社团结构产生，可以测试不同算法划分社团结构的有效性。

采用两种广泛使用的人工生成网络来测试算法的性能，分别为GN (Girvan-Newman)^[5]和LF (Lancichinetti-Fortunato) ^[27]基准网络。

1) GN基准网络

本文测试了两种类型的GN网络，包含128个节点。第一种为社团结构数量为4，每个社团含有32个节点，即社团规模是均匀分布的，记为GN₁；另外一种为社团结构规模不均匀的情况，记为GN₂。本文产生的GN网络为有向网络，每个节点的平均入度 $\langle {d^{{\rm{in}}}}\rangle $ 为10。另外还引入了一个能刻画网络社团结构的参数 $\mu $ ，它是一个混合比例，是网络中的节点连接社团外部的度与该节点总的度数的比例。随着 $\mu $ 的增加，网络的社团结构越不明显。

2) LF基准网络

为了进一步评估本文算法的精度，采用了另一种人工基准网络。该网络与GN网络的不同在于网络中的节点的度分布和社团规模分布均服从幂律分布，这一点与真实世界网络更为相似。本文选取的LF网络的参数如下：网络的节点数为1 000，节点的平均入度为20，最大入度值为50。

本文测试了两种不同社团大小规模分布的网络。一个是社团结构大小在10~50之间，记为LF₁；一个是20~100之间，记为LF₂。

对于这两种网络的测试结果如图 2所示。从中可以看出，本文的算法在探索有向网络的社团结构时的性能。图 2a为GN网络中社团结构规模均匀的情况，当 $\mu \le 0.4$ 时即网络社团结构比较明显，本文的算法跟SA算法所得到的NMI的值都能达到1，能准确地划分网络的社团结构。随着 $\mu $ 的增加，当 $0.4 < \mu \le 0.5$ 时，本文算法所取得NMI值有所下降，但比SA算法取得的效果要好。图 2b显示了GN网络社团结构规模分布不均匀的实验结果，结果跟图 2a类似，可以发现当网络中社团结构明显时即 $\mu \le 0.4$ ，本文的算法能准确划分社团结构。并且当 $\mu > 0.4$ 时，即网络社团结构越来越不明显时，MEL算法划分社团结构的效果要优于SA和SOM算法。当 $\mu = 0.5$ 时，MEL算法所得NMI值比SA算法提高了9.50%。

图 2c~图 2d给出了每种算法的NMI值在LF网络上随混合参数 $\mu $ 的变化趋势。可以看出，当 $\mu \le 0.7$ 时，本文算法所得到的NMI的值接近于1，并且略优于SA算法，能较为准确地划分网络的社团结构。当 $0.7 < \mu \le 0.8$ 时，即网络的社团结构并不明显，SA算法明显下降，本文的算法也有所下降但NMI值仍大于其他两种算法。实验结果表明本文算法在有向网络探索社团结构上的有效性。

本文使用的数据为美国伊利诺斯州的一个中学朋友关系的社会网络^[34]。该网络为有向的朋友关系，节点代表一个人，边代表他们之间的选择朋友关系。该网络有70个节点和366条边。用MEL、SOM和SA这3种算法对该网络进行社团结构划分，然后计算得到了每种算法的模块度值如表 1所示。

从表 1可以得知MEL算法比其他两种算法Q值分别提高了17.28%和19.21%，说明本文算法对实际社交网络的社团结构划分也有一定的有效性。

然而，由于真实网络的社团结构的数量是未知的，因此，本文首先要解决的一个问题是将真实网络的社团结构个数找出来。本文根据邻接矩阵的谱性质^[21]，即具有社团结构的网络，它的邻接矩阵的c个特征值与其他特征值相差较远，因此可以得到网络的社团结构的个数。通过该方法计算得到了本文实证网络的社团结构个数为10。

本文考虑多个拉普拉斯矩阵的特征向量，提出了一种谱聚类算法来探索社团结构。首先计算有向网络的拉普拉斯矩阵，并得到其特征向量。然后，取前c个作为聚类目标得到网络的社团结构。人工网络的实验结果表明该算法能有效划分网络的社团结构。当社团结构明显时，本文算法能准确地划分网络的社团结构；当网络社团结构不明显时，与模块度的谱优化和模拟退火算法相比，本文算法取得的效果更好。在实证网络上，模块度Q分别提高了17.28%和19.21%。本文算法考虑了多个特征向量所包含的社团结构信息，并没有迭代过程，因此算法较为简单和高效。

本文利用拉普拉斯矩阵的多个特征向量对有向网络的社团结构进行了划分，该工作可以进一步扩展，比如对于非强连通网络拉普拉斯矩阵的形式可以用其他方法^[35-36]修正转移概率矩阵的形式，算法最后一步也可以用其他聚类算法来代替k-means算法等。本文的工作有助于研究者认识有向网络的拉普拉斯矩阵特征向量与网络结构的关系。