本文選題：社交網(wǎng)絡(luò) + 社區(qū)發(fā)現(xiàn)　； 參考：《國防科學(xué)技術(shù)大學(xué)》2015年博士論文

【摘要】：隨著網(wǎng)絡(luò)社交的普及,人類社會快速步入在線社交網(wǎng)絡(luò)時代。在線社交網(wǎng)絡(luò)普遍具有“社區(qū)結(jié)構(gòu)”特性,社區(qū)結(jié)構(gòu)的挖掘和分析已成為在線社交網(wǎng)絡(luò)領(lǐng)域的一個研究熱點(diǎn)和重點(diǎn)。社區(qū)發(fā)現(xiàn)技術(shù)的研究已經(jīng)開展了很多年,并取得了豐碩的成果。然而隨著信息技術(shù)的進(jìn)步,當(dāng)前的社交網(wǎng)絡(luò)所呈現(xiàn)出的大規(guī)模、高復(fù)雜性、動態(tài)演化的特征,對社區(qū)發(fā)現(xiàn)方法在處理速度、精確性及動態(tài)應(yīng)對等方面提出了更高的要求:1)快速性是社區(qū)發(fā)現(xiàn)的基本要求。面對規(guī)模持續(xù)膨脹的、交互不斷加強(qiáng)的、以及群體行為不斷變化的在線社交網(wǎng)絡(luò),如何利用更加高效的方法和技術(shù)來處理大規(guī)模在線社交網(wǎng)絡(luò)數(shù)據(jù),是社區(qū)發(fā)現(xiàn)面臨的重要難題。2)準(zhǔn)確性是社區(qū)發(fā)現(xiàn)技術(shù)追求的目標(biāo)。關(guān)于社區(qū)劃分質(zhì)量的衡量,雖然沒有統(tǒng)一的標(biāo)準(zhǔn),但在同一指標(biāo)下,各種方法的優(yōu)劣好壞卻一目了然。如何發(fā)現(xiàn)社交網(wǎng)絡(luò)中的自然意義下的真實(shí)社區(qū)劃分,是所有社區(qū)發(fā)現(xiàn)方法前進(jìn)的方向和終極目標(biāo)。3)高可擴(kuò)展性是社區(qū)發(fā)現(xiàn)方法的發(fā)展方向。傳統(tǒng)的社區(qū)發(fā)現(xiàn)方法缺乏可擴(kuò)展性,不支持大規(guī)模并行處理,不適合處理當(dāng)前千萬級節(jié)點(diǎn)規(guī)模的在線社交網(wǎng)絡(luò)。4)社區(qū)結(jié)構(gòu)的動態(tài)演化為社區(qū)發(fā)現(xiàn)技術(shù)帶來新的挑戰(zhàn)。在線社交網(wǎng)絡(luò)的結(jié)構(gòu)動態(tài)變化,個體及群體行為復(fù)雜多樣,這給社區(qū)發(fā)現(xiàn)帶來了新的困難和提出了更高要求。只有準(zhǔn)確發(fā)現(xiàn)發(fā)展過程中的社區(qū)結(jié)構(gòu),才有可能理解和掌握社區(qū)演化的內(nèi)在機(jī)理。針對上述問題,本文基于MapReduce的大規(guī)模并行處理思想,精選目前優(yōu)秀的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法infomap進(jìn)行并行化,并對社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法大規(guī)模并行化的支撐技術(shù)進(jìn)行了研究,具體研究成果如下:(1)提出了基于MapReduce模型的社區(qū)發(fā)現(xiàn)算法infomap的并行化算法inforMR,實(shí)現(xiàn)了infomap算法的高可擴(kuò)展性。infomap算法是目前社區(qū)發(fā)現(xiàn)算法中精度最高的,但該算法需要大量的隨機(jī)數(shù)據(jù)訪問,所以一般基于內(nèi)存實(shí)現(xiàn),對于大規(guī)模在線社交網(wǎng)絡(luò)而言,infomap面臨計(jì)算時間和內(nèi)存空間開銷方面的不足。針對這一問題,inforMR首先基于分治思想,按照節(jié)點(diǎn)到達(dá)順序?qū)⑸缃痪W(wǎng)絡(luò)進(jìn)行分割;然后對infomap中基于全局搜索的社區(qū)合并策略進(jìn)行改進(jìn),通過局部貪婪搜索方式,減少搜索空間,并利于MapReduce實(shí)現(xiàn);最后通過MapReduce編程,實(shí)現(xiàn)了infomap算法的大規(guī)模并行化。實(shí)驗(yàn)表明,該算法具有較好的可擴(kuò)展性,在計(jì)算速度上具有接近線性的加速比。(2)提出了基于mapreduce的多層次圖劃分算法dmgp。informr可擴(kuò)展性好,但準(zhǔn)確度與原算法比有所降低,主要是因?yàn)槠洳捎昧撕唵蔚木W(wǎng)絡(luò)劃分算法,網(wǎng)絡(luò)劃分的質(zhì)量較差。多層次圖劃分模型的實(shí)現(xiàn),如metis,是目前普遍采用的圖劃分方法,具有較高的劃分質(zhì)量,但已有算法不能滿足大規(guī)模在線社交網(wǎng)絡(luò)的分析需要。dmgp基于mapreduce模型對metis算法進(jìn)行了并行化,1)在圖壓縮階段,基于mapreduce模型實(shí)現(xiàn)了重邊匹配策略,實(shí)現(xiàn)了圖規(guī)模以近似指數(shù)級的速度快速壓縮;2)在圖壓縮階段,通過大規(guī)模并行,提高i/o性能,避免了保存大量中間結(jié)果所需的開銷;3)在劃分的還原迭代階段,通過大規(guī)模并行提高劃分質(zhì)量評估的性能和分區(qū)優(yōu)化調(diào)整性能。實(shí)驗(yàn)表明,dmgp能對千萬節(jié)點(diǎn)規(guī)模的在線社交網(wǎng)絡(luò)進(jìn)行有效劃分,且其精度與metis相差不到10%;基于dmgp的社區(qū)發(fā)現(xiàn)算法infomr的精度與informap相當(dāng)。(3)提出了一個通用的基于mapreduce的社區(qū)發(fā)現(xiàn)框架mrhcd。傳統(tǒng)的社區(qū)發(fā)現(xiàn)方法大多面臨infomap同樣的困境。分析總結(jié)了infomr的實(shí)踐過程后,我們認(rèn)為可以將該方式推廣:大規(guī)模在線社交網(wǎng)絡(luò)中的層次社區(qū)結(jié)構(gòu)發(fā)現(xiàn)以及非重疊社區(qū)結(jié)構(gòu)發(fā)現(xiàn)可以通過類似的兩階段過程實(shí)現(xiàn):網(wǎng)絡(luò)劃分階段和并行社區(qū)發(fā)現(xiàn)階段。mrhcd集成了dmgp和hcd。在網(wǎng)絡(luò)劃分階段,dmgp具有較高的精度,能夠勝任大規(guī)模在線社交網(wǎng)絡(luò)的劃分任務(wù),且不破壞網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。在并行社區(qū)發(fā)現(xiàn)階段,基于hadoopstreaming的hcd模型在不需要修改社區(qū)發(fā)現(xiàn)算法業(yè)務(wù)邏輯的情況,實(shí)現(xiàn)了社區(qū)發(fā)現(xiàn)算法的大規(guī)模并行化,而且可以保證較高的社區(qū)發(fā)現(xiàn)精度。在實(shí)驗(yàn)過程中,我們在mrhcd框架部署了三個優(yōu)秀層次社區(qū)發(fā)現(xiàn)方法,驗(yàn)證了提出的mrhcd可以快速實(shí)現(xiàn)louvain、oslom等算法的大規(guī)模并行化,加速了算法的計(jì)算過程,并提高了可擴(kuò)展性,同時還保持了與原算法相當(dāng)?shù)乃惴ň取?4)提出了一種多網(wǎng)絡(luò)協(xié)同劃分算法cpmn。協(xié)同劃分是跨網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的一個支撐技術(shù),目前還缺乏相關(guān)研究。許多用戶在多個社交網(wǎng)絡(luò)中注冊賬號并產(chǎn)生行為活動。為了更加全面地了解社交網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu),需要進(jìn)行跨社交網(wǎng)絡(luò)的協(xié)同分析。多網(wǎng)絡(luò)比單網(wǎng)絡(luò)規(guī)模更大,且因?yàn)榉植荚诓煌W(wǎng)絡(luò)中的同一個體(錨點(diǎn))而產(chǎn)生了聯(lián)系。即使采用mrhcd框架,也無法處理有關(guān)聯(lián)關(guān)系的跨網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)。根據(jù)錨點(diǎn)的分布對這些網(wǎng)絡(luò)進(jìn)行劃分,錨點(diǎn)分布一致度較高的分區(qū)被認(rèn)為是相似分區(qū),將這些相似分區(qū)置于同一服務(wù)器處理,即可實(shí)現(xiàn)跨網(wǎng)絡(luò)的協(xié)同分析。cpmn是在dmgp的基礎(chǔ)上改進(jìn)的,增加了錨點(diǎn)分布限制條件。cpmn在圖粗化階段引入優(yōu)先級機(jī)制和純度的概念保證和記錄錨點(diǎn)的一致性,并通過mapreduce模型實(shí)現(xiàn)圖的快速壓縮;在初始劃分階段則通過標(biāo)簽傳播模型得到初始劃分;在細(xì)化階段通過大規(guī)模并行實(shí)現(xiàn)分區(qū)調(diào)整,優(yōu)化割集和分區(qū)均衡度。實(shí)驗(yàn)表明,CPMN框架可以有效地處理多個在線社交網(wǎng)絡(luò)中的協(xié)同劃分問題,并使得錨點(diǎn)的分布盡可能一致,同時該框架具有較高的處理速度和可擴(kuò)展性�？偟膩碚f,本文針對大規(guī)模在線社交網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)相關(guān)問題展開研究,主要技術(shù)思路是通過大數(shù)據(jù)分析處理工具以及分治策略對已有的優(yōu)秀算法進(jìn)行并行化以適用于大規(guī)模網(wǎng)絡(luò)。此外,我們還對跨網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)的支撐技術(shù) 多網(wǎng)絡(luò)協(xié)同劃分展開研究。整體上看,本文中提出的方法和框架基本都達(dá)到了設(shè)計(jì)指標(biāo),可以有效處理千萬節(jié)點(diǎn)規(guī)模以上的社交網(wǎng)絡(luò)。
[Abstract]:With the popularization of social networking , the human society has entered the online social network rapidly . The online social network has the characteristics of " community structure " , the mining and analysis of community structure has become a research focus and focus in the field of online social networking . The large - scale parallelizing of infomap algorithm is realized . The experiment shows that the algorithm has better scalability , and has a close linear acceleration ratio on the computing speed . (3)鎻愬嚭浜嗕竴涓，

本文編號：1769210