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

项目名称： 大型网络中基于局部谱的社团检测算法研究

项目编号： No.61772219

项目类型： 面上项目

立项/批准年度： 2018

项目学科： 自动化技术、计算机技术

项目作者： 何琨

作者单位： 华中科技大学

项目金额： 16万元

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

中文关键词： 算法设计与分析；社团检测；社交网络；局部谱；谱扩散

英文摘要： 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.

英文关键词： Aalgorithm design and analysis;community detection;social networks;local spectral;spectral diffusion