社交網(wǎng)絡中相關社區(qū)查詢研究.pdf

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

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

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

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

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

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

7、過全面的實驗對比，驗證了算法的有效性和改進算法的高效性。
　　2基于大數(shù)據(jù)平臺的Top-K相關社區(qū)查詢算法研究。大數(shù)據(jù)時代來臨，我們周圍充斥的海量數(shù)據(jù)，對于海量數(shù)據(jù)的數(shù)據(jù)處理成為一個熱點。社交網(wǎng)絡上社區(qū)探測的研究，也面臨了大數(shù)據(jù)的沖擊，怎樣在大的社交網(wǎng)絡圖上進行社區(qū)查詢成為一個難點。定義查詢節(jié)點可達的社區(qū)為其相關社區(qū)，在大圖上怎樣快速查找與查詢點相關的Top-K相關社區(qū)具有現(xiàn)實研究意義。本文依舊根據(jù)團的概念來定義社區(qū)，依據(jù)相關社區(qū)