通信網絡中復雜用戶關系查詢和頻繁通信關系挖掘并行算法研究.pdf

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

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

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

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