大數據環境下面向社交網路的圖匹配查詢研究

《大數據環境下面向社交網路的圖匹配查詢研究》是依託西南交通大學，由王欣擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：大數據環境下面向社交網路的圖匹配查詢研究
• 項目類別：青年科學基金項目
• 項目負責人：王欣
• 依託單位：西南交通大學

項目摘要

社交網路已成為新的信息傳播載體，具有極高的商業套用價值；與此同時，圖結構特點使得圖匹配查詢成為社交網路分析的關鍵技術，如：社交圈子發現、角色分析、專家推薦等。然而，龐大的社交網路和昂貴的圖匹配計算，制約了圖匹配查詢的套用。面對上述挑戰，本課題在統一的邏輯框架下，從套用需求出發，針對社交網路數據規模大，查詢結果複雜，數據更新頻繁，分散式存儲等特點，系統性地開展圖匹配查詢研究。主要創新點包括：(1)在top-k多樣性計算和有限資源近似計算兩個方向探索近似圖匹配查詢；(2)探索層級圖壓縮及壓縮圖增量維護技術，實現通過視圖、壓縮圖最佳化圖匹配查詢；(3)克服分散式計算的複雜性並發揮並行計算的優勢，探索有效的分散式圖匹配查詢技術；(4)實驗驗證上述技術的有效性並進行整合，完善原型系統。本課題的研究有利於建立系統完整的面向“大數據”的圖匹配查詢技術，對“大數據”環境下社交網路分析具有重要的理論意義和套用價值。

結題摘要

圖結構匹配是一個經典的研究問題,在多個領域內有著廣泛的套用。近年來，隨著社交網路的興起，圖結構匹配進一步地成為社交網路分析的關鍵技術之一，被套用於社交圈子發現、角色分析、目標推薦等。然而，由於社交網路數據量十分龐大，且圖結構匹配問題的計算複雜度非常高，例如，子圖同構是NP完全問題，不存在多項式時間複雜度的算法；圖仿真算法的時間複雜度也是輸入圖G的平方，因此在大規模圖數據上進行圖結構匹配運算有著很高的開銷，難以滿足實際套用需求。為此，如何有效地提高圖結構匹配運算的效率是當前社交網路分析研究的熱點。本課題著眼於這一現實問題，針對社交網路數據“規模大”，“查詢結果複雜”，“分散式存儲”等特點，系統性地開展圖匹配查詢研究。課題組經過三年多的努力，在多樣化圖結構匹配，基於視圖的圖結構匹配，分散式圖結構匹配，有限資源圖結構匹配等問題上進行了深入探索，取得了一系列的研究成果，具體包括：探索了top-k多樣化查詢技術，設計了具有“提前終止”性能的算法，使得查詢更有針對性，且計算更加高效；設計了基於視圖的查詢技術，大大提高了圖結構匹配運算的效率；探索了分散式環境下圖結構匹配的問題，開發了可並行運行的分散式算法，極大地提高了運算效率；提出了“有限資源查詢計算”的框架，設計了有限資源查詢算法，實現了在有限資源環境下高效率的查詢計算。以上這些成果發表在了國際高水平的期刊和學術會議，如：TKDE (CCF A類)1篇，VLDB (CCF A類)1篇，EDBT(CCF B類) 1篇， DASFAA(CCF B類)1篇，DEXA(CCF C類) 1篇，產生了一定的學術影響力。不僅如此，上述成果還得到了企業，如華為，長虹等的套用，幫助他們取得了良好的經濟效益；同時也申請國內外發明專利6項，其中美國發明專利1項（已獲授權），國內發明專利5項。同時在本項目研究成果的基礎上，課題組負責人作為主要參與人獲批國家自然科學基金重大項目1項，作為主持人獲批軟體開發環境國家重點實驗室開放課題1項及多項縱橫向科研項目。