【学术论文】基于非加权图的大型社会网络检测算法研究
近年来，随着信息交互和数据共享的不断增加，社交网络的数量显著提高。在分析此类网络时，图论提供了一个重要的建模模型。当节点代表用户，边表示互联时，可以将此类网络定义为一张图[1-3]，该图中的节点可以是直接或间接相连的。在分析社交网络数据时，定义和计算社区是最关键的步骤。同时,社区可以被看作是对整个网络的概要表示(Summarization)，因此,在社区检测中需要使用这种概要设计理念[4]。
当前对于社区网络划分研究已取得了很多研究成果，特别是社会网络分析，但其仍然是一项具有挑战性和吸引力的研究。因为在给定的图中进行社区检测，可以用于搜索潜在的合作者，用于优化社会关系，或在不同的社区中搜索一个关键人物等[5]。
基于图论的原理，已经提出了不少方法用来解决社区检测的问题，如谱分析方法[6]，其代表了一种非常特殊的社区检测技术。这种方法的特殊性表现在其分类性能上，并以拉普拉斯矩阵的特征向量为基础。使用这样一个矩阵在时间和内存方面需要付出很高的代价。此外，在时间复杂度上，k个特征向量的计算复杂度为O(n3)。虽然，很容易计算出给定矩阵的特征向量，但是不方便计算大型拉普拉斯矩阵。这个方法的第二个缺点是假设社区的数量必须是已知的，但是在实际的大型社交网络中很难获得这一信息。文献[7]提出了一种基于聚类概念的社区检测方法。这种技术的优点是它能够提供丰富的结果，使用这种方法发现的社区节点之间相互连接非常紧密。然而，在时间和内存方面代价很高，而且非常复杂。BASUCHOWDHURI P等人[8]提出了一种基于最大生成树的并发方法。该方法使用共同邻居的相似性作为边的权重。将每个节点都与邻居相连接，共享了大量的共同邻居，从而建造了最大生成树。与文献[7]的方法相比较，这种方法在占用内存方面效果较好，但是其时间运行成本还是较高。文献[9]提出了一种基于节点和边的检测社区方法，可广泛用于查找网桥和服务供应商。但是，对于大型的社交网络而言，这些方法的适用性均较差。
在以上文献提出的方法中，运行时间的复杂度和内存的使用成本问题仍然存在。因此，它们的适用性具有一定的局限。为了解决这些问题，本文提出了一种有效的社区检测算法方法，该方法基于聚类系数和共同邻居指标。实验结果表明，在大规模社会网络数据集中提出的方法提供了较高质量的社区划分结果，并具备线性运行时间的复杂度特性。
1 模型和指标定义
1.1 问题描述
在一个网络模型中，一张图G由有限集合(V，E)构成，其中V表示节点集合(网络的用户)，E表示边或节点之间相互联系的集合，V={vi|i=1，…，n}，E={eij|vi，vj∈V}，n=|V|为节点总数，m=|E|为边的总数。此外，当图G′中节点的集合E′和边的集合V′都是图G中V和E的子集
时，G′表示G的子图。社交网络可以建模为一个有向图或一个无向图，其中节点表示个体，边表示节点之间的关系。本文重点是在社交网络中进行社区检测，它可以用一个无向图来表示。这个社区可以被定义为节点的一个子集，与网络的其他节点相比较，这些节点更有可能连接在一起。图1显示了一张具有3个社区的信息图。
1.2 采用的度量标准
本文采用共同邻居的相似性来衡量两个节点的相似度，这意味着，当此度量指标较高时，节点更有可能是在同一个社区内。相比应用平均聚类系数来衡量集群的方法，本文提出的结果准确性更高。本文采用了两种度量标准：
(1)共同邻居的相似性：在参考文献[8]和[10]中使用共同的邻居来定义节点之间的相似性。如果两个节点有大量的共同邻居，那么它们更相似。这个指标由以下公式进行计算。
式中，A表示邻居相似性。
(2)聚类系数：采用此类度量标准的目的是评估节点在一个集群中的集群化趋势。其中最受欢迎的一个测量标准是模块性最大化，但是它存在两个问题：①它合并小型子图，当分辨率较低时，它占主导地位；②它分裂大型子图，当分辨率较高时，它占主导地位。另一种被广泛使用的度量称为聚类系数[10-11]，在一个社区内提供了一个强大的邻居结构。这项标准被广泛应用于社会网络分析中，它被定义为封闭的三联体(三角形)数量和给定图的三联体数量之间的比率，式(2)给出了其定义[2]：
式中，C表示聚类系数。
2 提出的权重系数
本研究的目的是研究社区之间的边所存在的一些性质，最后提取新的社区。
引理1：假设G是一张无向非加权图，E表示G的边集合，V表示G的节点集合，得到如下公式：
其中，L表示节点vi邻居之间的关联数量。
论证：假设G为一张图，仅仅包含一个三角形T，本文假设它由3个节点组成(v1，v2，v3)。
如果计算L(v1)，则发现一对关联(v2和v3)；如果计算v2的这一度量，则发现v1和v3之间的关联；最后计算v3，得到了v1和v2之间的关联。之后，如果计算总和L(v1)+L(v2)+L(v3)，那么得到的结果是3对关联。总之，当本文计算一张图中每个节点与其邻居之间的关联数量时，对同一个三角形计算了3次。
图2阐释了一张无向图，由7个节点和10条边构成。该图由3个三角形组成。当本文计算这7个节点邻居之间的关联数量总和时，得到表1所示结果。
根据这些结果，3个三角形共计算了3次，这意味着3×(在G1中的三角形数量)等于在G1中每个节点邻居之间的关联数量总和。
性质1：运用式(1)，本文可以得出结论：两个社区之间的一条边的节点是不同的。它们没有或仅有少数几个共同的邻居。
性质2：本文研究的重点在于在社区内最大化聚类系数(式(2))。为了达到这一目标，三角形的数量以及式(4)中的度量必须尽可能地最大化。实际上，在一个社区中每个节点邻居之间的关联数量必须最大化。这意味着对于具有较高聚类系数(大量三角形)的两个社区之间的节点，其邻居之间的关联数量较大。
引理2：假设G是一张无向非加权的图。在两个社区之间一条边e(vi，vj)的节点没有或有几个共同邻居，节点vi和vj具有较高的度量L。
论据：通过使用性质1和性质2获得引理2。
本文将节点邻居之间的关联数量标准化。由以下方程来定义标准化：
式中，B表示的是节点邻居关联数据标准。
通过式(1)可知节点之间共同邻居的数量。从引理2可以得知，本文的目标是找到这些边e(vi，vj)，它们在邻居i和j之间的关联数量较大(见式(5))，而在i和j之间的共同邻居数量较少(见式(1))。因此，以这些边为基础，所提方法的目标是找到度量W，W可以由如下公式定义：
3 本文提出的方法
在过去的几年中，在社交网络中进行社区检测已经吸引了很多研究人员，但它仍是一项具有挑战性的任务。事实上，大多数现有方法的适用性受限于它们的计算成本。本文提出的方法通过删除在未加权图中的社区之间的边，从社交网络中找到社区。本文假设一个社区必须至少有4个节点，如参考文献[2]所使用的社区。删除边是为了最小化每条边节点之间的共同邻居数量(少于共同邻居的20%)，并且提高社区划分的质量。下面介绍算法步骤和实例分析。
3.1 算法描述
本文提出的方法使用了以下步骤：
输入：无向非加权的网络G(V，E)
输出：n个社区，Gs={Gs1，Gs2，…，Gsn}
(1)首先，本文计算在图G中每个节点邻居之间的关联数量L(vi)。然后，本文计算每条边e共同聚类数量C，以及这条边的节点之间邻居U的结合情况。之后，设L=L(vi)+L(vj)和S=|邻居(vi)+邻居(vj)|，其中vi、vj表示由边e相连的两个节点。
(2)本文使用W在表格T中以递减顺序对边进行分类。一旦这个操作完成，就按照在T中的顺序找到第一条边e(vi，vj)。如果在删除这条边之后，vi邻居的数量和vj邻居的数量均会超过0，那么将这条边从G中删除，否则不删除。本文需要对T中的其他边重复测试，直到表格T是空为止。
(3)本文应用了一个社区必须至少包含4个节点的假设。为了确保该假设成立，需要把每张少于4个节点的子图G′加入到在步骤(2)中已经被分离的最后一张子图中。
3.2 实例分析
设一个网络N1结构如图3所示，图4体现了提出的方法应用于网络N1的结果。首先，运用步骤(1)在未加权的图中计算每条边的W值。然后，本文选择符合以下条件的边e(vi，vj)：在节点vi和vj之间共同邻居的数量较低(少于20%)。
本文运用W值对这些边进行分类，按照递减顺序将这些边储存在表格T中。重复步骤(2)中边的删除操作，直到为空白为止。注意，大小小于2的群组不可以被分为独立的群组。
最后，本文将少于4个节点的每张子图G′加入到已经被分离的最后一张子图中。
4 实验结果与分析
为了验证本算法的有效性，采用真实的较大规模社会网络数据集进行实验分析，并与生成树算法[8]、CBCD算法[12]进行比较分析。
实验环境中服务器设备参数为：Xeon E7-4820双核处理器，2.5 GHz CPU频率，16 GB内存，Windows Server 2012系统。本文在核心图社区检测时采用GN算法(Girvan-Newman)。
本文采用模块性Q函数[13]来评价划分出的模块性，采用NMI[13]来评价划分结果的相似性，两个评价指标的数值越接近1，说明算法划分的效果和质量越高。实验采用的4个较大社会网络数据集的具体参数如表2所示。
4.1 结果分析
采用生成树算法、CBCD算法和本文提出算法在以上4个社会网络数据集上分别进行了100次运行测试，实验结果的平均指标数据如表3所示。
通过表3可以看出，在Q函数指标结果上，本文提出算法比其他两种算法都表现更好，即社会发现更有效，更好地体现了社区结构的划分。在NMI指标结果上，相比其他两种算法，本文算法的数值更接近于1，即划分结果和真实的划分更相似。
从表4中可以看出，本文算法在4个社会网络数据集上的运行时间均比其他两种算法少，即相比其他两种算法，本算法具有更高的效率。
4.2 复杂度分析
该方法不是对所有的边进行分类，而仅仅对共同邻居少于20%的边进行分类。例如，在Ca-CondMat网络中，包含186 936条边，本文仅仅对其中的67 297条边进行分类。同样，本文在Cit-HepTh网络中仅仅对352 807条边中的176 403条边进行分类。
在步骤(2)中，本文对一部分共同邻居少于20%的边进行分类。如果本文假设这些边的数量为k，那么复杂度为O(k·log(k))，即具有线性复杂度。在本算法的实施过程中，运用了python 3.3分类算法。如果假设在步骤(3)的操作之后发现子图的数量为c，由少于4个节点构成的子图数量为c1，那么复杂度为O(c1·log2(c))。因为O(c1·log2(c))<<O(N)，根据所选择的网络，本文得到出算法的复杂度取决于O(k·log(k))。因此，本文提出的算法具有线性复杂度，即使在运行时间最坏的情况下，复杂度为O(k·log(k))。
5 结束语
本文提出了一种适用于社交网络的新型社区检测新方法。该方法使用了两个最重要的度量来定义社区：(1)聚类系数，用于定义社区的质量；(2)属于同一条边的两个节点共同邻居的数量。实际上，与在不同社区中的两个节点相比，在同一个社区中的两个节点具有的共同邻居数量较高。基于这些度量，本文推导出一个公式，允许在社区之间查找边。在这个迭代的算法中，运用一些查找社区的标准来删除边。最后，实验结果表明，与传统的算法相比，本文提出的方法提供的网络数据集合划分不但模块性高，NMI指标和运行效率也非常高。此外，该方法的运行时间具有线性复杂度，由此可以应用于大型的社交网络中。