作者简介:王 娜(1977-),女(汉族),河北省保定市人,深圳大学教授.E-mail:wangna@szu.edu.cn
中文责编:英 子; 英文责编:雨 辰
Wang Na, Li Xia, and Xu HongyingCollege of Information Engineering, Shenzhen University, Shenzhen 518060, P.R.China
data mining; social network; community detection; heterogeneous multimodal information network; heterogeneous network with multidimensional relations
DOI: 10.3724/SP.J.1249.2014.01035
评述基于链接的同质社会网络社区发现方法,介绍基于多维链接关系和多模信息属性的异质网络社区发现方法,指出社会网络个体间不仅存在多种相互联系,其本身还存在描述自身特性的多种特征信息属性; 对社会网络认识的逐渐深入,需融合多方面信息协同处理.根据链接关系矩阵,选取博客平台BlogCatalog,在协同训练框架下融合用户特征信息并进行仿真,模拟异质多模社会网络社区发现.结果表明,对多种链接信息和内容属性信息的融合研究和协同处理可为社会网络社区发现提供准确丰富的信息.
The analysis of social networks, in particular, the discovery of communities within a network, has been a focus of recent research with diverse applications in several fields. In many social networks, there exist different link relations between users while attributes or content information and factors such as demographic details or user-generated content may be associated with those users. In this paper, we outline the state-of-the-art community detection methods based on linked homogeneous social networks. Then, we emphasize community detection in a heterogeneous social network either with multimodal information for each user in the network or with multidimensional relations between users. For the heterogeneous multimode social network, a new community detection method is proposed in the framework of co-training to combine both links and content analysis. Experimental simulations on a real heterogeneous multimode social network dataset were performed and the results have shown that integration of links information and content attributes provided richer and more accurate information for detecting social network community structures.
Web 2.0时代的博客、微博、社会标注及社交网站等社会网络应用系统正在蓬勃发展.不同于传统意义上的Internet网络,社会网络(social network)是基于用户且反映用户社会关系的网络拓扑.社会网络由许多节点(node)和连接这些节点的一种或多种特定链接(link)组成,根据功能可划分为社交性网站(social network site,如Facebook和Myspace等)、多媒体网络(multimedia network,如You Tube和Flickr等)、社会媒体网络(social media,如新浪博客和Twitter等)、即时通信网络(instant communication network,如MSN和QQ等)和论坛网络(online forum,如天涯社区等)等,这些网络的注册用户少则几十万,多则几千万,甚至上亿,为研究社会网络的结构和性质提供了丰富的平台.
社会网络的研究主要从社会网络的静态性质和动态特征两方面考虑.前者的研究包括拓扑分析[1]、社区发现[2]和关键节点挖掘[3]等; 后者的研究主要集中在社会网络形成、社区进化和社会网络中的信息传播[4]等方面.不同的社会网络有相同特征,即每个网络都由若干个“社区”(community)构成,社区内部节点间的联系相对紧密,社区之间的节点联系相对稀疏.不同的社会网络可划分为几个,几十个,甚至上万个社区.分析社会网络,社区发现是最难解决和核心的问题之一.事实上,发现社会现象的因果关系是通过研究群体而非个体来实现的.许多基于社会网络的应用研究,如关系学习、行为建模和预测、链接特征选择、可视化及群的演化分析都是以社区检测和分析为前提.由于社区检测能揭示网络结构和功能之间的关系,且对包括信息科学、物理、数学和生物等领域都有重要意义,因此近年来倍受关注.
根据社区发现所研究社会网络类型的不同,社区发现可简单划分为同质和异质两类.已有的社区发现方案大多假设网络对象为单一类型,它们之间的关系也被认为是单一类型,简称同质社会网络(homogeneous social network).但在现实中,同一网络中可能存在多种类型的实体(entity),它们通过不同的链接与其他实体(同种类型或不同类型)关联,即网络实体及实体之间的关系在性质上是异质的(heterogeneous),此类社区发现网络被称为异质网络.若网络中包含异质实体或角色,称做多模(multi-mode)网络,图1是异质多模网络示意图[5].该网络中视频、标注和用户表示3种不同的实体类型,每种实体代表一模.现广泛应用的博客即典型的异质多模网络,既有博客用户所发的内容信息属性,又有其用户的社会属性.若网络中的实体间存在多种交互方式,则被称为多维(multi-dimension or multi-relation)网络,每一维表示实体间多样化互动中的一种交互方式,Flickr和You Tube就是典型的异质多维网络,存在着标注、回帖和评价等多种交互关系,如图2[5].
本文评述基于链接的同质社会网络社区检测方法,介绍基于多维链接关系和多模信息属性的异质网络社区发现,结合本课题组在网络社区发现方面的研究进展,探讨社区分析的研究趋势及其应用前景.
链接是社会网络的一个本质属性,从数据挖掘角度来看,社会网络分析又称作链接挖掘(link mining).在社会网络社区发现研究中,最深入且最广泛的社会网络社区发现算法是基于链接分析的社区检测,可分为基于量度标准的方法和基于概率模型的方法.
在基于量度标准的方法中,量度标准旨在量化社区划分的质量,而社区划分则通过优化量度标准,或以迭代方式从当前划分中增加和移除边或顶点提高量度标准获得.该社区发现方法的思路可归结为3种:
1)层次社区检测方法,包括分裂法和凝聚法两种策略.该方法传承了复杂网络社团检测的经典理论算法.Newman[6]提出社会网络社区发现算法时使用的就是分裂式层次聚类方法.但这两种策略的层次社区检测方法都是在缺乏相应评价标准的情况下进行,难以抉择最优的分割层次结果;
2)基于图分割的方法,是将用户分到各子图中,使不同社团之间边的数量最小.图分割中应用最广的是谱方法.该方法通常需预测网络中的社团数,这在社会网络的社区检测中很难预知,因此成为制约其发展的因素之一;
3)基于模块化函数的方法.模块化函数Q[7]是评价社团划分质量的指标函数,通常Q越大对应的社团结构越明显.目前公认的是,若社区网络的划分Q>0.3, 则该网络存在明显的社团结构.该方法是最流行的社区分类质量的度量方法.不过,基于模块化函数的方法也存在缺陷[8]:① 网络具有大Q值并非网络具有明显社团结构的充分条件,随机网络的划分也可能具有大Q值; ② Q存在严重的分辨率极限问题[9],即优化Q所能检测出的最小社团依赖于与网络总边数有关的某尺度,小于该尺度的社团即使与外界只有一条边的全连接子图,此方法也不能将之检出.
在基于概率模型的方法中,已有多种概率模型用于社区检测,随机块模型便是其中之一.该模型假定可将顶点划分到两个未知社区,且两个顶点之间边(即链接)的概率分布只依赖于它们所归属的社区[10].该方法的理论依据是:当顶点数量趋于无穷大,可用概率1准确发现社区结构.改进的随机块模型包括混合成员随机块模型[11]和Bayesian 随机块模型[12],前者是运用具有层级结构概率假设的Bayesian模型,以获得潜在社区、节点间典型交互模式以及节点隶属于某个社区的程度; 后者是基于Bayesian法对模型进行选择,该方法不仅克服了分辨率极限问题,还可准确获得社区数量,缺点是需即时对候选方法择优,实现复杂度高.其他基于概率模型的方法还包括通过软图聚类识别最佳社区,如将数据依概率“软”分配到相应社区,自然衍生聚类层次方法[13]; 利用期望最大化算法(expectation-maximization,EM)提出基于最小描述长度的准则用以确定社区的最优个数[14]; 在无先验知识的情况下,通过建立社区结构的混合概率模型以概率方法对社区结构进行探索,以求得期望最大的社区结构[15]等.
上述方法假设网络间节点的链接是无向或视为无向的,但仍有一些基于有向链接的社区发现方法,如PageRank[16]、HITS(hyperlink-induced topic search)[17]和PHITS(probabilistical hyperlink-induced topic search)[18].PageRank算法基于随机游走模型为每个网页(节点)分配一个分值; HITS算法从链接结构中为每个网页获取一个权威中心得分; PHITS算法通过一种概率潜在语义分析(probabilistic latent semantic analysis,PLSA)[19]的概率模型拓展HITS算法来进行社区检测.另外,LDA(latent Dirichlet allocation)链接模型通过为每个社区假定一个链接分布的方法LDA来进行链接分析[20-21].文献[22]拓展混合隶属度概率块(mixed membership stochastic block,MMSB)模型[23]来分析有向链接检测社区.
与人们在现实世界中形成的链接不同,社交网络用户自由度更大,他们可用不同方式和不同理由与更多用户建立链接.由于链接信息成本低,虚假和随意链接在社交网络中普遍存在,这些高度不平衡的相互作用,仅靠单一类型的相互作用或实体角色,难以获得真实的网络社区结构.例如,一些在线用户拥有几千个在线好友,实际上这不太可能.Flickr中甚至有用户拥有超过19 000个好友,对于这类用户,只利用链接来挖掘其参与的社区会很模糊.在社区发现中只考虑链接关系,还是局限于复杂网络的社团检测思想,把社会网络看做了同质网络.实际上,社会网络本身是一个异质网络,它含有异质的交互方式或节点.以下分别从异质多维和异质多模两个角度评述近年提出的异质社会网络社区发现研究工作.
在社会网络中,总是存在多种交互或关系,如果每种交互可看成一维关系网络,多种交互就形成多维社会网络.实际上,在异质多维网络中,每种关系都可构成一个关系网络, 此网络也称为多关系网络.由于用户间的交互可反映其亲密程度,因此对社会网络中群的发现非常重要.近年,在异质多维社会网络社区发现方面,提出了一些利用多种社交媒体关系融合的社区发现方法.
依照对多关系网络的研究思路,目前异质多维网络社区发现可分为5种方式:①多关系融合.已经证明对单维网络来说具有代表性的社区检测方法可用统一的方式表示,在此基础上提出交互类型整合策略,使社区发现从一维网络扩大到多维网络[24]; ②协同聚类.如基于协同聚类框架融合用户的标注行为[25],表明利用标注信息(tag information)可获得更精准的社团结构,或采用最小描述长度和张量分析构成的多图聚类技术[26]以利用多种类型的链接关系进行社区发现; ③元图分解.通过元图分解方法融合不同的相互交流信息可提取更准确的社区结构[27]; ④线性组合.通过对关系强度预测来对异质性的相互作用信息进行明确整合达到社区检测的目标.如文献[28]分析了异质多维社会网络中的不同关系,认为不同关系在不同环境中的重要性各异,提出一种学习社区成员关系的优化线性组合方法,以更好地满足用户的期望; ⑤概率模型.其基本思想认为社会网络中的不同相互作用可看作同一顶点集合的不同网络视图,提出潜在空间联合模型(latent space joint model,LSJM)[29],在该模型框架下每个网络视图的任意两个顶点之间的连接概率由某个独特的潜在变量决定,从而实现对多重网络视图已知信息的融合.
在基于多维交互关系的社区发现中,仅考虑了社会网络中多种异质的相互作用,如共享网络中的用户朋友关系和用户标注关系[25],科学合作网[26]中的合作者关系、朋友关系和引用关系等,但整个网络中的研究对象是同一种类型的,即只考虑一种实体.在真实社会网络中,实体或对象通常是异质的,如在论坛社会网络中包含的网络对象有论坛用户、论坛主题和主题回复等,这些异质对象会带来丰富的内容信息和新的结构,使联合内容的社区发现成为处理异质网络社区模糊不确定的新途径,由此掀起异质多模网络的社区发现研究.
对于异质多模社区发现,有学者针对Web 1.0时代的互联网提出一些社团检测方法,其具有代表性的方法诸如将PLSA与PHITS相结合的PHITS-PLSA算法[30],用于文档聚类的LDA-链接-字模型[20],整合链接和内容信息的概率模型[31],融合LDA和混合隶属度随机块模型的拓展LDA-链接-字模型[22]等.这些方法存在的一个主要问题是,它们应用生成模型来进行内容分析,但容易受到不相关关键字的影响.除概率模型外,还有其他用于融合链接和内容信息[32]的方法,如用于谱聚类的矩阵分解[33]和信息融合[34].
不同于Web 1.0时代的多模网络,社会网络属Web 2.0时代产物,用户而非网页成为异质多模网络的主体,直接应用Web 1.0时代的异质多模网络社区分析方法往往无效或无实际意义.用户的随意性、主观性使网络更复杂和嘈杂,面向Web 2.0时代的异质多模网络社区分析挑战性更大.
2010年,Sun等[35]提出并倡导新的基于异质多模社会网络的研究.2012年中国计算机学会的《社会媒体》也指出:目前对社会媒体信息属性和社会属性两方面融合性研究不完善,已成为社会媒体研究中揭示本质规律的瓶颈,制约着社会媒体分析技术的实际应用.学界对异质社会网络中多模社区的研究仍处于初期探索阶段.如2008年美国亚利桑那州立大学的DMML(数据挖掘与机器学习)实验室利用时间信息,分析多模网络并提出基于谱分析框架(spectral framework)的异质多模社区发现方法[36].2012年,该实验室进一步将异质实体均看做网络图中的节点,将异质实体之间的关系与同质实体之间的关系均看作图中的边[37],提出新的异质多模网络社区检测方法.此方法实际上忽略角色实体间的差异性,简单地将不同的角色实体同等看待,仍将异质网络转换成同质网络.
中国学者在异质多模社会网络分析方面也进行了积极尝试,提出基于不同视角的解决思路.2012年,Yang等[38]通过探索跨异质多模网络社区的网络模式,挖掘网络社区竞争关系,发现具有竞争关系的网络社区表现出互补的比赛模式.他们提出局部因子图模型,通过定义一个潜在的主题来弥合两个网络社区并学习一个半监督学习模型来对不同实体(企业及其产品)之间的关系进行分类.Tang等[5]认为,社会媒体链接信息可揭示各种混杂的关系强度,但存在大量噪声,而社会媒体中不同的数据源却可提供互补信息.为此,他们提出一种联合优化框架融合社会媒体中的多种数据源,以提高社区检测能力,这在一定程度上揭示了多源异质数据类型融合的必要性及面临的挑战.
此外,基于位置的社会网络的无明确社区结构、线上线下社会交互关系共存、用户或场地属性共存的问题,可采用以边为中心的合作聚类框架来发现重叠的社区,该框架的基本思想是从不同的社会角度将志趣相投的用户分为一组[39].Comar等[40]提出一个多任务学习框架来处理混合网络数据问题.多任务学习通过引入一个联合目标函数来优化目标函数,以使一种数据源(如链接和顶点属性等构成的网络)的分类结果与另一种数据源构成的网络的社区检测结果一致.在此基础上,将不同源构成的网络聚类和分类之间的对应关系作为先验信息,改进并拓展了算法.例如,将原社区发现问题转化为多目标优化问题,探索优化结合多种数据源构成的知识以提高谱聚类划分能力,通过Pareto优化寻找最优解[41].
实际上,无论是基于多维交互关系的异质社会网络社区发现,还是链接和内容的异质多模社会网络社区发现,都只关注了一种异质因素,在社会网络分析中同时考虑异质对象实体及其异质的交互关系极具挑战性.Greene等[42]指出,在社会网络中同一用户集之间不仅有不同的链接关系,也有与用户相关的属性或内容信息,用户的多种类型数据使社区发现问题更复杂.本质上,异质社会网络即一个具有多源实体角色和多关系的网络,社区发现可看作如何融合多源数据及其多关系在图上的分类或聚类.本课题组在谱图分析、融合监督信息和无标签数据的半监督学习及其高维数据分类、聚类等机器学习方面进行了研究[43-44],提出在协同训练框架下,通过构建半监督模块最大化谱分析方法和贝叶斯分类器研究异质多模社会网络中的社区发现.
实验以典型的异质多模社会网络(博客平台)为例.如前所述,文献[24]利用谱分析设计了4种交互类型整合策略处理社会网络中的异质关系以进行社区发现.依此思路,本课题组将其用于处理异质多模实体,设计相应的融合方式,包括将博文信息融合到反映链接关系的矩阵中(integA),将博文信息融合在反映链接关系矩阵的变换矩阵中(integM),将博文信息融合在变换矩阵的结构特征矩阵中(integS)以及将博文信息融合在基于链接的社区划分结果中(integH),用以改变模块最大化方法中网络链接强度,进行社区发现.
为评价社区划分的真实性和准确性,采用真实的社会网络数据集BlogCatalog[5]进行实验仿真.BlogCatalog是一个博客平台,用户可在预设的类别标签下记录自己的博文,这些帖子都是经过停用词的移除等相关预处理,并通过TFIDF(term frequency and inverse document frequency)去除不相关的特征词以得到博文内容属性信息. 该数据集共有9 026个帖子,13 450个特征属性,及2 242个用户.由于数据量较大,本研究只选取其中用户数量最多的前两个社区及其中所属的2 507个用户,保留所选用户使用频率较高的前1 544个特征属性,用户之间共有60 404条链接.
采用归一化互信息(normalized mutual information,NMI)来度量社区划分结果.实验结果如图3,横坐标为使用监督信息(博文信息)的比例,纵坐标为NMI值.从图3可见,融合了博文信息的NMI值明显高于未融合的NMI值,且随监督信息的增加,NMI值显著提高,表明博文信息有助于提高异质网络社区划分质量,改善社区划分结构.
图3 四种融合方法下的异质多模网络社区检测对比
Fig.3 Community detection in heterogeneous multi-mode network with four integration methods
实际上,在异质多模网络中,不同角色实体提供不同信息以反映同一事物的不同侧面,相互关联又互有差异.本课题组提出一种基于协同训练框架融合用户博文信息与用户链接信息的异质社会网络社区发现方法.该方法将用户博文信息和用户链接信息作为描述网络社区结构数据的两个不同视图,分别利用朴素贝叶斯分类器和模块最大化算法对两个视图划分.由于用户博文信息视图数据维度很高可能导致“小样本”问题,因此引入Fisher_score特征选择算法减小博文内容信息特征维数.在划分用户链接信息视图时,鉴于模块性最大化算法本质上是无监督聚类,而协同训练需半监督分类器,因此可利用用户博文信息属性修改用户链接关系构成的邻接图.在协同训练中,分别利用置信度和节点归属社区的中心性作为可信度,以相互标记.对此方法在Blogcatalog数据集上进行实验仿真,并与单纯利用用户特征属性的基于朴素贝叶斯分类器的社区检测算法、只利用链接关系属性的最大模块化函数社区检测算法,进行检测社区准确率对比.实验选择特征个数分别为50、100、150、200和m. 其中, m=1 544为数据集中样本特征总数.实验结果是20次不同监督信息的平均值.图4为基于最大模块化(只利用链接)和基于协同训练的社区划分算法社区检测准确率.图5为基于朴素贝叶斯(只利用用户特征)和基于协同训练的社区划分算法利用不同特征数量时(如50F表示利用50个特征并依此类推)社区检测准确率.
图4 基于协同训练和基于最大模块化的社区划分准确率比较
Fig.4 Accuracy comparison of community detection with co-training and modularity maximization
图5 基于协同训练和基于朴素贝叶斯的社区划分准确率比较
Fig.5 Accuracy comparison of community detection with co-training and Naive Bayesian
结果表明,相比仅单纯利用单一数据资源的社区检测算法,基于协同训练的社区检测准确率远高于基于模块最大化和优于基于朴素贝叶斯的社区检测方法,说明同时利用异质多模网络中的用户特征属性和链接关系属性的协同训练算法可获得更有效的社区划分结果.随着选取特征数量的增加,准确性有所提升,但增幅不大,有效特征数量可在保持准确性稳定的前提下远少于原始特征数量,降低计算复杂度.此外,随着监督信息的增加,社区检测准确性都显著提升.需说明的是,虽然只运用最经典的协同训练方法c-training就取得了不错的划分效果,表明协同训练可能确实是异质网络分析的有效手段,并为寻求异质多模网络社区结构检测算法提供了新途径,但其模型构建、算法分析、局限性及改进方向都需深入且全面探索.
本文分析近年异质多维(或多模)社会网络中的社区发现,指出尽管目前对异质多模网络的研究尚处起步阶段,异质网络社区发现应是社会网络研究的重点之一,是一个非常前沿且具有生命力的研究方向.未来影响社会网络分析发展的关键是实验数据的获取.如何与已有互联网公司合作,或建立统一规范的实验数据平台,都极具挑战性.企业、高校和科研院所的多方合作将是在社会网络分析领域取得较大技术突破的有效途径.
深圳大学学报理工版
JOURNAL OF SHENZHEN UNIVERSITY SCIENCE AND ENGINEERING
(1984年创刊 双月刊)
主 管 深圳大学
主 办 深圳大学
编辑出版 深圳大学学报理工版编辑部
主 编 阮双琛
国内发行 深圳市邮电局
国外发行 中国国际图书贸易集团有限公司(北京399信箱)
地 址 北京东黄城根北街16号
邮 编 100717
电 话 0755-26732266
0755-26538306
Email journal@szu.edu.cn
标准刊号 ISSN 1000-2618
CN 44-1401/N