基于三元闭包和会员闭包的社区发现算法研究

许云峰，赵 宁，郝雪君，李 兵，刘慧娟

(1.河北科技大学信息科学与工程学院，河北石家庄 050018；2.河北科技大学人事处，河北石家庄 050018)

基于三元闭包和会员闭包的社区发现算法研究

许云峰1，赵 宁2，郝雪君1，李 兵1，刘慧娟1

(1.河北科技大学信息科学与工程学院，河北石家庄 050018；2.河北科技大学人事处，河北石家庄 050018)

随着网络的发展和人们沟通方式的扩展，社交网络影响了人们的生活，改变了人们传播与分享消息的方式，吸引了越来越多的人关注和研究社交网络。社交网络即社交网络服务，源自英文SNS(social network service)的翻译，社交网络有多种表现平台，比如QQ、微博、Facebook和微信。本文主要研究微博这一新兴的社交平台,研究微博的主要目的是搞清用户之间的种种关系。当代人一般认为，微博中存在5种关系即关注关系、提及关系、转发关系、评论关系以及好友关系。由于社交网络中人数众多，关系错综复杂，因而产生的社交数据和传统的数据相比具有数据量大、结构复杂、语义丰富等特点，针对这种情况，依据用户之间的关系，提出了一种基于三元闭包的社区划分算法。

该算法首先设初始社区为空，在所有的顶点中，选择度最大的顶点作为初始顶点；然后求初始顶点与其邻接顶点的三元闭包数和顶点属于该社区的概率PS，取它们最大的邻接顶点加入初始顶点所在社区，形成新的社区，继续迭代，当剩余的顶点很少时，可以使用会员闭包和三元闭包这种归集算法把剩余的顶点划分到不同的社区，直到把整个社区划分完毕；最后以图形这种直观、形象的方式把每一个社区表示出来。在该算法中，三元闭包数、顶点属于某社区的概率、扩张度的差是评估复杂网络中顶点划分的关键。该方法综合了顶点全局重要性的特点, 即在复杂网络中,三元闭包数越大，它们处在一个社区的可能性就越大；顶点的会员闭包越大,该顶点就会越优先被划分；扩张度的差是确定第i个社区是否被划分完毕的关键。

社交网络的研究不仅可以帮助人们了解网络结构、分析网络结构特性、探测分析网络的社团结构，而且还可以把虚拟世界中这种关系链接到现实世界中，即把虚拟关系转化成利润，为企业提供有价值的关系网络，从而挖掘出潜藏在社交网络背后的巨大的经济价值，具体体现在：1)帮助企业找到潜在的商机，比如分析某个用户的评论和发表内容，可知他的消费能力、喜好和最近的购买习惯，从而知道他购买自己产品的概率；2)危机预警，根据用户的消息内容可以知道他对自己产品的满意度；3)带动了消息的传播速度和广度。企业可以利用这一点，为自己的产品更好地做宣传。

通过与宽吻海豚网和Zachary空手道俱乐部的社区网络作比较，证明了该算法的有效性和可行性。

社交网络； 三元闭包； 社区划分

近年来，随着时代的进步，社交网络的发展逐渐被人们所关注，社交网络已成为人们生活的一部分，并对人们的信息获得、思考和生活产生巨大的影响，社交网络在人们的生活中扮演着重要的角色，社交网络成为人们获取信息、展现自我、营销推广的窗口。社交网络即社交网络服务，源自英文SNS(social network service)的翻译，中文直译为社会性网络服务或社会化网络服务，意译为社交网络服务。社交网络含义包括硬件、软件、服务及应用，由于四字构成的词组更符合中国人的构词习惯，因此人们习惯上用社交网络来代指SNS。Web 2.0 的广泛应用和新型社会化网络媒体的盛行，促使网络服务从以数据为核心的模式开始转变为以用户或用户关系为核心的模式。

社交网络中的微博是近年来刚刚兴起的一种信息交流媒体，每个用户可以通过手机、QQ等多种方法来改变微博的状态，发表自己当前的心情，而每一条微博可以是一个符号，一个表情，一张图片，一段视频等。与传统社会媒体相比较，具有信息实时、内容简洁、用户交互等特点，它作为一种新型媒体，是一个基于草根用户的关系构建及个性化用户信息的即时传播、共享和获取的平台，它的发展趋势更加迅速，已经表现出后来居上的趋势，由于微博具有以上特点成为当今国内外的主流社交媒体。

具体的讲，关注关系是指用户以粉丝的形式关注另外一个用户，这种关注形式是以单向微博作为一个新的平台，对于它的研究具有广阔的前景，尤其是在信息传播、用户关系等方面。研究微博的主要目的就是搞清用户之间的种种关系，比如，用户之间的关注关系、社区中的好友或亲情关系、实时交互过程中因共同购买或评论产品而结成的共同兴趣关系等。GRANOVETTER提出社会网络中普遍存在的两种关系：强关系与弱关系[1]，社会学家普遍认为强关系是一种基于信任的关系，而弱关系是一种信息流通的渠道。人们一般认为，微博社交网络中存在5种关系：关注关系、提及关系、转发关系、好友关系以及评论关系，微博社交网络是一种单向关系与双向关系并存的网络，这种关系展现的是一种拓扑结构。而提及关系以及转发关系是一种以关注关系为基础的关系，这种关系是由于用户因被关注者的内容吸引而产生的关系链接。好友关系是用户互为关注的关系模式。评论关系是一种以好友关系为基础的关系，这种关系是由于用户评价好友的信息产生的关系。

社区现象是一种复杂网络中的普遍现象，表述的是多个个体之间具有的共同特性。社区发现技术从最初的图割KL算法[2]、w-H算法[3-4]、GN算法[5-6]等，经过逐渐的发展和改进，形成了包括改进后的如：基于“边介数”概念的GN算法[7]、凝聚CNM算法[8]、CPM算法[9]、LP算法[10]、Louvain算法[11]、多模型聚类算法[12-14]等更具可操作性的方法。网络的社区发现可分为个性化服务、信息推送等，并提供基本数据，尤其是在信息时代，社区的存在更加普遍，发现技术的应用也更加方便，其商业价值和服务价值更大[15]，所以这个方向慢慢的成为人们研究的焦点。现在的许多社区发现算法复杂度都很高，只能作用在比较小的网络中，而对于大规模的复杂网络，提高社区发现的准确度也许并非其关键，而提高社区发现的速度才是关键。NEWMAN提出的基于Betweenness的算法[16]，是利用多核CPU来加速Betweenness计算的，通过适当的调度算法，可以用分布式的方式来并行计算Betweenness,从而比在单CPU上的计算速度提高了3～4倍，这些发现与研究都为社区的发展做出了贡献。方平等提出了基于共同好友数的社区发现算法[17]，该算法符合社交网络的特点，适合对大规模社交网络进行社区划分，本文在方平等的工作基础上，根据三元闭包原理，提出了一种基于三元闭包的大规模社交网络社区发现算法，同时用会员闭包原理加快了社区划分的速度。

1 相关概念

首先将一个社交网络定义为一个有n个顶点，m条边的图G(V,E),其中n=|V|，m=|E|。S为社区中的顶点集，其中NS为S中的顶点的数目,记为NS=|S|，MS为S中边的数目，记为MS=|{(u,v):u∈S,v∈S}|;CS是S向外连接的边的数目，记为CS=|{(u,v):u∈S,v∉S}|。

定义1(图) 社交网络中可以由顶点集和连接2个顶点之间关系的边的集合组成一个图来表示。在这个图中，顶点代表一个个体或组织，顶点之间的边代表它们之间存在着某种关系。而在图形中，顶点之间的关系可以是任意的，图中任意2个个体之间的关系都可能是相关的，根据每边之间是否有方向和权值，图又可以分为有向图、无向图，有全图、无全图。本文主要研究无向无权图。

定义2(度) 网络中顶点的度是指与顶点相关联的边的数目。网络又可分为有向网络和无向网络，在有向网络中，度又有入度和出度之分，入度定义为以顶点为头的边的数目，出度定义为以顶点为尾的边的数目。一般认为，顶点的度越大，就说明这个顶点越重要，与其他顶点联系越密切。

定义3顶点i的邻居顶点集合记为NB(i)，顶点i的度记为D(i)，S的邻居顶点集合为NBS。

定义4(三元闭包) “在一个社交圈内，若2个人有1个共同朋友则这2个人成为朋友的可能性就会提高”。在社交网络中，广泛的存在三元闭包。

定义5(三元闭包数) 假设A与B为好友，同时A与C也为好友，那么B与C的共同好友为A。由三元闭包可知，在一个社区网络中，2个人如果有共同的好友，那么他们成为好友的几率就会增大，所以取2个顶点间三元闭包数来衡量这2个顶点的相似度。

定义6会员闭包是指在一个社交网络中，若一个人的朋友参加了某个社团则其参加这个社团的可能性就会提高。如果顶点i有x个朋友在S中，则顶点i相对于S的会员闭包数x=|NB(i)∩S|。

2 算法描述

本算法首先设初始社区为空，在所有的顶点中，选择度最大的顶点作为初始顶点；然后求初始顶点与其邻接顶点的三元闭包数，取三元闭包数最多的邻接顶点加入初始顶点所在社区；之后再求初始社区中的所有顶点的各邻接顶点属于初始社区概率PS，将PS最大的顶点加入，形成新的初始社区；继续迭代，通过不断加入与初始社区会员闭包最大的顶点的方法把社区刷新，当所要加入的顶点的扩张度的差大于0或者所剩顶点的个数小于w时，这个小社区就划分完毕。将以上步骤在剩下的网络顶点中继续执行，直到将网络中所有顶点都被划分或者所剩顶点的个数小于w。此处的w可根据|V|的大小来定，例如|V|的1/10,因为在大规模社区中，当划分到图中的顶点较少时，此时真正有价值的社区已经很少了，此时再用以上步骤去划分，找出来的社区会更小，此时剩余的顶点可以用更简单的算法归集，如用社会学里的会员闭包通过判断其好友属于的社区来确定其属于的社区，最终把整个社区划分完毕。

算法实现步骤：

1)如果|V|>w，初始社区Ci=Null,V!=Null,否则跳转到步骤9)；

2)查找V中度最大的顶点Va，加入到社区Ci中，V=V-Va;

3)根据定义5查找没有被分配且与顶点Va三元闭包数最大的顶点Vb加入到初始社区Ci中，此时Ci=Ci+Vb，V=V-Vb；

4)根据定义9求顶点属于社区的概率PS；

5)找到顶点PS最大的顶点Vx;

6)由定义8求ED(Vx)，如果ED(Vx)<0，则令Ci=Ci+Vx,V=V-Vx;

7)循环步骤5)和步骤6)，当ED(Vx)>0时，这个社区的添加顶点完毕，此社区划分好；

8)令i=i+1，返回步骤1);

9)当|V|

3 算法应用

3.1某文学网站的用户

本研究将某文学网站的数据用基于三元闭包的算法进行划分，得到了65个社区，然后将划分结果放到NodeXL中，分别展示每个小社区的图形，但是由于数据比较大，虽然很多小的社区已经被大社区覆盖掉了，但是小社区能够较清晰地体现出来，最终得出的图形如图1所示。

图1 基于三元闭包的算法Fig.1 An algorithm based on triadic closure

由CNM算法划分的社区如图2所示，使用这种算法划分出的社区比较少，并且包含了数据量巨大的社区，这说明使用CNM算法实现的社区划分对具有包含类似于节点1这样的度很大的用户的网络进行细分有些不足；而根据三元闭包数所划分成的社区则相对平均，划分出的社区数目相对大些，所以这样划分出的社区才更具有研究价值。

图2 CNM 算法划分的社区Fig.2 Community structure found by CNM algorithm

为了更形象的对CNM算法与基于三元闭包的算法作比较，分别对这两种算法所得到的社区数据进行详细统计，结果如表1所示。

表1 CNM算法与基于三元闭包算法的比较Tab.1 Comparison of CNM algorithm and the algorithm based on triadic closure

3.2宽吻海豚网

该网络为一个动物社会关系网络，数据来自网络公开数据集。LNSSEAU等人对新西兰Doubtful Sound峡湾的一个宽吻海豚群体进行长达7年的观察所构造出该海豚关系网，见图3。该网络中每个节点代表一个海豚，边表示2个海豚之间有频繁的接触，在该网络中共有62个节点、159条边。本文基于三元闭包的社区发现算法对该数据集的划分结果与实际社区划分相吻合。

图3 宽吻海豚网Fig.3 Bottlenose dolphins network

3.3Zachary空手道俱乐部网络

Zachary空手道俱乐部的关系网共有34个节点、78条边，见图4。本文基于三元闭包的社区发现算法对该数据集的划分结果与实际社区划分相吻合。

图4 Zachary空手道俱乐部网络Fig.4 Zachary of karate club network

4 总 结

以微博用户的信息数据为依据，提出了一种基于三元闭包和会员闭包的网络社区结构发现算法，提出顶点会员闭包定义，以网络中三元闭包数最多的2个顶点为初始社区，根据顶点会员闭包和扩张度的差不断增加邻接顶点，形成局部最优初始社区，适用于比较复杂的在线社会网络。本文算法对宽吻海豚网与实际网络社区结构基本相符，对“Zachary空手道俱乐部网络”的划分结果与实际网络结构一致，并且对有关顶点接近度进行了重新定义，这种定义更适用于比较复杂的网络，提高了算法的效率与可行性，使相关代码更容易实现。

/

[1] GRANOVETTER M S. The strength of weak ties[J]. American Journal of Sociology，1973，78(6)：1360-1380.

[2] KERNIGHAN B W，LIN S．An efficient heuristic procedure for partitioning graphs[J]．Bell System Technical Journal,1970，49(1)：291-307．

[3] NEWMAN M E J. A measure of betweenness centrality based on random walks[J]. Social Networks, 2005, 27(1):39-54.

[4] 张 聪, 沈惠璋, 李 峰. 复杂网络中社团结构划分的快速分裂算法[J]. 计算机应用研究, 2011, 28(4):1242-1244. ZHANG Cong，SHEN Huizhang,LI Feng. Community structure in complex networks rapidly dividing division algorithm[J]. Application Research of Computers, 2011, 28(4):1242-1244.

[5] 肖 晶. 基于WAF的社区发现及用户推荐[D]. 北京：北京邮电大学，2013. XIAO Jing. Based WAF User Community Discovery[D]. Beijing：Beijing University of Posts and Telecommunications,2013.

[6] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. National Academy of Sciences, 2002, 99(6):7821-7826.

[7] CLAUSET A，NEWMAN M E J，MOORE C．Finding community structure in very large networks[J]．Physical Review E：Statistical，Nonlinear and Soft Matter Physics，2004，70(6)：6111-6116．

[8] PALLA G，DERDNYI I，FARKAS I，et al．Uncovering the overlapping community structure of complex networks in nature and society[J]．Nature，2005，435：814-818．

[9] RAGHAVAN U N，ALBERT R，KUMARA S．Near linear time algorithm to detect community structures in large-scale networks[J]．Physical Review E，2007，76(3)：6106-6111．

[10] BLONDEL V D，GUILLAUME J L，LAMBIOTTE R，et al．Fast unfolding of communities in large networks[J]．Journal of Statistical Mechanics，2008(10)：10008-10018．

[11] TANG L，LIU H，ZHANG J．Identifying evolving groups in dynamic multi-mode networks[J]．IEEE Transactions on Knowledge and Data Engineering，2012，24(1):72-85.

[12] FABER V. Clustering and the continuousk-means algorithm[J]. Los Alamos Science, 1994, 22:138-144.

[13] ZHAO W, MA H, HE Q. Parallelk-means clustering based on mapreduce[A].Cloud Computing[C]. Berlin：Springer, 2009. 674-679.

[14] KRISHNA K, NARASIMHA M M. GeneticK-means algorithm[J]. IEEE Transactions on Systems, Man and Cybernetics, Part B:Cybernetics, 1999, 29(3):433-439.

[15] 淦文燕, 赫 南, 李德毅. 一种基于拓扑势的网络社区发现方法[J]. 软件学报, 2009, 20(8):2241-2254. GAN Wenyan, HE Nan, LI Deyi. A network of community-based topology discovery potential method[J]. Journal of Software, 2009, 20(8):2241-2254.

[16] NEWMAN M E J. A measure of betweenness centrality based on random walks[J]. Social Networks, 2005, 27(1):39-54.

[17] 方 平，郭正彪，李芝棠，等.基于共同好友数的在线社会网络社区发现算法[J]. 计算机科学与探索, 2012,6(5):456-464. FANG Ping, GUO Zhengbiao, LI Zhitang，et al. Online social network community structure detection algorithm based on number of shared friends[J]. Journal of Frontiers of Computer Science & Technology, 2012,6(5):456-464.

[18] RADICCHI F,CASTELLANO C,CECCONI F,et al.Defining and identifying communities in networks[J].National Academy of Sciences,2004,101(9):2658-2663.

A community detection algorithm based on triadic closure and membership closure

XU Yunfeng1, ZHAO Ning2, HAO Xuejun1, LI Bing1, LIU Huijuan1

(1.School of Information Science and Engineering, Hebei University of Science and Technology, Shijiazhuang Hebei 050018, China;2.Personnel Department, Hebei University of Science and Technology, Shijiazhuang Hebei 050018, China)

With the development of network and the expansion of people's communication ways, the social network penetrates into almost every corner of the entire society, and changes the ways of information communicating and news sharing, attracting more and more people's attention and research on it. Social network, also named social networking service, originated from the translation of British SNS (social network service), was literally translated as social network services or social networking service in Chinese. There're many manifestations of social networking platforms, such as:QQ, WeChat, Facebook and Micro-blog.In this paper, we mainly focus on the micro- blog, the emerging social platform. The main purpose of research on micro-blog is to find out the various relationships between users. People generally believe there're mainly 5 relations existing in miro-blog among users:the relationship of concerning, mentioning, forwarding, commenting and being friends. Due to the large number of social network users and the complicated relations among them, the generated social data, compared with the traditional data, has the characteristics of large amount of data, complex structure and semantically rich features. So according to the relationship among users, this paper proposes divided community algorithm based on triadic closure.

In the first instance, this algorithm took the initial community as being empty, in which the vertex degree maximum among all vertices was chosen as the initial vertex, then requesting for the number of Triadic closures between the initial vertex and the adjacent vertex, and requesting for the probability of vertices belonged to the community. The vertex with the maximumPsjoined the initial vertex community, forming a new initial community. With continued iterating, and by using collection algorithm of triadic and membership closure, the remained few vertices could be divided into different communities until the entire community was completely divided. Finally, every community was intuitively and visually presented by Graphics. When using this algorithm, the number of Triadic closure, the probability of vertex belonged to a community and the difference in expansion degree are the keys to value vertices in complex network. This method combines the characteristics of the global importance of vertices. Namely, in complex networks, the greater the number of Triadic closure is, the greater the likelihood of them in a community will be. The greater the vertex membership closures are, the priorer the vertex will be divided. The difference in expansion degree is to determine whether theicommunity is divided completely or not.

The research of social networking can not only help us understand and analyze the network structure, and detect to analyze network, but also can help link the relationship in virtual world to the real world. So the virtual relationship could be transferred into profits, providing valuable network for enterprises, and digging out the great economic value behind the social network. It can be embodied like this:firstly, to help companies find potential business opportunities by analyzing users' comments and published content to learn their consumption power, preferences and recent buying habits, thus to know the probability that he could purchase products. Second, it can give crisis warning message. According to user's information, products satisfaction degree of users can be learnt. Third, it can drive the information propagation speed and message breadth, of which the enterprises take advantage, achieving better product publicity.

Compared with the community network of Bottlenose Dolphin Internet and Zachary, the algorithm mentioned in this paper was proved to be effective and feasible.

social network; number of triadic closure; community divide

1008-1542(2014)01-0103-06

10.7535/hbkd.2014yx01017

2013-11-01；

2013-12-02；责任编辑：陈书欣

国家自然科学基金(71271076)

许云峰(1980-),男,河北沧州人,讲师,硕士,主要从事网络安全、神经网络等方面的研究。

E-mail：386839300@qq.com

TP391.1

A

许云峰，赵 宁，郝雪君，等.基于三元闭包和会员闭包的社区发现算法研究[J].河北科技大学学报，2014，35(1)：103-108.

XU Yunfeng, ZHAO Ning, HAO Xuejun, et al.A community detection algorithm based on triadic closure and membership closure[J].Journal of Hebei University of Science and Technology,2014,35(1):103-108.