基于动态节点运动的网络社区发现方法研究

Complex networks are abstraction from the relations among real-world objectives. It is rather significant and challenging to study the structures of different complex networks. The analysis of complex network structure is essentially a problem of clustering for the vertices according to their similarities, so that community features can be detected. There exist various types of algorithms for community detection. However, most of them bear restrictions and relatively high computation complexity. Recently, our research team proposed a novel algorithm based on the motions of dynamical systems. The algorithm can achieve automatic community detection by employing the group consensus motions of the dynamic vertices within a common state space. Actually, this algorithm integrates the clustering problem of complex networks with the theory on systems dynamics and essentially belongs to a category of algorithms which are based on the exchange of information among data points. Evidently, potential theoretical and practical significances for such an algorithm are both prominent. Thus, rigorous and extensive studies aiming at relevant problems are deserved. The scheme of the current project will be tightly focused on the community detection algorithms based on motions of dynamic vertices, consisting of four major aspects: 1. research on the straight relationship between group consensus motions and the topological structures of networks; 2. research on the robustness of the community structure detected under a situation with uncertainty of the network topologies; 3. research on the algorithms under the specific scenario with the network topologies being slowly varying ; 4. research on the classification of natural languages of human based on the relevant algorithms.

复杂网络是现实中客体之间关系的抽象，对其结构和特征的研究具有意义和挑战性。复杂网络结构分析根本是根据节点的相似程度对它们进行聚类，从而实现社区发现。已有的各类社区发现算法大都有局限性，且计算复杂度普遍较高。课题组初步探讨了一种基于动态系统运动的新算法。该算法结合了系统动力学理论和复杂网络的聚类问题，能利用动态节点在状态空间中的分组趋同运动实现自动聚类。这类算法本质上属于基于网络节点之间信息交换的动态社区发现方法。相比其他算法，这种新算法具有显著的理论和现实意义，值得深入探究。本项目的计划研究内容将密切围绕基于动态系统运动的网络社区发现算法，分别在四个主要方面展开: 1. 研究基于动态系统运动的社区发现与网络拓扑结构之间的直接关联; 2. 研究网络拓扑结构具有不确定性情况下的社区结构鲁棒性; 3. 研究网络拓扑慢时变情况下的动态社区发现算法; 4. 基于社区发现算法，研究自然语言系谱分类。

社区发现问题本质上是对具有一定同质性的个体子系统进行归类。本项目专注于通过个体子系统的运动以及子系统之间进行信息交互动态地实现分类。趋同既是复杂多个体系统聚类运动的基础，也是聚类运动的极端情况。项目组从群镇定控制和网络能控性的角度对约束条件下的趋同控制器设计方法开展了研究。编队属于精细化的准趋同类型，实现难度更大。项目组主要基于虚拟结构法，对具有不确定性和时变性的复杂多个体系统的分组编队控制方法开展了研究。项目组还研究了如何利用动态聚类基于人类个体行为动力学针对具体社会现象进行分类的方法以及心电信号与心血管疾病表征与分类方法。研究工作取得一系列成果，发表了13篇期刊论文，2篇会议论文，培养研究生10名。