基于用户紧密度的微博网络社区发现算法

韦庆杰　李京腾　汪　雨

1(重庆邮电大学计算机科学与技术学院　重庆 400065)2(重庆邮电大学软件工程学院　重庆 400065)



基于用户紧密度的微博网络社区发现算法

韦庆杰1李京腾2汪雨2

1(重庆邮电大学计算机科学与技术学院重庆 400065)2(重庆邮电大学软件工程学院重庆 400065)

针对微博网络社区难以准确划分的问题，根据微博网络的特性，提出一种基于用户紧密度的微博网络社区发现算法。根据微博网络中用户间的交互度与共有邻居相似度来计算用户紧密度，并与传统的GN算法相结合对微博网络进行社区划分。通过对真实社会网络和微博模拟网络进行实验验证，实验结果表明，该算法可以有效地发现网络中的社区结构。

社区发现微博网络GN算法用户紧密度共有邻居相似度

0　引　言

微博作为目前国内最具代表性的社交网络平台，已经成为人们日常进行信息分享和交流的重要工具。由于其具有实时性强、传播速度快、覆盖范围广和信息传播方式多样简便等特点，吸引了越来越多的用户。微博采用了全新的社交模式—“关注”，用户间不需要经过授权就能建立关注关系[1]。在关注关系基础之上，微博的部分用户通过更多的“评论”、“转发”等用户行为逐步形成一个社区。社区这一概念来源于对复杂网络的研究，“小世界特征”[2,3]和“150法则”[4]的提出使复杂网络的研究进入了一个新的阶段。Girvan等人[5]于2002年正式提出了复杂网络中社区的概念，社区的一般定义是同一社区内节点间的连接很紧密，而社区之间的连接比较稀疏[6]。发现微博网络中潜在的社区，能更好地理解社区内个体的属性，社区内个体之间以及社区之间的结构关系，可以为个性化推荐等实际应用提供重要的理论依据。

近年来，国内外学者在社区发现方面做了大量研究，已有的社区发现算法多种多样。传统的社区发现算法主要分为两类，即图分割算法和层次聚类算法。其中图分割算法中具有代表性的算法包括Kernighan-Lin算法[7]和谱二分算法[8]，GN算法[5]则是层次聚类算法中的经典代表。传统的社区发现算法关注图的几何特征以及图论概念，而忽视了节点本身的属性以及节点与节点之间的信息交互影响。而目前微博网络中存在着大量的信息分享和交互等用户行为，所以再对微博网络使用传统的社区发现算法已不能得到准确的社区划分结果。考虑到微博这类真实网络所具有的特性，Lin等人[9]提出了NAS算法和CNS算法来进行社区发现，算法考虑了节点属性的相似度以及共有邻居的相似度；乔秀全等人[10]在对电子商务的研究中，考虑了用户的社会信息和交互行为来进行社区发现，也提到在采集用户信息时有一定的局限性；林友芳等人[11]的研究是在GN算法的基础上改进，提出CIG_ESC算法将边介数转化成紧密度，基于紧密度进行删边得到社区划分结果，虽然算法易于理解，但是该算法没有给出紧密度计算的具体公式，只给出了抽象函数公式，不容易实现。

借鉴林友芳等人[11]的研究，本文引入用户紧密度这一概念，针对传统的社区发现算法难以对微博网络进行准确的社区划分的问题，提出一种基于用户紧密度的社区发现算法。该算法首先考虑了转发微博、评论微博等用户行为对用户间交互关系的影响，然后考虑了用户间共有邻居相似程度并计算用户紧密度，最后与传统的GN算法相结合对微博网络进行社区发现。

1　相关研究

1.1微博网络

微博网络即是对微博社交平台系统的一种抽象。将微博中的用户抽象为网络中的节点，将微博中用户间的关注关系抽象为网络中的边，将微博中用户的交互行为抽象为网络中边的权值，这样就抽象出一个由节点、边和边权值构成的微博网络。

1.2社区概念

社区这一概念起源于社会学研究领域中，一个被大家普遍接受的概念是社区内部的节点之间的连接非常紧密，而社区外部的节点之间的连接极为稀疏。

1.3GN算法

GN算法是基于删边的聚类算法，其基本思想是不断地从网络中删除介数最大的边，通过计算模块度Q值[12]来判断算法是否终止以及评价社区划分的优劣。

GN算法的流程包括：(1)计算网络中每条边的边介数；(2)删除边介数最大的边；(3)判断网络是否产生新的社区结构，如有进行第4步，若无则进行第2步；(4)计算模块度值；(5)将新的模块度与之前的模块度进行比较，如果新模块度大于之前的模块度，则将删除后的网络作为新网络进行第1步，反之输出之前模块度对应的社区结构，算法结束。

1.4微博用户交互度

文献[13]通过分析用户行为的相互性和频度来评估用户交互程度，但是该文献中没有给出具体的算法公式。本文考虑了微博中转发与评论行为，量化了用户交互程度。假设Wij表示网络中用户i与用户j连接边的权值，对应微博网络中用户i对用户j主动发生Wij次转发和评论的次数总和；Fij表示用户之间的交互程度值，计算公式如下：

(1)

Fmax=maxi=1→N,j=1→N{Fij}

(2)

接下来使用Fmax对Fij的结果进行归一化处理，最终的用户交互程度值为：

(3)

经过上述处理之后，能保证Fij的值均在(0,1)之间，这样能够更好地反映网络中用户的交互程度，同时微博网络可以使用无向带权图来表示，大大降低了算法的难度。

1.5微博用户共有邻居相似度

在微博网络，处在同一社区的两个节点往往比处于不同社区的两个节点拥有更多相同的邻居节点，所以用户的相似程度是从两个用户的共同朋友的相似度来考虑的。假设N(i)表示用户i的邻居节点，N(j)表示用户j的邻居节点，Sij表示用户相似度，CNS算法中计算用户相似度的公式如下：

(4)

从式(4)中可以看出，两个节点共同朋友的数量在它们所有朋友中所占的比例越高，它们的相似度越大。

2　基于用户紧密度的微博网络社区发现算法

2.1问题提出和改进思想

目前已有的社区发现算法在计算微博用户间的紧密度时，缺乏对转发微博、评论微博以及共有邻居相似性等信息对微博用户间紧密度有较大影响的考虑。针对这一问题，本文提出了一种新的用户间紧密度计算方法，同时考虑微博用户的交互程度与共有邻居相似程度，使计算结果能够更加全面地反映用户间的紧密关系。在新的微博用户紧密度计算方法的基础上，结合GN算法的思想，在GN算法进行删边时使边介数除以用户紧密度值作为边的权值，降低紧密度强的边被删除的概率，通过删除权值对微博网络社区进行划分。

2.2算法定义

定义1微博网络是一种加权图G(V,E,W)，其中V为微博网络中包含n个节点的集合{v1,v2,…,vn}，vi表示一个微博用户；E为包含m条边的集合{e1,e2,…,em}，ei=(vi,vj) 表示用户vi和vj之间存在关注关系；W为用户间紧密度的集合{w1,w2,…,wn}，wij表示用户vi与vj的紧密程度。

定义2微博用户紧密度是两个微博用户间关系亲密度的体现，是划分微博网络社区的依据，由以下公式求得：

(5)

为了便于后续的计算，这里对Gij进行归一化处理，和处理用户交互程度时相同，先从Gij中找出一个最大值，将它定义为：

Gmax=maxi=1→N,j=1→N{Gij}

(6)

(7)

使用上述的用户紧密程度，更加全面地衡量了用户之间的紧密关系。

3　算法描述

本文提出了基于用户紧密度的微博网络社区发现算法，首先计算用户间的紧密度，然后与GN算法相结合。算法流程如下：

算法1改进的GN算法

输入：经过预处理的网络

输出：社区列表以及各社区内的节点

方法：执行以下步骤

步骤1根据式(1)-式(3)计算所有边的用户交互程度值；

步骤2根据式(4)计算所有边的用户相似度值；

步骤3根据式(5)-式(7)计算所有边的用户紧密度值，并乘以一个设定的正整数，使紧密度最小值大于1；

步骤4计算网络中每条边的边介数，并用边介数除以用户紧密度值作为每条边的权重；

步骤5删除权重最大的边，如果有多条边的权重都为最大值，则随机选取一条边删除；

步骤6判断网络是否产生新的社区结构，若产生则执行步骤7，否则执行步骤4；

步骤7计算网络社区结构模块度Q值并记录对应的社区划分结构，模块度初始化值为0，得到模块度的增量ΔQ；

步骤8若ΔQ>0，执行步骤4，否则输出之前模块度Q值对应的社区划分结构，算法结束。

4　实　验

4.1实验设计

在本节，因为采集的微博真实数据没有社区划分的标准，不能验证算法的准确性，所以采用了真实社会网络和人工生成网络进行实验来验证本文算法的有效性和准确性。实验环境为CPU双核2.4 GHz，内存4 GB，操作系统为Win8；开发语言为Java，编程工具为Eclipse。

4.2数据集

Zachary网络[14]是1970年Zachary用了两年时间观察美国一所大学空手道俱乐部成员间的社会关系得到的。这个俱乐部由34个人组成，由于俱乐部主管和校长之间产生争执，俱乐部分裂成为两个分别以主管和校长为核心的小团体。将该网络抽象成一个拥有34个节点、78条边的图，图中边的权值代表两个节点成员的交流频率。

LFR人工生成网络[15]通过设定不同的网络参数和社区参数来生成带有划分标准的复杂网络，可以用来生成与微博网络特征相似的人工网络，其源程序可以从Fortunato[16]的个人网站中下载。该算法提供了社区划分的标准，即带有原始社区，解决了验证算法正确性的问题。使用LFR人工生成网络时需要设置的主要参数如表1所示。

表1　LFR人工生成网络主要参数

在LFR人工生成无向加权网络时，n、k、maxk、muw的值需要设置，其他值都有默认初始值，t1=0，t2=1，beta=1.5，mut=muw，minc和maxc的取值根据节点度数序列的范围来选取。网络是否具有社区性主要与参数mut和muw有关，当mut越接近0时，社区结构越显著；越接近1，社区结构越不显著。muw同样类似，越接近0时，社区中节点的权值会更加集中在社区内部，社区之间的权值会越小。

4.3评价标准

为验证算法的有效性和准确性，本文采用模块度值和纯度值来作为评价标准。模块度Q值[14]定义为社区内实际边数与随机连接情况下社区内期望边数之差，用来定量地描述网络社区结构的优劣，公式如下：

(8)

其中，eii表示社区i内部边条数，ai表示与社区i中任意节点相连边的条数。Q的取值范围为[0,1]，在实际网络中，Q值通常在0.3到0.7之间，Q值越大，网络的划分效果越好，社区结构越明显。

纯度(purity)[16]，评价由不同方法生成的社区的准确性。纯度的定义如下：对于n个顶点的网络，对于特定划分R，其社区落在标准划分G中的节点数目所占全部节点的比例。公式如下：

(9)

其中，R为划分结果，G为标准结果，纯度的取值范围为[0,1]，纯度值越大表明方法的准确性越高。

4.4实验结果及分析

为了验证算法的有效性和准确性，本文对Zachary网络和LFR生成的模拟微博网络进行社区划分实验。将基于用户紧密度的社区发现算法与GN算法的实验结果进行对比，并对实验结果进行分析，选用NodeXL[17]作为可视化工具来展示社区划分效果。Zachary网络原始拓扑如图1所示。

图1　Zachary网络原始拓扑图

图1中每一个节点代表一个空手道俱乐部会员，每条边代表成员间的社会关系，边的权值代表会员之间交流的频率。实验中将边权值作为用户交互程度值来计算，根据算法1的步骤计算出网络中紧密度最小值为0.109，将所有用户的紧密度值乘以10，使用户紧密度最小值大于1。使用传统的GN算法、CIG_ESC与基于用户紧密度的社区发现算法进行社区发现实验，社区划分可视化结果分别如图2所示。

图2　Zachary网络划分结果图

图2(a)中实心节点和空心节点分别代表两个社区内的成员，使用GN算法第一次分割把原始社区划分成了两个社区，这个划分结果与Zachary网络的标准划分结果完全一致。(b)的划分结果与GN算法的划分结果一致，同样将原始社区划分成了两个社区，与Zachary网络的标准划分结果也一致。图2(c)中实心节点、空心节点和三角形节点分别代表三个社区内的成员，使用基于用户亲密度的算法最终把原始社区划分成了三个社区。现在根据式(8)和式(9)的评价函数进行计算，计算结果如表2所示。

表2　评价函数结果

可以从表2看出基于用户亲密度的算法得到的社区划分结构，基于用户亲密度的算法在将网络进行第一次划分成两个社区时，其划分结果与标准划分结构一致。但该算法最终将网络划分为三个社区，导致纯度值有所降低，但是其模块度值有所增高。由图2(a)-(c)可知，(c)中的实心节点和三角形节点属于(a)和(b)中标准划分的实心节点社区，可见该算法对标准划分中的实心节点社区进行了更加深层次的划分。由此可知，该算法可以将Zachary网络的社区结构正确地划分出。从表2还可以看出，GN算法也能得到正确的划分结果，经过分析是因为Zachary网络的社区结构非常明显。为了验证基于微博网络时，基于用户亲密度的算法比传统GN算法更加有效和准确，当LFR人工生成一个模拟微博网络时，设置参数使muw

图3　LFR模拟微博网络原始拓扑图

图3中的实心节点模拟微博网络中的用户，边模拟微博网络中互粉的用户，权值模拟微博网络中的用户交互程度值，该网络社区划分标准结构如表3所示。

表3　LFR人工网络社区划分标准结构

根据算法1基于用户亲密度的社区发现算法步骤计算出网络中紧密度最小值为0.0000235。将所有用户的紧密度值乘以100 000，使用户紧密度最小值大于1。使用传统的GN算法、CIG_ESC算法和基于用户紧密度的算法进行实验，可视化效果如图4所示。

图4　LFR模拟微博网络划分结果图

图4(a)中实心节点、空心节点、三角形节点分别代表三个社区内的成员;(b)中实心节点、空心节点、三角形节点和正方形节点分别代表四个社区内的成员;(c)中实心节点、空心节点、三角形节点和正方形节点分别代表四个社区内的成员。使用CIG_ESC算法与基于用户关系紧密度的算法都将原始社区划分成了四个社区，但是CIG_ESC算法将部分节点划分错误。而基于用户亲密度的算法划分出的这四个社区与标准划分结果完全一致，现在根据式(8)与式(9)的评价函数进行计算，计算结果如表4所示。

表4　评价函数结果

可以从表4看出,基于用户亲密度算法的模块度值和纯度值均高于传统的GN算法与CIG_ESC算法。该算法可以将LFR生成的微博模拟网络正确地划分出社区结构，说明基于用户亲密度的社区发现算法可以对具有微博网络特征的网络进行社区划分，并能得到有效和准确的社区划分结构，具有一定的实用价值。

5　结　语

本文研究了基于用户紧密度的微博网络社区发现算法。首先考虑用户间的交互程度以及共有邻居相似性，使用这些信息量化了用户的关系紧密度，用户间紧密度值越大表明越难被划分开。根据传统GN算法删除边介数值最大边的思想，基于用户亲密度的算法在删边时使边介数除以用户紧密度值作为边的权值，降低紧密度强的边被删除的概率，通过删除权值最大的边得到网络的划分结构。对真实社会网络Zachary网络以及LFR人工生成的微博模拟网络的实验表明，基于用户亲密度的算法可以发现这两类网络中的社区结构，并且对社区结构不明显的网络得到的实验结果要优于传统的GN算法，表明该算法是有效的。

在下一步工作中，如何降低算法的复杂度或将算法并行化来提高算法的执行效率，能够对海量的微博真实数据进行社区发现将会成为工作的重点。

[1] Kwak H, Lee C, Park H, et al. What is Twitter, a social network or a news media？[C]//Proceedings of the 19th international conference on World wide web. New York: ACM, 2010: 591-600.

[2] Milgram S. The small world problem[J]. Psychology today, 1967,1(1): 61-67.

[3] Watts D J, Strogatz S H. Collective dynamics of ‘small-world’networks[J].Nature, 1998, 393(6684): 440-442.

[4] Dunbar R. Grooming, gossip, and the evolution of language[M]. Cambridge: Harvard University Press, 1996.

[5] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.

[6] Newman M E J. Communities, modules and large-scale structure in networks[J]. Nature Physics, 2012, 8(1): 25-31.

[7] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J]. Bell system technical journal, 1970, 49(2): 291-307.

[8] Pothen A, Simon H D, Liou K P. Partitioning sparse matrices with eigenvectors of graphs[J]. SIAM Journal on Matrix Analysis and Applications, 1990, 11(3): 430-452.

[9] Liu H, Salerno J, Young M J. Social computing and behavioral modeling[M]. Berlin: Springer Science & Business Media, 2009.

[10] 乔秀全, 杨春, 李晓峰, 等. 社交网络服务中一种基于用户上下文的信任度计算方法[J]. 计算机学报, 2011, 34(12): 2403-2413.

[11] 林友芳, 王天宇, 唐锐, 等. 一种有效的社会网络社区发现模型和算法[J]. 计算机研究与发展, 2012, 49(2): 337-345.

[12] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical review E, 2004, 69(2): 026113.

[13] Kahanda I, Neville J. Using Transactional Information to Predict Link Strength in Online Social Networks[C]//Proceedings of the Third International AAAI Conference on Weblogs and SocialMedia, 2009：74-81.

[14] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of anthropological research, 1977, 33(4): 452-473.

[15] Lancichinetti A, Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J]. Physical Review E, 2009, 80(1): 016118.

[16] Khorasgani RR, Chen J, Zaine C R. Top Leaders Community Detection Approach in Information Networks[C]//4th SNA-KDD Workshop on Social Network Mining and Analysis. Washington DC: USA, 2010, 1-9.

[17] Smith M A, Shneiderman B, Milic-Frayling N, et al. Analyzing (Social Media) Networks with NodeXL[C]//Proceedings of the 4th International Conference on Communities and Technologies. New York: ACM, 2009:255-264.

DETECTION ALGORITHM FOR MICROBLOGGING NETWORKS COMMUNITY BASED ON USER CLOSENESS

Wei Qingjie1Li Jingteng2Wang Yu2

1(College of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)2(CollegeofSoftwareEngineering,ChongqingUniversityofPostsandTelecommunications,Chongqing400065，China)

Aiming at the problem of difficult in accurately partitioning the microblogging network community, based on the characteristics of microblogging network, this paper proposes a user closeness-based detection algorithm for microblogging network community. The algorithm computes user closeness based on interaction level between users and common neighbours similarity in microblogging network community, and combines with traditional GN algorithm to make community partition in microblogging network. Experimental verifications are conducted on real social network and simulated microblogging network, results show that the algorithm can effectively detect the community structure in networks.

Community detectionMicroblogging networkGN algorithmUser closenessCommon neighbour similarity

2015-04-19。国家自然科学基金项目(61171060)；重庆市经信委软件精英人才培养与公共服务平台建设项目(渝经信投资[2011]167号)；重庆市教委基金项目(渝教高[2010]48号)。韦庆杰，教授级高工，主研领域：协同计算，软件工程。李京腾，硕士生。汪雨，硕士生。

TP391

A

10.3969/j.issn.1000-386x.2016.09.060