基于群体一致性动力学的网络社团结构识别研究

A swarm is a complex system composed of a large number of interacting autonomous or semiautonomous subsystems interconnected by networks. Swarms of mobile robots, sensor networks, and even social networks are typical instances. Research during the past decade showed that the complex network topologies intensively govern the organizations and functions of the swarms. This evidence suggests inverse approaches to the problem in which the consensus dynamics is used as a probe for the understanding of the community structure of networks. We propose a dynamical theoretical framework for the community detection, with an emphasis on tackling the inherent flaws of the traditional modularity function method. Our dynamical approaches clarify the deep connections between the dynamics and the network topology. The proposed research mainly involves 1) cluster analysis method under spatial transformation, and 2) distributed computing method based on network leaders. For the first theme, we extract the information from the time series data by observing the dynamical behaviors of the swarm consensus, then transform the community detection problems into the vector cluster analysis problems in the Euclidean space, and finally detect the community structure by the methods of the k-nearest neighbor density and kernel function. For the second theme, we identify the skeleton structure of networks based on the local information with an influence analysis, and then prospect the microscopic structure of network communities in a distributed and asymptotic manner using the swarm consensus dynamics. The research targeted will advance the theory and practice of swarms and complex networks.

群体系统是由大量相互作用的自主或半自主子系统通过网络互联所构成的复杂系统。移动机器人群、传感器网络甚至社会网络都是典型实例。群体的复杂网络拓扑结构强烈地支配着系统的组织与功能。本项目基于上述事实做逆向考量，将群体一致性动力学作为群体网络社团结构的探测工具，提出复杂网络社团结构识别的动力学理论框架，克服传统模块函数方法存在的固有缺陷，揭示动力学与网络拓扑间的内在深刻联系。研究内容主要包括1）空间变换下的聚类分析方法：对群体一致性动力学行为的时间序列数据进行信息抽取，将复杂网络中的社团识别问题变换为欧氏空间中的向量聚类分析问题，应用k近邻密度与核函数方法识别网络拓扑的社团结构；2）基于领导者的分布计算方法：运用影响力分析，在节点邻域层次上辨识网络社团的骨架结构，进而运用群体一致性动力学作为分布式计算工具渐近地探明网络社团的微观结构。研究结果对群体系统与网络理论及其工程实践的发展具有重要意义。

群体的复杂网络拓扑结构强烈地支配着系统的功能与行为。本项目基于上述事实做逆向考量，将群体一致性动力学作为群体网络社团结构的探测工具，提出复杂网络社团结构识别的一致性动力学理论框架，克服传统模块函数方法存在的固有缺陷，揭示一致性动力学与网络拓扑间（特别是社团结构）的内在深刻联系。本项目的主要研究内容与重要结果包括：1）提出了基于一致性动力学的空间变换聚类分析方法识别网络的社团结构，将社团识别问题转化为欧氏空间中的向量聚类问题。用气体扩散模型模拟一致性动力学过程，利用气压分布向量表征节点对网络的影响程度，基于k近邻密度与核函数方法分析计算节点间的非相似测度并融合凝聚聚类算法识别网络拓扑的社团结构。2）提出了基于群体一致性动力学的局部社团结构探测方法。利用节点度信息描述节点影响力从而确定网络领导者节点，利用一致性动力学分析计算其跟随者，将社团从整个网络中逐一剥离从而识别社团结构。3）基于已建立的局部社团结构探测方法，提出了基于一致性动力学与领导者-跟随模型的分布式社团结构定量探测算法。通过一致性动力学过程定量表征节点与领导者的紧密程度，分布式计算节点隶属概率，从而依据节点隶属向量完成社团识别并揭示中间节点的归属倾向性。4）研究了复杂网络中的社团结构与一致性动力学之间的内在联系，发现不同拓扑尺度下的社团结构会在一致性动力学过程中的不同时间尺度上显现出来。为了揭示网络中的社团与层次结构，构造一致性动力学过程中的多个动态矩阵观测量并分析其时间序列行为从而辨识复杂网络的社团与层次结构。5）深入系统地分析与解决了群体任意高阶一致性问题在通信约束下的稳定性切换问题。证明了在网络连通与一致性高阶多项式赫尔维兹稳定的情形下，任意高阶一致性在合适的通信时延约束下是渐近可达的。提出了描述任意高阶一致性与复杂网络拓扑结构、通信约束以及控制反馈增益之间严格关联的解析方程。厘清了一致性与网络结构间的深刻联系。给出了群体广义一致性对通信时延的紧上界（即控制协议对通信约束的鲁棒性测度）与稳定性切换机制。进一步地，利用复杂网络的拓扑性质给出了具有低时间复杂度的高阶一致性稳定的充分条件。6）构建了多属性决策的节点重要性综合评价方法，用于分析与辨识复杂网络中的关键节点或领导节点。该方法已被成功运用于关键词同现复杂网络的实证研究中。本项目研究结果对群体系统与网络理论及其工程实践的发展具有重要意义。