网络设计中的离散数学方法

项目名称： 网络设计中的离散数学方法

项目编号： No.11331003

项目类型： 重点项目

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 范更华

作者单位： 福州大学

项目金额： 240万元

中文摘要： 网络设计中的许多问题都可以转化为离散数学问题, 尤其是图论问题, 例如复杂网络的社团分析、大规模集成电路的划分问题都可以转化成图/超图的划分问题, 复杂网络的重构问题可以表示成图的重构问题, 这些问题的研究不仅与计算机学科、网络、现代信息科学与技术等学科的发展密切相关, 并对之产生重要影响, 而且在图论中具有影响整个学科发展的重要地位. 本课题申请人和研究人员长期从事图论与算法及其应用领域研究工作,取得了一系列的研究成果, 在不少问题的研究进展方面保持着国际领先的地位. 本项目主要利用离散数学方法, 尤其是图论方法, 对网络设计中的几个主要问题进行研究. 包括完善图划分理论, 利用现代图/超图划分理论建立复杂网络社团结构分析理论基础, 设计社团划分和大规模集成电路划分的有效算法, 利用压缩感知理论重构复杂网络.在理论和方法上取得较大突破.对相关问题的研究起到实质性的推动作用.

中文关键词： 复杂网络;图;超图;划分;算法设计

英文摘要： In network design, many problems can be transferred into problems in discrete mathematics, especially in graph theory. For example, the analysis of community structure in complex networks and the circuit partitioning in the VLSI (Very Large Scale integration) design are essentially the graph/hypergraph partition problems. Furthermore, the reconstruction of complex networks may be expressed as the graph reconstruction problem. The investigation of these problems is closely related to the development of computer science, network, modern information science and technology, and has an important influence over the development of graph theory. The applicants have been working on graph theory, algorithms, and related applications, achieving a series of important results. In some areas, they hold an internationally leading position. In this project, the applicants will investigate some problems in network design, using discrete mathematics methods, especially graph theory methods. More precisely, we will improve the partition theory of graph/hypergraph, which will be used to establish the theoretical basis of community analysis in complex network, obtain effective algorithms for community analysis and circuit partitioning, and reconstruct complex networks by compressed sensing method. Our goal is to make some major breakthroughs both on theory and methods in the investigations of the above-mentioned problems and significantly promote such investigations. Another goal is to strengthen the academic exchanges domestically and internationally and to establish a strong team with talented young researchers. The success of the project will promote the reputation of our country in the international graph theory community.

英文关键词： Complex network;Graph;Hypergraph;Partition;Algorithm design