《大規模網路子圖模式快速挖掘方法研究》是依託西安交通大學，由王平輝擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：大規模網路子圖模式快速挖掘方法研究
- 項目類別：青年科學基金項目
- 項目負責人：王平輝
- 依託單位：西安交通大學
中文摘要,結題摘要,
中文摘要
挖掘大規模網路中局部連線的子圖模式（或稱為網路模體）對於理解生物網路和線上社會網路的結構和功能有著重要的意義。實際套用中，存在網路結構未知、網路規模大、子圖數目海量、子圖模式分析運算大等問題和挑戰，這使得準確快速的分析大規模網路圖的子圖模式變得相當困難。本項目針對此問題展開研究：擬設計網路爬蟲和採樣的方法來獲取未知網路的拓撲結構，同時對數據獲取過程中引入的偏差進行建模分析，進而得以補償修正；擬分別設計適用於大規模靜態圖和高速動態流圖的子圖採樣無偏估計方法，並研究算法的並行化技術；擬研究的子圖採樣估計方法採用目前流行圖計算系統平台的計算範式，研發基於各流行圖計算系統平台的子圖採樣估計系統。本項目的研究成果能夠用來準確快速的挖掘估計子圖模式的特徵值（如某種子圖模式出現的次數），為計算機網路流量監控、線上社會網路分析和生物分子網路信息挖掘提供重要技術手段。
結題摘要
針對大規模網路中局部連線的子圖模式的挖掘，項目組展開了一系列的研究。在網路數據收集發現方面，提出基於隨機遊走的網路數據快速獲取技術，基於馬爾可夫模型對由數據採集過程中引入的偏差進行建模分析，進而給出了有效的偏差修正模型，解決了深網子圖模式難以準確獲取的難題，為深網用戶畫像和行為監控奠定了基礎。提出的深網數據採集方法利用馬爾科夫模型對數據採集引入的測量誤差進行精確的建模分析，進而制定快速且偏差可計算修正的採樣策略，在原圖上隨機遊走實現對節點或者子圖的快速採集，進而通過對深網小規模的數據獲取即可實現對深網節點屬性和用戶群體知識的準確獲取，在同等實驗對比條件下，數十倍的減小了已有方法的估計誤差。在大圖子圖挖掘方面，提出基於採樣技術的子圖挖掘分析方法，解決了現有子圖挖掘方法計算量大、分析時間和精度不可控的問題，為複雜網路高階結構特徵分析奠定了基礎。針對具有數億條邊的靜態大圖，提出的基於路徑採樣和T型樹採樣的子圖頻數估計方法，將3至5節點全局和局部子圖頻數計算時間從數十天降為數分鐘，估計誤差小於1%。針對大規模高速流圖的挖掘分析，提出的基於隨機邊採樣的數據稀疏採樣技術，可以有效控制計算和存儲上的代價。該技術實現了在數十倍數百倍縮減原流圖規模的同時，仍可以準確估計原圖子圖頻數的良好效果。 基於上述研究，項目組在IEEE TKDE、IEEE TPDS、IEEE Internet Computing、ACM TKDD、Information Sciences等高水平國際期刊，以及SIGKDD、VLDB、ICDE、INFOCOM、WWW、IJCAI等高水平會議上發表論文23篇，其中SCI論文13篇，CCF A類會議或期刊論文13篇，IEEE期刊論文5篇，申請國家發明專利4項（其中3項已授權），獲得軟體著作權1項。培養研究生8人，4人已畢業，指導學生髮表論文10餘篇。項目研究內容同時獲得2017年CCF-騰訊犀牛鳥創意基金，研究內容和方向得到專家的認可，研究成果落地套用與騰訊公司。
