基于图论的复杂网络高阶组织结构挖掘算法研究

There has been quite a bit of research about lower-order connectivity patterns which can be captured at the level of independent vertices or edges in complex networks. But the research about higher-order connectivity patterns which are substructures consist of vertices and edges with specific structure characteristics is still in its infancy. The communities which consist of rich edges, while the structures which consist of rich higher-order connectivity patterns are called as higher-order organization structures. In this project, we mining higher-order organization structures based on graph theory, defining a metric for measuring the influence of vertices from the viewpoint of structure, and further identifying essential vertices within higher-order organization structures based on the proposed structure influential metric. Its main contents include three aspects: (1) we extract higher-order connectivity patterns based on the basic edge-connectivity patterns with the hybrid information from the characteristics of basic graphs and practical network properties, and then we define the induced subgraphs which are equivalent to the structures consisting of rich extracted higher-order connectivity patterns as higher-order organization structures; (2) we design two algorithms for mining higher-order organization structures, and one is based on iteratively removing edges, the other is based on the extension of seed vertices and we also design the quality measures for algorithms; (3) we convert higher-order organization structures to their own structure equivalent trees, based on the unique advantage of the intrinsic structure characteristics, and based on the hierarchical relations of trees, we can define a structure influential metric for vertices, and further we can also identify essential vertices within higher-order organization structures according to the proposed metric. If controlling signal is input into the identified essential vertices, the whole network can be intervened accurately.

当前复杂网络中研究依靠独立的点或边捕获信息的低阶连接性模式较多，而关于高阶连接性模式——点和边组成具有特定结构特征的子结构的相关研究尚处于起步阶段。富含边的结构称为社团，而富含高阶连接性模式的结构称为高阶组织结构。本项目基于图论挖掘复杂网络中的高阶组织结构，并利用其内在精细结构特征定义节点的结构影响力度量指标，进而依据该指标识别高阶组织结构内部的关键节点，主要内容包括以下几点：（1）基于图论中基本图的结构信息并融合实际网络领域信息，依据网络中的基本连边类型提取高阶连接性模式，定义与富含该高阶连接性模式结构等价的诱导子图为高阶组织结构；（2）设计基于边删除和种子节点扩展的挖掘算法及其评价标准；（3）利用其内在精细结构特征，将高阶组织结构转化为结构等价的树，根据树的层次关系定义节点的结构影响力度量指标，进而依据该指标识别高阶组织结构内部的关键节点。通过这些关键节点输入控制信号可精准干预网络。

复杂网络中富含高阶连接性模式的高阶组织结构相较于网络中富含边的社团有诸多优势，不仅可用于从整个网络中提取功能模块，更为独特的是可利用高阶组织结构独有的内在精细结构特征可以提取传统方法所不能提取的构成社团的子组，并将高阶组织结构转化为结构等价的树，根据树的层次关系定义节点的结构影响力度量指标，进而依据该指标识别高阶组织结构内部的关键节点。通过这些关键节点输入控制信号可对网络实施精准干预。本项目主要围绕以下三个内容展开研究：.1）给出复杂网络中高阶组织结构的明确定义.基于图论中基本图的结构信息，并融入实际网络领域信息，依据网络中的基本连边类型提取高阶连接性模式，定义网络中与富含该高阶连接性模式结构等价的诱导子图为高阶组织结构。.2）设计基于边删除的划分式和基于种子节点扩展的凝聚式高阶组织结构挖掘算法，给出体现能够评价内在精细结构特色的高阶组织结构挖掘算法评价标准。首先基于迭代删边技术设计划分式的高阶组织结构挖掘算法；其次采用了相反的思路，设计了基于种子节点扩展的凝聚式高阶组织结构挖掘算法，并将其扩展为可挖掘重叠高阶组织结构的算法。本项目利用网络中高阶组织结构内外所含高阶连接性模式的数量差定义了算法的评价标准。.3）高阶组织结构内部关键节点的识别.充分利用了高阶组织结构的内在精细结构特征，将其转化为结构等价的树，利用树的层次关系定义高阶组织结构内部节点的结构影响力度量指标，根据该指标识别高阶组织结构内部的关键节点。.复杂网络中的高阶组织结构是通过计算的方法识别系统生物学中蛋白质互作网络中的关键蛋白质、基因失调模块中的致病基因以及药物靶标等重要目标以及恐怖网络研究中恐怖团伙内部的零联系小组的重要模型。开展复杂网络中高阶组织结构的挖掘及应用研究不仅具有重要的科学理论价值更具有迫切的实际需求。