图熵若干问题的研究

Graph theory focuses on discrete objects and their relationships. In her paper “Graph Theory in the Information Age” (2010), Fan Chung pointed out: the development of graph theory is on a new journey, becoming the core of information science and information revolution. Graph entropy is an important measurement, which belongs to the interdiscipline of graph theory and information theory. The researchers on this topic include Korner, Tusa, Mohar, Lovasz, Babai, Godsil etc. This project will deal with the following three aspects: study normal graph .conjecture and characterize the structural properties of normal graphs, try to extend Mohar’s result; find the efficient methods for dealing with extremal problems on graph entropies, investigate the relations between graph entropies and some other graph invariants; study the applications of graph entropies in disease networks and bioinformatics, discuss the properties of these networks by using graph entropies, then provide better prediction and design of drugs for the treatment of these diseases. The study of problems on graph entropies is not only of great theoretical significance, but also has strong applications. This project will strengthen the research of graph entropy and the applications of graph entropy in chemistry, biology and information sciences.

图论专注于离散对象及其相互关系的研究，美国艺术和科学院院士金芳蓉教授曾指出：图论已经成为信息科学和信息革命的核心部分。香农提出了熵的概念，开启了人们对信息度量的新纪元，图熵的研究属于图论与信息论交叉的范畴，包括Korner、Tusa、Mohar、Lovasz、Babai、Godsil等国际著名专家都参与到该领域中来。本项目将开展如下三方面的工作：围绕normal图猜想展开研究，刻画normal图的结构性质, 争取拓展Mohar等人的结果；寻找图熵极值问题研究的有效方法，研究图熵与图的若干不变量之间的关系；探讨图熵在疾病网络和生物信息学中的应用，用图熵研究刻画这些网络的性质，从而更好地预测和设计治疗这些疾病的药物。图熵相关问题的研究不仅具有重要的理论意义，还具有很好的应用背景和应用前景。相信通过本项目，会进一步推动图熵相关问题的研究，更好的促进图论与网络科学、生物学、信息科学的交叉应用。

本项目已按计划完成，达到预期目标。主要取得了如下研究成果：(A). 与南开大学黄申为副教授合作，刻画了不含5点路和4点圈作为导出子图的图的结构性质。(B). 与奥地利Dehmer教授等合作，研究了图的各种非正则度量的Nordhaus-Gaddum型结果。 (C). 与他人合作，研究了图的彩虹饱和数，给出了路的彩虹饱和数的新的上界，改进了Barrus, Ferrara, Vardenbussche和Wenger等的结果。(D). 与他人合作，研究了图的部分Hosoya 多项式的根，研究了某些情形的极值和相应的结构。(E). 从多个数据库收集Alzheimer’s disease（AD）相关基因考虑多因素构造基因网络，借助多种网络划分方法对其进行划分，并利用基于网络节点重要度的网络结构熵来筛选出最优的模块划分方法，并利用多种网络指标及统计方法来筛选出AD的本质基因，进而筛选出效果较好的治疗AD的中药复方和中药。 (F). 基于网络结构熵从多种非重叠模块划分方法筛选出适用于Alzheimer’s disease（AD）基因网络模块划分的方法，并将皮尔逊相关系数等关联指数推广，使其适用于度量原网络与子网络功能之间的相关性，从而得到AD的关键模块。