您现在的位置:首页 > >

大数据环境下复杂社会网络的社区发现方法研究综述

发布时间:

龙源期刊网 http://www.qikan.com.cn 大数据环境下复杂社会网络的社区发现方法 研究综述 作者:赵中英 李超 来源:《软件导刊》2016 年第 12 期 摘 要:社会化媒体大数据环境下的社区发现研究,是社会网络分析与挖掘领域的一个热 门研究方向,已有众多学者提出各种研究方法,但对当前研究工作的进展分析相对较少。首先 从局部、全局、节点相似度 3 个角度讨论社区的定义,然后针对网络的大规模、动态、异构 3 个特性,分别调研与梳理国内外相关文献,并从采取的主要技术、数据建模方法、可处理的网 络规模、网络时序特征 4 个方面比较与总结其中的代表性方法,分析当前的学术思路与发展动 态,最后指出该研究领域存在的挑战及未来可能的研究方向。 关键词:大数据;社区发现;复杂社会网络 DOIDOI:10.11907/rjdk.162505 中图分类号:TP301 文献标识码:A 文章编号:1672-7800(2016)012-0164-04 0 引言 社区发现旨在探测复杂社会网络中具有共性特征或紧密关系的群体。该研究能帮助人们从 介观(Mesoscopic)的视角分析网络的*私峁梗斫馔绻δ埽沂就缰械囊J剑 及分析预测网络行为。同时,还可以应用在智能推荐、精准营销、个性化服务等诸多领域。因 此,社区发现研究具有重要的理论意义和较高的应用价值。社区发现的重要性,吸引了国内外 学者的广泛关注。斯坦福大学、康奈尔大学、卡内基梅隆大学、亚利桑那州立大学、清华大 学、中科院等国内外许多大学和研究机构都围绕此课题开展了深入研究,取得了一系列重要的 研究成果。当前,对社区发现研究的分析与综述工作较少,不利于把握整体脉络及发展趋势。 本文对大数据环境下复杂社会网络的社区发现方法进行综述。首先从三个层面讨论社区定 义,然后针对网络的大规模、动态、异构 3 个特性,阐述与比较已有的社区发现方法,分析现 有工作的学术思路与发展动态,最后指出存在的挑战及可能的发展方向。 1 社区定义 社区本身只是一个定性的概念,自提出之日起,关于社区的定量定义就引起了来自不同领 域学者们的争议与广泛讨论,直至目前,仍然没有一个被广为接受的定量定义。直观上讲,社 龙源期刊网 http://www.qikan.com.cn 区通常被认为是复杂网络中的一些节点组(团),同一组内的节点之间连接相对紧密,组与组 之间连边相对稀疏。 当前对社区的定义,可以分为 3 类:基于局部的社区定义、基于全局的社区定义与基于结 构相似度的社区定义[1]:①基于局部的社区定义,只考虑社区内部节点及社区内部节点与外 部节点间的联系,而不考虑社区外部节点之间的联系信息。局部社区定义一般会给出一种社区 应满足的条件或约束,据此找出网络中能够满足该条件的极大子网络,这些子网络则被称为社 区。例如:Palla 等[2]提出 k-clique(大小为 k 的 clique)社区定义,通过 k-clique 的滚动得到 最终的社区;②基于全局的社区定义,则从网络整体出发,通过网络中的某个性质间接给出社 区定义。全局定义方式中最有代表性的社区定义是基于模块度的定义(modularity)[3]。基于 模块度的社区定义,以随机网络(代表性的有 E-R 网络)为参照,依据当前网络与参照网络的 偏差来定义社区。即在保证两种网络节点度分布相同的情况下,随机放置节点间的边,若某一 个子网络内部的连边数高于其在参照网络中的期望连边数,则认为该子网络为一个社区。基于 模块度的社区定义,是当前广为接受的一种社区定义方法;③基于节点相似度的社区定义,以 同一社区内的节点相似度较高为指导思想,其基本框架为:首先根据网络*诵畔⒓扑闳我饬 对节点间的相似度;然后根据节点间的相似度采用层次聚类的方式把节点分成各个组,每个节 点归属于与其最相似的组;最终,每个组被视为一个社区[4]。 2 复杂社会网络的社区发现研究进展 在社区发现方面,研究者们提出了许多网络社区发现算法。根据其采取的基本求解策略不 同,可以划分为两类[5]:基于优化的方法(Optimization Based Method)和启发式方法 (Heuristic Method)。前者将社区发现问题转化为优化问题,通过最优化预定义的目标函数计 算网络的簇结构。例如,谱方法(Spectral Method)[6]将网络聚类问题转化为二次型优化问 题,通过计算矩阵的特征向量来优化预定义的“cut”函数,文献[7]中也描述了类似工作;启发 式方法则是将网络社区发现问题转化为预定义启发式规则的设计问题,已经成功地应用在各种 社会网络或交互网络中,如 Email 网、人类社交网、科学家协作网等。然而,这些算法都具有 较大的计算开销,只能应用在规模为数万节点以下的中小规模网络中。 随着互联网的发展及社交媒体的盛行,社会网络的规模不断增大,人们开始探索大规模图 的快速社区发现算法。Wakita 等[8]给出 3 种不同的社区规模度量指标,通过控制社区的*衡 增长方式,提出了一种改进的 CNM 算法;Raghavan 等[9]提出一种基于标签传播(Label Propagation)的局部社区发现方法,该方法能够将计算过程并行化,其时间复杂度*乎线性, 因而能够适用于大规模的网络分析;Ghosh 等[10]以“影响力”(任意两个节点之间的路径长 度)作为度量,给出一种新的基于全局影响力的社区发现算法;Koutsourelakis 等[11]考虑到社 区的重叠性现象,提出了基于概率混合模型的社区发现算法;Rohe 等[12]基于随机分块模型, 给出了面向大规模社会网络的谱聚类方法;Tang 等[13-14]将大规模网络的社区发现问题转化 为社区核检测问题,提出了“Greedy”和“We BA”算法。 龙源期刊网 http://www.qikan.com.cn 动态性是社会网络最本质的特点之一,研究社区的动态性可以帮助人们发现社区随时间变 化的


热文推荐
猜你喜欢
友情链接: 医学资料大全 农林牧渔 幼儿教育心得 小学教育 中学 高中 职业教育 成人教育 大学资料 求职职场 职场文档 总结汇报