大规模图数据的拓扑表达性和超低复杂度可计算性研究

Big data consisting of cloud of nodes and complex links are called large-scale graph, with node diversity, structural complexity and link diversity, which can model, express and analyze big data produced from traffic, Internet, social, commercial, biological and other fields. Therefore it is of great importance to study basic theory of information and computation of large-scale graphs. This project aims to solve two key scientific problems: one is expression of data and topology in large-scale graph and the other is ultra low computability. The emphasis is on developing properties of information representation, computing method of information processing and other basic theory research of large-scale graph. The main work includes: representation and visualization of multimodal data in large-scale graph; accessibility of distributed nodes in large-scale graph and frequent sub-graph mining, especially the centrality and similarity of nodes, reliability of nodes and edges; multimodal retrieval method, ultra-low complexity clustering algorithm, and ultra-low complexity matching algorithm of large-scale graph; modeling method of gene networks and application demonstration in gallstone disease.

大规模图是一类“节点云团+复杂链接关系”的大数据，具有节点多样性、结构复杂性、链接多样性等特点，交通、互联网、社交、商业、生物等领域产生的大数据都可以基于大规模图建模来表达和分析，因此开展大规模图信息与计算基础理论研究意义重大。本项目旨在解决大规模图的“数据和拓扑的表达性”和“超低复杂度的可计算性”两个关键科学问题，重点开展大规模图的性质、信息表达、信息处理的计算方法等基础理论研究，内容包括：研究大规模图数据多模态的表示方法与可视化，解决大规模图数据的表达性；研究大规模图节点的分布式可达性和频繁子图挖掘，特别是研究节点的中心性及相似性、节点和边的可靠性，解决大规模图的拓扑结构可表达性问题；研究大规模图的多模态检索方法、多模态数据超低复杂度聚类算法、超低复杂度大规模图匹配算法等，解决大规模图的超低度可计算性问题；最后开展基因网络的大规模图建模方法及胆石病识别中的示范应用。

本项目开展了大规模图数据的表示方法、拓扑结构、多模态数据处理算法等研究，并建立了基因网络的大规模图分析方法。在理论研究方面，提出了一种融合原始网络中节点的一阶和二阶相似性的算法，来实现大规模图的表示方法；分析了大规模图节点的中心性、相似性、可靠性等拓扑结构的性质，提出了基于元子图的异构图注意力网络模型；改进了大规模图的多模态哈希检索方法，建立了模态和模态间关系分析的并行算法；设计了基于核与核度的大规模图多模态数据超低复杂度聚类算法；提出了基于高斯相似性的静态图匹配算法，实现了特征的快速选择、缩小了索引规模，提高了匹配效率。在应用方面，从DNA芯片及其他新测序技术获取的大规模基因数据出发，挖掘基因间复杂的相互关系，构建基因网络，建立基于大规模图的基因网络分析方法，主要包括基于条件互信息的基因网络分析方法以及基于大规模网络节点中心性的基因网络分析方法等内容。上述方法主要用于识别与发现复杂疾病风险有关的基因，预测疾病-基因的关联关系，揭示复杂疾病的基因组学规律，为人类遗传学研究中复杂疾病相关基因定位提供新思路和新方法。