社交網(wǎng)絡(luò)的服務(wù)模式不斷創(chuàng)新、應(yīng)用功能日益豐富,正逐漸滲透到即時(shí)通信、新聞推送、支付交易、游戲娛樂(lè)等社會(huì)生活的各個(gè)方面。對(duì)社交網(wǎng)絡(luò)中社區(qū)檢測(cè)的研究成果已被廣泛應(yīng)用到市場(chǎng)精準(zhǔn)營(yíng)銷、搜索引擎開發(fā)、網(wǎng)絡(luò)輿情分析等眾多領(lǐng)域。然而由于在線社交網(wǎng)站的用戶數(shù)量急劇上升,網(wǎng)絡(luò)規(guī)�？焖僭鲩L(zhǎng),產(chǎn)生了樣本數(shù)量巨大、關(guān)系復(fù)雜、超高維度的社交網(wǎng)絡(luò)大數(shù)據(jù),使得社交網(wǎng)絡(luò)大數(shù)據(jù)分析的性能成為社區(qū)檢測(cè)結(jié)果是否具有高價(jià)值的關(guān)鍵因素。因此,對(duì)大規(guī)模社交網(wǎng)絡(luò)進(jìn)行社區(qū)檢測(cè)面臨如下挑戰(zhàn):社交網(wǎng)絡(luò)中的多樣化數(shù)據(jù)類型使得根據(jù)異構(gòu)數(shù)據(jù)源進(jìn)行社區(qū)檢測(cè)變得更加困難;對(duì)基于云計(jì)算的大規(guī)模社區(qū)檢測(cè)的性能需求愈發(fā)迫切;巨大的用戶數(shù)量使分布式社區(qū)檢測(cè)中的統(tǒng)計(jì)推理成為性能瓶頸;高維數(shù)據(jù)導(dǎo)致的頻繁構(gòu)造列聯(lián)表嚴(yán)重影響了分布式社區(qū)檢測(cè)的效率。針對(duì)社交網(wǎng)絡(luò)大數(shù)據(jù)分析中多樣化、高速度、大容量和高維度四個(gè)方面的問(wèn)題,論文研究工作分別對(duì)如何使用多元化社交網(wǎng)絡(luò)數(shù)據(jù)提高社區(qū)檢測(cè)的準(zhǔn)確性、如何使用云計(jì)算資源以較高的并行度進(jìn)行社區(qū)檢測(cè),以及如何提升大數(shù)據(jù)量和高維數(shù)據(jù)下的分布式社區(qū)檢測(cè)的性能進(jìn)行了深入的研究。研究工作的主要?jiǎng)?chuàng)新性成果如下:(1)提出了一種基于概率圖的社交網(wǎng)絡(luò)社區(qū)檢測(cè)方法。建立了基于概率圖的社區(qū)檢測(cè)模型,根據(jù)用戶特征相似度概率圖對(duì)用戶特征相似性之間的潛在關(guān)聯(lián)進(jìn)行建模;采用社交圈集合以同時(shí)描述與社交圈相關(guān)聯(lián)的用戶和特征;給出了關(guān)系概率集合的計(jì)算方法,可描述在給定一組用戶和社交圈時(shí)自我網(wǎng)絡(luò)形成的概率;提出了特征相似度概率圖學(xué)習(xí)算法,并給出了基于概率圖的社區(qū)檢測(cè)模型的評(píng)分函數(shù)。使用Facebook、Twitter和Google+等真實(shí)數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn),驗(yàn)證了由本文提出的FSPG學(xué)習(xí)算法訓(xùn)練得到的PGCD模型可以高效、準(zhǔn)確地預(yù)測(cè)社交圈。(2)提出了一種基于Storm Topology的分布式社區(qū)檢測(cè)方法。通過(guò)將一個(gè)有向無(wú)環(huán)圖的評(píng)分和擴(kuò)展操作作為基本計(jì)算單元,使得集中式社區(qū)檢測(cè)的過(guò)程可被劃分到最細(xì)的粒度,提高了FSPG學(xué)習(xí)算法的并行度;設(shè)計(jì)了一種標(biāo)識(shí)符自動(dòng)生成機(jī)制,以保證每個(gè)概率圖模型只對(duì)應(yīng)于集群中的一個(gè)計(jì)算節(jié)點(diǎn),從而能夠自動(dòng)檢測(cè)并處理搜索空間中的環(huán)路;通過(guò)使用每個(gè)概率圖模型的哈希值作為狀態(tài)元組的鍵值,實(shí)現(xiàn)了更高效地向計(jì)算節(jié)點(diǎn)分配計(jì)算任務(wù)。分析了算法的并行度,并搭建了Storm云計(jì)算平臺(tái),在分布式環(huán)境下進(jìn)行了綜合的性能測(cè)試實(shí)驗(yàn),驗(yàn)證了算法可以達(dá)到很高的并行度,并且在數(shù)據(jù)量較大時(shí)性能有顯著提升。(3)提出了一種基于稀疏ADtree的分布式社區(qū)檢測(cè)性能優(yōu)化方法。提出基于稀疏ADtree的充分統(tǒng)計(jì)量提取算法,通過(guò)使用稀疏ADtree存儲(chǔ)充分統(tǒng)計(jì)量并分發(fā)給各個(gè)搜索和評(píng)分節(jié)點(diǎn),可避免各搜索和評(píng)分節(jié)點(diǎn)對(duì)分布式文件系統(tǒng)的頻繁訪問(wèn);提出基于稀疏ADtree的概率圖快速評(píng)分算法,在評(píng)分節(jié)點(diǎn)中使用稀疏ADtree恢復(fù)出列聯(lián)表以計(jì)算概率圖的評(píng)分值,并通過(guò)建立本地列聯(lián)表集合以減少列聯(lián)表的重復(fù)計(jì)算。使用真實(shí)數(shù)據(jù)集在分布式環(huán)境下進(jìn)行了性能測(cè)試實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明社區(qū)檢測(cè)的搜索和評(píng)分時(shí)間大幅縮短,模型參數(shù)的分布式學(xué)習(xí)過(guò)程得到了明顯加速。(4)提出了一種高維數(shù)據(jù)下分布式社區(qū)檢測(cè)性能的優(yōu)化方法。設(shè)計(jì)了兩個(gè)高效的列聯(lián)表數(shù)據(jù)結(jié)構(gòu),即鏈?zhǔn)搅新?lián)表和哈希列聯(lián)表,通過(guò)分別使用一維數(shù)組和哈希表以記錄條件概率,簡(jiǎn)化了列聯(lián)表的結(jié)構(gòu),從而減少了從高維數(shù)據(jù)創(chuàng)建和索引列聯(lián)表的時(shí)間;提出了列聯(lián)表快速構(gòu)造算法,可避免列聯(lián)表構(gòu)造過(guò)程中的遞歸調(diào)用,為解決使用非遞歸方式從稀疏ADtree中恢復(fù)MCV節(jié)點(diǎn)的問(wèn)題提供了一種有效的方法,從而可大幅縮短列聯(lián)表的構(gòu)造時(shí)間。使用大量的隨機(jī)數(shù)據(jù)集和真實(shí)數(shù)據(jù)集進(jìn)行了綜合的性能對(duì)比實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,從高維數(shù)據(jù)構(gòu)造鏈?zhǔn)搅新?lián)表和哈希列聯(lián)表的時(shí)間均比現(xiàn)有方法更短,并且FCTC算法可使概率圖評(píng)分函數(shù)的計(jì)算過(guò)程進(jìn)一步加速。
【學(xué)位單位】：南京航空航天大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位年份】：2018
【中圖分類】：TP301.6;TP393.09

【參考文獻(xiàn)】

相關(guān)博士學(xué)位論文 前2條

1 付京成;復(fù)雜網(wǎng)絡(luò)中的社區(qū)內(nèi)部結(jié)構(gòu)研究[D];山東大學(xué);2017年

2 陳毅;基于統(tǒng)計(jì)推理的復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)分析[D];哈爾濱工業(yè)大學(xué);2016年

本文編號(hào)：2824494