论文部分内容阅读
真实世界的网络表现出突出的层次结构和模块结构,并以各种子图作为构建块。现有的大多数研究通常将不同的子图提取出来作为模体,并简单地使用它们在网络中出现的频次来描述底层网络。虽然这些统计数据可以用来描述一个网络模型,甚至可以用来设计一些网络算法,但是这些研究不足以发挥子图的关键性作用。本文进一步探讨了子图在网络算法中的应用以及模型的性能。本研究就子图在网络分析研究中的可扩展性做了较为深入的研究,并分别从以下三个方面依次展开,提出了一些子图网络模型及其在网络分析应用中的算法:
(1)提出一种新的子图网络模型。现有的网络主要是利用实体作为节点,实体之间特定的关系作为连边来构建的。这种基本构建规则下的网络是一种基础的、底层的网络结构,其对应的网络分析任务也只能在节点层级(node-level)的视角展开。子图是网络中部分节点与连边的集合,也是复杂网络的基本构建块,在某些特定网络中被认为是一种功能模块(比如化合物网络中的苯环结构),所以研究网络子图对理解与分析网络结构具有重要意义。本文提出了一种新的网络映射模型,子图网络(SubGraph Networks,SGN)模型。该模型聚焦于网络中子图之间的连接模式,随着将模型逐渐向高阶映射,该算法能够在图层次(graph-level)上窥探整个网络的拓扑结构。这些高阶子图网络通过显式地展现子图之间的交互,使原始网络中许多隐含的结构特征更加易于发掘。
(2)基于子图网络特征空间扩展的图分类模型。受益于子图网络可对不同特征提取算法进行结构特征空间扩展的优点,本文利用子图网络构建了图分类模型。现有的利用子图进行图分类研究工作主要是从单一的子图层次(subgraph-level)来揭示不同网络之间的结构差异(比如简单地将不同子图出现的频率作为特征来表征网络),忽略了网络结构中子图之间的交互作用。本文采用了上述提出的子图网络模型,利用其能够在图层次(graph-level)上捕获网络中更多结构信息的优势,将其应用到图分类任务中,并在多个数据集上验证了该模型能够增强图分类算法分类效果的良好性能。
(3)基于采样子图网络的特征空间扩展算法。针对子图网络计算复杂度较高且易于引入网络“噪声”的不足,本研究提出了一种子图网络的变体算法,采样子图网络。该算法利用采样策略使子图网络构建的规模实现可控,进而减少了网络噪声并降低了算法复杂度。受益于采样策略,该算法框架不仅限于图分类应用,还可以扩展至更微观的节点分类任务。本文利用改进后的模型算法结合特征空间扩展分别在图分类和节点分类任务中进行了实验验证。研究结果发现采样子图网络可以达到甚至超越原始SGN算法的最优结果并增强模型分类稳定性。
(1)提出一种新的子图网络模型。现有的网络主要是利用实体作为节点,实体之间特定的关系作为连边来构建的。这种基本构建规则下的网络是一种基础的、底层的网络结构,其对应的网络分析任务也只能在节点层级(node-level)的视角展开。子图是网络中部分节点与连边的集合,也是复杂网络的基本构建块,在某些特定网络中被认为是一种功能模块(比如化合物网络中的苯环结构),所以研究网络子图对理解与分析网络结构具有重要意义。本文提出了一种新的网络映射模型,子图网络(SubGraph Networks,SGN)模型。该模型聚焦于网络中子图之间的连接模式,随着将模型逐渐向高阶映射,该算法能够在图层次(graph-level)上窥探整个网络的拓扑结构。这些高阶子图网络通过显式地展现子图之间的交互,使原始网络中许多隐含的结构特征更加易于发掘。
(2)基于子图网络特征空间扩展的图分类模型。受益于子图网络可对不同特征提取算法进行结构特征空间扩展的优点,本文利用子图网络构建了图分类模型。现有的利用子图进行图分类研究工作主要是从单一的子图层次(subgraph-level)来揭示不同网络之间的结构差异(比如简单地将不同子图出现的频率作为特征来表征网络),忽略了网络结构中子图之间的交互作用。本文采用了上述提出的子图网络模型,利用其能够在图层次(graph-level)上捕获网络中更多结构信息的优势,将其应用到图分类任务中,并在多个数据集上验证了该模型能够增强图分类算法分类效果的良好性能。
(3)基于采样子图网络的特征空间扩展算法。针对子图网络计算复杂度较高且易于引入网络“噪声”的不足,本研究提出了一种子图网络的变体算法,采样子图网络。该算法利用采样策略使子图网络构建的规模实现可控,进而减少了网络噪声并降低了算法复杂度。受益于采样策略,该算法框架不仅限于图分类应用,还可以扩展至更微观的节点分类任务。本文利用改进后的模型算法结合特征空间扩展分别在图分类和节点分类任务中进行了实验验证。研究结果发现采样子图网络可以达到甚至超越原始SGN算法的最优结果并增强模型分类稳定性。