通信網(wǎng)絡中復雜用戶關(guān)系查詢和頻繁通信關(guān)系挖掘并行算法研究.pdf

1、隨著移動通信技術(shù)和互聯(lián)網(wǎng)的飛速發(fā)展，移動通信設(shè)備已經(jīng)成為絕大多數(shù)人隨身攜帶的工具，這些設(shè)備之間互相通信產(chǎn)生的數(shù)據(jù)構(gòu)成了通信網(wǎng)絡。通信網(wǎng)絡中隱含了用戶之間的人際關(guān)系，具有重要的研究價值。相對于傳統(tǒng)的數(shù)據(jù)類型，通信網(wǎng)絡的復雜性體現(xiàn)在:一、通信網(wǎng)絡數(shù)據(jù)體量巨大，數(shù)據(jù)記錄往往以百萬甚至千萬數(shù)億計;二、網(wǎng)絡本身結(jié)構(gòu)上具有復雜性，在最壞情況下，網(wǎng)絡中用戶之間關(guān)系的規(guī)模與用戶的數(shù)量呈平方關(guān)系。用戶關(guān)系的查詢和挖掘是通信網(wǎng)絡研究中的重要內(nèi)容，可被廣泛應

2、用于商品（服務）推薦、用戶行為分析和社會結(jié)構(gòu)分析等。本文利用并行計算框架Spark研究用戶通信關(guān)系查詢和頻繁通信關(guān)系并取得以下研究成果:
　　1.提出了帶屬性的并行同構(gòu)子圖匹配算法PISM。該算法利用Spark編程模型，把圖拆分為邊不重疊的鄰接表存儲，所有的同構(gòu)匹配、連接等操作都在鄰接表基礎(chǔ)上完成，使同構(gòu)子圖匹配處理能高效地在分布式集群中實現(xiàn)，適合分析大規(guī)模圖數(shù)據(jù)集上的任務。通過一些定理證明和實驗，驗證了該并行同構(gòu)子圖匹配算法的正

3、確性和有效性。
　　2.提出了針對海量通信數(shù)據(jù)的復雜查詢的并行算法CQCN。該算法利用并行計算框架Spark，將通信數(shù)據(jù)和查詢需求分別轉(zhuǎn)換為通信圖和帶變量約束的查詢圖處理，算法主要分為三個階段:通信圖的預處理、通信表的匹配、迭代連接映射，通過將規(guī)模巨大的通信圖劃分為若干不重疊的子圖再均勻分布到各個計算節(jié)點上去，同時將規(guī)模較小的查詢圖分布到各個計算節(jié)點，再在各個計算節(jié)點上并行地完成各自的計算任務。整體思路符合分而治之的思想，實驗結(jié)果

4、表明，該算法可以高效地完成了大數(shù)據(jù)集下查詢的任務。
　　3.提出了針對海量通信數(shù)據(jù)的頻繁通信子圖并行挖掘算法PMFCS。該算法利用并行計算框架Spark，在頻繁項目集挖掘思想和子圖連接規(guī)則的基礎(chǔ)上，將所有的圖以邊為單位分布到各個計算節(jié)點，在各個節(jié)點統(tǒng)計1階候選頻繁子圖，匯總候選子圖得到1階頻繁子圖。PMFCS算法通過迭代地連接k-1階子圖和1階子圖生成k階候選子圖，再計算k階候選子圖的頻繁度，直至k階頻繁子圖集合為空集。實驗結(jié)果表