社交網(wǎng)絡(luò)中相關(guān)社區(qū)查詢(xún)研究.pdf

1、互聯(lián)網(wǎng)上的許多應(yīng)用形成了社交網(wǎng)絡(luò)。社交網(wǎng)絡(luò)上一些鄰近節(jié)點(diǎn)構(gòu)成社區(qū)，社區(qū)就是聯(lián)系緊密的成員聚集的一個(gè)子圖結(jié)構(gòu)。如何在社交網(wǎng)絡(luò)中發(fā)現(xiàn)和分析社區(qū)是目前的一個(gè)研究熱點(diǎn)。研究工作的很大部分是關(guān)于社區(qū)發(fā)現(xiàn)，即如何在整個(gè)社交網(wǎng)絡(luò)中找出其中所隱含的所有社區(qū)。和社區(qū)發(fā)現(xiàn)相對(duì)應(yīng)的另一類(lèi)研究是社區(qū)查詢(xún)。社區(qū)查詢(xún)是指：給定社交網(wǎng)絡(luò)上的某個(gè)節(jié)點(diǎn)作為查詢(xún)點(diǎn)，找出該點(diǎn)所在的一個(gè)或多個(gè)社區(qū)。當(dāng)查詢(xún)點(diǎn)所在的社區(qū)有多個(gè)時(shí)，這些社區(qū)稱(chēng)為重疊社區(qū)。
　　不少學(xué)者對(duì)社交網(wǎng)

2、絡(luò)中的社區(qū)查詢(xún)進(jìn)行了研究。這些研究中的社區(qū)查詢(xún)只查找查詢(xún)點(diǎn)所在的社區(qū)。但我們的研究發(fā)現(xiàn)，在社交網(wǎng)絡(luò)的實(shí)際應(yīng)用中，用戶(hù)還經(jīng)常會(huì)關(guān)心查詢(xún)點(diǎn)不在，但與查詢(xún)點(diǎn)相近的社區(qū)。如基于論文合作關(guān)系形成的研究者社交網(wǎng)絡(luò)中，某個(gè)研究者可能會(huì)查看他本人所在的社區(qū)，也會(huì)查看他不在但鄰近社區(qū)中有哪些研究人員，即那些和他研究工作相近的研究人員。
　　本文引入相關(guān)社區(qū)的概念來(lái)解決上述問(wèn)題，定義查詢(xún)點(diǎn)可達(dá)的社區(qū)為該查詢(xún)點(diǎn)的相關(guān)社區(qū)。相關(guān)社區(qū)既包括查詢(xún)點(diǎn)所在的社區(qū)

3、，也包括查詢(xún)點(diǎn)不在，但有路徑可達(dá)的社區(qū)。因而相關(guān)社區(qū)既可能與查詢(xún)點(diǎn)鄰近，也可能處于社交網(wǎng)絡(luò)上離查詢(xún)點(diǎn)較遠(yuǎn)的位置。在實(shí)際應(yīng)用中，當(dāng)然主要關(guān)心那些離查詢(xún)點(diǎn)近的相關(guān)社區(qū)，即要找出離查詢(xún)點(diǎn)最近的若干個(gè)相關(guān)社區(qū)，將該問(wèn)題稱(chēng)為 Top-K相關(guān)社區(qū)查詢(xún)。
　　同時(shí)，研究領(lǐng)域和工商業(yè)大數(shù)據(jù)時(shí)代來(lái)臨，數(shù)據(jù)量數(shù)據(jù)類(lèi)型膨脹式的增長(zhǎng)，社交網(wǎng)絡(luò)也急速發(fā)展，往往形成很大的圖。針對(duì)大圖的社區(qū)查詢(xún)面臨著數(shù)據(jù)量大，單機(jī)裝載計(jì)算困難的難題。同樣，在相關(guān)社區(qū)查詢(xún)的算法

4、設(shè)計(jì)上也面臨著大數(shù)據(jù)的挑戰(zhàn)。單臺(tái)計(jì)算機(jī)的處理能力以及傳統(tǒng)的技術(shù)架構(gòu)已經(jīng)很難滿(mǎn)足海量數(shù)據(jù)處理的計(jì)算要求，而分布式并行計(jì)算框架的出現(xiàn)為海量數(shù)據(jù)下的數(shù)據(jù)處理帶來(lái)了曙光。Hadoop云平臺(tái)為大數(shù)據(jù)的處理而生，能夠處理海量數(shù)據(jù)，但是其計(jì)算框架面臨著計(jì)算單一，不支持循環(huán)迭代計(jì)算等難題，基于Hadoop的Spark內(nèi)存計(jì)算平臺(tái)集成了Hadoop云平臺(tái)的優(yōu)點(diǎn)，支持迭代計(jì)算，同時(shí)內(nèi)存計(jì)算極大的減小了大數(shù)據(jù)計(jì)算處理的時(shí)間消耗。由此本文深入研究了Spark平

5、臺(tái)分布式大圖社區(qū)查詢(xún)計(jì)算算法，提出大圖中 Top-K相關(guān)社區(qū)查詢(xún)的解決方法。
　　論文在第一章和第二章介紹了研究背景，在第三章和第四章分別提出一種社交網(wǎng)絡(luò)中Top-K相關(guān)社區(qū)查詢(xún)方法以及基于大數(shù)據(jù)平臺(tái)的Top-K相關(guān)社區(qū)查詢(xún)算法研究，并分別在單機(jī)和集群環(huán)境（Hadoop，Spark集群)進(jìn)行了測(cè)試驗(yàn)證和結(jié)果分析。其中大數(shù)據(jù)平臺(tái)的Top-K相關(guān)社區(qū)查詢(xún)算法研究是對(duì)社交網(wǎng)絡(luò)中 Top-K相關(guān)社區(qū)查詢(xún)方法的補(bǔ)充與完善，它利用分布式并行內(nèi)

6、存計(jì)算，解決了大圖中相關(guān)社區(qū)查詢(xún)的難題，并且通過(guò)算法改進(jìn)，進(jìn)一步提高檢索效率。本文的主要工作包括兩個(gè)方面：
　　1提出一種社交網(wǎng)絡(luò)中 Top-K相關(guān)社區(qū)查詢(xún)方法。本文定義了團(tuán)和相關(guān)社區(qū)的概念，研究一種快速檢測(cè)查詢(xún)點(diǎn)的Top-K相關(guān)社區(qū)的方法。文中提出了一個(gè)向下探測(cè)搜索算法：從查詢(xún)點(diǎn)出發(fā)探測(cè)團(tuán)結(jié)構(gòu)，再由團(tuán)結(jié)構(gòu)向外延伸擴(kuò)展得到社區(qū)，通過(guò)循環(huán)迭代快速得到查詢(xún)點(diǎn)的Top-K相關(guān)社區(qū)。同時(shí)，為了減少搜索空間和計(jì)算時(shí)間，對(duì)原算法進(jìn)行了改進(jìn)。通

7、過(guò)全面的實(shí)驗(yàn)對(duì)比，驗(yàn)證了算法的有效性和改進(jìn)算法的高效性。
　　2基于大數(shù)據(jù)平臺(tái)的Top-K相關(guān)社區(qū)查詢(xún)算法研究。大數(shù)據(jù)時(shí)代來(lái)臨，我們周?chē)涑獾暮Ａ繑?shù)據(jù)，對(duì)于海量數(shù)據(jù)的數(shù)據(jù)處理成為一個(gè)熱點(diǎn)。社交網(wǎng)絡(luò)上社區(qū)探測(cè)的研究，也面臨了大數(shù)據(jù)的沖擊，怎樣在大的社交網(wǎng)絡(luò)圖上進(jìn)行社區(qū)查詢(xún)成為一個(gè)難點(diǎn)。定義查詢(xún)節(jié)點(diǎn)可達(dá)的社區(qū)為其相關(guān)社區(qū)，在大圖上怎樣快速查找與查詢(xún)點(diǎn)相關(guān)的Top-K相關(guān)社區(qū)具有現(xiàn)實(shí)研究意義。本文依舊根據(jù)團(tuán)的概念來(lái)定義社區(qū)，依據(jù)相關(guān)社區(qū)