自动化学报
ACTAAUTOMATICASINICA
Vol.41,No.10October,2015
基于话题概率模型的语义社区发现方法研究
辛宇1,2
谢志强1
杨静2
摘要语义社会网络(Semanticsocialnetwork,SSN)是一种由信息节点及社会关系构成的复杂网络,也是语义信息时代社会网络技术研究的热点,相较于传统社会网络更具实用价值.其研究内容包含了社会网络的语义分析及社会关系分析,因此,语义社会网络的社区挖掘建模具有一定的复杂性.在语义社会网络的社区挖掘研究方面,本文分析了当前基于话题概率模型的语义社区发现方法,并在综述其内容的同时总结了各方法的优缺点,为后续研究提供了理论基础.在语义社会网络社区挖掘结果的评判方面,本文归纳了相关的评价模型,并通过实验分析对比了各模型对拓扑相关性和语义相关性的倾向性.关键词引用格式DOI
语义社会网络,话题概率模型,社区挖掘,社区结构
辛宇,谢志强,杨静.基于话题概率模型的语义社区发现方法研究.自动化学报,2015,41(10):1693−171010.16383/j.aas.2015.c150136
SemanticCommunityDetectionResearchBasedonTopicProbabilityModels
XINYu1,2
XIEZhi-Qiang1
YANGJing2
AbstractSemanticsocialnetwork(SSN)isacomplexnetworkconsistingoftextualnodeinformationandsocialrela-tionships,andhasmorevaluableapplicationsthanthetraditionalsocialnetworkwhichfocusesonsocialnetworkanalysis(SNA)withsemanticinformation.Asitcontainsthesemanticanalysisandsocialrelationshipanalysis,thereissomecomplexityforthemodelinginminingtheSNAcommunity.IntheSNAcommunityminingaspect,theadvantagesanddisadvantagesofeachmethodbasedontopicprobabilitymodelsaresummarizedtoprovideatheoreticalbasisforthefurtherresearch.IntheevaluationaspectofSNAcommunitymining,relevantevaluationmodelsaresummarized.Thetendencyofeachevaluationmodeltowardtopologicalandsemanticrelevanceiscomparedbyexperimentalanalysis.Keywords
Semanticsocialnetwork(SSN),topicprobabilitymodel,communitymining,communitystructure
CitationXinYu,XieZhi-Qiang,YangJing.Semanticcommunitydetectionresearchbasedontopicprobabilitymodels.ActaAutomaticaSinica,2015,41(10):1693−1710
现实世界中人与人的交互活动是人类社会活动的基础.在社会学研究中将社会关系和社会个体所构成的网络称为社会网络[1].随着网络技术及通讯技术的发展,人与人交互活动的途径呈数字化趋势,对社会网络的研究也从传统社会学研究转变为数据挖掘研究,从社会行为及社会关系研究转
录用日期2015-06-24
ManuscriptreceivedMarch31,2015;acceptedJune24,2015国家自然科学基金(61370083,61370086),国家教育部博士点基金(20122304110012),黑龙江省自然科学基金(F201101),黑龙江省教育厅科技项目(12531105),黑龙江省博士后科研启动项目(LBH-Q13092)资助
SupportedbyNationalNaturalScienceFoundationofChina(61370083,61370086),NationalResearchFoundationfortheDoctoralProgramofHigherEducationofChina(20122304110012),NaturalScienceFoundationofHeilongjiangProvince(F201101),EducationalCommissionofHeilongjiangProvince(12531105),PostdoctoralScienceFoundationofHei-longjiangProvince(LBH-Q13092)本文责任编委赵铁军收稿日期2015-03-31
RecommendedbyAssociateEditorZHAOTie-Jun
1.哈尔滨理工大学计算机科学与技术学院哈尔滨1500802.哈尔滨工程大学计算机科学与技术学院哈尔滨150001
1.CollegeofComputerScienceandTechnology,HarbinUni-versityofScienceandTechnology,Harbin1500802.CollegeofComputerScienceandTechnology,HarbinEngineeringUni-versity,Harbin150001
变为网络数理统计及量化分析研究[2].社会网络的研究方法也从以链接关系为主体,发展到了以语义链接关系为主体,从而产生了语义社会网络(Se-manticsocialnetwork,SSN)的概念.文献[3]利用FOAF(Friendofafriendproject)模型,对语义社会网络进行了如下定义:语义社会网络是在传统社会关系基础上,通过对网络中的“知识”进行表达、关联及推理,建立社会网络的语义相关性模型,从而实现社会网络的语义化.随着早期语义社会网络的资源标注模型(如RDF(Resourcede-scriptionframework)[4]、RDFS(Resourcedescrip-tionframeworkschema)[5]、OWL(Webontologylanguage)[6]、SPARQL(SimpleprotocolandRDFquerylanguage)[7])的出现,对语义社会网络中社区发现的研究成为语义社会网络研究的重要方向.由此使得社区发现研究从传统非语义社区发现过渡到了语义社区发现.非语义社区即为传统关系社区,其中的“关系”是所有交互活动的统一表达,不对具体的关系内容进行区分;语义社区是在传统关系社区(非语义社区)中加入了关系内容的约束,更强调社区的语义相关性.图1表达了传统社区发现方法与
1694自动化学报41卷
语义社区发现方法的区别.
图1中传统非语义社区发现与语义社区发现的结果存在一定偏差,且以语义分析为主导的社区发现结果较传统社区发现结果,具有更合理的内部一致性,其有效性更高.
非语义社区发现研究即为仅以拓扑关系为研究对象的传统社区发现研究,其研究内容为社会网络的拓扑关系,并从中挖掘出内部关系紧密的社区结构.非语义社区发现的研究过程经历了硬社区划分和重叠社区划分阶段.其中硬社区划分即所划分的社区不包含相交的用户节点,其代表算法有:GN(GirvanNewman)[1]、FN(FastNewman)[8]、FUA
[9]
(Fastunfoldingalgorithm)等.由于实现社会生活中,社会个体的生活领域并不单一化,某一社会个体可同时具备多重社会身份,从而引发了硬社区划分结果对现实模拟具有偏差性的讨论.为此,Palla等[10]提出了重叠社区的概念,即社会网络中存在某些用户节点隶属于不同社区.至此,社区发现研究进入了重叠社区发现的时代,各类经典算法孕育而生,如EAGLE(Agglomerativehierarchicalclusteringbasedonmaximalclique)[11]、LFM(Lancichinetti-[12]
Fortunatomethod)、RAK(RaghavanAlbertKumara)[13]等.
语义社区发现以拓扑关系和语义内容作为研究对象,即在传统社区发现方法中加入了语义分析,其语义关系包含了工作、生活、娱乐和兴趣等多方面内容,因此为使社区发现结果更加合理化,需要在社区挖掘过程中加入对社会个体的交流内容和行为言论的分析(即语义分析).目前,语义社区发现方法包含本体–社区挖掘[14−15]、多元属性建模[16]及话题概率关系建模等.在基于话题概率模型的社区挖掘研究方面,其研究目标在于借用文本分析模型实现对语义社会网络中社会个体的话题相似性(即语义相似性)挖掘,并建立社会个体或社会团体的相似性
模型.其主要的研究工作在于以各类话题发现模型(如LDA(Latentdirichletallocation)[17]、PLSA(Probabilisticlatentsemanticanalysis)[18]、HPC(Hierarchicalpoissonconvolution)[19]等)为基础,融合社会网络的拓扑关系特性,建立话题–社会个体关系模型,将话题关系相近且拓扑相关性强的社会个体聚合为社区.
本文对以话题概率关系模型为基础的语义社区发现算法进行了归纳,在论述各方法的实现过程及理论意义的同时,对其存在的缺点及改进方法进行了总结,并利用图示表达法直观地阐述了各算法的内在关联.另外,本文对传统社区发现算法的评价指标及度量方法进行了改进,使其满足语义社区评判的要求,并在实验中对比了各方法的有效性.
1主要研究方法
语义社会网络是语义信息与网络拓扑结构相结合的一类复杂系统,且文本分析与社会网络结构均具有统计学特性(如文本具有潜在话题分布[17],社会网络用户节点具有幂率分布[20]),因此,基于概率模型的语义社区建模方法是语义社区发现的主要方法.Ding[21]对比了面向拓扑与话题分析的社区发现算法的区别,在利用AT(Author-topic)模型[22]对话题进行抽取和分析后,阐明了利用话题分析发现的社区比利用拓扑分析发现的社区具有更紧密的内在关联性.继AT模型后,学术界对语义社区挖掘的研究大量利用了统计学模型,通过在文本、潜在话题、链接和社区间建立贝叶斯关联模型,估计潜在变量的取值.目前面向社区发现的话题概率模型(如AT模型、ART模型[23−24]及CART模型[25]等)大多以LDA的建模方法为基础,本文根据各类算法的LDA建模特征,将基于概率模型的语义社区挖掘方法分为以下4类:节点–话题概率模型、D2D(Documenttodocument)–话题概率模型,链接–
图1
Fig.1
语义社区发现与传统非语义社区发现对比
Thecomparisonofsamenticcommunitydetectionwithtraditionalnon-semanticcommunitydetection
10期辛宇等:基于话题概率模型的语义社区发现方法研究1695
话题概率模型和社区–话题概率模型,以下为4类模型的主要研究内容及区别.
1)节点–话题概率模型,此类模型以用户的言论、情感及兴趣趋向作为语义信息,并将语义相似性高的一类用户作为基本的社区结构.此类模型不考虑用户的社会关系层.
2)D2D网络–话题概率模型,此类模型以文本–文本网络作为社会网络,将文本内容作为语义信息,将文本内容相似的文本划分为同一社区.此类模型是简化的链接–话题概率模型.
3)链接–话题概率模型,此类模型假设每个用户是一个文本集合,即每个用户具有多重语义,通过对用户–用户的链接关系与语义关系进行综合分析,得到语义相似度高且结构紧密的社区.
4)社区–话题概率模型,此类模型假设每个用户的语义趋向受其所在社区的影响,在进行语义分析时,将用户的拓扑环境作为调控语义信息分布的因素.此类模型所得到的社区结构的语义相似度最高,但复杂度较高且结果的波动性较大.
为论述上述模型的区别及联系,本文利用“盘图”对上述4类模型的贝叶斯模型框架进行表达,其关系如图2所示.图2中各符号表示如下:
G表示全局网络,Gi表示网络中的节点i;ad表示被取样点Gd的相邻节点集合;
Communityd表示被取样点Gd所隶属的社区
集合;
x表示集合ad中抽取的一个元素;
N表示语义社会网络中的关键字个数,Ni表示节点Gi的关键字个数;
D表示语义社会网络中语料信息个数;
w表示关键字的集合,wi为集合w中第i个关键字所对应的编号;
z表示与关键字的集合w对应的话题编号集合,zi表示wi所隶属的话题编号;
T表示话题个数;θ表示话题分布概率;Φ表示关键字的分布;
α表示各节点的话题分布先验参数;
β表示某一话题内部,关键字分布的先验参数;γ表示社区分布的先验参数.
从图2的对比可知:节点–话题概率模型即在LDA模型的基础上,考虑了节点的分布状态;D2D–话题概率模型考虑了节点的关联性;链接–话题概率模型考虑了节点的关联性及节点的语义多重性;社区–话题概率模型考虑了节点的社区属性.利用话题概率模型进行语义社区挖掘的相关研究,大多以上述4种模型为基础,通过建立新的求解思路及关联规则,不断充实、完善及扩展各模型的应用需求.本文分别对上述4种模型的相关研究进行了总结,并归纳了各算法的优缺点及可改进之处.
图2
Fig.2
各类话题概率模型的贝叶斯模型框架
TheframeworkofBayesmodelsforvarioustopicprobabilitymodels
1696自动化学报41卷
1.1节点–话题概率模型
用户节点是语义社会网络中话题的发起者,由于用户节点的角色具有多面性,因此用户节点可看作话题的集合,且其包含的话题不唯一.语义社会网络中用户节点的这一特性符合了话题概率模型的基本假设,对此,2004年,Steyvers等[22]提出了AT模型.该模型首次将LDA模型引入社会网络中,实现了用户节点的潜在话题提取,并开创了对用户节点的话题分布进行LDA建模的方法.由于AT模型仅为LDA模型的套用,缺少对社会网络链接关系及社区结构的考虑,为此许多研究者借由AT模型的原理和模型基础,提出了各类节点–概率模型.图3为面向社区发现的节点–话题概率建模方法的主要模型,本文根据各模型的特点对其进行了分类.
图3各类节点–话题概率模型关系图Fig.3Therelationshipofvariousnode-topic
probabilitymodels
2006年,Airoldi等[26]提出了MMSB(Mixedmembershipstochasticblock)模型.该模型首先假设每个用户节点可隶属多个社区,藉此将社区作为LDA中的“topic”,将用户节点作为LDA中的“document”;其次,预先设定若干社区作为初始社区,具有多个社区属性的用户节点作为重叠节点;最后,在对LDA模型进行求解时,利用网络的拓扑关系对同一社区中的用户节点进行取样,从而优化所划分的社区结构.其优点在于:以发现潜在话题的形式发现潜在社区,符合了Barab´asi等[20]对社会网络中用户节点和社区之间满足一定分布关系的假设.其缺点在于:初始社区结构的设定对MMSB的结果影响很大,因此,初始社区结构的设定优化问题是MMSB需要面对的挑战.
2006年,Wang等[27]假设“随着时间累加,
LDA模型中话题先验参数的变化服从Beta分布”,从而在LDA模型中加入了话题先验参数层,建立了TOT(Topicsovertime)模型,以实现动态话题变化的模拟.在进行求解时,对一定时间段内的语义信息进行Gibbs取样[28],并将求得的参数结果作为下一次取样的初始值.其优点在于:对话题的建模结果较好,其建模及求解过程满足Gibbs方法的求解特征.其缺点在于:忽略了网络的关系特性,即话题的动态改变没有考虑人与人的交流过程及话题的扩散特性.
2007年,Wang等[29]在二元LDA模型BTM(Bigramtopicmodel)[30]的基础上加入了话题与关键字的关联关系,提出了TNG(TopicalN-gram)模型.该模型构建了关键字的情感倾向性与关键字间的关联,并直接影响了话题的分类结果,可直接应用于情感分类中.其优点在于:由于TNG包含了BTM的关键字关联假设,使得TNG在面向语义社会网络研究时,可依据用户节点的链接关系追踪关键字的扩散对社区的影响.其缺点在于:TNG的模型结构过于复杂,其中隐含变量过多,导致Gibbs取样的结果不精确.
2008年,Mei等[31]利用谐波正则化的建模方法,将LDA或PLSA的Likelihood值与社区划分结果的谱分解相混合,提出了TMN(Topicmod-elingwithnetwork)模型也称NetPLSA.TMN以LDA或PLSA的分析结果作为网络中链接的权重,建立了语义社会网络的有权邻接矩阵,并将该有权邻接矩阵作为谱分解的输入矩阵.其优点在于:充分利用了谱分解及谱聚类在社区发现中的有效性[32−33].TMN构建目标函数时采用了谐波正则化函数,对考虑语义与结构双向优化的社区发现问题具有一定的启示作用.其缺点在于:TMN直接套用了LDA或PLSA的分析结果,因而在进行语义建模时缺少对网络拓扑结构的考虑.
2009年,Lin等[34]在LDA模型基础上,为每个话题增加了一个情感取向先验参数,提出了JST(Jointsentimenttopic)模型.JST将LDA的话题发现结果附加了情感特征,从而实现了情感主题的挖掘.其优点在于:利用文本的情感属性细化了话题的分类结果,增加了各话题的差异性,有利于精确定位用户节点的社会属性.其缺点在于:JST需要预先量化各关键字的情感值,由于大量关键字无法指定确切的情感指标,因此JST的实现过程依赖于人为经验.
2009年,Yang等[35]提出了PCL(Popularity-basedconditionallinkmodel)模型.该模型将语义社区建模分为语义建模及拓扑关系建模.其中在语义建模方面采用了DiscLDA话题提取模型[36],在
10期辛宇等:基于话题概率模型的语义社区发现方法研究1697
拓扑关系建模方面利用了社会网络的用户节点与链接的分布关系,建立了Conditionallinkmodel,在进行社区划分时以DiscLDA和Conditionallinkmodel的混合函数作为目标函数进行EM(Expec-tationmaximization)迭代求值.其优点在于:其目标函数的混合形式可直接套用各类语义分析模型及拓扑分析模型,具有较好的可扩展性.其缺点在于:EM算法的复杂度较高,对此,在进行实际应用时需要考虑换用Gibbs取样算法.
2010年,Li等[37]在利用TTR-LDA-Community模型[38]发现社区基础上,利用ACT分析模型[39−40]分析了以时间片为单位的话题变化,并得出了以下结论:1)同一社区内话题的变化具有趋同性;2)话题在变化时,其自身的子话题会扩散到与其相邻的用户节点或社区中.文章在进行语义社区评价时改进了一般社会网络的NCP评价指标[41],为其加入了语义相似度因子,使之可以度量语义社区结构.其优点在于:所得出的结论可作为语义社会网络话题传播及动态演变的实现基础,其实验方法的说明及对ACT模型的运用十分恰当,是对ACT模型的扩展研究.其缺点在于:对话题的动态跟踪过程中,隐含假设了社区结构无变化,因此,其本质上是对静态社区结构的语义分析.
2012年,R´ıos等[42]提出了SLTA(Speaker-listenertopicpropagationalgorithm)算法.SLTA在LDA分析后,对每一个用户节点选择一个权重最高的话题,以此作为用户节点的标签,再套用非语义社区发现的SLPA算法[43−44]实现语义社区划分.其优点在于:将语义分析后的标签作为话题传播中的标签,强化了标签的语义相关性,为SLPA的模糊标签研究提供了方法.其缺点在于:语义社会网络中,话题间具有一定的相关性,且每个用户需要用多个标签描述,只选择一个话题进行传播存在语义相关性偏差的弊端.
2013年,Jang等[45]以舆论领袖的影响力及影响范围决定了社区的大小及紧密性为指导思想,首先利用LDA模型将语义社会网络中的文本信息进行统一挖掘,并将其挖掘结果作为社会个体的得分.其次通过对得分及网络相关性的综合评价,确定舆论领袖及其引领的话题社区.其优点在于:以“舆论领袖”作为社区核心的假设符合社区的结构特性.其缺点在于:进行全局文本信息的LDA挖掘时,没有考虑局部的文本差异性及网络拓扑关联性,使得零散的社会个体享有与核心个体同样的“话语权”,容易产生对全局文本挖掘结果的误导.
1.2D2D-话题概率模型
D2D网络由早期引文网络发展而来,其研究对
象是以Document作为用户节点的关系网络.随着文本挖掘技术的发展,其研究内容已从传统的拓扑关系挖掘发展到文本语义–拓扑关系综合挖掘.2004年,Erosheva等[46]将D2D网络看作一类特殊的语料库,并将LDA模型直接应用于D2D网络,从中挖掘相关话题.Erosheva等的研究开创了利用概率模型挖掘D2D网络的先河.此后,各类以D2D网络为研究对象的算法层出不穷,其研究方向逐步从话题挖掘过渡到了社区挖掘.图4为当前面向社区发现的D2D–话题概率建模方面的主要模型,本文根据各模型的特点对其进行了分类.
图4各类D2D–话题概率模型关系图Fig.4TherelationshipofvariousD2D-topic
probabilitymodels
2007年,Dietz等[47]提出了CIM(Citationin-fluencemodel)模型.该模型以LDA模型为基础对引文网络(有向D2D网络)的有向链接进行文本分析,因此CIM属于层次LDA模型,其取样过程以有向链接作为基本单元.CIM在引用与被引用的Document之间创新建立了取样平衡参数,藉此修正了层次LDA存在的引用Document对被引用Document的完全包含假设.其优点在于:对有向链接进行取样的方式有利于CIM面向连接预测应用,所建立的平衡参数为利用LDA模型处理有向语义社会网络社区挖掘问题提供了参考.其缺点在于:平衡参数需要人为预先设定.
2009年,Chang等[48]在LDA模型的基础上建立了D2D网络的话题发现模型RTM(Relationaltopicmodel).RTM将两个有关联的Document的话题分布进行关联分析,从而将Document的相似性引入LDA模型.其优点在于:RTM在改进LDA的同时既保持了LDA文本分析的有效性,又在文本分析的同时加入了拓扑关联性,为后续的语义社区挖掘研究开拓了新的研究方法,许多语义社区研究方法藉此而生.其缺点在于:RTM仅以直接链接
1698自动化学报41卷
关系作为网络的关联,忽略了网络的区域性及规模性.
2009年,Sun等[49]提出了用于D2D网络社区发现的iTopicModel模型.该模型利用MRF(Markovrandomfield)方法[50]将LDA模型中的话题先验参数进行关联,改进了MRF方法无法处理有权网络的问题,并提出了可用于度量语义社区发现结果的NMI模型.其优点在于:在MRF中加入了社区因素,使其具有社区发现功能.其缺点在于:其建模方式是在原有的三层LDA模型中增加了话题先验参数分布层,且话题的先验参数分布不够明确,使得其实现过程复杂化,精确度较差.
2009年,Liu等[51]提出了Topic-LinkLDA模型.该模型为简化ART模型的取样频数,将Author所共享的所有Document综合为一个Document,从而将语义社会网络转化为D2D(Document-to-document)网络,并在假设的社区内对Author进行取样以优化社区结构.其优点在于:采用简化的D2D形式,适合处理大规模语义社会网络数据.其缺点在于:需要预先设定初始社区结构及社区个数.
2009年,LHuillier等[52]首先在D2D网络中建立了Topic-document关联矩阵SWM(Semanticweightsmatrix),以此作为LDA模型的输入;其次将LDA模型所得出的话题分布参数作为阈值,据此为话题相似度接近的用户节点建立一个虚拟链接,从而形成虚拟网络VcoI(Virtualcommunitiesofinterests).重新整理后的有权网络结构可作为输入,套用非语义社区发现算法即可实现语义社区划分.其优点在于:采用了话题相似度进行虚拟链接补全的形式,适用于语义结构洞分析及动态演化分析.其缺点在于:对虚拟链接的考虑仅以话题相似度为出发点,缺少对网络结构的考虑.
2011年,Zheng等[53]指出:Net-PLSA等模型所采用的D2D网络,将用户节点的所有Document拼凑为一个Document而忽略了Document的分布特性.针对这一问题,提出了ToP(Topicsonpar-ticipations)算法.ToP在CIM[47]基础上,将社区发现模型分成了HierarchicalDirichletprocess和Documentmodeling阶段,在进行社区发现的同时考虑了Document的分布性.其优点在于:实现过程中,通过对社区个数的增量训练避免了LDA模型需要预先设定社区个数的问题.其缺点在于:增量式训练过程的运算代价较大.
2013年,Chahal等[54]利用词汇的相似性匹配关系建立了Documents相似性度量方法,即将Documents看作词汇的集合,通过词汇相似性匹配关系的累加关系得出Documents的相似性匹配关
系;其次,以Document相似性匹配关系为输入,通过对Documents的邻接关系聚类实现了D2D网络的社区划分.其优点在于:根据Documents相似性关系,在LDA模型中加入Documents相关性参数,提高了LDA挖掘模型的分类精度.其缺点在于:Documents的相似性分类过程中需要人工分组,由于人为经验而产生的偏差直接影响了分类结果.
1.3链接–话题概率模型
1999年,Kleinberg[55]提出网络通讯以话题作为信息单元以链接作为途径.其理论依据在于:由于用户节点具有多重社会角色,使用户节点所包含的话题复杂化,而用户节点大多使用同一种身份与另一用户节点进行交流,因此,同一链接所包含的话题内容相似.Kleinberg所得出的结论是面向语义链接建模的理论基础,后续的研究者将用户节点的语义信息看作其链接所包含的话题信息的集合,从而开拓了以链接为研究对象的语义社区挖掘方法.本节综述了此类方法与概率模型相结合的相关研究.图5为当前面向社区发现的链接–话题概率建模方面的主要模型,本文根据各模型的特点对其进行了分类.
图5各类链接–话题概率模型关系图Fig.5Therelationshipofvariouslink-topic
probabilitymodels
2005年,McCallum等[23−24]提出了ART(Au-thorrecipienttopic)模型.该模型在AT模型的基础上加入了邻居节点的取样过程.其实现过程为:对
10期辛宇等:基于话题概率模型的语义社区发现方法研究1699
某一用户节点进行文本取样时,随机选择该取样对象的一个邻居,将该用户节点与其邻居节点的取样结果作为该用户节点的取样结果.ART模型的取样过程考虑了用户节点对其周围节点的语义影响.其优点在于:ART模型将以用户为中心的局部小区域的语义信息作为用户节点的语义信息,使得取样后的话题分布融合了网络的拓扑特性.另外,由于每次取样都随机选择一个邻居作为取样节点的扩展,保障了取样节点的语义支配地位.其缺点在于:利用了均匀分布的形式对邻居进行选择,即假设所有邻居对取样点的影响力均相同,没有考虑邻居对取样用户节点的拓扑影响力.
2006年,Kemp等[56]考虑了网络度分布对节点关系的影响,提出了以链接存在概率为研究对象的IRM(Infiniterelationalmodels)模型,IRM将已存在的链接看作概率分布的一个样本,并假设链接服从用户节点对度的Beta分布,计算任意用户节点间的链接概率.在进行社区发现时,IRM以链接概率矩阵为输入,建立了社区内部链接概率最优化模型,通过最优划分社区内部的链接概率实现社区发现.其优点在于:以链接概率矩阵的形式泛化了邻接矩阵,从而使网络的拓扑结构可以应用于各类概率关系模型.其缺点在于:其链接概率的计算过程缺少了社会网络度的幂率分布假设,因此其链接概率矩阵不能准确表达社会网络的特征.
2007年,Long等[57]为实现社会网络中的多种关系混合建模,提出了MMRC(Mixmembershiprelationalclustering)算法.其在AT模型中加入了节点–链接的混合层,以链接的种类(如一般朋友关系、挚友关系、上下级关系等)作为节点分布的权重,强调链接在网络分布中的主导作用.另外,算法在进行局部拓扑关系挖掘方面采用了结构简单的Sortrelationalclustering方法以降低计算代价,在全局范围的聚类划分方面采用了精确性高的Hardrelationalclustering方法.MMRC属于两阶段聚类方法,其优点在于:合理地分配了2阶段的计算代价问题,适用于处理大规模数据及云计算数据.其缺点在于:各聚类簇的内部紧致性不高,将链接关系作为语义同样无法解决社区个数需要预先设定的问题.
2007年,Zhu等[58]利用NMF[59−60]的非语义社区发现形式进行语义社区划分,提出了CCLC(Combiningcontentandlinkforclassification)算法,其实现过程为:首先,对具有语义关联的链接进行语义加权,由此将语义社会网络转化为有权社会网络;其次,将网络加权邻接矩阵按NMF的形式构建以加权邻接矩阵近似为目标的社区–特征分解表达式;最后,以社区–特征分解表达式为目标函数,建立参数估计的最优化方法,以此计算社区划分结果.其优点在于:设计了NMF与语义社区发现相结合的平滑参数,且其目标函数的构建方法值得借鉴.其缺点在于:继承了NMF的高计算复杂度,不利于算法的推广.
2008年,Nallapati等先后提出了Link-PLSA-LDA[61]和Pairwise-link-LDA[62]取样模型对具有引用关系的语义网络进行建模,以提取其中的潜在话题.其假设被引用者的话题完全包含于引用者的话题结构内,从而在LDA模型中加入了话题–话题关系.其优点在于:对引文类型网络的挖掘效果较好,通过加入了引用者与被引用者的社会关系挖掘方法MMSB[26]实现了引文网络的社区挖掘.其缺点在于:语义社会网络的话题关系大多不具备完全包含关系,限制了Link-PLSA-LDA和Pairwise-link-LDA的应用范围.
2012年,Yin等[63]提出了ICDT(Integrationofcommunitydiscoverywithtopicmodeling)模型.该模型将取样过程分为用户节点取样和链接取样.其过程为在对某一用户节点进行取样后,对该用户节点的所有连接进行一次取样,将这2阶段的取样结果作为该用户节点的取样结果,即将AT与ART的结果相混合.另外,ICDT为每个用户节点及链接均分配了社区隶属度属性,在取样过程结束后可根据社区隶属度对用户节点分配社区.其优点在于:2阶段的取样过程形成了以用户节点为核心的取样区域,该区域可模拟用户节点对周边链接的语义影响力.其缺点在于:ICDT在进行社区隶属度假设时,没有考虑社会网络的链接关系,导致所划分的社区出现不连通的情况.
2012年,Cha等[64]根据社交网络中跟帖人的话题信息抽取出树状关系模型,并利用层次LDA算法对树状关系模型中的文本信息进行建模,提出了面向语义社会网络分析的HLDA模型.该模型在进行文本生成取样时,以取样节点为核心,对与之距离为2,···,3的用户节点进行分层取样.其优点在于:可有效处理论坛类(非熟人关系)网站的用户节点分类问题,此外,其文本生成的取样方式可兼顾网络的拓扑特性.其缺点在于:HLDA的分层取样过程为无权取样过程,没有考虑话题的传播受距离影响的因素.
2012年,Hu等[65]以“朋友关系越亲密其话题分布越接近”为假设,提出了面向语义分析的FT(Featuretopic)模型和面向关系分析的ST(Socialtopic)模型,其中FT与ST模型为相互独立的LDA模型.在话题挖掘过程中,利用Gibbs取样方法,分别对FT及ST进行交叉取样,从而保证了LDA模型参数求解时满足FT和ST的贝叶斯关系条件.其优点在于:通过建立两个LDA模型(FT和
1700自动化学报41卷
ST)的方式避免了混合模型的复杂化,同时,其求解方式又保持了FT及ST的约束条件.其缺点在于:以FT及ST的形式使用户节点的语义信息和拓扑信息相独立,缺少了语义–拓扑相关性(即语义对拓扑结构的影响力)的考虑.
2013年,Natarajan等[66]以Linkcommu-nity[67]为切入点,建立了以Link-content为语义分析目标的LCM(Link-contentmodel)模型.该模型以用户节点间的共享信息及用户节点间的传递信息作为Link-content,在进行LDA建模时将Link作为社区分类的基本单元.其优点在于:构建了Link-content的LDA模型,在发现Linkcom-munity的同时可处理语义社会网络的链接预测问题.其缺点在于:Link-content属于用户节点话题概率模型的简单套用,没能结合Link-content的特征进行改进,因此LCM同样具有用户节点–话题概率模型的一般缺点.1.4社区–话题概率模型
局部区域性是社会网络有别于一般图状网络的特有拓扑特征,传统社会网络研究中对社会网络中的局部区域性结构(如Clique社区[10]、Block社区[68−69])的存在性已做了充分证明.近些年在基于概率关系模型的语义社区挖掘过程中,将社会网络的局部区域性与概率生成关系相混合,提出了一系列考虑局部区域性因素的语义社区挖掘方法.图6为当前面向社区发现的社区–话题概率建模方面的主要模型,本文根据各模型的特点对其进行了分类.
2005年,Wang等[70]为了使LDA具有社区分类的能力,提出了GT(Grouptopic)模型.该模型在LDA模型中加入了社区元素,并将关键字分为社区内部关键字与全局关键字.其中全局关键字的分布仅依赖于话题分布,社区内部关键字的分布依赖于话题与社区的混合分布.GT模型的参数估计过程为:先以全局关键字估计话题分布,再以社区内部关键字及话题分布估计社区分布,如此反复直到参数收敛.其优点在于:GT所建立的话题与社区独立的两阶段混合取样方式,提高了LDA面向多元参数估计时的精度.其缺点在于:GT没有考虑用户节点间的链接关系,应对社会网络的社区结构挖掘时效果较差.
2006年,Zhou等[71]为了解决社区的不连通现象,提出了CUT(Communityusertopic)模型.其在AT模型的基础上为用户节点加入了社区分布条件.其贝叶斯依赖关系为:先以社区生成用户节点,再以用户节点生成语义话题.通过对中间层(用户节点层)进行估计可挖掘出以语义作为区分的用户节点簇,从而实现社区划分.其优点在于:CUT模型弥补了AT模型不考虑用户节点间关联性的不足,为后续的语义社区挖掘研究作了铺垫.其缺点在于:用户节点的社区分布没有考虑用户的链接关系,仅在处理不强调链接关系的语义社区挖掘时有效,在处理以网络拓扑为基础的社区挖掘问题时,会出现社区内部不连通的情况.
图6
Fig.6
各类社区–话题概率模型关系图
Therelationshipofvariouscommunity-topicprobabilitymodels
10期辛宇等:基于话题概率模型的语义社区发现方法研究1701
2007年,Zhang等[72]提出了SSN-LDA(Sim-plesocialnetwork-LDA)模型.该模型建立了用户节点对所有相邻用户节点的SIW(Socialinter-actionweight)分布函数,以此模拟相邻用户节点间的影响力.随后Zhang等[73]在SSN-LDA的基础上考虑了权重因素,提出了GWN-LDA(Genericweightednetwork)模型.SSN-LDA与GWN-LDA在进行LDA模型求解时,按SIW对取样元素进行加权,从而划分出考虑用户节点相关性的社区结构.其优点在于:SIW的加权取样过程可作为考虑语义相关性的基础取样模型,其建模过程简单,具有较强的可扩展性.其缺点在于:语义社会网络中节点的语义信息(如话题及标签关键字)间同样存在着关联性,而SSN-LDA与GWN-LDA仅面向有权网络缺少对语义信息相关性的考虑.随后,Zhang等[74]又提出了HSN-PAM(Hierarchicalsocialnetworkpachinkoallocation)模型,HSN-PAM利用LDA模型的层次性建立了多层社区模型,即在LDA的社区分布中加入了多层变量,所求解出的各层社区间存在树状包含关系.其优点在于:将社区变量进行多层化,不仅可以对HSN-PAM的求解过程进行分布式计算以应对大规模数据挖掘的需要,而且树状结构使HSN-PAM模型具有网络拓扑整体性约束,即下层社区内容的变更需要依赖上层的全局状态.其缺点在于:由于HSN-PAM模型的层次数较多,导致对LDA进行多层求解时,各层变量的准确性降低.
2008年,Pathak等[25]在ART模型[23]的基础上提出了CART(Communityauthorrecipienttopic)模型.该模型在ART模型中加入了社区元素,将用户节点和话题作为社区的生成结果.不同于TURCM(Topicuserrecipientcommunitymodel)[75]将社区隶属度作为用户节点先验参数的建模方式,CART将用户节点作为社区和话题的中间变量,以挖掘潜在用户节点簇的方式实现社区发现.其优点在于:建立了社区与用户节点及社区与话题的双向关联,使得所发现的语义社区结构中保持了同一社区话题相近的条件.其缺点在于:CART模型中预设社区个数对社区挖掘的结果影响较大,对社区预设个数的最优化选取是CART模型急需解决的问题.
2009年,Lacoste-Julien等[36]为解决LDA模型需要预先设定社区个数的问题,提出了DiscLDA(DiscriminativevariationonLDA)模型.该模型在LDA模型的话题分布的先验参数中加入了转移概率矩阵.DiscLDA模型利用k维话题先验参数与转移概率矩阵的乘积形式对k维话题进行降维调整,最终实现话题个数的迭代优化.其优点在于:利用转移概率矩阵的形式对话题进行优化迭代,解决了LDA模型的分析结果依赖于话题的预设个数问题.其缺点在于:DiscLDA以k维话题的分布参数与转移概率矩阵之积作为话题的先验参数,在进行Gibbs取样时无法求得准确的转移概率矩阵取值,因此其分类结果较差.
2009年,Henderson等[76]为了在D2D网络中挖掘潜在的Documentcommunity,提出了LDA-G模型.该模型将网络中的所有用户节点作为LDA中的Document,将社区作为Topic,将用户节点间的链接作为Word关联.LDA-G将网络中的拓扑信息作为文本信息,从而将LDA模型中Word-docuemt-topic套用为Node-link-community,再利用LDA的求解方式实现社区发现.其优点在于:LDA-G发现了LDA模型与社区模型的相似之处,从而保证了其理论可行性.其缺点在于:其本质上不属于面向文本话题分析的社区挖掘算法,且LDA-G在直接套用LDA模型时,对社区紧致性的考虑较少,所挖掘的社区结构模块度不高.
2010年,Henderson等[77]在LDA-G模型的基础上为用户节点加入了属性元素提出了HCDF(Hybirdcommunitydiscoveryframework)模型.HCDF通过对用户节点及属性的混合建模,建立了考虑属性分类和用户节点分类双向优化的LDA模型,其社区划分结果满足了社区内部语义的一致性.其优点在于:所建立的双目标混合概率模型,满足了语义社区对拓扑关系和语义关系的双向要求.其缺点在于:双目标混合优化的LDA模型不同于单目标混合优化LDA模型(如CART[25]),需要在求解过程中增加额外的参数估计过程,从而降低了参数估计的准确性.
2010年,Kumar等[78]建立了社区话题动态变化的度量方法,其中包括零散用户节点、小社区和大规模社区话题变化度量.对3种规模社区的话题跟踪及度量得出了以下结论:不同规模及不同结构的社区,其话题内容均具有一定的相关性,即社区的划分无法隔断话题的连通性和一致性.其研究结论为语义社区发现提供了一种新的思路:对局部话题的分析是否需要以全局语义为基础,以及如何解决局部语义对全局语义的依赖性建模问题.
2010年,Kwak等[79]在网络节点的幂率分布假设[20]的基础上,分别在Follower、Reciprocity、DegreeofSepara-tion、Homophily4个方面分析了用户节点之间的关联性,并给出了用于评价用户节点权威性的Rank指标.Kwak等通过实验对比得出以下结论:1)用户节点的行为及社会特征极大程度受与之相邻的用户节点影响,即语义环境决定了用户节点的
1702自动化学报41卷
属性;2)各用户节点的差异性分布在环境接受阈内,其特征与环境呈同向变化的趋势.文章从理论推导和实验验证2方面论证了语义相关性对社区挖掘的影响,支持了社会网络语义层面的相关性,是语义社会网络挖掘的重要依据.
2011年,Sachan等[75]提出了TURCM模型.该模型以一次文本交互中的链接关系作为文本取样的对象,并在取样过程中加入了用户节点从属多个社区的假设.通过对TURCM的取样分析,可得到各个用户节点对各个社区的隶属关系,从而将隶属度大的社区作为用户节点所在的社区.其优点在于:将用户节点对社区的隶属度作为用户节点分布的先验参数,通过Gibbs取样法对TURCM进行求解,可直接得出用户节点对社区的隶属关系.其缺点在于:没有考虑社区与话题间的关联,其概率模型结构不稳定.为了弥补TURCM的这一缺点,Sachan等[80]随后提出了TURCM的改进模型TURCM1,在TURCM的基础上增加了社区与话题的关联.然而TURCM与TURCM1的共同缺点在于,在将社区作为用户节点属性的同时缺少对社区连通性的考虑,所挖掘出的社区结构会出现不连通的情况.
2014年,辛宇等在Semantic-LDA[81]基础上,分别以节点的Block区域及有权Field区域为中心,以Block区域及有权Field区域的语义分析作为该取样节点的语义信息,提出了BAT(Blockau-thortopic)模型[82]及LFT(Linkfieldtopic)模型[83],并随后提出了可加速Gibss取样过程的多重取样ARTMS(ARTsmultiplesampling)[84]方法.此类算法采用语义分析与社区发现相分离的2阶段混合策略.其优点在于:可对第1阶段的语义社区划分结果套用传统社区发现算法,易于直接应用于动态社区发现及重叠社区发现且无需预先设定社区个数;其缺点在于:Semantic-LDA、BAT、LFT及ARTMS在处理节点间语义相关性较低的问题时,各节点的语义分析结果差异较大,导致所划分的同一社区中存在与社区语义相关性低的噪音节点.
2语义划分结果的度量方法分析
语义社区结构在传统社区结构中加入了语义信息,因此,语义社区划分的评价标准需要兼顾社区内部的语义相关性及社区结构的紧致性.本文综述了语义社区评价中常用的方法及模型,并设计了对比各模型评价性能的实验方法.
2.1度量方法综述
本文对各类评价方法进行了统一描述,所涉及的数学符号如下:
G表示全局网络,|G|表示网络中用户节点的数量,Gi表示网络G中的第i个用户节点;
L表示网络G中的链接集合,|L|表示网络中的链接数量,l(i,j)表示连接用户节点Gi和Gj的链接;
A表示网络G的邻接矩阵;degreei表示用户节点Gi的度;
C表示所划分的社区集合,|C|表示社区个数,|Ci|表示社区Ci内的用户节点个数;
mi表示用户节点Gi的属性(话题)向量,其维数为k.
各语义社区评价模型如下:
1)Qov模型[42−85]:该模型是模块度Q[86]的广义模型,可用于评价有权有向网络,适用于评价将语义相似性量化后的语义社区结构.
其表达式如式(1)所示,其中f(x)=2px−p,αi,c是节点i对社区c的贡献度,βl(i,j),c是社区c的内部链接l(i,j)对社区c的贡献度,βlin(i,j),c和βlout(i,j),c分别为有向边缘链接对社区c的贡献度,Qov取值越大社区结构越合理.
2)ACS(Averageclustersimilarity)模型[87]:该模型利用RBF(Radialbiasfunction)核模型[88]对语义社区结构进行评价,其表达式为
ACS=
Gi∈c,Gj∈c
K(mi,mj)
k
(2)
其中,K(mi,mj)表示RBF核模型,其表达式为
|C|c=1
outininoutβl(i,j)degreeiβl(i,j)degreej1
Qov=βl(i,j),cAij−
2|L|c∈Ci,j∈G2|L|
F(αi,c,αj,c)F(αi,c,αj,c)βlout(i,j),c=βl(i,j),c=
j∈/c,i∈c
αi,c=1
(1)
i,j∈c
|G|
F(αi,c,αj,c)|V|
,
,
βlin(i,j),c=
j∈/c,i∈c
|V|
1
(1+e−f(ai,c))(1+e−f(aj,c))
F(αi,c,αj,c)=
10期辛宇等:基于话题概率模型的语义社区发现方法研究1703
K(m−mi−mj2λ
2
i,mj)=exp
2
(3)
其中,λ为控制因子,ACS∈(0,1],ACS越大社区内部的语义相似性越高,社区划分结果越合理.
3)PWF(PaierwiseF-measure)模型[35]:该模型建立了语义和社区相关性度量方法,其表达式为
PWF=2|R∩T|
|R|+|T|(4)
其中,T表示具有相同标签的相邻用户节点的集合,R表示划分为同一社区的相邻用户节点的集合.PWF的取值越大说明语义社区划分的结果越好.
4)PurQ模型[89]:该模型建立了模块度Q与语义话题相关性相混合的度量方法,其表达式为
PurQ=(1+γ2)
Purity·Qγ2·Purity+QPurity=1
(5)
|C|C||nij
i=11max
≤j≤k|Ci|其中,Q为社区划分结果的模块度,nij表示属于社区Ci和话题j的用户节点个数,Purity表达了社区的话题关联性,其取值越高话题的划分效果越好,γ为Purity与Q的平衡参数,当0<γ<1时,PurQ偏重于Purity,当1<γ<∞时,PurQ偏重于Q.
5)NR(Networkregulaziation)模型[31]:该模型在GHF(Graphharmonicfunction)[90]的基础上,建立了基于矩阵分解模型的语义社区度量方法,其表达式为
|C|
Reg=12fT
j
(c)(D(c)−W(c))fj(c)(6)
c∈Cj=1其中,W(c)为社区c的权重邻接矩阵,D(c)为社区
c的对角阵,其中,Dc)=
u,u(vWu,v(c),fj(c)为由社区c的所有用户节点对话题i的隶属度所构成的向量.
6)SCE(Semanticcommunityentropy)模型[91]:该模型建立了以语义相似性量化为前提的语义社区度量方法,其表达式为
H|C|C=
H(Ci)i=1
|CH(Ci|−1
|Ci|
i)=sjllnsjl+
j=1l=j+1
(1−sjl)ln(1−sjl)
(7)
其中,sjl为用户节点Gj与Gl的相似性,HC的取值越小,则社区内部的语义相似度越高,语义相关性越强.
7)全局语义相关性模型[49]:该模型可表达网络G的语义相似性与拓扑结构的相关度,其表达式为
Corr=
wijcos(mi,mj)Gi,Gj∈L
w2ij
cos(mi,mj)
(8)
Gi,Gj∈LGi,Gj∈L
其中,wij为Gi与Gj间链接的权重,cos(mi,mj)
为Gi与Gj的话题向量mi与mj的余弦相似度.本文在该理论的基础上建立了语义社区度量的语义NMI模型(记作s-NMI),该模型以传统度量方法中的NMI模型[92]为基础,其表达式为
s-NMI(c,c)=
p(i,j)log
p(i,j)
i∈ci∈c
pc(i)pc(j)pc(i)logp)×c(ipc(j)logpc(j)
i∈c
j∈c
(9)
式中,p(i,j)为用户节点Gi和Gj的1-dis社区
(用户节点与其自身的邻居所构成的社区)的交集内某些话题出现的概率,pc(i)表示在c社区中的用户节点Gi所构成的1-dis社区内某些话题出现的概率.s-NMI(c,c)表达了社区间的话题相关性.
8)OFS(Occurrencefrequencysimilarity)[93]:该模型利用了Document中关键字的出现频率及关键字间的相关性,在关键字的分类记录中分析用户节点间的语义相似性.其表达式如下:
of(i)=
1
Vu,ix×1+log×|N
|n∈Nf(iun)logV
f(i)(10)
un式中,N为Document属性构成的集合,|N|为属性总数,V为记录中关键字的总数.iun表示节点iu的第n个属性,f(iun)是节点iu的第n个属性在总体记录中出现的次数,OFS∈(0,1]且OFS越大则户节点间的语义相似性越高.
9)PMI(Pointwisemutualinformation)模型[94]
:该模型是在Networksimilarity模型[95]作为拓扑结构相似性度量的基础上结合语义相似度分析,对用户与社区相关性概率分布进行互信息建模.若两个社区对同一用户的相关性相近,则说明这
1704自动化学报41卷
两个社区相似,藉此实现语义社区间的相似性度量.Networksimilarity模型的表达式如式(11)所示.评价模型可评价语义社区划分结果.经过改造后的模型记为“s-model”(如s-EQ).
NS(u,x)=
log(|MFG(u,x)E|)log(2|FG(u)E|)
(11)
2.2度量方法的实验对比
本文利用实验分析对各类语义社区度量方法进行了社区结构相关性测试及语义相关性测试.由于某些度量方法(如AF模型)需要预先设定参数,且参数的取值决定了模型的度量性能.由于对各模型的参数进行对比讨论需要大量的篇幅.对此,本文仅从对比分析的实验方法出发,对各类语义社区度量方法进行方法性比较,不作参数取值的对比,其中模型的参数根据相关文献进行设定.
1)数据集与度量方法
在实验数据集方面,本文利用LFRBenchmark[96−97]生成模拟数据集G1000作为语义社会网络的关系拓扑.其参数设置为(|G|=1000,ad=4,dmax=16,cmin=15,cmax=50,on=80,om=5,mi=2.5),其中参数|G|表示用户节点的个数;ad和dmax分别表示网络中用户节点的平均度和最大度;cmin和cmax分别表示最小社区和最大社区中用户节点的数量;on表示重叠用户节点个数;om表示每个重叠用户节点连接的社区个数;mi为混合系数,表示用户节点与社区外部连接的概率,随着mi值的增大,网络社区结构越来越模糊,当mi>0.5时,网络的社区结构不明显.
在语义数据模拟方面,本文随机选择30组话题,每组话题包含200个关键字.选择G1000中度数最大的30个用户节点作为话题源用户节点,为每个
其中,FG(u)E为Gu的1-dis社区的内部边数.MFG(u,x)E为Gu的1-dis社区和Gx的1-dis社区所构成的社区交集的内部边数.在NS模型基础上,PMI(Pointwisemutualinformation)模型的表达式为
PMI(u,s)=P(Fu,Fs)log
P(Fu,Fs)
(12)
P(Fu)·P(Fs)
其中,Fu表示Gu的朋友圈,P(Fu)表示某一用户节点成为Gu的朋友的概率,P(Fu,Fs)表示某一用户节点成为Gu和Gs的共同朋友的概率.
10)传统社区评价模型的语义改进模型:语义社会网络的分析结果可量化为用户节点的多维属性mi,且用户节点Gi和Gj间的相似性U(mi,mj)可代表l(i,j)的权重,因此,可利用U(mi,mj)建立网络G的有权邻接矩阵S,Sij=U(mi,mj).
表1为传统社会网络的社区评价指标,其
in
A,C=中Ciout=pqip∈Ci,q∈/Cip,q∈CiApq,
|L|=p,q∈GApq,Ciin(j)=p∈CiAjp,Ciout(j)=p∈/CiAjp,在语义社会网络的评价方面,本文借用传统社会网络评价模型的表达形式,对其中
的参数进行了如下改造Ciout=p∈Ci,q∈/CiSpq,inCiin=|=p,q∈GSpq,Ci(j)=p,q∈CiSpq,|Lout
(j)=p∈/CiSjp,使传统社会网络p∈CiSjp,Ci
表1
Table1
算法
各类社区评价模型
Variousmeasurementmodelsforcommunitydetection
表达式
EQ[11]s-EQ
Averagecondutance[41]
MinMaxCut[98]Silhouette[99]Ductance[100]Expansion[101]
NCut[102]
Averagefitness[12]
Sil=
1|C|
|C|j=1
EQ=s-EQ=
1
2|L|
|C|
i=1v,w∈Ci
1
OvOw
Avw−
degree(v)degree(w)
2|L|
12|L|
|C|
cosmi,mjOvOw
(
)
Avw−)(i=1v,w∈Ci1|C|
|C|i=1
min
degree(v)degree(w)
2|L|
AC=
1
((
i∈Cj
ai−bimaxbi,ai
MMC=,ai=
outCi
1Cout+Cin,2|L|−Cout−1Cinii2i2i
|C|out2Ci
Cinii=1
1
))
1
|Cr|
i,j∈Ck
|Cj|()|Ck||C|
Aij,bi=max
i∈/Cr,j∈Cr
Aij
NCut=
AF=
outCi
inC+Coutiii=1|C|outCi
Ci
i=1
|C|outoutCiCi
1inoutC+C2|L|−Cin+Coutiii=1i2i|C|in(j)C1i
r|C|Cin(j)+Cout(j)
i=1j∈Ciii
Duc=
Exp=
||+
()()10期辛宇等:基于话题概率模型的语义社区发现方法研究1705
话题源用户节点分配一组话题,并记录各话题与关键字的对应关系.网络中各用户节点同时随机选择自身的80个关键字向邻居用户节点进行扩散,如此循环直到网络中每个用户节点分配到的关键字数量均大于200.此过程模拟话题的传播特性、各节点所分配的关键字可作为其语义信息.在多维话题向量生成方面,本文利用关键字与话题的对应关系,统计话题分配次数.将每个用户节点的话题分配次数作为话题向量m,并将话题向量进行整理mi=mi/max(m),所得到的多维属性作为各用户节点的话题隶属度.
在度量方法的选择及参数设置方面,选用余弦相似度作为多维相似度度量,对比模型为:Qov(p=0.5),ACS(λ=1.5),PWF,PurQ(γ=1),NR,SCE,s-NMI,PMI,s-EQ,s-AC,s-MMC,s-Sil,s-Duc,s-Exp,s-Ncut和s-AF共16个模型(由于OFS模型不含社区结构度量,不对其进行比较).其中,Qov,ACS,PWF,PurQ,NR,s-NMI,s-EQ,s-Sil,s-Exp和s-AF的取值越大语义社区划分的结果越优,SCE,PMI,s-AC,s-MMC,s-Duc和s-Ncut的取值越小语义社区划分的结果越优.语义社区评价模型需要综合考虑社区结构的拓扑相关性及语义相关性,由于各模型的表达式不同,其对拓扑相关性及语义相关性的敏感度不同.为此,本实验设计了社区结构相关性测试实验及语义相关性测试实验.
2)拓扑相关性测试,分析语义数据不变的条件下各评价模型对网络拓扑结构的依赖性.
本实验首先利用G1000的网络生成方法及语义数据模拟方法,随机生成20组G1000数据,并在各用户节点的语义数据不变的条件下,对每组数据的2个社区之间随机加边,由于LFRBenchmark具有固定的社区结构,社区间的随机加边会导致社区的结构变得模糊,从而导致模块度EQ下降;其次,在社区的模糊化时,跟踪20组数据中各语义评价指标的变化情况,以此来评价各模型对拓扑相关性的依赖;最后,记录20组G1000数据EQ从0.6到0.2的变化过程中各评价模型的取值变化,并将评价模型的取值映射在(0,1)区间内以增加可对比性.图7为16个模型在20组G1000数据中的社区结构相关性对比.
图7
Fig.7
各评价模型的社区结构相关性测试
Thecorrelationtestoncommunitystructureforeachevaluationmodel
1706自动化学报41卷
图7中虚线为EQ的线性变化辅助线,实线为20组G1000数据的均值.各评价模型与EQ的相关系数分别为:Qov(0.98),ACS(0.88),PWF(0.83),PurQ(0.82),NR(0.68),SCE(−0.73),s-NMI(0.80),PMI(−0.75),s-EQ(0.98),s-AC(−0.90),s-MMC(−0.89),s-Sil(0.84),s-Duc(−0.76),s-Exp(0.80),s-Ncut(−0.72)和s-AF(0.76),说明NR,SCE,PMI,s-Duc,s-Duc,s-Ncut和s-AF与模块度Q的线性变化偏差较大,当社区拓扑相关性(非语义结构)发生改变时,上述模型的变化量不与拓扑相关性的变化量线性相关,即上述评价模型更强调语义相关性,适合用于评价语义社区划分.
3)语义相关性测试,分析网络拓扑结构不变的条件下各评价模型对语义数据的依赖性.
本实验首先利用G1000的网络生成方法及语义数据模拟方法随机生成20组G1000数据,并在20组数据的拓扑结构不变的条件下,按高斯场的势能函数[90,103]在关键字的扩散过程中增加扩散系数exp(−(step/σ)2),其中step=0,1,···为扩散的步数;其次以扩散系数作为关键字扩散的权重,跟踪20组G1000数据在σ∈(1,5)时,各评价模型的取值,其中σ较大时,各step的扩散系数趋于均等,导致社区间的语义相似性高,即σ越大语义相关性越差;最后,记录20组G1000数据σ从1到5的变化过程中各评价模型的变化状态,并将评价模型的取值映射在(0,1)区间内以增加可对比性.图8为16个模型在20组G1000数据中的语义相关性对比,其中虚线为σ的线性变化辅助线,实线为20组G1000数据的均值.各评价模型与σ的相关系数分别为:Qov(−0.95),ACS(−0.90),PWF(−0.76),PurQ(−0.78),NR(−0.88),SCE(0.88),s-NMI(−0.76),PMI(0.87),s-EQ(−0.88),s-AC(0.81),s-MMC(0.81),s-Sil(−0.82),s-Duc(0.80),s-Exp(−0.88),s-Ncut(0.78)和s-AF(−0.77),说明PWF,PurQ,s-Ncut和s-AF与σ的线性变化偏差较大,说明上述评价模型的变化量不与语义相关性的变化量线性相关,即上述评价模型更强调拓扑相关性,适合用于评价传统非语义社区划分.综合拓扑相关性测试的结果,s-Ncut和s-AF的综合评价性能较强.
图8
Fig.8
各评价模型的语义相关性测试
Thecorrelationtestsonsemanticforeachevaluationmodel
10期辛宇等:基于话题概率模型的语义社区发现方法研究1707
3结论
本文对基于话题概率模型的语义社区发现方面的相关文献进行了归纳,在描述其各自实现过程的同时总结了各种算法的优缺点,其中优点可作为后续研究的指导思想,缺点可作为后续研究的改进方向.语义社会网络的社区挖掘兼备了语义分析和拓扑分析2方面技术,本文所列举的大多文献的共同缺点在于没有将二者进行有效结合,如在语义分析过程中没有考虑拓扑结构对语义分析的影响,以及在社区挖掘过程中融入语义–拓扑混合的相关性分析.对此,后续的工作需要借鉴以往算法的经验和不足,在语义–拓扑层面对语义社区挖掘方法进行创新.
本文最后综述了语义社区的评价模型,并利用实验分析对比了各模型的评价特性.由于本文的写作目的在于综述各类评价模型的表达形式及设计思想,其实验的目的在于方法性说明,因此,实验过程及参数讨论相对简略.在后续的研究中,可利用本文所提供的实验方法,改进语义数据的话题标签扩散方式,以及利用社区的结构特性指导话题的扩散方向,实现评价模型的多角度对比.
由于基于话题概率模型的语义社区发现具有较复杂的文本训练过程,且仅适用于静态社会网络.对此,在未来大数据环境下,需要解决话题模型的简化,并建立动态流式数据的增量挖掘模式,实现动态语义社会网络(包含节点的动态交互及语义信息的动态变化)的动态语义社区挖掘,包括动态语义社区发现、语义社区推荐、动态语义话题溯源等.综上所述,本文对语义社区挖掘相关文献的归纳和总结,可作为该领域后续工作的参考.
References
1GirvanM,NewmanMEJ.Communitystructureinso-cialandbiologicalnetworks.ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2002,99(12):7821−78262WattsDJ,StrogatzSH.Collectivedynamicsof‘small-world’networks.Nature,1998,393(6684):440−4423GolbeckJ,RothsteinM.LinkingsocialnetworksonthewebwithFOAF:asemanticwebcasestudy.In:Proceedingofthe23rdAssociationfortheAdvancementofArtificialIn-telligenceConferenceonArtificialIntelligence.MenloPark,Canada:AAAI,2008.1138−11434KlyneG,CarrollJJ.Resourcedescriptionframework(RDF):conceptsandabstractsyntax[Online],available:http://www.w3.org/TR/REC-rdf-syntax,February1,20065BrickleyD,GuhaRV.RDFvocabularydescriptionlan-guage1.0:RDFschema.W3CRecommendation10Febru-ary2004,WorldWideWebConsortium,004[Online],available:http://www.w3.org/TR/rdf-schema/,November,20066W3COWLWorkingGroup.OWL2webontologylan-guage:documentoverview.W3CRecommendation27
October2009,WorldWideWebConsortium,2009[On-line],available:http://www.w3.org/TR/2009/REC-owl2-overview-20091027/,November,2007
7
PrudhommeauxE,SeaborneA,LaboratoriesHP,Bristol.SPARQLquerylanguageforRDF.W3CRecommendation15January2008,WorldWideWebConsortium,2008[On-line],available:http://www.w3.org/TR/rdf-sparql-query/,Auguest,2007
8
NewmanME.Fastalgorithmfordetectingcommunitystructureinnetworks.PhysicalReviewE,2004,69(6):066133
9
BlondelVD,GuillaumeJL,LambiotteR,LefebvreE.Fastunfoldingofcommunitiesinlargenetworks.JournalofStatisticalMechanics:TheoryandExperiment,2008,DOI:10.1088/1742-5468/2008/10/P1000810
PallaG,Der´enyiI,FarkasI,VicsekT.Uncoveringtheover-lappingcommunitystructureofcomplexnetworksinnatureandsociety.Nature,2005,435(7043):814−818
11
ShenHW,ChengXQI,CaiK,HuMB.Detectoverlappingandhierarchicalcommunitystructureinnetworks.PhysicaA:StatisticalMechanicsanditsApplications,2009,388(8):1706−1712
12
LancichinettiA,FortunatoS,Kert´eszJ.Detectingtheover-lappingandhierarchicalcommunitystructureincomplexnetworks.NewJournalofPhysics,2009,11(3):03301513
GregoryS.Findingoverlappingcommunitiesinnetworksbylabelpropagation.NewJournalofPhysics,2010,12(10):103018
14Berners-LeeT,HendlerJ,LassilaO.Thesemanticweb.Sci-entificAmerican,2001,284(5):28−37
15ThovexC,TrichetF.Semanticsocialnetworksanalysis.So-cialNetworkAnalysisandMining,2013,3(1):35−49
16
YangJing,XinYu,XieZhi-Qiang.Semanticssocialnetworkcommunitydetectionalgorithmbasedontopiccomprehen-sivefactoranalysis.JournalofComputerResearchandDe-velopment,2014,51(3):559−569
(杨静,辛宇,谢志强.基于话题综合因子分析的语义社会网络社区发现算法.计算机研究与发展,2014,51(3):559−569)
17BleiDM,NgAY,JordanMI.Latentdirichllocation.Jour-nalofMachineLearningResearch,2003,3(8):993−102218
HofmannT.Probabilisticlatentsemanticindexing.In:Pro-ceedingsofthe22ndAnnualInternationalACMSIGIRCon-ferenceonResearchandDevelopmentinInformationRe-trieval.NewYork,USA:ACM,1999.50−57
19
BischofJ,AiroldiE.Summarizingtopicalcontentwithwordfrequencyandexclusivity.In:Proceedingsofthe29thInter-nationalConferenceonMachineLearning.NewYork,USA:ICML,2012.201−20820Barab´asiAL,AlbertR.Emergenceofscalinginrandomnetworks.Science,1999,286(5439):509−512
21DingY.Communitydetection:topologicalvs.topical.Jour-nalofInformetrics,2011,5(4):498−514
22
SteyversM,SmythP,Rosen-ZviM,GriffithsT.Probabilis-ticauthor-topicmodelsforinformationdiscovery.In:Pro-ceedingsofthe10thACMSIGKDDInternationalConfer-enceonKnowledgeDiscoveryandDataMining.NewYork,USA:ACM,2004.306−315
23
McCallumA,Corrada-EmmanuelA,WangXR.Topicandrolediscoveryinsocialnetworks.In:Proceedingsofthe19thInternationalJointConferenceonArtificialIntelligence.SanFrancisco,USA:ACM,2005.786−791
24
McCallumA,WangXR,Corrada-EmmanuelA.TopicandrolediscoveryinsocialnetworkswithexperimentsonEn-ronandacademicemail.JournalofArtificialIntelligenceResearch,2007,30(1):249−272
1708自动化25PathakN,DeLongC,BanerjeeA,EricksonK.Socialtopic
modelsforcommunityextraction.In:Proceedingsofthe2ndSNA-KDDWorkshop.NewYork,USA:ACM,2008.1−826AiroldiEM,BleiDM,FienbergSE,XingEP,Jaakkola
T.Mixedmembershipstochasticblockmodelsforrelationaldatawithapplicationtoprotein-proteininteractions.In:Proceedingsofthe2006InternationalBiometricsSocietyAnnualMeeting.Tampa,FL,USA:ENAR,2006.23−3127WangXR,McCallumA.Topicsovertime:anon-Markov
continuous-timemodeloftopicaltrends.In:Proceedingsofthe12thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork,USA:ACM,2006.424−43328GriffithsT.Gibbssamplinginthegenerativemodeloflatent
dirichletallocation.StandfordUniversity,2002,518(11):1−329WangXR,McCallumA,WeiX.Topicaln-grams:phrase
andtopicdiscovery,withanapplicationtoinformationre-trieval.In:Proceedingof7thIEEEInternationalConferenceonDataMining.Omaha,USA:IEEE,2007.697−70230WallachH.Topicmodeling:beyondbag-of-words.In:Pro-ceedingsofthe23rdInternationalConferenceonMachineLearning.Pittsburgh,USA:ACM,2006.977−98431MeiQZ,CaiD,ZhangD,ZhaiCX.Topicmodelingwith
networkregularization.In:Proceedingsofthe17thinter-nationalconferenceonWorldWideWeb.NewYork,USA:ACM,2008.101−11032WhiteS,SmythS.Aspectralclusteringapproachtofinding
communitiesingraphs.In:Proceedingsofthe5thSIAMInternationalConferenceonDataMining.Houston,USA:SIAM,2005.76−8433AzranA,GhahramaniZ.Spectralmethodsforautomatic
multiscaledataclustering.In:Proceedingofthe2006IEEEComputerSocietyConferenceonComputerVisionandPat-ternRecognition.Piscataway,USA:IEEE,2006.190−19734LinCH,HeYL.Jointsentiment/topicmodelforsentiment
analysis.In:Proceedingsofthe18thACMConferenceonInformationandKnowledgeManagement.NewYork,USA:ACM,2009.375−38435YangTB,JinR,ChiY,ZhuSH.Combininglinkandcon-tentforcommunitydetection:adiscriminativeapproach.In:Proceedingsofthe15thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork,USA:ACM,2009.927−93636Lacoste-JulienS,ShaF,JordanM.DiscLDA:discrimina-tivelearningfordimensionalityreductionandclassification.In:Proceedingofthe2009AdvancesinNeuralInformationProcessingSystems.Piscataway,USA:NIPS,2009.897−90437LiDF,HeB,DingY,TangJ,SugimotoC,QinZ,YanE
J,LiJZ,DongTX.Community-basedtopicmodelingforsocialtagging.In:Proceedingsofthe19thACMInterna-tionalConferenceonInformationandKnowledgeManage-ment.NewYork,USA:ACM,2010.1565−156838LeskovecJ,LangKJ,MahoneyM.Empiricalcomparisonof
algorithmsfornetworkcommunitydetection.In:Proceed-ingsofthe19thInternationalConferenceonWorldWideWeb.NewYork,USA:ACM,2010.631−64039TangJ,JinRM,ZhangJ.Atopicmodelingapproachand
itsintegrationintotherandomwalkframeworkforacademicsearch.In:Proceedingof8thIEEEInternationalConferenceonDataMining.Pisa,Italy:IEEE,2008.1055−1060
学报41卷
40TangJ,ZhangJ,YaoLM,LiJZ,ZhangL,SuZ.Arnet-Miner:extractionandminingofacademicsocialnetworks.In:Proceedingsofthe14thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork,USA:ACM,2008.990−99841LeskovecJ,LangKJ,DasguptaA,MahoneyMW.Com-munitystructureinlargenetworks:naturalclustersizesandtheabsenceoflargewell-definedclusters.InternetMathe-matics,2009,6(1):29−12342R´ıosSA,Mu˜nozR.DarkWebportaloverlappingcommu-nitydetectionbasedontopicmodels.In:Proceedingsofthe
2012ACMSIGKDDWorkshoponIntelligenceandSecurityInformatics.NewYork,USA:ACM,2012.1−743XieJR,SzymanskiBK,LiuXM.Slpa:uncoveringoverlap-pingcommunitiesinsocialnetworksviaaspeaker-listenerinteractiondynamicprocess.In:Proceedingofthe11thIEEEInternationalConferenceonDataMiningWorkshops.Piscataway,USA:IEEE,2011.344−34944BarberMJ,ClarkJW.Detectingnetworkcommunitiesby
propagatinglabelsunderconstraints.PhysicalReviewE,2009,80(2):026129.1-026129.1145JangJ,MyaengSH.Discoveringdedicatorswithtopic-basedsemanticsocialnetworks.In:Proceedingofthe7thInternationalConferenceonWeblogsandSocialMedia.Boston,USA:ICWSM,2013.1−1246EroshevaE,FienbergS,LaffertyJ.Mixed-membership
modelsofscientificpublications.ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2004,101(S1):5220−522747DietzL,BickelS,SchefferT.Unsupervisedpredictionofci-tationinfluences.In:Proceedingsofthe24thInternationalConferenceonMachinelearning.Piscataway,USA:ACM,2007.233−24048ChangJ,BleiDW.Relationaltopicmodelsfordocument
networks.In:Proceedingsofthe2009InternationalCon-ferenceonArtificialIntelligenceandStatistics.Piscataway,USA:IEEE,2009.81−8849SunYZ,HanJW,GaoJT.Itopicmodel:information
network-integratedtopicmodeling.In:Proceedingof9thIEEEInternationalConferenceonDataMining.Miami,FL,USA:IEEE,2009.493−50250PerezP.Markovrandomfieldsandimages.CWIQuarterly,
1998,11(4):413−43751LiuY,Niculescu-MizilA,GrycW.Topic-linkLDA:joint
modelsoftopicandauthorcommunity.In:Proceedingsofthe26thAnnualInternationalConferenceonMachineLearning.Piscataway,USA:ACM,2009.665−67252LHuillierG,R´ıosSA,AlvarezH,AguileraF.Topic-based
socialnetworkanalysisforvirtualcommunitiesofinterestsinthedarkweb.In:Proceedingofthe2010ACMSIGKDDWorkshoponIntelligenceandSecurityInformatics.NewYork,USA:ACM,2010.23−3153ZhengGQ,GuoGW,YangLC,XuSL,BaoSH,Su
Z,HanDY,YuY.Miningtopicsonparticipationsforcommunitydiscovery.In:Proceedingsofthe34thInter-nationalACMSIGIRConferenceonResearchandDevel-opmentinInformationRetrieval.NewYork,USA:ACM,2011.445−45454ChahalP,SinghM,KumarS.Anontologybasedapproach
forfindingsemanticsimilaritybetweenwebdocuments.In-ternationalJournalofCurrentEngineeringandTechnology,2013,3(5):1925−193155KleinbergJM.Authoritativesourcesinahyperlinkedenvi-ronment.JournaloftheACM,1999,46(5):604−632
10期辛宇等:基于话题概率模型的语义社区发现方法研究1709
56KempC,TenenbaumJB.Learningsystemsofconcepts
withaninfiniterelationalmodel.In:Proceedingofthe21stNationalConferenceonArtificialIntelligence.MenloPark,Canada:AAAI,2006.1−1557LongB,ZhangZM,YuPS.Aprobabilisticframework
forrelationalclustering.In:Proceedingsofthe13thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork,USA:ACM,2007.470−47958ZhuSH,YuK,ChiY,GongYH.Combiningcontentand
linkforclassificationusingmatrixfactorization.In:Pro-ceedingsofthe30thAnnualInternationalACMSIGIRCon-ferenceonResearchandDevelopmentinInformationRe-trieval.NewYork,USA:ACM,2007.487−49459XuW,LiuX,GongYH.Documentclusteringbasedonnon-negativematrixfactorization.In:Proceedingsofthe26thannualinternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.NewYork,USA:ACM,2003.267−27360WangF,LiT,WangX,ZhuSG,DingC.Communitydis-coveryusingnonnegativematrixfactorization.DataMiningandKnowledgeDiscovery,2011,22(3):493−52161NallapatiR,CohenW.Link-PLSA-LDA:anewunsuper-visedmodelfortopicsandinfluenceinblogs.In:Proceedingofthe2ndInternationalConferenceonWeblogsandSocialMedia.Piscataway,USA:AAAI,2008.1−1262NallapatiRM,AhmedA,XingEP,CohenWW.Joint
latenttopicmodelsfortextandcitations.In:Proceed-ingsofthe14thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork,USA:ACM,2008.542−55063YinZJ,CaoLL,GuQQ,HanJW.Latentcommu-nitytopicanalysis:integrationofcommunitydiscoverywithtopicmodeling.ACMTransactionsonIntelligentSystemsandTechnology,2012,3(4):63−6364ChaY,ChoJ.Social-networkanalysisusingtopicmodels.
In:Proceedingsofthe35thInternationalACMSIGIRCon-ferenceonResearchandDevelopmentinInformationRe-trieval.NewYork,USA:ACM,2012.565−57465HuB,SongZ,EsterM.Userfeaturesandsocialnetworksfor
topicmodelinginonlinesocialmedia.In:Proceedingofthe2012InternationalConferenceonAdvancesinSocialNet-worksAnalysisandMining.WashingtonD.C.,USA:ACM,2012.202−20966NatarajanN,SenP,ChaojiV.Communitydetectionin
content-sharingsocialnetworks.In:Proceedingsofthe2013IEEE/ACMInternationalConferenceonAdvancesinSo-cialNetworksAnalysisandMining.NewYork,USA:ACM,2013.82−8967EvansTS,LambiotteR.Linegraphs,linkpartitions,and
overlappingcommunities.PhysicalReviewE,2009,80(1):01610568NowickiK,SnijdersTAB.Estimationandpredictionfor
stochasticblockstructures.JournaloftheAmericanStatis-ticalAssociation,2001,96(455):1077−108769JamaliM,HuangTL,EsterM.Ageneralizedstochastic
blockmodelforrecommendationinsocialratingnetworks.In:Proceedingsofthe5thACMConferenceonRecom-menderSystems.NewYork,USA:ACM,2011.53−6070WangXR,MohantyN,McCallumA.Groupandtopicdis-coveryfromrelationsandtext.In:Proceedingsofthe3rdInternationalWorkshoponLinkDiscovery.NewYork,USA:ACM,2005.28−35
71ZhouD,ManavogluE,LiJ,GilesCL,ZhaHY.Probabilis-ticmodelsfordiscoveringe-communities.In:Proceedingsofthe15thInternationalConferenceonWorldWideWeb.NewYork,USA:ACM,2006.173−18272ZhangHZ,QiuBJ,GilesCL,FoleyHC,YenJ.AnLDA-basedcommunitystructurediscoveryapproachforlarge-scalesocialnetworks.In:Proceedingofthe2007IEEEIntel-ligenceandSecurityInformatics.NewBrunswick,NJ,USA:IEEE,2007.200−20773ZhangHZ,GilesCL,FoleyHC,YenH.Probabilisticcom-munitydiscoveryusinghierarchicallatentgaussianmixturemodel.In:Proceedingofthe22ndNationalConferenceonArtificialIntelligence.MenloPark,Canada:AAAI,2007.663−66874ZhangHZ,LiW,WangXR,GilesCL,FoleyHC,Yen
J.HSN-PAM:findinghierarchicalprobabilisticgroupsfromlarge-scalenetworks.In:Proceedingofthe7thIEEEInter-nationalConferenceonDataMiningWorkshops.Omaha,NE,USA:IEEE,2007.27−3275SachanM,ContractorD,FaruquieT,SubramaniamV.
Probabilisticmodelfordiscoveringtopicbasedcommunitiesinsocialnetworks.In:Proceedingsofthe20thACMInter-nationalConferenceonInformationandKnowledgeMan-agement.NewYork,USA:ACM,2011.2349−235276HendersonK,Eliassi-RadT.Applyinglatentdirichletallo-cationtogroupdiscoveryinlargegraphs.In:Proceedingsofthe2009ACMSymposiumonAppliedComputing.NewYork,USA:ACM,2009.1456−146177HendersonK,Elisssi-RadT,PapadimitriouS,FaloutsosC.
HCDF:ahybridcommunitydiscoveryframework.In:Pro-ceedingsofthe2010SIAMInternationalConferenceonDataMining.Columbus,Ohio,USA:SIAM,2010.754−76578KumarR,NovakJ,TomkinsA.Structureandevolutionof
onlinesocialnetworks.LinkMining:Models,AlgorithmsandApplications.NewYork:Springer,2010.337−35779KwakH,LeeC,ParkH,MoonS.WhatisTwitter,asocial
networkoranewsmedia?In:Proceedingsofthe19thIn-ternationalWorldWideWebConferenceSeries.NewYork,USA:ACM,2010.591−60080SachanM,ContractorD,FaruquieTA,SubramaniamLV.
Usingcontentandinteractionsfordiscoveringcommunitiesinsocialnetworks.In:Proceedingsofthe21stInternationalConferenceonWorldWideWeb.NewYork,USA:ACM,2012.331−34081XinYu,YangJing,XieZhi-Qiang.Anoverlappingsemantic
communitystructuredetectingalgorithmbylabelpropaga-tion.ActaAutomaticaSinica,2014,40(10):2262−2275(辛宇,杨静,谢志强.基于标签传播的语义重叠社区发现算法.自动化学报,2014,40(10):2262−2275)82XinYu,YangJing,XieZhi-Qiang.Anoverlappingcommu-nitystructuredetectingalgorithminsemanticsocialnet-workbasedontheblockfield.ActaAutomaticaSinica,2015,41(2):362−375
(辛宇,杨静,谢志强.一种面向语义重叠社区发现的Block场取样算法.自动化学报,2015,41(2):362−375)83XinY,YangJ,XieZQ.Asemanticoverlappingcommunity
detectionalgorithmbasedonfieldsampling.ExpertSystemswithApplications,2015,42(1):366−37584XinY,YangJ,XieZQ,ZhangJP.Anoverlappingsemantic
communitydetectionalgorithmbaseontheARTsmultiplesamplingmodels.ExpertSystemswithApplications,2015,42(7):3420−3432
1710自动化学报41卷
85NicosiaV,MangioniG,CarchioloV,MalgeriM.Extending
thedefinitionofmodularitytodirectedgraphswithoverlap-pingcommunities.JournalofStatisticalMechanics:TheoryandExperiment,2009,(3):P03024
86NewmanMEJ,GirvanM.Findingandevaluatingcommu-nitystructureinnetworks.PhysicalReviewE,2004,69(2):026113
87JavaA,JoshiA,FininT.Detectingcommmunitiesviasi-multaneousclusteringofgraphsandfolksonomies.In:Pro-ceedingsofthe10thWorkshoponWebMiningandWebUsageAnalysis.NewYork,USA:ACM2008.23−32
88ChenS,CowanCFN,GrantPM.Orthogonalleastsquares
learningalgorithmforradialbasisfunctionnetworks.IEEETransactionsonNeuralNetworks,1991,2(2):302−30989ZhaoZY,FengSZ,WangQL,HuangZX,GrahamJW,
FanJP.Topicorientedcommunitydetectionthroughso-cialobjectsandlinkanalysisinsocialnetwork.Knowledge-BasedSystems,2012,26:164−173
90ZhuXJ,GhahramaniZ,LaffertyJ.Semi-supervisedlearn-ingusingGaussianfieldsandharmonicfunctions.In:Pro-ceedingsofthe20ndInternationalConferenceonMa-chineLearning.WashingtonD.C.,USA:MITPress,2003.912−919
91CruzJD,BothorelC,PouletF.Entropybasedcommunity
detectioninaugmentedsocialnetworks.In:Proceedingsofthe2011InternationalConferenceonComputationalAs-pectsofSocialNetwork.Salamanca,Apain:IEEE,2011.163−168
92StrehlA,GhoshJ.Clusterensembles—aknowledgereuse
frameworkforcombiningmultiplepartitions.TheJournalofMachineLearningResearch,2003,3:583−61793RawashdehA,RawashdehM,D´ıazI,RalescuA.Measures
ofsemanticsimilarityofnodesinasocialnetwork.In:Pro-ceedingofthe15thInformationProcessingandManage-mentofUncertaintyinKnowledge-BasedSystems.Piscat-away,USA:IEEE,2014.76−85
94AkcoraCG,CarminatiB,FerrariE.Networkandprofile
basedmeasuresforusersimilaritiesonsocialnetworks.In:Proceedingofthe2011IEEEInternationalConferenceonInformationReuseandIntegration.LasVegas,NV,USA:IEEE,2011.292−298
95DeshpandeM,KarypisG.Item-basedtop-Nrecommenda-tionalgorithms.ACMTransactionsonInformationSystems,2004,22(1):143−177
96DemirGN,UyarAS,Og¨¨ud¨uc¨uSG.Graph-basedsequence
clusteringthroughmultiobjectiveevolutionaryalgorithmsforwebrecommendersystems.In:Proceedingsofthe9thAnnualConferenceonGeneticandEvolutionaryComputa-tion.NewYork,USA:ACM,2007.1943−1950
97RousseeuwPJ.Silhouettes:agraphicalaidtotheinterpre-tationandvalidationofclusteranalysis.JournalofCompu-tationalandAppliedMathematics,1987,20:53−65
98KannanR,VempalaS,VettaA.Onclusterings:good,bad
andspectral.JournaloftheACM,2004,51(3):497−51599RadicchiF,CastellanoC,CecconiF,LoretoV,ParisiD.
Definingandidentifyingcommunitiesinnetworks.Proceed-ingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2004,101(9):2658−2663
100ShiJ,MalikJ.Normalizedcutsandimagesegmentation.
IEEETransactionsonPatternAnalysisandMachineIntel-ligence,2000,22(8):888−905101LancichinettiA,FortunatoS,RadicchiF.Benchmark
graphsfortestingcommunitydetectionalgorithms.Phys-icalReviewE,2008,78(4):046110102LancichinettiA,FortunatoS.Benchmarksfortestingcom-munitydetectionalgorithmsondirectedandweightedgraphswithoverlappingcommunities.PhysicalReviewE,2009,80(1):016118103LindgrenF,RueH,Lindstr¨omJ.Anexplicitlinkbetween
GaussianfieldsandGaussianMarkovrandomfields:thestochasticpartialdifferentialequationapproach.JournaloftheRoyalStatisticalSociety:SeriesB(StatisticalMethod-ology),2011,73(4):423−498
辛宇哈尔滨理工大学计算机科学与技术学院讲师.2015年获得哈尔滨工程大学计算机应用技术博士学位.主要研究方向为数据库与知识工程.E-mail:xinyu@hrbeu.edu.cn
(XINYuPh.D.,lecturerattheCol-legeofComputerScienceandTechnol-ogy,HarbinUniversityofScienceand
Technology.HereceivedhisPh.D.degreefromHarbinEn-gineeringUniversityin2015.Hisresearchinterestcoversdatabaseandknowledgeengineering.)
谢志强哈尔滨理工大学计算机科学与技术学院教授.主要研究方向为数据库与知识工程.
E-mail:xiezhiqiang@hrbust.edu.cn(XIEZhi-QiangProfessorattheCollegeofComputerScienceandTech-nology,HarbinUniversityofScienceandTechnology.Hisresearchinterest
coversdatabaseandknowledgeengineering.)
杨静哈尔滨工程大学计算机科学与技术学院教授.主要研究方向为数据库与知识工程.本文通信作者.
E-mail:yangjing@hrbeu.edu.cn
(YANGJingProfessorattheCol-legeofComputerScienceandTech-nology,HarbinEngineeringUniversity.Herresearchinterestcoversdatabase
andknowledgeengineering.Correspondingauthorofthispaper.)
因篇幅问题不能全部显示，请点此查看更多更全内容