基于局部扩充优化的重叠社群检测方法的改进

优先出版

计 算 机 应 用 研 究

第32卷

基于局部扩充优化的重叠社群检测方法的改进

王 茜，张 晨

(重庆大学 计算机学院，重庆 400044)

摘 要：生物信息学、社会网络、web分析等方面的发展积累了大量的复杂网络数据信息，在对这些复杂网络进行社群检测时，往往会将一些节点归类于多个社群，目前已经提出了一些处理此类问题的算法（如LFK、GCE等），然而这类算法对局部扩充函数中参数α的选取过程复杂，无法一次性获取最优α，直接影响到了算法的可应用性。针对该缺点，论文提出了一种基于局部扩展的重叠社群检测的改进算法。该算法通过将α参数考虑进社群的成长过程中，使算法在保持原有速度与精度的情况下自适应地选取最优α。 关键词：数据挖掘；重叠社群检测；局部聚类 中图分类号：TP391 文献标志码：A

Improvement of overlapping community detection based on

local expansion and optimization

WANG Qian, ZHANG Chen

(College of Computer Science, Chongqing University, Chongqing 400044, China)

Abstract: Large amounts of complex networks data have been accumulated in the development of bioinformatics, social networks, Web analysis, etc. We tend to classify some of the nodes into multiple communities for some complex network community detection. Recently, scholars have raised the issue of such processing algorithms (such as LFM, GCE, etc. ). However, this kind of algorithm can’t obtain the optimal α in one time and it has a complex process while selecting parameter α in the local expansion function which directly affects the applicability of the algorithm. To get rid of the shortage, this paper presents an improved method based on local expanding to detect overlapping community. In this method, it considers α in the growth process of communities, so that it can select parameter α in an adaptive way while maintaining the speed and accuracy. Key Words: data mining; overlapping community detection; local clustering

过一个局部优化函数(如f(S)=kin(S)/(kin(S)+kout(S))α)对社群种子进行局部扩充优化，使其成长为一个最终社群。这类算法中较具代表性的是Lancichinetti等所提出的LFK [4]算法与Lee等所提出的GCE[5]算法。这类算法均是先获取网络结构中定义出的社群种子，然后对这些种子进行局部的扩充优化，获取最终的社群。根据具体算法的不同，在算法中存在如LFK[4]中的社群退化及GCE[5]中的过滤种子等不同的算法步骤。虽然这两种算法在速度与精度均能取得较好的效果，但是由于局部优化函数中的参数α是一个需要针对不同网络结构选取不同值的经验参数，α往往需要通过多次尝试以获取最适合当前网络结构的值，这致使算法的应用性大打折扣。论文将针对这一缺点对已有算法进行改进，改进后的算法能自适应的选取参数α，同时保持算法原有的速度与精度。

0 引言

社群结构是被各个领域所认可的广泛存在于复杂网络模型中的数据结构类型，如社交网络与蛋白质网络结构模型中均拥有大量的社群结构。对社群结构的一种普遍描述为:它由节点集合组成，集合内部节点之间的联系紧密，而内部节点与集合外部节点之间的联系稀疏。对各种复杂网络模型按图结构进行建模，进而挖掘其中的社群结构，可以清晰的揭示出网络的内在组织结构[1] [2]。

近年来对社群检测的研究表明，不同网络中的社群结构之间还存在着重叠的子结构，即一个节点可以同时被归类到几个社群之中。对这种具有重叠子结构社群的挖掘已成为当前数据挖掘领域的一个热点，学者们对此提出了大量算法，这类算法大致分为了如下几类[3]：基于最大团过滤的方法、基于线图与边分割的方法、基于局部扩充优化的方法、基于模糊图理论的方法、基于动态代理的方法以及其他一些方法。

基于局部扩充优化的方法是基于一种社群成长的思想，通

--------------------------------

1 相关概念

在设计与介绍本文算法之前，首先给出本文将会使用到的一些参数符号的概念与定义，为便于描述，用v、v′表示网络结

作者简介：王茜(1964-)，女，重庆人，教授，博士，主要研究方向为网络安全、电子商务、数据挖掘；张晨(1990-)，男，重庆人，硕士研究生，主要研究方向为数据挖掘(chen726296@qq.com)．

文章预览已结束

获取全文请访问 http://www.arocmag.com/article/02-2015-04-016.html