关于社交网络方面硕士学位论文范文与社交网络上的社团发现方法综述方面硕士学位论文范文-毕业论文网

该文是关于社交网络论文范文，为你的论文写作提供相关论文资料参考。

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

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

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

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

一、社团发现背景

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

社交网络是一种复杂网络,因此它有诸多特性：小世界效应、无尺度性、聚类性,具有社团结构等等.对于大规模网络而言,很难对整个网络进行完整的研究,而社团结构描述了网络成员的联系模式,即同一个社团内的成员联系紧密,而不同社团之间的成员联系松散[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,它的时间复杂度为Ο(m2n).因此GN算法无法处理大规模网络.2.2基于模块度模型的Louvain方法[3]

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

其中,A为邻接矩阵, i k 为节点i的度, i c 为节点i所在的社团, m为边数.

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

2.3标签传播算法[6]

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

a)初始化阶段,初始化所有节点,给每个节点赋值唯一的标签.b)处理每个节点,考虑它的邻居标签,也就是选取大多数邻居具有的标签作为节点的新标签.

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

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

2.4重叠的社团发现方法

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

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

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

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

四、总结

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