复杂网络的对称性理论与算法及应用研究

The complex network is an important math model in charactering the complex system of real world. The use of complex network to model and research the topology of those complex systems attracts much attention. The latest research results in the field of complex networks show that symmetry is a significant feature. The notion of symmetry of complex networks means invariance by permutating nodes. Thus, the symmetry of complex networks can be captured by graph symmetry theories. The research of symmetry of complex networks has been effectively applied in the redundancy compression, quotient and computational reduction, and so on. Hence, a further research of theories, algorithms and applications of the symmetry of complex networks has its own high theoretical and applied value. In this project, we will continue investigate the theory, algorithm and application of symmetry of complex. The main topics includes: (1) the theories of characterization, measurement and detection of symmetry of complex networks; (2) the detection algorithm and application of symmetry theories in network, social network and information network, and so on. The further research can extend the current research on related networks; and can be effectively applied in the detection of symmetry.

复杂网络是刻画现实世界各种复杂系统的重要数学模型之一。利用复杂网络来模拟并研究这些复杂系统的拓扑结构得到了大量的关注。复杂网络领域最新的研究结果表明，对称性是复杂网络的典型特征。所谓复杂网络的对称性是指置换复杂网络的节点而其性质保持不变。因此，复杂网络的对称性可由其基图的自同构来表示。目前为止，复杂网络的对称性研究已在网络冗余压缩、商网络及约化计算等发面得到了有效的应用。因此继续研究复杂网络的对称性理论与算法及应用有着重要的理论意义和应用价值。本项目的主要研究复杂网络的对称性相关理论与算法及应用。包括:（1）复杂网络的对称性特征刻画与探测理论；（2）对称性理论在网络中的探测算法及应用。本项目的研究可进一步深化和扩展相关理论；并在生物网络、社交网络等复杂网络的对称性探测中得到应用。

复杂网络是刻画现实世界各种复杂系统的重要数学模型之一。近年来，利用复杂网络来模拟并研究复杂系统的拓扑结构越来越得到关注；尤其是复杂网络的对称性特征在网络冗余压缩、商网络、约化计算及数据传输等方面得到了有效的应用。本项目主要研究复杂网络的对称性相关理论与算法及应用，在项目执行期内深化、扩展和推广了部分已有工作，并针对复杂网络的对称性特征刻画与探测理论，以及对称性理论在网络中的探测算法及应用展开了研究。. 首先，复杂网络基图的各类参数与网络的拓扑结构、各种性质之间关系密切，项目刻画了各参数与整体对称性之间的关系，给出了具有对称性质的复杂网络的拓扑结构刻画；同时，给出了几种量化方法，用以比较不同复杂网络之间的对称性强弱程度。. 其次，针对部分给定的复杂网络，项目研究了其对称性存在的内在规律，并结合对称性与自同构群的密切关系，初步探索了基图的自同构群中非平凡正规子群在对称性探测中的影响。我们还发现复杂网络的对称性探测中能起到更有效作用的是部分正规初等交换子群，后续将尝试给出新的对称性探测的理论与算法。. 最后，复杂网络基图的自同构群可以进行唯一不可约“直积”分解，分解结果中的每一个子群均为对称群或对称群的圈积。相应的，各自同构子群在基图上的作用与子图结构之间的局部作用密切相关，进而影响整个网络的结构。但自同构群的分解并不能体现对应的各子图之间的联系，项目发现对于自同构群在部分子图上的诱导子群来说，若其在该子图的补图上有非平凡的作用，则该复杂网络的局部对称性越强。. 本项目研究成果对于完善复杂网络的对称性的相关理论与算法及应用研究，具有一定的理论与应用意义。