大規模圖數據的最大k邊連通子圖查詢處理研究

《大規模圖數據的最大k邊連通子圖查詢處理研究》是依託深圳大學，由李榮華擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：大規模圖數據的最大k邊連通子圖查詢處理研究
• 項目類別：青年科學基金項目
• 項目負責人：李榮華
• 依託單位：深圳大學

項目摘要

凝聚子圖的分析處理是指從圖數據中查詢或者搜尋頂點之間緊密相連的子圖結構，是一項具有重大商業價值和社會效益的前沿技術。近年來，隨著圖數據規模只承剃達的不斷增大，凝聚子圖分析處理的複雜性越來越高，這就迫切需要提出一套快速的凝聚子圖查詢處理方法加以支持。本項目深入分析當前凝聚子圖查詢處理所面臨的挑戰，計畫採用最大k邊連通子圖的凝聚子圖模型，在此基礎上重點研究最大k邊連通子圖的快速查詢處理技術。具體地，本項目旨在解決以下三個基本問題：面向圖流數據的最大k邊連通子圖動態維護算法、最大k邊連通子圖的基本查詢處理，以及支持圖流數據的最大k邊連通子圖快速查詢處理技術。漏船雄牛集成以上技術，本項目將最終提出一套支持大規模圖數據的最大k邊連通子圖查詢處理原型系統，為基於最大k邊連通子圖的聚子圖分析處理奠定基礎。本項目預期產生具有國際影響的研究成果，包括高水平論文10篇以她章騙上，以及自主研發的最大k邊連通子圖查詢處理原型系統。

結題摘要

近年來，凝聚子圖的挖掘和搜尋已經成為資料庫和數據挖掘領域的一大研究熱點。凝聚子圖的挖掘和搜尋對分析大規模社交網路中的社區探測、用戶朋友圈子挖掘等具有重要意義。本項目主要研究了大規模圖數據中的凝聚子圖搜尋問題。首先，本項目提出了一種基於k-核凝聚子圖的影響社區模型，該模型不僅能夠刻畫子圖的凝聚程度，而且還能夠刻畫該子圖在網路中的重要性。基於這一模型，本項目開發了一種新型的樹型索引結構，該索糊主妹引結構可以用於支持快速的影響社區搜尋。而且，本項目還提出了一種高效的索引維護技術，用於支持面向動態圖數據的影響社區搜尋。相關科研成果發表在資料庫領域的CCF A類會議VLDB 2015以及CCF A類期刊VLDB Journal上。其次，本項目還開發了一種基於k-truss凝背永姜聚子圖的影響社區模型，並提出了一去臘種類似的樹型索引結構用於支持快速的k-truss影響社區搜尋，相關成果發表在CCF B類期刊Information Sciences上。再次，本項目提出了一種統一於k-核和k-truss的凝聚子圖模型，並且設計了一種高效的凝聚子圖搜尋算法，相關研究成果捆屑船發表在資料庫領域的CCF C類會議WISE 2017上。最後，我們提出了一種局部稠密的凝聚子圖模型，並且設計了一套高效的求解算法來計算局部稠密的凝聚子圖，相關成果發表在數據挖掘領域的CCF A類會議KDD 2015上。 此外，在本項目的支持下，我們還研究了基於斯坦納樹的凝聚子圖搜尋算法，以及針對動態圖數據的結構聚類等相關問題，相關成果發表在資料庫領域CCF A類會議SIGMOD 2016以及CCF C類會議WISE 2017上。