浅论SocialNetwork和GraphMining的应用和机器学习技术

./浅析SocialNetwork和GraphMining的应用和机器学习技术--吴斌224227[摘要]随着移动互联网的到来,UCG〔用户产生内容的不断发展,社交网络〔SocialNetwork已经不断普及并深入人心,用户可以随时随地在网络上分享内容,由此产生了海量的用户数据,面对大数据时代的来临,复杂多变的SocialNetwork数据是有很多实用价值有待挖掘的。本文通过对专家协作和主题的关系发现系统/和其相关的论文材料进行分析,讨论SocialNetwork和GraphMining相关的机器学习技术,为基于关系图谱的SocialNetwork数据挖掘和应用提供一些思路。随着Facebook,Twitter,新浪微博,LinkedIn等社交媒体网站的流行,对SocialNetwork的数据挖掘是近几年的一个技术热点,而SocialNetwork中的用户与用户,用户与主题,用户与活动的关系网络就是一种图结构的海量数据,所以SocialNetwork的分析中一个主要方向就是针对关系图的GraphMining。而针对SocialNetwork和GraphMining,传统计算机技术面临很多挑战,比如,图节点和边的数据已经达到数十亿的数据级别,海量图数据的分析计算和检索比较困难。而且,图数据结构是很复杂的,基于图结构的数据构建算法模型复杂度很高,比如,构建SocialNetwork影响力传播的动态传播模型是很复杂的。还有,海量数据处理,势必带来并行化处理的要求,而图数据的关联性大,图数据分割复杂,导致基于图数据的分析算法并行化难度很大。面对这些挑战和困难,学术界已经有一些研究和实验,以下介绍的arnetminer系统的算法介绍,可以为基于图数据的SocialNetwork和GraphMining工作提供一些方法和思路。先来看一下,什么是图数据挖掘？图是一种很重要的数据结构,关于图数据的数据挖掘有很多方向和应用领域,简介如下：纯理论的图数据挖掘中一个热点是频繁子图的数据挖掘〔FrequentSubgraphMining,即从图数据集合中寻找出现次数不少于最小支持度的子图。这个领域中有很多算法,AMG,FSG,FFSM,gSpan,SUBDUE,GBI,SIGMAR,GREW等等。本文分析的是面向SocialNetwork的图数据挖掘,主要关注的是社群发现〔CommunityDetection,专家发现和排名〔Ranking,结构洞分析〔StructureHole,影响力分析〔InfluenceAnalysis,社交关系〔SocialTie,还有多种不同类型网络的数据集成等问题。首先,讨论一下SocialNetwork数据挖掘的应用方式：基于SocialNetwork的意见传播,动态网络影响力传播分析。举个例子：华为发布P6手机后,需要做媒体宣传推广,假设领导给定100万预算,需要利用新浪微博做P6手机推广,那么市场人员最关心的问题就是,预计每个新浪博主的宣传费是1万元,怎么用这100万预算,在新浪微博上把P6手机的推广做的效果最好?具体化描述就是：基于新浪微博数据的用户SocialNetwork中,需要找到Topic是"手机"相关的100个人〔节点,这100个节点的影响力传播范围最大。这就是SocialNetwork分析的典型应用之一,需要分析相关主题图结构数据中的"意见领袖","结构洞"〔即跨越不同社群子网络的桥接节点,"动态网络影响力传播模型"等问题。类似的影响力传播图示：领域专家发现,排名。举个例子：公司需要招聘数据挖掘方面的专家和牛人,招聘人员最关心的问题是,怎么找到学术界最有影响力的专家,以及这些专家擅长的学术课题,研究的技术方向,主要参加哪些学术会议,发表哪些论问题,合作者有哪些？具体化描述就是：在某个学术主题Topic下,在相关论文,会议和作者构成的图数据中,找到专家的综合影响力分析排名,并找到专家与和合作者的关系,专家与研究课题,和相关学术会议的关系。〔注：学术界专家评价有一个重要的参数是H-index指数,H-index指发表N篇论文,每篇论文的引用数至少是N,他的H-index就是N。比如,数据挖掘领域专家排名：社交关系分析。按照SocialNetwork的六度空间理论,每两个人的关系一般只需要通过6个中间人就可以建立关系,所以社交媒体中,人们之间关系基本都可以组成网络结构。社交关系分析,典型的应用案例是：通过用户的电话记录,或者邮件记录,分析哪些人是你的家人,哪些人是你的同事,谁是谁的领导等关系。比如下图：相关主题的历史和趋势分析。某个主题,他的描述表达方式,在不同的时间,会有很多表达方式,会有一些相关的子主题,这些不同的表达方式或子主题就是针对某个主题的一个Topic演进关系图。比如：与DeepLearning相关的主题有Deeparchitecture,Deepbeliefnetwork,Neuralnetwork,Featureselection,Reinforcementlearning等,这些主题都与DeepLearning有着密切的关系,分析这些主题随着时间的变化可以看下图：基于地理位置的某领域专家分布分析。比如,公司想做某个领域的研究,并建立相关主题的研究所,就需要分析,哪些地区,这个领域的专家有哪些。比如,下图中我们看到DeepLearning方面,全球顶尖专家的分布和介绍：知识图谱的构建。知识图谱是Google,Baidu,Yahoo,SOSO等知名搜索引擎近几年新发展的技术。其核心是提供用户查询信息与相关知识的关系,直接通过图示的方法展现密切关联的信息,比仅仅提供网页链接,对用户而言,价值要大很多。而且,信息的关联就是知识的直接体现.所以,知识图谱被称作新一代的搜索引擎技术。比如,某明星最近有哪些热点新闻,并且与哪些人有哪些关系等等。腾讯的SOSO华尔兹提供的明星社交图谱就是一个典型应用：实际上,各大通信运营商已经开始关注社交网络的数据挖掘和应用。比如,中国移动已经在规划基于VGOP分析构建用户关系网,简介如下：通过以上的介绍,我们可以知道SocialNetwork和GraphMining的实用价值和应用场景。然后,我根据专家协作和主题的关系发现系统/,具体分析SocialNetwork和GraphMining的相关技术。该系统是清华的唐杰老师带领团队研发的针对学术专家研究分析的系统,唐杰老师是SocialNetwork领域学术界的大牛,这里可以看到SocialNetwork领域学术界的专家和发展趋势：Arnetminer系统是以学术论文为主要数据,进行专家排名,关系挖掘,学术主题相关性发现,历史趋势分析等课题进行研究的公开网站,上面的这些图就是该网站上截取的内容。该系统与华为公司有合作项目。唐杰老师有一个PPT"ComputationalModelsforSocialNetworks",对SocialNetwork的模型,算法和应用做了一个全面的总结,网上可以下载：我根据唐杰老师发表的相关论文进行技术分析。我分析的论文如下：1ExpertFindinginASocialNetworkJingZhang,JieTang,andJuanziLiDASFAA'2007,主要是对领域专家发现排名系统的模型算法进行说明。2TopiclevelexpertisesearchoverheterogeneousnetworksJieTang·JingZhang·RuomingJin·ZiYang·KekeCai·LiZhang·ZhongSuMLJ2011,主要是ArnetMiner系统构建和查询的模型进行详细说明,这篇论文很长,介绍很全面。3ArnetMiner:ExtractionandMiningofAcademicSocialNetworksJieTang,JingZhang,LiminYao,JuanziLi,LiZhang,ZhongSuKDD2008,主要是对于学术领域,ArnetMiner系统的信息抽取,名称消歧,数据集成等的模型和架构,ACT模型详细说明。与上一篇论文不同的是,上一篇很全面,这一片很详细,对核心的关系构建模型ACT,有详细的说明。4InferringSocialTiesacrossHeterogenousNetworksJieTang,TianchengLou,JonKleinbergWSDM'2012,主要是从不同类型的多个网络中,对用户信息进行集成Transfer学习。5SocialInfluenceAnalysisinLarge-scaleNetworksJieTang,JimengSun,ChiWangandZiYangKDD2009,主要是对网络节点影响力评估模型TAP进行详细说明。6SocialActionTrackingviaNoiseTolerantTime-varyingFactorGraphsChenhaoTan,JieTang,JimengSun,QuanLinandFengjiaoWangKDD2010,主要是针对基于时间段的网络影响力活动动态传播模型NTT-FGM进行详细说明。7>LearningtoInferSocialTiesinLargeNetworksWenbinTang,HongleiZhuang,andJieTangKDD2011,主要是使用半监督学习的方法进行自动添加关系label的模型PLP_FGM详细说明。8SAE:SocialAnalyticEngineforLargeNetworksYangYang,JianfeiWang,YutaoZhang,WeiChen,JingZhang,HongleiZhuang,ZhilinYang,BoMa,ZhanpengFang,SenWu,XiaoxiaoLi,DebingLiu,andJieTangKDD2013,主要是对ArnetMiner的新版本SAE平台框架进行说明,数据集成方面比较详细。同时,以上资料中还有介绍大规模分布式图数据挖掘的并行算法介绍。其他参考资料：THUKEG-SAE-D1-1,THUKEG-SAE-D3-12,THUKEG-SAE-C1-C2,THUKEG-SAE-B2等,不一一列举。ArnetMiner〔即SAE总体架构可以看以下几张图：下面介绍几个专题技术：社群发现〔CommunityDetection,即相关主题的图节点聚类。主要使用了FCM算法,即基于模糊集的均值聚类算法。与普通K-means聚类不同的是,每个点可以与多个类群建立关系,而且,每个关系有个叫"隶属度"的权重系数,范围是[0,1],0.8,0.5…等等,所以每个点有一个模糊分类子集,N个类的模糊子集形成隶属度矩阵,通过迭代方法求聚类中心点,得到N个社群聚类。专家排名：学术论文中,每篇文章的合作者,可以构成一个网络,而且这个网络,是基于该论文主题〔Topic的专家网络。所以,根据专家基本信息〔Profile给出初始分数〔Score,针对某个Topic的很多论文中的专家网络关系,基于类似GooglePageRank的算法,可以迭代地计算每个节点〔专家的排名。这也被称为基于传播的算法"apropagationbasedapproachforfindingexpertinasocialnetwork.",专家网络如下图：另外,H-index是学术界的比较重要的排名指数。针对论文和作者,会议构建TopicModel,专家查询时,要区分领域,需要把专家,论文,会议,分成不同的Topic进行查询。与业界流行的TopicModel算法,LatentDirichletAllocation<LDA>方法类似,参考了Author-Topic<AT>model模型,ArnetMiner提出了两种优化的模型,结合论文作者和会议,Author-Conference-Topic<ACT>model和结合论文引用的Citation-Tracing-Topic<CTT>model。这里的ACT模型是核心模型,论文中提到3种ACT模型的实现方法：Threedifferentstrategiesareemployedtoimplementthetopicmodel,Inthefirstmodel<ACT1,Figure6<a>>,eachauthorisassociatedwithamultinomialdistributionovertopicsandeachwordinapaperandtheconferencestampisgeneratedfromasampledtopic.Inthesecondmodel<ACT2,Figure6<b>>,eachauthor-conferencepairisassociatedwithamultinomialdistributionovertopicsandeachwordisthengeneratedfromasampledtopic.Inthethirdmodel<ACT3,Figure6<c>>,eachauthorisassociatedwithatopicdistributionandtheconferencestampisgeneratedaftertopicshavebeensampledforallwordtokensinapaper.对比languagemodel<LM>,Author-Topic<AT>model,LDA模型的论文数据测试结果如下：专家或Topic查询时,使用了迪科斯彻算法求图的最短关联路径〔Dijkstraalgorithmtofindtheshortestassociations。社交网络节点影响力的算法模型。ArnetMiner提出了TopicalAffinityPropagation<TAP>模型,基于Topic在Socialnetwork构建影响力模型。这个模型基于因子图〔FactorGraph,又称作TopicalFactorGraph<TFG>model,该模型图示如下：通过该模型计算SocialNetwork中,针对某主题〔Topic影响力最大节点的概率。该模型在实现时,基于一个逻辑回归的算法,计算每个节点的影响力分数〔influencescore,这是主要的衡量数据。"Finally,accordingtotheobtainedinfluencescoresandthetopicdistribution,wecaneasilygeneratethetopic-levelsocialinfluencegraphs."使用以上网络影响力算法模型在Socialnetwork中用于发现某个Topic的"意见领袖",进行测试对比的算法：Herewepresent3methodsforexpertidentification:1>PageRank+LanguageModeling<PR>,2>PageRankwithglobalInfluence<PRI>and3>PageRankwithtopic-basedinfluence<TPRI>.〔1是传统算法,2,3是基于影响力分数〔influencescore的PageRank。从这里看PageRank是网络节点影响力排名的核心算法。。结果如下：在一定时间段内,社交网络影响力传播的动态图模型算法。ArnetMiner提出了NoiseTolerantTime-varyingFactorGraphModel<NTT-FGM>模型,Attributeaugmentednetwork:TheattributeaugmentednetworkisdenotedasGt=<Vt,Et,Xt,Yt>,whereVtisthesetofusersandEtisthesetoflinksbetweenusersattimet,andXtrepresentstheattributematrixofallusersinthenetworkattimet,andYtrepresentsthesetofactionsofallusersattimet.〔动态网络定义,图节点边的状态+时间t+用户属性+活动该模型比较复杂,可以表现出SocialNetwork的网络动态模型,依据该模型可以对网络中的活动,进行预测,分析出下一时刻某活动主题在网络中的传播状态。我估计这个模型的实现类似于马尔科夫随机场的算法。细节还不是很清楚。对于网络中节点关系的自动标注。很多情况下,各种不同网络中的数据关系是未知的,或者只有小部分数据有关系标注〔Label,大部分数据是没有关系标注的。这就需要一些半自动的算法进行关系标注,ArnetMiner提出了一种半监督〔semi-supervised的算法Partially-labeledPairwiseFactorGraphModel<PLP-FGM>。图示如下：这里使用了信念传播网模型LoopyBeliefPropagation,使用牛顿-拉夫逊方法<Newton-Raphsonmethod>求解。不过,我觉得首先假设节点关系是有一定规律的,如不同时间打电话或发邮件的关系不同〔主观分析规则或从已有Label数据分析得出规则,这个是关键。该模型与支持向量机SVM,转移概率流图TPFG方法的对比测试：不同网络系统中的数据对齐。相同的名称实体在不同的网络中名称可能是不同的。ArnetMiner提出一种方法进行数据对齐和数据集成："inthefirststage,wecalculatetherelevancescoreofanentitytothequeryqbyutilizinglanguagemodel;inthesecondstage,weselectthetop-rankedentitiesascandidatesandconstructaheterogeneoussubgraph."参看"SAE:SocialAnalyticEngineforLargeNetworks"。图模型算法的并行化分