刘 阳 季新生 刘彩霞



+一种基于边界节点识别的复杂网络局部社区发现算法

刘 阳 季新生 刘彩霞

(国家数字交换系统工程技术研究中心 郑州 450002)

在网络日益巨大化和复杂化的背景下，挖掘全局网络的社区结构代价较高。因此，基于给定节点的局部社区发现对研究复杂网络社区结构有重要的应用意义。现有算法往往存在着稳定性和准确性不高，预设定阈值难以获取等问题。该文提出一种基于边界节点识别的复杂网络局部社区发现算法，全面比较待合并节点的连接相似性进行节点聚类；并通过边界节点识别控制局部社区的规模和范围，从而获取给定节点所属社区的完整信息。在计算机生成网络和真实网络上的实验和分析证明，该算法能够自主挖掘给定节点所属的局部社区结构，有效地提升局部社区发现稳定性和准确率。

复杂网络；社区发现；局部社区；边界节点识别

1 引言

近年来复杂网络的研究蓬勃发展，已成为人们深入了解和分析真实世界网络的重要理论和方法之一。其中，社区结构作为复杂网络中广泛存在的重要属性，是认识复杂网络的功能与特征的基础，对研究网络的模块化、异质性等特征，分析网络内部相互作用、网络演化都具有重要意义。而在许多实际应用中，由于条件限制往往只能获取局部网络信息，或者只需分析某特定节点、特定群体的社区结构，这就从网络拓扑信息和复杂度等方面对社区发现提出了限制和要求，需要根据局部网络信息进行局部社区发现。

基于此，本文提出了一种基于边界节点识别的局部社区发现算法，主要贡献如下：(1)在局部社区聚合的过程中，综合考虑并比较待合并节点与局部社区及其外部节点的连接相似性，避免直接从给定节点进行外部扩张而引入异质节点；(2)通过边界节点识别以控制社区聚类，从而确定局部社区的范围和大小，无需设置人工参数进行干预。通过计算机生成网络和真实网络实验发现，本文算法能够基于给定节点自主有效地挖掘并识别其真实边界，从而发现接近真实完整的局部社区结构，具有相对较高的稳定性和准确率。

本文第2节分析现有局部社区发现方法的问题与局限；第3节介绍基于边界节点识别的局部社区发现算法；第4节介绍了局部社区发现的评价准则与方法，并基于计算机生成网络和真实网络给出实验和分析结果；第5节对全文进行总结。

2 问题分析

如图1所示，在局部社区“由内而外”的扩展过程中，沿用了全局网络社区发现中最大化模块度的思想，将满足或者能够改善社区内聚指标的节点加入到该社区中，使得局部社区倾向于优先引入大度数节点。而大度数节点的引入往往又会引起连锁反应，改变了局部社区扩展的方向和范围，使其邻近节点容易被划分到给定节点所属的局部社区，引入原本不属于该局部社区的异质节点，影响了局部社区发现的性能。

基于上述分析，本文提出了一种基于局部社区聚合和边界节点识别的两阶段局部社区发现算法，一方面通过全面分析局部社区邻接子图范围内连接相似性，从而获取给定节点所在社区的局部结构特征并进行节点聚类；同时在社区聚类过程中，基于邻接节点内外的连接状况反复识别其边界节点，从而控制社区聚类的规模和范围以完成局部社区发现。该算法采用了有别于最大化局部社区结构指标的思路和方法，以节点相似性模块度作为局部社区发现的衡量标准，通过边界节点识别解决已有方法存在的“何时停止聚类迭代”和给定节点位置敏感等问题。

图1 “由内而外”的局部社区发现模型

3 基于边界节点识别的局部社区发现算法

3.1 基本定义

连接相似度借鉴了余弦相似性[8]作为衡量节点相似性的标准，表示两节点的共有连接在两节点的所有直接连接中权重越大，说明二者联系越紧密，节点连接的相似性越强，越有可能属于同一社区。

如图2所示，由于网络结构具有社区内部连接紧密而社区间连接稀疏，呈现出“内紧外松”的结构特征，使得距离社区核心较远的边缘节点构成了所属社区的天然边界。在局部社区发现过程中，随着社区聚类的扩展，必然逐步到达社区的边界。边界节点大多处于多个网络社区的交界处，并往往同时与多个社区建立了连接。因此，如何基于节点及其邻接子图的连接关系与拓扑结构判断其所属社区，是局部社区发现的一个重要难点。而通过边界节点识别，能够帮助确定局部社区的边界，从而有效地精确控制局部社区发现的范围和规模，确保社区发现的稳定性和有效性，使得从同一社区不同节点出发所获得局部社区趋于一致。

3.2 算法描述

本文提出了基于边界识别的局部社区发现算法，主要包含两个环节：社区节点聚类阶段及社区边界节点识别阶段。该算法基于网络节点的局部结构信息来衡量节点间的连接相似度，从给定节点开始进行节点聚类；并基于节点相似性模块度判别边界节点，以优化局部社区发现。通过两阶段的反复迭代，最终得到具有稳定边界的局部社区。

图3 局部社区节点聚类示意图

4 实验

4.1 评价准则与方法

局部社区发现的评价准则相比全局社区发现，除了评价社区发现精确度，还需要评价节点划分的正确性。因而选择的评价准则也必须能够从这两方面来考察该模型的性能。本文实验部分采用了复杂网络局部社区发现领域常用的典型指标：precision[10](正确率)，recall[10](查全率)及调和指标F-measure评价局部社区发现算法的性能。

由于计算机生成网络和部分真实网络社区结构已知，其给定节点所属社区的标准数据集易于获取；对于未知社区结构的真实网络，本文采用当前公认准确度较高的Louvain[11]社区发现算法挖掘给定节点的所属社区结构作为标准数据集。为了分析基于边界节点识别的局部社区发现算法的性能，实验同时基于计算机生成网络和真实网络进行局部社区发现，并选取文献[1]，文献[3]和文献[12]3种常见的典型算法与之进行性能对比。

表1 局部社区发现算法

4.2 计算机生成网络

表2 LFR网络配置参数

4.3 真实网络

真实网络相比计算机生成网络更不规则，因而其社区结构往往也更加复杂。这里采用5个具有不同规模的典型真实网络数据集：2000赛季大学生美式足球联赛网络(Football)[14], 2004年美国政治博客网络(Polblogs)[15]、美国航空网络(US Airport)[16]、美国电力网络(US power grid)[17]、2005年Internet拓扑网络(Internet)[18]来进一步测试算法性能，表3描述了这些真实网络的基本属性。

表3实验采用的真实网络的基本属性

网络数据集节点数边数连接类型网络结构 Football[14] 115 616无向已知 Poldlogs[15] 149019025有向已知 US Airport[16] 157428236有向未知 US Power grid[17] 4941 6594无向未知 Interner[18]34761171403无向未知

在真实网络中，4种局部社区发现算法的调和指标如表4所示。分析可知：由于真实网络的社区结构彼此存在差异，给定节点的选取也具有一定的随机性，因而4种算法的调和评价指标在不同真实网络中也各不相同。对于 Football, US power grid，本文算法对局部社区发现性能改善有限；对于Polblog, US Airport, Internet网络，本文算法的社区发现性能优势更加明显。相比真实网络条件下的其它3种算法，基于边界节点识别的局部社区发现算法都表现出了相对较高的社区发现精确度；在给定节点随机选取的条件下，本文算法的综合调和指标均值达到了86.07%，体现了较强的抗干扰能力，说明本文算法稳定性更优，并且与标准社区结构的匹配效果较好。

综合计算机生成网络和真实网络的实验可以得出结论：在不同网络环境、不同给定节点条件下，基于边界节点识别的局部社区发现算法在正确率、查全率方面相比其它算法都有不同程度的改善。尽管并不能在正确率、查全率两项指标上同时达到最优，但在这两项评价指标上较为均衡且处于较高水平，使其性能具有一定的整体优势。该结论在表4所示的综合调和指标上也得到了充分验证。

表4调和指标均值：4种算法在真实网络中基于随机给定节点的局部社区发现性能

网络数据集文献[1]文献[12]文献[3]本文算法 Football[14]0.62670.76230.76330.7815 Poldlogs[15]0.54330.81110.80250.8603 US Airport[16]0.49500.78330.82570.9145 US Power grid[17]0.68820.74520.75840.8160 Interner[18]0.63190.85730.87260.9314

图5 4种算法基于真实网络的正确率、查全率、调和指标的性能对比

5 结束语

本文提出了一种基于边界节点识别的复杂网络局部社区发现算法，采用有别于最大化局部社区结构指标的思路和方法，通过扩展余弦相似性作为局部社区发现的衡量标准，以边界节点识别控制社区聚类的规模和范围以完成局部社区发现，从而解决已有方法稳定性不高，预设定阈值难以获得等问题。通过实验和分析证明：对于不同的给定节点，基于边界节点识别的局部社区发现算法具有较高的准确率和稳定性，能够较真实地反映给定节点所属的局部社区结构。在保证准确度和稳定性的前提下，如何将局部社区发现进一步应用于大规模网络局部结构分析，以及动态时序网络中局部社区结构的演化分析等实际问题，是我们下一步研究工作的重点。

[1] Clauset A. Finding local community structure in networks[J].2005, 72(2): 026132..

[2] Radicchi F, Castellano C, Cecconi F,. Defining and identifying communities in networks[J]., 2004, 101(9): 2658-2663.

[3] Chen Q, Wu T T, and Fang M. Detecting local community structures in complex networks based on local degree central nodes[J]., 2013, 392(3): 529-537.

[4] Wu Y J, Huang H, Hao Z F,.. Local community detection using link similarity[J]., 2012, 27(6): 1261-1268.

[5] 潘磊, 金杰, 王崇骏, 等. 社会网络中基于局部信息的边社区挖掘[J].电子学报, 2012, 40(11): 2255-2263.

Pan Lei, Jin Jie, Wang Chong-jun,. Detecting link communities based on local information in social networks[J]., 2012, 40(11): 2255-2263.

[6] Qi X, Tang W, Wu Y,Optimal local community detection in social networks based on density drop of subgraphs[J]., 2014, 36(1): 46-53.

[7] Newman M E J. Modularity and community structure in networks[J]., 2006, 103(23): 8577-8582.

[8] Fouss F, Pirotte A, Renders J M,Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[J].2007, 19(3): 355-369.

[9] Feng Z, Xu X, Yuruk N,A Novel Similarity-based Modularity Function for Graph Partitioning[M]. Berlin Heidelberg Springer, Data Warehousing and Knowledge Discovery2007: 385-396.

[10] Zhang Aidong. Protein Interaction Networks[M]. NewYork: Cambridge University Press, 2009: 44-47.

[11] Blondel V D, Guillaume J L, Lambiotte R,. Fast unfolding of communities in large networks[J].:, 2008, doi: 10.1088/1742-5468/2008/10/ P10008.

[12] Luo F, Wang J Z, and Promislow E. Exploring local community structures in large networks[J]., 2008, 6(4): 387-400.

[13] Lancichinetti A, Fortunato S, and Radicchi F. Benchmark graphs for testing community detection algorithms[J]., 2008, 78(4): 046l10.

[14] Girvan M and Newman M. Community structure in social and biological networks[J]., 2002, 9(12): 7821-7826.

[15] Adamic L A and Glance N. The political blogosphere and the 2004 US election: divided they blog[C]. Proceedings of the 3rd International Workshop on the Weblogging Ecosystem, New York, USA, ACM, 2005: 36-43.

[16] US power grid network dataset-KONECT[OL]. http://konect.uni-koblenz.de/networks/opsahl-powergrid, November 2013.

[17] US airports network dataset-KONECT[OL]. http:// konect.uni-koblenz.de/networks/opsahl-usairport, November 2013.

[18] Zhang Beichuan, Liu Raymond, Massey Daniel,Collecting the Internet AS-level topology[J]., 2005, 35(1): 53-61.

刘 阳： 男，1986年生，博士生，研究方向为社会网络分析、数据挖掘.

季新生： 男，1969年生，教授，博士生导师，主要研究领域为电信网安全、移动通信安全.

刘彩霞： 女，1974年生，副教授，硕士生导师，主要研究领域为移动通信安全、社会网络分析.

Detecting Local Community Structure Based on the Identification of Boundary Nodes in Complex Networks

Liu Yang Ji Xin-sheng Liu Cai-xia

(&&,450002,)

In the context that social network becomes more and more complicated and huge, it is extremely difficult and complex to mine the global community structures of large networks. Therefore, the local community detection has important application significance for studying and understanding the community structure of complex networks. The existing algorithms often have some defects, such as low accuracy and stability, the preset thresholds difficult to obtain,.. In this paper, a local community detecting algorithm is proposed based on boundary nodes identification, and a comprehensive consideration of the external and internal link similarity of neighborhood nodes for community clustering is given. Meanwhile, the method can effectively control the scale and scope of the local community based on the boundary node identification, so as the complete structure information of the local community is obtained. Through the experiments on both computer-generated and real-world networks, the results show that the proposed algorithm can automatically mine local community structure from the given node without predefined parameters, and improve the performance of local community detection in stability and accuracy.

Complex networks; Community detection; Local community; Identification of boundary nodes

TP311

A

1009-5896(2014)12-2809-07

10.3724/SP.J.1146.2013.01955

刘阳 liuyang198610@163.com

2013-12-17收到，2014-04-24改回

国家863计划项目(2011AA010604)和国家重大科技专项(2012ZX03006002)资助课题