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

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

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

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

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