社交网络上的社团发现方法综述

王英奎　郭洪亮　朱鹏飞

摘 要：近年来社交网络快速发展，例如新浪微博、微信、各种在线论坛等，这类网络是互联网重要的组成部分。对社交网络的研究已成为热点，其中一项重要的研究内容是社团发现，即探测社交网络的社团结构，其主要方法是对社交网络中的用户进行划分，处于同一个社团的用户具有高度的交互关系，而社团之间的用户交互十分稀疏。目前，研究人员已提出大量的社团发现方法，本文对现有的经典方法进行分析综述。

关键词：社交网络 社团发现 社团结构

中图分类号：TP393 文献标识码：A 文章编号：1003-9082（2018）06-000-01

一、社团发现背景

1.社交网络

当今社会中，我们无法离开网络，人与人在网络中的沟通成为我们日常生活中不可缺少的联系方式，诸如腾讯QQ、微信、新浪微博、在线论坛、邮件服务等等。我们称这类网络为社交网络SNS（Social Network Service），社交网络由用户和用户之间的交互关系构成，用户既是网络内容的生产者也是消费者，使得网络呈现社会化，成为现实社会的缩影。我们可以把网络中的每个用户抽象为节点，用户之间的关系（例如粉丝关系、转发、回复）抽象成边，这样社交网络可以抽象为图的形式进行研究。

社交网络是一种复杂网络，因此它有诸多特性：小世界效应、无尺度性、聚类性，具有社团结构等等。对于大规模网络而言，很难对整个网络进行完整的研究，而社团结构描述了网络成员的联系模式，即同一个社团内的成员联系紧密，而不同社团之间的成员联系松散[1，2]，网络中的大量成员可以划分到不同的社团中，社团结构是网络的一个重要的特征。

1.1社团发现的意义

对社交网络的社团结构的研究具有十分重要的意义。通过社团结构我们能够获得用户的喜好，如喜欢旅游还是电子产品？是偏爱IOS系统的苹果品牌手机还是基于安卓系统的手机？获得这一信息有利于广告的精准投放。

此外，现实社会中的犯罪行为也逐步转移到社交网络中，犯罪分子会在网络中互相联络，准备实施犯罪行为，这样他们形成在线犯罪团伙，这就是一个社团，对犯罪社团组织的检测已经开始辅助公安系统打击犯罪。

近期美国的Facebook用户信息泄露，进而影响美国大选事件闹得沸沸扬扬，这就是一个研究机构充分利用社交网络引导舆情的现实例子。如果能够在网络中利用社团结构监控和引导舆情，对社会的稳定发展具有十分重要的意义。

二、社团发现方法

1.社交网络建模

社交网络中的用户抽象为节点，用户之间的联系抽象为边，因此大多数社团发现方法把社交网络抽象为图的形式。图1显示了一个样例网络，具有8个节点，它对应的邻接矩阵如图2所示。

2.经典的社团发现方法

2.1 Girvan和Newman的社团发现方法[5]

Girvan和Newman首次提出了GN社团发现算法，该算法基于一个简单的方法：逐步删除社团之间的边，最后得到的联通分支就是社团。它的算法如下：

a） 计算所有边的中心度，中心度用边的介数来衡量，其定义为网络中所有节点对之间的最短路径经过当前边的条数。

b） 删除具有最大中心度的边，如果多条边的中心度相同，则随机选择一条。

c） 重新计算网络所有边的中心度。

d） 迭代执行b）

GN方法是社团发现领域非常著名的方法，其优点是理论简单可行，但缺点是计算的时间复杂度过大，假设网络中边的条数为m，节点个数为n，它的时间复杂度为。因此GN算法无法处理大规模网络。

2.2基于模块度模型的Louvain方法[3]

Newman和Girvan提出了模块度模型，Q函数 [4]能够衡量对网络社团划分的优劣。其定义如公式1所示。

（1）

其中，A为邻接矩阵，为节点i的度，为节点i所在的社团，为边数。

Louvain的主要优点是能够处理大规模的网络，尽管它不能保证最优的图划分。它的处理过程如下：在初始化阶段，假设每个节点自己构成一个社团。接下来，对每个节点，计算把它放入它的邻居节点所在的社团时的模块度，选取模块度最大的社团作为该节点的社团，下一步处理时，把已经形成的社团视为一个新的节点，并计算该新节点和其余节点的度，即社团内所有节点和其它节点的度之和，重复迭代上述过程，知道模块度不再增大为止。

2.3标签传播算法[6]

标签传播算法由Raghavan等人提出，其算法流程如下：

a）初始化阶段，初始化所有節点，给每个节点赋值唯一的标签。

b）处理每个节点，考虑它的邻居标签，也就是选取大多数邻居具有的标签作为节点的新标签。

c）迭代处理所有节点，使得所有节点都和自己的多数邻居具有相同的标签。

标签传播算法的处理速度很快，只需接近线性时间。

2.4重叠的社团发现方法

这类方法基于一个现实，即网络中的成员可能同时属于多个社团，因此社团之间是有重叠的，并不只是节点的划分[7]。

重叠的社团发现方法包括基于团渗透的方法（CFinder[9]）、基于链接划分的方法（扩展的Infomap[8]）、基于局部扩展的方法（LFM[10]）等。

三、社团发现方法评价指标

对社团发现算法的效果进行评价的常用指标包括模块度函数Q，F-score，Jaccard index和标准互信息NMI（Normalized Mutual Information），其中NMI是最常用的评价标准。

四、总结

本文对社交网络，以及社交网络上的社团发现方法进行了讨论，总言之，社交网络是互联网上具有重要研究价值的目标，它是真实社会的在线表现形式，社团发现算法能够探测出的这些网络的社团结构，这对广告投放、舆情引导、犯罪分子检测等领域都具有现实的意义。

參考文献

[1]杨博，刘大有，金弟等.复杂网络聚类方法[J].件学报， 2009（1）：54-66.

[2]刘大有，金弟，何东晓等.复杂网络社区挖掘综述[J].算机研究与发展， 2013（10）：2140-2154.

[3]Vincent D Blondel， Jean-Loup Guillaume， Renaud Lambiotte， and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics： theory and experiment， 2008（10）：P10008， 2008.

[4]Mark Newman； M. Girvan. Finding and evaluating community structure in networks. Physical Review E， 69（2）， February 2004.

[5]Girvan M； Newman M E J.Community structure in social and biological networks.2002（12）.

[6]Raghavan U N；Albert R； Kumara S.Near linear time algorithm to detect community structures in large scale networks.2007（03）.

[7]Palla G；Derenyi I；Farkas I. Uncovering the overlapping community structures of complex networks in nature and society.2005（7043）.

[8]Rosvall M；Bergstrom C T.Maps of random walks on complex networks reveal community structure. 2008（04）.

[9]Palla G；Derényi I；Farkas I.The software of clique percolation method. 2012.

[10]Lancichinetti A；Fortunato S；Kertesz J.Detecting the overlapping and hierarchical community structure in complex networks.2009（03）.