大型网络中基于局部谱的社团检测算法研究

The community detection problem is a relaxed variant of the maximal clique problem in large graphs, and finds numerous applications in social and biological networks. It not only leads to new opportunities for the national economy and social construction, but also brings new challenges to the area of data mining and social computing. This project will systematically investigate the local spectral method and theory for community detection. We will explore the performance of different local sampling methods based on breadth-first search, random walk and heat kernel diffusion, and analyze the property of various spectral diffusion methods. We will define the local spectral invariant subspace based on different spectral approximation methods (power method, Krylov subspace and Lanczos method), explore the algorithm performance on the subspace dimension and random walk steps. We aim to establish a set of theories based on the Rayleigh quotient, investigate the impact on the community detection quality for different optimization objectives: minimum one norm, quadratic optimization and regularization term. This project will help us design series of local community detection algorithms, which are of low complexity, high robustness and high reliability as verified on large-scale real networks. We will build systematic local spectral methods and theories, and offer technical support for efficient community detection in large-scale networks.

社团检测是图结构问题中极大团检测的一种松弛问题，在社交网络、生物网络中有着广泛的应用。其研究不仅为国家经济和社会建设带来新的机遇，也为数据挖掘和社会计算带来新的挑战。本项目拟对大型网络中基于局部谱的社团检测理论和方法进行系统、深入的研究。拟探索宽度优先检索、随机游走和热核扩散等不同局部采样算法的性能，挖掘各类谱扩散方法的特性；基于不同的谱近似方法（幂方法、Krylov子空间和Lanczos方法等）定义局部谱不变子空间；分析子空间维度和随机游走步数对算法性能的影响；基于Rayleigh熵建立局部谱的理论体系；研究最小一范式、二次优化等不同优化目标和正则项对社团检测质量的影响。通过本项目，将设计可快速检测网络局部结构的低复杂度、高鲁棒性和高可靠性的一系列局部社团检测算法，并在大规模的真实网络中进行验证；建立基于局部谱的较完整的社团检测理论和方法，为大型网络中社团检测的研究提供有效的技术支持。

以社交网络为代表的复杂网络的社团检测是机器学习的热点研究问题。随着现实中复杂网络的规模不断扩大，针对大型网络的全局社团检测复杂度很高甚至难以在有效时间内完成。近年来，国内外研究者将重心转移到了局部社团结构检测。本项目针对大型网络中基于局部谱的社团检测的理论和方法进行了系统、深入的研究。探索了宽度优先检索、随机游走和热核扩散等不同局部采样算法的性能，挖掘各类谱扩散方法的特性；基于不同的谱近似方法（幂方法、Krylov子空间和Lanczos方法）定义局部谱不变子空间；分析子空间维度和随机游走步数对算法性能的影响；基于Rayleigh熵建立局部谱的理论体系；研究最小一范式近似零范式优化建立优化目标和模型。设计了可快速检测网络局部结构的低复杂度、高鲁棒性和高可靠性的一系列局部社团检测算法，并在大规模的真实网络中进行实验验证；建立了基于局部谱的较完整的社团检测理论和方法，为大型网络中局部社团检测的研究提供了有效的理论与方法支持。