基于社交网络的社区发现算法研究

毋建军

(北京政法职业学院 信息技术系, 北京 102628)



基于社交网络的社区发现算法研究

毋建军

(北京政法职业学院 信息技术系, 北京 102628)

摘要：随着社交网络的快速发展及应用,围绕社交网络用户及信息交互自发形成的网络社区已经成为当前社交网络研究领域的重要分支，并取得了许多研究进展及成果，但仍然存在许多挑战及问题。本文从网络社区研究的网络结构、网络信息、时间三个重要因素考虑，在网络社区的定义、特性的基础上，分类、对比了典型的社区发现模型、算法及社区划分评价方法，并对其存在的问题及未来发展方向进行了分析探讨。

关键词：社交网络；社区算法；动态社区；SNS分析

0引言

随着Twitter、Facebook、新浪微博、人人网、微信等社交网络的广泛应用，社交网络大数据集合孕育而生，在大数据基础上，不同领域、学科的研究人员基于社交网络的链接结构、用户交互行为、信息扩散传播等方面，进行了社交网络用户关系挖掘、信息扩散传播的机制分析、网络结构变迁、新型(网络)虚拟关系演化等基础性问题的研究。

早期关于网络结构的研究主要着重于小规模的网络(如问卷调查、美国大学生足球网络等)。但近年来随着社交网络规模及应用的急剧发展，关于复杂网络的研究及数据集的采样规模，已递增为百万或千万、甚至上亿。社交网络已经成为复杂网络研究中一个新兴的研究领域。Watts等[1]提出的小世界模型,描述网络具有集聚、较小平均路径长度等特性。Barahasi等验证了度分布服从幂律分布p(k)=ck-r的复杂网络[2,3]，具有“小世界”、 “聚集性”、“无标度”等特性。

在社交网络中，人们之间是如何进行交互、传递信息、它们之间的结构如何形成、迁移；哪些用户具有相似的爱好及兴趣、哪些用户在社交网络信息传播中具有重要的作用及天然优势；它们之间是否会自发的形成具有直接链接(拓扑结构社区)或不具有之间链接的社区(隐含社区)，这些都是当前社交网络(SNS,Social Network Site)研究中的热点。本文将就社交网络(SNS)研究的基础核心热点—社交网络社区发现(探测)进行分析。

1社交网络特性及社区定义

社交网络是一种全新的虚拟交流形态，人们通过网络空间进行相互交流，并形成比较亲密的关系或不同的角色，即社交网络中总是有一部分较为活跃的用户充当着组织者(领导者)的角色，其他用户在相同的话题或兴趣下，逐渐聚合在一起，从而形成一个有自我认同的虚拟网络社区。另外Stanley Milgram 的“六度分隔”理论、Cameron Marlowe的120及150法则的理论也在社交网络应用中得到了验证。

目前，社交网络中关于社区(社团)的定义纷杂并没有统一的标准，大致可分为基于链接关系的社区、基于信息内容的社区、链接和内容相结合的社区三类。基于链接关系的社区，通常把社交网络中的用户作为节点，用户之间的关系作为边，网络中那些内部连接“紧密”、外部连接“稀疏”的子团结构，称为虚拟网络社区。Radicchi等针对社区内部链接紧密、社区间连接稀疏不能很好量化、应用于社区结构划分的缺陷，提出了强社区组织和弱社区组织，强社区中节点之间连接的度大于其与社区外部节点所连接的度；弱社区组织中全部节点的度大于社区中所有节点与外部节点相连接的度之和。Palla等人提出由几个全连通的子社区构成的社区，子社区之间共有许多节点，所有的k-群子社区组成一个k-群社区，社区中任意一个节可以通过邻接的k-群社区互通(共有k-1个节点)，社区中某一节点有可能同属于几个社区，社区与社区之间有大量的重叠节点[4]。文献[5]中利用模块化函数，对网络中社区结构进行定量地描述，并用于评价网络中社区结构划分的质量。

Rheingold把虚拟社区[6]定义为认识的人们之间分享知识、信息所形成的社团。在研究中，通常把社交网络关系转化为图的结构，圈子或群体中用户作为图的节点，用户之间的连接或信息转发、评论或相似话题当做图的边，在不同的应用场景下，通过不同的社区发现算法，把社交网络划分为不同的子网络社区。

2社交网络(SNS)社区发现模型

社交网络结构转化为图结构的描述建模，可以分为静态和动态两类，静态建模和动态建模的主要区别在于动态社区发现模型考虑了社交网络的时间特性，在不同时刻，其结构有可能发生变化，而静态社区发现模型假设社交网络结构(取某一时刻)不发生变化。

2.1静态社区模型

静态社区发现主要是基于某一时刻网络社区结构进行描述、分析，用图G来描述社交网络结构,顶点表示用户,边表示有链接或转发、评论等。在此基础上，基于图理论或数据挖掘方法，实现社交网络(SNS)社区的发现和提取。其形式化建模描述如下：

通常用无向图G=(V,E)表示社交网络关系，描述如下：

(1) V表示顶点集合。即v∈V,表示社交网络中的用户。

(2) E是边集合。边e=(v1,v2),e∈E,表示分别顶点V1和顶点V2之间有相互的联系。

静态SNS的社区结构表示为CS，P=(C1,C2,C3,···,Cn)是对图G中顶点集合V的分割，分割后的集合Ci符合如下条件:

(1)Ci子集内顶点间连接比外部紧密。

(2)Ci子集与Cj子集内每个顶点i≠j之间都连接比子集内部松散。

在前述静态SNS社区组织的定义中,如图1所示，紧密、松散程度可以有多种衡量测度,常用的测度有凝聚度和分离度[7]及后续的模块度。

图1　社交网络(SNS)社区

2.2动态社区模型

真实社交网络中，SNS社区结构随时间变化有可能增加或删减。在时间因素的基础上，建立动态的SNS数学模型，描述社区结构,是动态社交网络社区划分研究的关键难点。

由于SNS网络结构随着时间在不断变化，节点之间的连接有可能增加或删除。在不同时刻对SNS社交结构进行采样，得到一个时间序列的静态SNS的无向图，每一个无向图称作动态SNS在这个时刻的社交网络结构拓扑快照。如在时刻1得到网络结构快照G1,在时刻2得到网络结构快照G2,依次类推,得到Gn-1，Gn等网络结构快照。用图序列G1,G2,G3,···,Gn表示从时刻1到时刻n的SNS网络结构，其中Gi=(Vi,Ei)是动态SNS在时刻i的网络拓扑快照，i=1,2,3,…,n。在时刻i,的SNS社区结构表示为Cs,i，Pi=(C1,C2,C3,···,Cn)是顶点集合V的一个社区划分,其中:

(1)Cs,i满足定义上述静态SNS社区的形式化描述,对任意i≥1。

(2)拓扑社区结构Cs,i与Cs,i-1之间的变化不大，具有典型的局部特性，满足于给定常数σ，如公式(1)所示

(1)

Lin[8]等人指出SNS网络结构的变化实际上是非常缓慢的. 单等人通过对Enron的真实数据分析统计也进行验证，即在相邻的时刻i-1和时刻i，SNS的拓扑结构变化相对于整个图结构而言非常小。但其结论是否适用Twitter、Facebook等大型的社交网络，尚不清楚有待验证。

3传统社区发现算法

传统划分社区结构的算法主要分为：图分割法和层次聚类法两大类[9,10]。

3.1图分割法

基于图的分割是将网络划分成节点数相等的子网或群组，使得子网内部节点连接紧密，子网或群组之间的连接数较少，然后通过不断迭代获得所要求的子网数目。其中代表性算法有Kernighan-Lin算法和Laplace矩阵特征值的谱平分法。Kernighan-Lin算法把网络分割为两个规模大小已知的社团，在分割过程中通过增益函数Q，来判定社区划分的好坏。

Fiedler等人[11]利用谱平分法，对无向网络G的Laplace矩阵的特征值进行分析，利用Laplace矩阵特征值分割网络为社区组织。谱平分法在网络只能分割为两个社区时，效果较为明显。通常转化后Laplace矩阵较为稀疏，在特征向量计算方面比较简单及快速，在有明显的优势。但Laplace特征值的谱平分法无法将网络划分为三个或三个以上的社区或社团(每次只能将网络平分)，网络的多个社区(社团)划分，需要应用该算法对子社区或社团多次平分，其缺陷是需要清楚知道社团的规模大小。为此Capocci等提出了一种基于标准矩阵N=K-1A的谱平分算法。该算法仅取其中一个特征向量(K-1个)，便可将网络中的节点划分为k个社区。

3.2层次聚类法

层次聚类法分为层次分裂法(divisive method)和层次聚合法(agglomerative method)两类。主要利用节点之间的相似性或者连接强度，对网络中的节点进行社区划分。层次分裂法是通过不断重复寻找对网络图中相似性最低的节点对之间的边，然后进行删减，自上往下逐步把网络中的节点进行分割，最终形成不同的社区。而层次聚合法通过计算并选择相似性最高的节点对，根据相似度从强到弱连接相应节点对，自底向上，不断地往原始空的网络图中添加边，最终构成树状图(Dendrogram)，依据应用需求横切树状图，获得不同的社区组织，如下图3所示；不论是分裂还是聚合方法，都可终止于任意步骤，则在此状态下的网络划分，便构成网络社区组织。在划分后层次聚类树中，不同的社区划分层次得到的社区结构不尽相同，Newman[13]等使用度量函数Q来评价社区划分质量。模块度定义如公式(2)所示：

(2)

元素eij表示社区i和社区j之间所有的边占整个网络所有边的比例，i∈Ci,j∈Cj，Ci表示社区i, Cj表示社区j，∑ieii表示矩阵中对角线的所有元素之和，表示网络中所有社区的内部边(即该边的两个端点属于同一个社区)占整个网络所有边的比例；ai=∑eij表示第i行(或者第j列)所有元素之和，表示与社区i中节点相连的所有的边占整个网络所有边的比例。Q越接近1表明社区结构特征越明显，得到社区的划分越好。

图3　层次聚类及分裂法网络社区划分过程

如何定义相似度是层次聚类算法的关键所在。其特点是能够发现高相似性的节点对，而相似度较小的社区边界节点社区划分精度较低；层次聚类法具有不需已知社团规模的优势，但最终社区(社团)划分的个数也无从知晓。其不适用于大型真实网络应用。

3.3GN系列算法

(3)

Tyler[14]等人采用网络部分节点的方法代替GN算法中所有节点作为源节点，只计算这些节点所对应边的边介数，以弥补GN算法的计算效率缺陷。另外，Radicchi等人[15]提出自包含GN算法，通过定量的社区结构定义，量化评价社区结构。GN算法在划分网络中社团结构时，通常会获得较为准确的效果，但算法复杂度较大，限制它仅应用于规模较小的网络。

在大规模的网络下，基于GN算法改进的快速社团划分算法(NF算法)，将贪婪算法和层次聚合算法相结合，适用于节点达百万的复杂网络。在计算速度方面，Clauset等人对NF快速算法进行了改进，提出了CNM算法，该算法通过使用堆结构和Q函数，降低了算法的时间复杂度为O(nlog2n)，接近线性时间复杂度。NF算法和CNM算法相比，前者利用连接矩阵对模块度ΔQ变化进行计算，后者通过构建模块度增量矩阵ΔQ，更新矩阵元素，来得到模块化Q值变化最大的社区合并。若两个社区间无边连接，则模块度Q值的不变。在算法应用中，可以通过只保存有边连接的社区及相应的模块度变化值，节省算法的存储空间。

4存在问题及未来方向

由于互联网网络结构本身具有复杂性、多变性等特点，尤其是网络结构实际环境中，并不是单一的、静态、简单的结构，围绕网络进行的社区结构划分存在多个维度，多种方法，但是大多数还是采用单一的网络拓扑结构，并没有考虑网络节点本身的信息或节点所参与的话题，如何把拓扑结构分析和话题分析相结合，分析、发现社区，必将是社区发现一个重要的研究点。此外，人们对社交网络拓扑结构与用户行为的影响，如何刻画和控制社交信息在网络上的传播等都还在不断的探索和发现中，特别是以微博为代表的社交网络所包含的信息相当丰富，如何利用这些属性信息挖掘社区是值得探讨的问题。另外，微博社交网络的一个重要特点是动态性，如何运用社交网络微博信息进行动态社区发现不仅是当前的研究热点，也是当前信息推荐、广告定点投放的重要市场应用方向。

参考文献：

[1]Watts D J，Strogatz S H．Collective Dynamics of‘Small World’Networks[J]．Nature，1998，393(6684)：440-441.

[2]Barabasi AL,Albert R．Emergence of Scaling in Random Networks[J]．Science，1999，286(10)：504.

[3]Baralbasi AL,Albert R,Jeong H. Mean-field Theory for Scalefree Random Networks[J]．Phys Review，1999(272)：173-187.

[4]Palla G,Dernyi I,el at．Uncovering the Overlapping Community Structure of Complex Networks inNature and Society[J].Nature，2005，435，(6)：814-818.

[5]NewmanME,Girvan M．Finding and Evaluating Community Structure in Networks[J].Phys Rev E Stat Nonlin Soft Matter Phys，2004，69(2)：026113.

[6]Howard Rheingold.The Virtual Community[M].London:HarperPerennial, 1994.

[7]Steinbach M, Tan PN, el at. Support Envelopes: A technique for Exploring the Structure of Association Patterns[C].SIGKDD2004:296-305.

[8]Lin YR, Chi Y, Zhu SH,Sundaram H, Tseng BL. FacetNet: A Framework for Analyzing Communities and Their Evolutions in Dynamic Networks[C]. WWW’08:proceeding of the 17th international conference on world wide web,2008:685-694.

[9]JohnScott.Social Network Analysis[J].Sociology,1998,22(1):109-127.

[10]Garey MR,Johnson DS．Computers and intractability：A Guide to the Theory of NP-Completeness[M].Newyork:W.H.Freeman & Co Ltd.1979.

[11]Fiedler M,Praha. Algebraic Connectivity of Graphs[J].Journal of Czechoslovak Mathematical.1973,23(2):298-305.

[13]Newman MEJ. Fast Algorithm for Detecting Community Structure in Setworks[J]. Physical Review E,2003,69(6):066133.

[14]Tyler JR,Wilkinson DM,el at. Automated Discovery of Community Structure within Organizations[J].Information Socity,2003,21(2):143-153.

[15]Radicchi F,Castellano C,et al．Defining and Identilying Communities in Networks[J].PNAS.2003,101(9):2658-2663.

责任编辑：程艳艳

Analysis of Community Discovery Algorithms Based on Social Communication Networks

WU Jianjun

(Department of Information Technology, Beijing College of Politics and Law, Beijing 102628, China)

Abstract：Along with the rapid development and application of social communication network, online community centering on social communication network users and information interaction becomes an important branch in the field of social communication network study. Although many results have been made, there are many challenges and problems. Considering network structure, network information and time, this paper analyzes and compares typical community discovery models, algorithms and evaluation methods based on the definitions and features of network community, and discusses the problems and future development direction.

Keywords：social network; community algorithm; dynamic community; SNS analysis

收稿日期：2016-04-30

基金项目：北京政法职业学院课题(KYZX201404)

作者简介：毋建军(1977- )，男，山西河津人，讲师，硕士，主要从事社交网络方面研究。

中图分类号：TP391

文献标志码：A

文章编号：1009-3907(2016)06-0035-04