大型網路中基於局部譜的社團檢測算法研究

《大型網路中基於局部譜的社團檢測算法研究》是依託華中科技大學，由何琨擔任項目負責人的面上項目。

基本介紹

• 中文名：大型網路中基於局部譜的社團檢測算法研究
• 項目類別：面上項目
• 項目負責人：何琨
• 依託單位：華中科技大學

中文摘要

社團檢測是圖結構問題中極大團檢測的一種鬆弛問題，在社交網路、生物網路中有著廣泛的套用。其研究不僅為國家經濟和社會建設帶來新的機遇，也為數據挖掘和社會計算帶來新的挑戰。本項目擬對大型網路中基於局部譜的社團檢測理論和方法進行系統、深入的研究。擬探索寬度優先檢索、隨機遊走和熱核擴散等不同局部採樣算法的性能，挖掘各類譜擴散方法的特性；基於不同的譜近似方法（冪方法、Krylov子空間和Lanczos方法等）定義局部譜不變子空間；分析子空間維度和隨機遊走步數對算法性能的影響；基於Rayleigh熵建立局部譜的理論體系；研究最小一範式、二次最佳化等不同最佳化目標和正則項對社團檢測質量的影響。通過本項目，將設計可快速檢測網路局部結構的低複雜度、高魯棒性和高可靠性的一系列局部社團檢測算法，並在大規模的真實網路中進行驗證；建立基於局部譜的較完整的社團檢測理論和方法，為大型網路中社團檢測的研究提供有效的技術支持。

結題摘要

以社交網路為代表的複雜網路的社團檢測是機器學習的熱點研究問題。隨著現實中複雜網路的規模不斷擴大，針對大型網路的全局社團檢測複雜度很高甚至難以在有效時間內完成。近年來，國內外研究者將重心轉移到了局部社團結構檢測。本項目針對大型網路中基於局部譜的社團檢測的理論和方法進行了系統、深入的研究。探索了寬度優先檢索、隨機遊走和熱核擴散等不同局部採樣算法的性能，挖掘各類譜擴散方法的特性；基於不同的譜近似方法（冪方法、Krylov子空間和Lanczos方法）定義局部譜不變子空間；分析子空間維度和隨機遊走步數對算法性能的影響；基於Rayleigh熵建立局部譜的理論體系；研究最小一範式近似零範式最佳化建立最佳化目標和模型。設計了可快速檢測網路局部結構的低複雜度、高魯棒性和高可靠性的一系列局部社團檢測算法，並在大規模的真實網路中進行實驗驗證；建立了基於局部譜的較完整的社團檢測理論和方法，為大型網路中局部社團檢測的研究提供了有效的理論與方法支持。