复杂网络的结构性质与参数的研究

The complex network, which is a new research area, has blended with natural sciences, social sciences and many different disciplines areas, and is of great theoretical and application prospect. Any network can be considered as a system established by some nodes connected in a certain way. Graph is a unified tool to describe the network in analyzing the general structural characteristics of various complex networks. Based on our long-term engaged in structural graph theory and network optimization, in this project, we first work on the condition for the existence of maximal clusters (maximal connected subgraphs) by focusing on the properties and characterization of topological structure of complex networks and related families of graphs; and then thoroughly study the structural properties of complex networks, especially of community structure of networks with methods of combinatorics, probability and algebra. Finally, we investigate the statistical characteristics of complex networks (such as diameter, average distance, clustering coefficient, betweenness centrality and spectrum of graph, etc.) and related parameters by means of graph operations and computer simulations. It will provide guidance and theoretical basis for complex network protocol performance evaluation and some practical network modeling.

复杂网络作为一个新的研究领域, 与自然科学、社会科学等众多不同的学科领域相互交叉融合，具有巨大的理论和应用前景。任何一个网络都可以看作是由一些节点按某种方式连接在一起而构成的一个系统。研究各种不同的复杂网络在结构上的共性，图（graph）是一种描述网络的统一工具。本项目拟在我们长期从事结构图论和网络优化研究的基础上，通过对图和复杂网络结构的刻画，探讨复杂网络的极大集群（极大连通子图）的存在条件；结合组合、概率和代数的方法，深入研究复杂网络的结构性质，特别是社团结构的划分等问题；利用计算机模拟和图运算，研究复杂网络的统计特征（如直径、平均距离、聚集系数、介数和图谱等）及相关参量，充分发挥我们在图论研究方面的优势，为复杂网络协议性能评估和一些实际网络的建模提供指导和理论依据。

本项目一方面继续对图的结构性质和参数作深入的研究，通过对边色临界图的结构分析，给出了一个判定新的边色临界图的哈密尔顿圈的充分条件和边色临界图的平均度的新的上界，改进了Woodall的结果；运用圈结构和路系统的新的研究方法，得到了一个连通拟无爪图包含至多k个叶子点的支撑树或路覆盖数至多为k-1的度和条件；结合极值图论和代数图论的方法，研究图谱与图的结构参数之间的关系，给出了判断一个图有完美匹配，或几乎完美匹配或因子临界的拉普拉斯特征值条件，在图的无符号拉普拉斯谱与图的半径和独立数之间建立了联系，也得到了图的的无符号拉普拉斯谱展的新的下界和给定独立数的图的代数连通度的下界以及下界可达时对应的极图; 确定了无爪图的3-动态染色数以及极图，找到了一般图的哈密尔顿连通因子，也得到了几类特殊图类的燃烧数。另一方面研究复杂网络的性质及各种参数在复杂网络中的应用，进一步拓展和改进我们已有的方法，并引进新的方法，推进复杂网络的结构性质与参数的研究以及图论在复杂网络中应用研究的发展。结合网络的结构性质，确定了几类特殊网络的外连通度、好邻居连通度以及星/路-结构连通度；研究了不含三角形的图的混合诊断度，不仅推广了一些正则网络的相关结论，而且给出了一些非正则网络的混合诊断度；给出了容错哈密尔顿图的分数（强）匹配排除数等于其最小度的独立数条件，进而得到一些常用的互连网络的分数（强）匹配排除数，也刻画了一些特殊网络的最优分数匹配排除集和最优分数强匹配排除集；通过对容错的扭立方体的拓扑结构的刻画，得到了有故障的扭立方体的哈密尔顿路和哈密尔顿圈的容错条件，对设计和优化以这类网络为基础拓扑构建的实际系统有着重要的意义。