大规模动态社交网络社团检测算法研究

Community structure is one of the most important statistical properties of complex networks. The study of community structure contributes greatly to understand the structure of networks, analyze the features of networks and discover the hidden laws in networks. The study of community structure is valuable not only in theory research, but also in practical applications. This project focuses on the community structure detection in social networks. Since social networks are dynamic, multi-dimensional, multi-scale, directed and large-scale, it is necessary to design special algorithms for detecting communities in social networks.This project studies the topological indexes of dynamic networks, which provide computational methods for further analysis of the networks. After that, effective algorithms are studied to detect overlapping and hierarchical communities in static networks. These algorithms are developed to incremental detecting community structure in dynamic networks. The project also considers the dynamic networks which consist of many snapshots as integration by simulating the dynamics process on them to detect dynamic community structure. Finally the influence of sub-graphs in dynamic networks is defined, which is used to judge the importance of nodes and communities.

社团结构是复杂网络的关键结构特征，研究网络社团有助于理解网络结构、分析网络特性、发现网络中的隐藏规律，不仅有重要的理论研究意义，还具有重要的实际应用价值。本项目研究社交网络中的社团检测问题，针对社交网络动态、多维、多尺度、有向、规模巨大等特点，设计符合社交网络特性的动态社团检测算法。项目首先研究动态网络的拓扑指标，为进一步分析网络性质提供计算手段；其次提出高效的能处理大规模数据的静态分层重叠社团检测算法，并扩展该算法使其能解决增量聚类的问题以快速得到下一时刻的社团结构，同时还通过模拟动态网络上的动力学过程，将分片的动态网络看做一个整体来检测社团结构；最后定义了动态网络上的子图影响力，分析动态网络中节点和社团的重要程度。

社交网络分析具有重要的理论和应用价值，特别是在当今这个在线社交的时代，对社交网络的研究受到了前所未有的关注。由于社交网络会随时间发生变化，将其建模为动态网络可以更准确的刻画网络特征、分析演化规律、预测网络变化。本项目主要研究动态社交网络中的社团检测及其相关问题，包括①设计静态和动态的社团挖掘算法，②分析动态网络关键节点演化规律，③预测动态网络中的链路变化。.重要研究结果包括：.⑴从网络控制的角度，定义了节点的支配中心性和节点间的支配能力相似性。通过实验验证得到了以下结论①支配中心性大的节点，在控制网络方面能力更强；②具有相似支配能力的节点具有相似的功能。该研究使我们能从控制的角度理解网络的拓扑结构特性。.⑵给出了新的社团结构定义。提出“富含三元组”能更好的刻画有意义的子图结构，在此基础上定义2-club子结构用于建模复杂社团。该定义捕获了社团更本质的特征，不仅可以检测到稠密社团，还可以检测到那些稀疏但有意义的社团。.⑶提出基于网络结构扰动及拓扑相似性的动态社团检测算法。结合网络拓扑与网络的结构扰动性质，构建节点相似性，从拓扑和时序两方面衡量节点的相似程度。基于该相似性，设计动态社团检测算法，将结构扰动理论应用到动态网络社团检测中。.⑷提出基于PageRank的动态网络核心节点检测算法。将前一时刻的PageRank值作为先验知识，调整随机游走策略，使当前网络上的核心节点检测更加鲁棒与平滑，能够更加准确的刻画节点中心性演化过程、预测节点中心性变化趋势。.⑸提出基于图正则化非负矩阵分解的动态网络链路预测算法。将之前全部时刻的网络作为非负矩阵分解时的约束条件，分解当前时刻网络，以得到下一时刻的网络。.以上研究成果为动态社交网络分析提供了数据与算法支持，为后续更深入的研究奠定了良好的基础。