基于非加权图的大型社会网络检测算法研究

1、基于非加权图的大型社会网络检测算法研究随着信息交互和数据共享的不断增加，社交网络的数量显著提高。在分析此类网络时，图论提供了一 个重要的建模模型。当节点代表用户,边表示互联时，可以将此类网络定义为一张图“】,该图中的节点可 以是直接或间接相连的。在分析社交网络数据时，定义和计算社区是最关键的步骤。同时，社区可以被看作 是对整个网络的概要表示(summarization),因此，在社区检测中需要使用这种概要设计理念。当前对于社区网络划分硏究已取得了很多硏究成果，特别是社会网络分析，但其仍然是一项具有挑战 性和吸弓i力的硏究。因为在给定的图中逬行社区检测,可以用于搜索潜在的合作者,用于优化社会关系

2、， 或在不同的社区中搜索一个关键人物等。基于图论的原理，已经提出了不少方法用来解决社区检测的问题，如谱分析方法，其代表了一种非 常特殊的社区检测技术。这种方法的特殊性表现在其分类性能上，并以拉普拉斯矩阵的特征向量为基础。 使用这样一个矩阵在时间和内存方面需要付出很高的代价。此外,在时间复杂度上，k个特征向量的计算 复杂度为0(2)。虽然，很容易计算出给定矩阵的特征向量，但是不方便计算大型拉普拉斯矩阵。这个方 法的第二个缺点是假设社区的数量必须是已知的，但是在实际的大型社交网络中很难获得这一信息。文献 刀提出了一种基于聚类概念的社区检测方法。这种技术的优点是它能够提供丰富的结果，使用这种方法发

3、现的社区节点之间相互连接非常紧密。然而,在时间和内存方面代价很高，而且非常复杂。 basuchowdhuri p等人冈提岀了一种基于最大生成树的并发方法。该方法使用共同邻居的相似性作为 边的权重。将每个节点都与邻居相连接，共享了大量的共同邻居,从而建造了最大生成树。与文献刀的方 法相比较,这种方法在占用内存方面效果较好，但是其时间运行成本还是较高。文献9提出了一种基于节 点和边的检测社区方法，可广泛用于查找网桥和服务供应商。但是，对于大型的社交网络而言，这些方法 的适用性均较差。在以上文献提出的方法中，运行时间的复杂度和内存的使用成本问题仍然存在。因此，它们的适用性 具有一定的局限。为了解决这

4、些问题，本文提出了一种有效的社区检测算法方法，该方法基于聚类系数和 共同邻居指标。实验结果表明，在大规模社会网络数据集中提出的方法提供了较高质量的社区划分结果， 并具备线，性运行时间的复杂度特，性。1.1问题描述在一个网络模型中,一张图g由有限集合(v , e)构成,其中v表示节点集合(网络的用户)，e表示边 或节点之间相互联系的集合,v=vj|i=l, . , n , e=eij|vi, vjev , n = |v|为节点总数,m = |e|为边的总 f 和 i ' c i 数。此外，当图g中节点的集合e和边的集合v'都是图g中v和e的子集山“丨 j 时,g'表示g的

5、子图。社交网络可以建模为一个有向图或一个无向图，其中节点表示个体,边表示节点之 间的关系。本文重点是在社交网络中进行社区检测，它可以用一个无向图来表示。这个社区可以被定义为 节点的一个子集,与网络的其他节点相比较，这些节点更有可能连接在一起。图1显示了一张具有3个社 区的信息图。1.2采用的度量标准本文采用共同邻居的相似性来衡量两个节点的相似度,这意味着,当此度量指标较高时，节点更有可 能是在同一个社区内。相比应用平均聚类系数来衡量集群的方法，本文提出的结果准确性更高。本文采用 了两种度量标准：(1) 共同邻居的相似性：在参考文献8和10中使用共同的邻居来定义节点之间的相似性。如果两个 节点有

6、大量的共同邻居，那么它们更相似。这个指标由以下公式进彳亍计算。式中，a表示邻居相似性。(2) 聚类系数：采用此类度量标准的目的是评估节点在一个集群中的集群化趋势。其中最受欢迎的一 个测量标准是模块性最大化，但是它存在两个问题：它合并小型子图,当分辨率较低时,它占主导地位； 它分裂大型子图，当分辨率较高时，它占主导地位。另一种被广泛使用的度量称为聚类系数"o-m ,在一 个社区内提供了一个强大的邻居结构。这项标准被广泛应用于社会网络分析中，它被定义为封闭的三联体 (三角形)数量和给定图的三联体数量之间的比率，式(2)给出了其定义：式中，c表示聚类系数。本研究的目的是研究社区之间的边所存

7、在的一些性质，最后提取新的社区。引理1 ：假设g是一张无向非加权图，e表示g的边集合，v表示g的节点集合，得到如下公式：厶他)=2(叹宀)w £!必，巧w v(3)3x三角形的数量二工厶(坯)(4)uc v其中，l表示节点vi邻居之间的关联数量。论证：假设g为一张图，仅仅包含一个三角形t ,本文假设它由3个节点组成(vi , v2, v3)o如果计算l(v1),则发现一对关联(v2和v3)；如果计算v2的这一度量，则发现vi和v?之间的关联； 最后计算v3 ,得到了 vi和v2之间的关联。之后，如果计算总和l(vi) + l(v2)+ l(v3),那么得到的结果是3 对关联。总之,当

8、本文计算一张图中每个节点与其邻居之间的关联数量时，对同一个三角形计算了 3次。图2阐释了一张无向图，由7个节点和10条边构成。该图由3个三角形组成。当本文计算这7个节 点邻居之间的关联数量总和时，得到表1所示结果。根据这些结果，3个三角形共计算了 3次,这意味着3 x (在g1中的三角形数量)等于在g1中每个节点邻居之间的关联数量总和。性质1:运用式(1),本文可以得出结论：两个社区之间的一条边的节点是不同的。它们没有或仅有少 数几个共同的邻居。性质2 :本文研究的重点在于在社区内最大化聚类系数(式(2)。为了达到这一目标，三角形的数量以 及式(4)中的度量必须尽可能地最大化。实际上，在一个社

9、区中每个节点邻居之间的关联数量必须最大化。 这意味着对于具有较高聚类系数(大量三角形)的两个社区之间的节点，其邻居之间的关联数量较大。引理2 :假设g是一张无向非加权的图。在两个社区之间一条边e(vi, v的节点没有或有几个共同邻 居，节点vi和vj具有较高的度量l。论据:通过使用性质1和性质2获得引理2。本文将节点邻居之间的关联数量标准化。由以下方程来定义标准化：式中，b表示的是节点邻居关联数据标准。通过式可知节点之间共同邻居的数量。从引理2可以得知，本文的目标是找到这些边e(vi, v， 它们在邻居i和j之间的关联数量较大(见式)，而在i和j之间的共同邻居数量较少(见式)。因此，以 这些边

10、为基础，所提方法的目标是找到度量w , w可以由如下公式定义：在过去的几年中，在社交网络中进行社区检测已经吸引了很多研究人员，但它仍是一项具有挑战性的 任务。事实上，大多数现有方法的适用性受限于它们的计算成本。本文提出的方法通过删除在未加权图中 的社区之间的边，从社交网络中找到社区。本文假设一个社区必须至少有4个节点，如参考文献2所使用 的社区。删除边是为了最小化每条边节点之间的共同邻居数量(少于共同邻居的20%),并且提高社区划分 的质量。下面介绍算法步骤和实例分析。3.1算法描述本文提出的方法使用了以下步骤：输入：无向非加权的网络g(v, e)输出:n 个社区，gs = gsi , gs2

11、 , . , gsn首先，本文计算在图g中每个节点邻居之间的关联数量l(vi)。然后，本文计算每条边e共同聚类 数量c,以及这条边的节点之间邻居u的结合情况。之后，设l二l(w)+l(vj)和s=|邻居")+邻居山)| ,其 中w、切表示由边e相连的两个节点。炉二丄丄 0(),-<0.2cxsu(7)w=lxu c=0本文使用w在表格t中以递减顺序对边进行分类。一旦这个操作完成，就按照在t中的顺序找到 第一条边e(vi , vj)。如果在删除这条边之后，w邻居的数量和vj邻居的数量均会超过0,那么将这条边从g 中删除，否则不删除。本文需要对t中的其他边重复测试，直到表格t是空为

12、止。g)本文应用了一个社区必须至少包含4个节点的假设。为了确保该假设成立，需要把每张少于4个 节点的子图g加入到在步骤中已经被分离的最后一张子图中。3.2实例分析设一个网络n1结构如图3所示，图4体现了提出的方法应用于网络ni的结果。首先，运用步骤 在未加权的图中计算每条边的w值。然后，本文选择符合以下条件的边e(vi, v：在节点w和vj之间共 同邻居的数量较低(少于20%)。本文运用w值对这些边进行分类,按照递减顺序将这些边储存在表格t中。重复步骤中边的删除 操作，直到为空白为止。注意，大小小于2的群组不可以被分为独立的群组。最后,本文将少于4个节点的每张子图g加入到已经被分离的最后一张子

13、图中。为了验证本算法的有效性，采用真实的较大规模社会网络数据集进行实验分析,并与生成树算法【8】、 cbcd算法心】进行比较分析。实验环境中服务器设备参数为：xeon e7-4820双核处理器，2.5 ghz cpu频率，16 gb内存， windows server 2012系统。本文在核心图社区检测时采用gn算法(girvan-newman)o本文采用模块性q函数问来评价划分出的模块性，采用nmi3来评价划分结果的相似性，两个评价 扌旨标的数值越接近1 ,说明算法划分的效果和质量越高。实验采用的4个较大社会网络数据集的具体参数 如表2所示。4.1结果分析采用生成树算法、cbcd算法和本文提

14、岀算法在以上4个社会网络数据集上分别进行了 100次运行 测试，实验结果的平均指标数据如表3所示。通过表3可以看出，在q函数指标结果上，本文提出算法比其他两种算法都表现更好，即社会发现 更有效，更好地体现了社区结构的划分。在nmi指标结果上，相比其他两种算法，本文算法的数值更接近 于1,即划分结果和真实的划分更相似。从表4中可以看出，本文算法在4个社会网络数据集上的运行时间均比其他两种算法少，即相比其 他两种算法，本算法具有更高的效率。4.2复杂度分析该方法不是对所有的边进行分类，而仅仅对共同邻居少于20%的边进行分类。例如，在ca-condmat 网络中，包含186 936条边，本文仅仅对其

15、中的67 297条边进行分类。同样，本文在cit-hepth网络中 仅仅对352 807条边中的176 403条边进行分类。在步骤中，本文对一部分共同邻居少于20%的边进行分类。如果本文假设这些边的数量为k ,那 么复杂度为o(klog(k),即具有线性复杂度。在本算法的实施过程中，运用了 python 3.3分类算法。如 果假设在步骤g)的操作之后发现子图的数量为c ,由少于4个节点构成的子图数量为ci,那么复杂度为 o(clog2(c)。因为o(clog2(c)v<o(n),根据所选择的网络，本文得到岀算法的复杂度取决于 o(k log(k)。因此，本文提出的算法具有线性复杂度，即使在运行时间最坏的情况下，复杂度为o(klog(k)。本文提岀了一种适用于社交网络的新型社区检测新方法。该方法使用了两个最重要的度量来定义