大规模网络中局部层次重叠社区的检测

王一萍

大规模网络中局部层次重叠社区的检测

王一萍

（齐齐哈尔大学 计算机与控制工程学院，黑龙江 齐齐哈尔 161006）

现实世界网络的规模越来越大，使得检测社区的工作变得更具有挑战性．提出了一种可扩展的局部社区检测方法，可有效地发现网络中给定节点的重叠社区．通过考虑图中链接对的相似性及它们在多个环境中的参与程度，确定加入链接对的顺序，形成有意义的分层社区．实验评估时使用了5个大型真实网络的真实社区，结果表明，LDLC算法在准确性和效率方面都显著优于最先进的方法．

复杂网络；等级社区；社区检测；分散

社区结构是现实世界网络的一个重要特性[1]．社区是有共同属性的节点组，如2个人可能在同一所学校、2部电影可能至少有一个共同演员．然而，社区往往是重叠的．如社交网络中某个人可能存在很多社区，如家人、同事、大学同学社区等．很明显社区可能以不同方式重叠，如同事也可能是大学同学．重叠社区可能有一个复杂的联结结构，与不重叠社区相比，识别重叠社区更具挑战性．早期社区检测方法侧重于对网络节点进行分组，或者侧重于删除分离集群的链接[2]764．然而，这些方法没有考虑社区重叠，从而无法准确地表示网络的社区结构．已有很多算法允许节点属于几个重叠社区[3-5]，但不适用于大数据的海量图．需要从全局结构转移到网络的局部观点，在局部上扩展感兴趣社区中的一组目标节点．

本文将重点放在网络中单个节点的邻接点上，提取它的可能重叠社区．借鉴链接聚类的思想，采用相似性度量，有效地处理社区之间密集链接的重叠．直觉上，当对链接分组时，应该捕获链接属于多个重叠社区的节点．利用一种基于分散度的联结强度的测量来量化参与多个社区的相邻节点．

1 背景知识

1.1 邻域网络

大规模图的挖掘通常基于节点的局部邻域[6-7]，允许对给定节点的邻接点集合进行各种分析．集中于节点的局部邻域，以扩展到大型网络中，因为可以对网络中的所有节点并行执行．在社交网络的背景下，这个节点的直接邻接点通常被称为结点的邻域网络（egonet）．

1.2 链接强度度量

对于社交网络，有共同背景的人更有可能分享共同活动． 因此，嵌入性可有效地应用于夫妻的识别[5]85．

使用式（4），发现式（4）第3次迭代后产生的值较好．

1.3 分区密度

2 LDLC算法

LDLC是一种聚类算法，目标是揭示网络中单个目标节点可能重叠社区的层次结构

LDLC算法描述：

2.1 加载egonet初始化社区

2.2 计算u的邻接点的递归分散值

2.3 计算链接节点对的相似性

目的是得出共享公共节点egonet中所有对链接的相似性．为此，对于egonet中的每个节点，检查其链接的所有可能节点的相似性，使用小顶堆可以使保持链接对的相似性排序．首先使用Jaccard相似系数计算2个链接的距离，然后使用之前计算的递推分散值来平衡这个距离，使用公式（6），最后将得到的相似值插入堆中，保持所有节点对的相似性．

2.4 创建树状图

2.5 分析LDLC

2.6 减少搜索空间

LDLC工作在目标节点的egonet上，因为网络全局结构中的社区检测对于大规模的图来说是费时的．然而在网络中某些节点的egonet中检测社区可能具有同等的成本．特别是，许多现实世界的网络，如互联网、万维网和引文网，表现出幂律度分布，其中一些节点度很大．因此，这些节点各自egonet的大小通常与网络的大小相当．

算法有效地发现具有大型egonet节点的社区结构，需要在egonet上应用一种采样技术来减少搜索空间．一种简单的方法是执行随机抽样，随机抽取egonet中节点的一个子集，并将LDLC应用于包含这些节点的相应子图上．这种方法成功地减少执行算法所需的时间，然而，度数高的节点邻域的随机样本可能包括许多不同的节点．

3 实验评估

将LDLC与基于种子集展开的3种效果较好的社区检测算法进行了比较，即LEMON，LOSP，Heat-Kernel[10]．这3种算法基于局部社区检测思想，可在相同的实验设置中与LDLC方法进行比较．

3.1 数据集

数据集包括５个不同大小的社交网络、合著网络和协作网络（见表1）．使用Python2.7和Snap.py接口实现了LDLC系统．

表1 分值比较

3.2 算法的评估

3.3 执行时间比较

执行时间评估LDLC见表2．采用citeHeSBHL方法，对于每个数据集，执行5 000次LDLC试验，包括均匀随机地选择网络中的一个节点作为种子．对于数据集5个较小的网络，对LEMON，LOSP，HeatKernel执行相同的实验．由表2可以看出，LDLC在执行时间方面明显优于LEMON和LOSP．这是预期的，因为LDLC只在目标节点的egonet上操作．为了产生egonet，只需要在目标节点的所有邻居的集合上应用交集．相反，LEMON和LOSP执行多个随机游走来生成目标节点周围的本地邻域，这一过程在时间上要花费得多．

表2 执行时间比较 s

4 结论

本文提出一种大规模网络上局部社区检测算法LDLC．LDLC的重点是网络中目标节点的egonet，并对egonet的链接对进行分层聚类．研究了评估网络中联结强度的度量，通过使用递归色散度量来平衡２个链接的相似性，并优先考虑在单个上下文中功能的相互邻居对链接的分组．因此，该方法能够适当地处理重叠社区，并提供更高的准确性．同时，也揭示了网络中节点社区的丰富层次结构，并将LDLC与３种最先进的本地社区检测方法进行比较，以突出LDLC方法在处理多个社区的重叠区域时的有效性．此外，对真实社区的准确性，发现LDLC在广泛的公开可用网络中的性能显著优于大部分算法．

[1] Fortunato S．Community detection in graphs[J]．Physics Reports，2010（3）：161-174

[2] Ahn Y Y，Bagrow J P，Lehmann S．Link communities reveal multiscale complexity in networks[J]．Nature，2010（466）：761-764

[3] 潘剑飞，董一鸿，陈华辉，等．基于结构紧密性的重叠社区发现算法[J]．电子学报，2019（1）：63-66

[4] 牛新征，司伟钰，佘堃．基于进化聚类的动态网络社团发现[J]．软件学报，2017（7）：42-46

[5] 吴蔚蔚，刘功申，黄晨．基于相似度的社团划分算法[J]．计算机工程，2015（11）：84-89

[6] 宋俐，谢刚，杨云云．基于模糊聚类的社团划分算法[J]．计算机工程，2016（8）：6-11

[7] 邱少明，於涛，杜秀丽，等．基于节点多属性相似凝聚的社团划分算法[J]．计算机工程，2019（8）：54-60

[8] 张振宇，朱培栋，王可，等．拓扑结构与节点属性综合分析的社区发现算法[J]．计算机技术与发展，2018（4）：33-37

[9] 朱牧，孟凡荣，周勇．基于链接密度聚类的重叠社区发现算法[J]．计算机研究与发展，2013（12）：65-70

[10] 时京晶．三种经典复杂网络社区结构划分算法研究[J]．电脑与信息技术，2011（4）：71-72

Detecting local hierarchical overlapping communities of large network

WANG Yiping

（School of Computer and Control Engineering，Qiqihar University，Qiqihar 161006，China）

The growing size of real-world networks makes detecting community more challenging．An extensible local community detection method is proposed，which can effectively find the overlapping communities of a given node in the network．By considering the similarity of the link pairs in the figure and their participation in multiple environments，determine the order in which the link pairs are added to form a meaningful hierarchical community．The results show that the LDLC algorithm is significantly superior to the most advanced methods in both accuracy and efficiency．

complex networks；hierarchical communities；community detection；dispersion

TP393

A

10.3969/j.issn.1007-9831.2020.10.007

1007-9831（2020）10-0027-05

2020-05-28

王一萍（1971-），女，黑龙江伊春人，副教授，硕士，从事复杂网络与群智能研究．E-mail：wypyzh2002@163.com