淺論SocialNetwork和GraphMining的應(yīng)用和機(jī)器學(xué)習(xí)技術(shù)

./淺析SocialNetwork和GraphMining的應(yīng)用和機(jī)器學(xué)習(xí)技術(shù)--吳斌224227[摘要]隨著移動互聯(lián)網(wǎng)的到來,UCG〔用戶產(chǎn)生內(nèi)容的不斷發(fā)展,社交網(wǎng)絡(luò)〔SocialNetwork已經(jīng)不斷普及并深入人心,用戶可以隨時隨地在網(wǎng)絡(luò)上分享內(nèi)容,由此產(chǎn)生了海量的用戶數(shù)據(jù),面對大數(shù)據(jù)時代的來臨,復(fù)雜多變的SocialNetwork數(shù)據(jù)是有很多實(shí)用價值有待挖掘的。本文通過對專家協(xié)作和主題的關(guān)系發(fā)現(xiàn)系統(tǒng)/和其相關(guān)的論文材料進(jìn)行分析,討論SocialNetwork和GraphMining相關(guān)的機(jī)器學(xué)習(xí)技術(shù),為基于關(guān)系圖譜的SocialNetwork數(shù)據(jù)挖掘和應(yīng)用提供一些思路。隨著Facebook,Twitter,新浪微博,LinkedIn等社交媒體網(wǎng)站的流行,對SocialNetwork的數(shù)據(jù)挖掘是近幾年的一個技術(shù)熱點(diǎn),而SocialNetwork中的用戶與用戶,用戶與主題,用戶與活動的關(guān)系網(wǎng)絡(luò)就是一種圖結(jié)構(gòu)的海量數(shù)據(jù),所以SocialNetwork的分析中一個主要方向就是針對關(guān)系圖的GraphMining。而針對SocialNetwork和GraphMining,傳統(tǒng)計算機(jī)技術(shù)面臨很多挑戰(zhàn),比如,圖節(jié)點(diǎn)和邊的數(shù)據(jù)已經(jīng)達(dá)到數(shù)十億的數(shù)據(jù)級別,海量圖數(shù)據(jù)的分析計算和檢索比較困難。而且,圖數(shù)據(jù)結(jié)構(gòu)是很復(fù)雜的,基于圖結(jié)構(gòu)的數(shù)據(jù)構(gòu)建算法模型復(fù)雜度很高,比如,構(gòu)建SocialNetwork影響力傳播的動態(tài)傳播模型是很復(fù)雜的。還有,海量數(shù)據(jù)處理,勢必帶來并行化處理的要求,而圖數(shù)據(jù)的關(guān)聯(lián)性大,圖數(shù)據(jù)分割復(fù)雜,導(dǎo)致基于圖數(shù)據(jù)的分析算法并行化難度很大。面對這些挑戰(zhàn)和困難,學(xué)術(shù)界已經(jīng)有一些研究和實(shí)驗(yàn),以下介紹的arnetminer系統(tǒng)的算法介紹,可以為基于圖數(shù)據(jù)的SocialNetwork和GraphMining工作提供一些方法和思路。先來看一下,什么是圖數(shù)據(jù)挖掘？圖是一種很重要的數(shù)據(jù)結(jié)構(gòu),關(guān)于圖數(shù)據(jù)的數(shù)據(jù)挖掘有很多方向和應(yīng)用領(lǐng)域,簡介如下：純理論的圖數(shù)據(jù)挖掘中一個熱點(diǎn)是頻繁子圖的數(shù)據(jù)挖掘〔FrequentSubgraphMining,即從圖數(shù)據(jù)集合中尋找出現(xiàn)次數(shù)不少于最小支持度的子圖。這個領(lǐng)域中有很多算法,AMG,FSG,FFSM,gSpan,SUBDUE,GBI,SIGMAR,GREW等等。本文分析的是面向SocialNetwork的圖數(shù)據(jù)挖掘,主要關(guān)注的是社群發(fā)現(xiàn)〔CommunityDetection,專家發(fā)現(xiàn)和排名〔Ranking,結(jié)構(gòu)洞分析〔StructureHole,影響力分析〔InfluenceAnalysis,社交關(guān)系〔SocialTie,還有多種不同類型網(wǎng)絡(luò)的數(shù)據(jù)集成等問題。首先,討論一下SocialNetwork數(shù)據(jù)挖掘的應(yīng)用方式：基于SocialNetwork的意見傳播,動態(tài)網(wǎng)絡(luò)影響力傳播分析。舉個例子：華為發(fā)布P6手機(jī)后,需要做媒體宣傳推廣,假設(shè)領(lǐng)導(dǎo)給定100萬預(yù)算,需要利用新浪微博做P6手機(jī)推廣,那么市場人員最關(guān)心的問題就是,預(yù)計每個新浪博主的宣傳費(fèi)是1萬元,怎么用這100萬預(yù)算,在新浪微博上把P6手機(jī)的推廣做的效果最好?具體化描述就是：基于新浪微博數(shù)據(jù)的用戶SocialNetwork中,需要找到Topic是"手機(jī)"相關(guān)的100個人〔節(jié)點(diǎn),這100個節(jié)點(diǎn)的影響力傳播范圍最大。這就是SocialNetwork分析的典型應(yīng)用之一,需要分析相關(guān)主題圖結(jié)構(gòu)數(shù)據(jù)中的"意見領(lǐng)袖","結(jié)構(gòu)洞"〔即跨越不同社群子網(wǎng)絡(luò)的橋接節(jié)點(diǎn),"動態(tài)網(wǎng)絡(luò)影響力傳播模型"等問題。類似的影響力傳播圖示：領(lǐng)域?qū)＜野l(fā)現(xiàn),排名。舉個例子：公司需要招聘數(shù)據(jù)挖掘方面的專家和牛人,招聘人員最關(guān)心的問題是,怎么找到學(xué)術(shù)界最有影響力的專家,以及這些專家擅長的學(xué)術(shù)課題,研究的技術(shù)方向,主要參加哪些學(xué)術(shù)會議,發(fā)表哪些論問題,合作者有哪些？具體化描述就是：在某個學(xué)術(shù)主題Topic下,在相關(guān)論文,會議和作者構(gòu)成的圖數(shù)據(jù)中,找到專家的綜合影響力分析排名,并找到專家與和合作者的關(guān)系,專家與研究課題,和相關(guān)學(xué)術(shù)會議的關(guān)系?！沧ⅲ簩W(xué)術(shù)界專家評價有一個重要的參數(shù)是H-index指數(shù),H-index指發(fā)表N篇論文,每篇論文的引用數(shù)至少是N,他的H-index就是N。比如,數(shù)據(jù)挖掘領(lǐng)域?qū)＜遗琶荷缃魂P(guān)系分析。按照SocialNetwork的六度空間理論,每兩個人的關(guān)系一般只需要通過6個中間人就可以建立關(guān)系,所以社交媒體中,人們之間關(guān)系基本都可以組成網(wǎng)絡(luò)結(jié)構(gòu)。社交關(guān)系分析,典型的應(yīng)用案例是：通過用戶的電話記錄,或者郵件記錄,分析哪些人是你的家人,哪些人是你的同事,誰是誰的領(lǐng)導(dǎo)等關(guān)系。比如下圖：相關(guān)主題的歷史和趨勢分析。某個主題,他的描述表達(dá)方式,在不同的時間,會有很多表達(dá)方式,會有一些相關(guān)的子主題,這些不同的表達(dá)方式或子主題就是針對某個主題的一個Topic演進(jìn)關(guān)系圖。比如：與DeepLearning相關(guān)的主題有Deeparchitecture,Deepbeliefnetwork,Neuralnetwork,Featureselection,Reinforcementlearning等,這些主題都與DeepLearning有著密切的關(guān)系,分析這些主題隨著時間的變化可以看下圖：基于地理位置的某領(lǐng)域?qū)＜曳植挤治觥１热?公司想做某個領(lǐng)域的研究,并建立相關(guān)主題的研究所,就需要分析,哪些地區(qū),這個領(lǐng)域的專家有哪些。比如,下圖中我們看到DeepLearning方面,全球頂尖專家的分布和介紹：知識圖譜的構(gòu)建。知識圖譜是Google,Baidu,Yahoo,SOSO等知名搜索引擎近幾年新發(fā)展的技術(shù)。其核心是提供用戶查詢信息與相關(guān)知識的關(guān)系,直接通過圖示的方法展現(xiàn)密切關(guān)聯(lián)的信息,比僅僅提供網(wǎng)頁鏈接,對用戶而言,價值要大很多。而且,信息的關(guān)聯(lián)就是知識的直接體現(xiàn).所以,知識圖譜被稱作新一代的搜索引擎技術(shù)。比如,某明星最近有哪些熱點(diǎn)新聞,并且與哪些人有哪些關(guān)系等等。騰訊的SOSO華爾茲提供的明星社交圖譜就是一個典型應(yīng)用：實(shí)際上,各大通信運(yùn)營商已經(jīng)開始關(guān)注社交網(wǎng)絡(luò)的數(shù)據(jù)挖掘和應(yīng)用。比如,中國移動已經(jīng)在規(guī)劃基于VGOP分析構(gòu)建用戶關(guān)系網(wǎng),簡介如下：通過以上的介紹,我們可以知道SocialNetwork和GraphMining的實(shí)用價值和應(yīng)用場景。然后,我根據(jù)專家協(xié)作和主題的關(guān)系發(fā)現(xiàn)系統(tǒng)/,具體分析SocialNetwork和GraphMining的相關(guān)技術(shù)。該系統(tǒng)是清華的唐杰老師帶領(lǐng)團(tuán)隊(duì)研發(fā)的針對學(xué)術(shù)專家研究分析的系統(tǒng),唐杰老師是SocialNetwork領(lǐng)域?qū)W術(shù)界的大牛,這里可以看到SocialNetwork領(lǐng)域?qū)W術(shù)界的專家和發(fā)展趨勢：Arnetminer系統(tǒng)是以學(xué)術(shù)論文為主要數(shù)據(jù),進(jìn)行專家排名,關(guān)系挖掘,學(xué)術(shù)主題相關(guān)性發(fā)現(xiàn),歷史趨勢分析等課題進(jìn)行研究的公開網(wǎng)站,上面的這些圖就是該網(wǎng)站上截取的內(nèi)容。該系統(tǒng)與華為公司有合作項(xiàng)目。唐杰老師有一個PPT"ComputationalModelsforSocialNetworks",對SocialNetwork的模型,算法和應(yīng)用做了一個全面的總結(jié),網(wǎng)上可以下載：我根據(jù)唐杰老師發(fā)表的相關(guān)論文進(jìn)行技術(shù)分析。我分析的論文如下：1ExpertFindinginASocialNetworkJingZhang,JieTang,andJuanziLiDASFAA'2007,主要是對領(lǐng)域?qū)＜野l(fā)現(xiàn)排名系統(tǒng)的模型算法進(jìn)行說明。2TopiclevelexpertisesearchoverheterogeneousnetworksJieTang·JingZhang·RuomingJin·ZiYang·KekeCai·LiZhang·ZhongSuMLJ2011,主要是ArnetMiner系統(tǒng)構(gòu)建和查詢的模型進(jìn)行詳細(xì)說明,這篇論文很長,介紹很全面。3ArnetMiner:ExtractionandMiningofAcademicSocialNetworksJieTang,JingZhang,LiminYao,JuanziLi,LiZhang,ZhongSuKDD2008,主要是對于學(xué)術(shù)領(lǐng)域,ArnetMiner系統(tǒng)的信息抽取,名稱消歧,數(shù)據(jù)集成等的模型和架構(gòu),ACT模型詳細(xì)說明。與上一篇論文不同的是,上一篇很全面,這一片很詳細(xì),對核心的關(guān)系構(gòu)建模型ACT,有詳細(xì)的說明。4InferringSocialTiesacrossHeterogenousNetworksJieTang,TianchengLou,JonKleinbergWSDM'2012,主要是從不同類型的多個網(wǎng)絡(luò)中,對用戶信息進(jìn)行集成Transfer學(xué)習(xí)。5SocialInfluenceAnalysisinLarge-scaleNetworksJieTang,JimengSun,ChiWangandZiYangKDD2009,主要是對網(wǎng)絡(luò)節(jié)點(diǎn)影響力評估模型TAP進(jìn)行詳細(xì)說明。6SocialActionTrackingviaNoiseTolerantTime-varyingFactorGraphsChenhaoTan,JieTang,JimengSun,QuanLinandFengjiaoWangKDD2010,主要是針對基于時間段的網(wǎng)絡(luò)影響力活動動態(tài)傳播模型NTT-FGM進(jìn)行詳細(xì)說明。7>LearningtoInferSocialTiesinLargeNetworksWenbinTang,HongleiZhuang,andJieTangKDD2011,主要是使用半監(jiān)督學(xué)習(xí)的方法進(jìn)行自動添加關(guān)系label的模型PLP_FGM詳細(xì)說明。8SAE:SocialAnalyticEngineforLargeNetworksYangYang,JianfeiWang,YutaoZhang,WeiChen,JingZhang,HongleiZhuang,ZhilinYang,BoMa,ZhanpengFang,SenWu,XiaoxiaoLi,DebingLiu,andJieTangKDD2013,主要是對ArnetMiner的新版本SAE平臺框架進(jìn)行說明,數(shù)據(jù)集成方面比較詳細(xì)。同時,以上資料中還有介紹大規(guī)模分布式圖數(shù)據(jù)挖掘的并行算法介紹。其他參考資料：THUKEG-SAE-D1-1,THUKEG-SAE-D3-12,THUKEG-SAE-C1-C2,THUKEG-SAE-B2等,不一一列舉。ArnetMiner〔即SAE總體架構(gòu)可以看以下幾張圖：下面介紹幾個專題技術(shù)：社群發(fā)現(xiàn)〔CommunityDetection,即相關(guān)主題的圖節(jié)點(diǎn)聚類。主要使用了FCM算法,即基于模糊集的均值聚類算法。與普通K-means聚類不同的是,每個點(diǎn)可以與多個類群建立關(guān)系,而且,每個關(guān)系有個叫"隸屬度"的權(quán)重系數(shù),范圍是[0,1],0.8,0.5…等等,所以每個點(diǎn)有一個模糊分類子集,N個類的模糊子集形成隸屬度矩陣,通過迭代方法求聚類中心點(diǎn),得到N個社群聚類。專家排名：學(xué)術(shù)論文中,每篇文章的合作者,可以構(gòu)成一個網(wǎng)絡(luò),而且這個網(wǎng)絡(luò),是基于該論文主題〔Topic的專家網(wǎng)絡(luò)。所以,根據(jù)專家基本信息〔Profile給出初始分?jǐn)?shù)〔Score,針對某個Topic的很多論文中的專家網(wǎng)絡(luò)關(guān)系,基于類似GooglePageRank的算法,可以迭代地計算每個節(jié)點(diǎn)〔專家的排名。這也被稱為基于傳播的算法"apropagationbasedapproachforfindingexpertinasocialnetwork.",專家網(wǎng)絡(luò)如下圖：另外,H-index是學(xué)術(shù)界的比較重要的排名指數(shù)。針對論文和作者,會議構(gòu)建TopicModel,專家查詢時,要區(qū)分領(lǐng)域,需要把專家,論文,會議,分成不同的Topic進(jìn)行查詢。與業(yè)界流行的TopicModel算法,LatentDirichletAllocation<LDA>方法類似,參考了Author-Topic<AT>model模型,ArnetMiner提出了兩種優(yōu)化的模型,結(jié)合論文作者和會議,Author-Conference-Topic<ACT>model和結(jié)合論文引用的Citation-Tracing-Topic<CTT>model。這里的ACT模型是核心模型,論文中提到3種ACT模型的實(shí)現(xiàn)方法：Threedifferentstrategiesareemployedtoimplementthetopicmodel,Inthefirstmodel<ACT1,Figure6<a>>,eachauthorisassociatedwithamultinomialdistributionovertopicsandeachwordinapaperandtheconferencestampisgeneratedfromasampledtopic.Inthesecondmodel<ACT2,Figure6<b>>,eachauthor-conferencepairisassociatedwithamultinomialdistributionovertopicsandeachwordisthengeneratedfromasampledtopic.Inthethirdmodel<ACT3,Figure6<c>>,eachauthorisassociatedwithatopicdistributionandtheconferencestampisgeneratedaftertopicshavebeensampledforallwordtokensinapaper.對比languagemodel<LM>,Author-Topic<AT>model,LDA模型的論文數(shù)據(jù)測試結(jié)果如下：專家或Topic查詢時,使用了迪科斯徹算法求圖的最短關(guān)聯(lián)路徑〔Dijkstraalgorithmtofindtheshortestassociations。社交網(wǎng)絡(luò)節(jié)點(diǎn)影響力的算法模型。ArnetMiner提出了TopicalAffinityPropagation<TAP>模型,基于Topic在Socialnetwork構(gòu)建影響力模型。這個模型基于因子圖〔FactorGraph,又稱作TopicalFactorGraph<TFG>model,該模型圖示如下：通過該模型計算SocialNetwork中,針對某主題〔Topic影響力最大節(jié)點(diǎn)的概率。該模型在實(shí)現(xiàn)時,基于一個邏輯回歸的算法,計算每個節(jié)點(diǎn)的影響力分?jǐn)?shù)〔influencescore,這是主要的衡量數(shù)據(jù)。"Finally,accordingtotheobtainedinfluencescoresandthetopicdistribution,wecaneasilygeneratethetopic-levelsocialinfluencegraphs."使用以上網(wǎng)絡(luò)影響力算法模型在Socialnetwork中用于發(fā)現(xiàn)某個Topic的"意見領(lǐng)袖",進(jìn)行測試對比的算法：Herewepresent3methodsforexpertidentification:1>PageRank+LanguageModeling<PR>,2>PageRankwithglobalInfluence<PRI>and3>PageRankwithtopic-basedinfluence<TPRI>.〔1是傳統(tǒng)算法,2,3是基于影響力分?jǐn)?shù)〔influencescore的PageRank。從這里看PageRank是網(wǎng)絡(luò)節(jié)點(diǎn)影響力排名的核心算法。。結(jié)果如下：在一定時間段內(nèi),社交網(wǎng)絡(luò)影響力傳播的動態(tài)圖模型算法。ArnetMiner提出了NoiseTolerantTime-varyingFactorGraphModel<NTT-FGM>模型,Attributeaugmentednetwork:TheattributeaugmentednetworkisdenotedasGt=<Vt,Et,Xt,Yt>,whereVtisthesetofusersandEtisthesetoflinksbetweenusersattimet,andXtrepresentstheattributematrixofallusersinthenetworkattimet,andYtrepresentsthesetofactionsofallusersattimet.〔動態(tài)網(wǎng)絡(luò)定義,圖節(jié)點(diǎn)邊的狀態(tài)+時間t+用戶屬性+活動該模型比較復(fù)雜,可以表現(xiàn)出SocialNetwork的網(wǎng)絡(luò)動態(tài)模型,依據(jù)該模型可以對網(wǎng)絡(luò)中的活動,進(jìn)行預(yù)測,分析出下一時刻某活動主題在網(wǎng)絡(luò)中的傳播狀態(tài)。我估計這個模型的實(shí)現(xiàn)類似于馬爾科夫隨機(jī)場的算法。細(xì)節(jié)還不是很清楚。對于網(wǎng)絡(luò)中節(jié)點(diǎn)關(guān)系的自動標(biāo)注。很多情況下,各種不同網(wǎng)絡(luò)中的數(shù)據(jù)關(guān)系是未知的,或者只有小部分?jǐn)?shù)據(jù)有關(guān)系標(biāo)注〔Label,大部分?jǐn)?shù)據(jù)是沒有關(guān)系標(biāo)注的。這就需要一些半自動的算法進(jìn)行關(guān)系標(biāo)注,ArnetMiner提出了一種半監(jiān)督〔semi-supervised的算法Partially-labeledPairwiseFactorGraphModel<PLP-FGM>。圖示如下：這里使用了信念傳播網(wǎng)模型LoopyBeliefPropagation,使用牛頓-拉夫遜方法<Newton-Raphsonmethod>求解。不過,我覺得首先假設(shè)節(jié)點(diǎn)關(guān)系是有一定規(guī)律的,如不同時間打電話或發(fā)郵件的關(guān)系不同〔主觀分析規(guī)則或從已有Label數(shù)據(jù)分析得出規(guī)則,這個是關(guān)鍵。該模型與支持向量機(jī)SVM,轉(zhuǎn)移概率流圖TPFG方法的對比測試：不同網(wǎng)絡(luò)系統(tǒng)中的數(shù)據(jù)對齊。相同的名稱實(shí)體在不同的網(wǎng)絡(luò)中名稱可能是不同的。ArnetMiner提出一種方法進(jìn)行數(shù)據(jù)對齊和數(shù)據(jù)集成："inthefirststage,wecalculatetherelevancescoreofanentitytothequeryqbyutilizinglanguagemodel;inthesecondstage,weselectthetop-rankedentitiesascandidatesandconstructaheterogeneoussubgraph."參看"SAE:SocialAnalyticEngineforLargeNetworks"。圖模型算法的并行化分