技术摘要：
本发明公开了一种基于网络分区的层次网络嵌入方法，包括：基于模块度增益判断网络原图中节点的归属社区，确定网络分区数；将网络分区数设定为最小规模抽象图的规模阈值，基于混合坍缩方法对网络原图进行图抽象，输出规模逐渐缩小的抽象图，直至最粗抽象图等于最小规模  全部
背景技术：
真实世界中许多复杂网络都具有数据稀疏的特点，例如我们所熟悉的科研合作网 络、社交网络等。这些具有核心节点的网络所呈现的分布形式是长尾分布，造成了网络的稀 疏性。网络嵌入又称网络表示学习，其核心思想是为了将网络数据映射为网络中每个节点 的低维向量表示，之后这些表示能够作为特征应用到网络应用任务，例如：链路预测、节点 分类、社区发现和推荐系统。网络嵌入不仅可以提升网络分析的计算效率，还可以缓解数据 稀疏的问题，从而得到更准确的节点表示。 基于矩阵特征向量计算的算法，是较早用于网络表示学习的方法，在一定程度上 扩大了对维数约简的认识。例如，Zhang等人提出一种针对非线性数据的无监督降维方法， 它在保持原始数据性质不变的情况下，将高维空间映射到低维空间上，实现特征值的二次 提取。Mikolov等人基于局部的角度去构建节点之间关系的方法，它假设邻居节点的降维表 示相近，该假设可以类似地转化为Laplace矩阵的特征向量进行计算。上述基于矩阵特征向 量计算方法最主要的缺点在于复杂度高，即针对于高维矩阵的特征向量计算比较消耗计算 时间和空间。Perozzi等人是第一个将深度学习中的技术应用到网络表示学习领域的算法， 使用随机游走序列建模而不是邻接矩阵，降低了邻接矩阵带来的较高的计算时间和空间消 耗问题。Tang等人提出一种适用于大规模有向带权图算法，首次提出了使用第一级相似度 和第二级相似度对节点对进行概率建模。然而，上述算法的策略在带来效率的同时，会忽视 网络中更深层的信息，如社区信息。Chen等人提出一种网络的多层级表示学习方法，基于混 合坍缩方法保留网络的结构，但人工设定的层级阈值在一定程度上影响了网络表示的效 果。 综上所述，现有的网络嵌入方法可以有效进行网络表示，但基于局部结构的思想 忽略了网络的全局结构，这将造成所学习的表示会丢失网络隐含的结构信息。此外，网络嵌 入方法中的目标函数几乎都是非凸问题，非凸优化问题的求解会在很大程度上影响算法的 性能。 因此，如何提供一种新型的基于网络分区的层次网络嵌入方法是本领域技术人员 亟需解决的问题。
技术实现要素：
有鉴于此，本发明提供了一种基于网络分区的层次网络嵌入方法，提高了基线方 法的网络表示效果，减少阈值设定的人为干预问题，进一步提高网络表示的准确度，可广泛 用于链路预测、多标签节点分类、社区发现、推荐系统领域。 为了实现上述目的，本发明采用如下技术方案： 4 CN 111597665 A 说　明　书 2/8 页 一种基于网络分区的层次网络嵌入方法，包括： 步骤1：基于模块度增益判断网络原图中节点的归属社区，确定网络分区数； 步骤2：将网络分区数设定为最小规模抽象图的规模阈值，基于混合坍缩方法对网 络原图进行图抽象，输出规模逐渐缩小的抽象图，直至最粗抽象图等于最小规模抽象图的 规模； 步骤3：根据基线算法对最粗抽象图进行表示学习，得到最粗抽象图的表示； 步骤4：通过嵌入传播方法由最粗抽象图的表示逐层传播和细化，得到原始图表 示。 进一步，步骤1包括： 步骤11：输入网络原图G＝(V,E)，其中，V表示网络原图G的节点集，E  表示网络原 图G的边集； 步骤12：根据模块度增益ΔQ将网络原图中的节点重新划分归属社区，从而确定出 网络分区数nc； ΔQ表示模块度增益，其值反应了节点i由当前社区并入到其邻居社区的模块度增 益，|E|表示网络原图中边数目，ca表示节点i发生社区变化前的邻居社区，cb表示节点i发生 社区变化前的当前社区， 表示节点i发生社区变化前社区ca中所有节点的度之和， 表示节点i发生社区变化前社区cb中所有节点的度之和，ki表示节点i的度， 表示节点i 与并入后社区ca中节点的连接边数， 表示节点i与并入前社区cb中节点的连接边数。 进一步，步骤2具体包括： 在图抽象的过程中，每层图的划分结果需要满足以下条件： 其中,Ci、Cj分别表示网络原图中第i、j个社区；|Ci|表示网络原图中的分区数目， vj表示网络原图分区Ci的节点集，V表示网络原图的节点集，G表示网络原图； 通过图抽象输出规模逐渐缩小的抽象图： Gai＝(Vai,Eai) ,i＝1,2,...,L    (3) 其中，|Vai|＜＜|V|,|Eai|＜＜|E|，|V|表示网络原图的节点数目，|E|表示网络原 图的边数目，Vai表示抽象图Gai的节点集，Eai表示抽象图Gai的边集，|Vai|表示抽象图Gai的节 点数目，|Eai|表示抽象图Gai的边数目，i表示第i层抽象图，即抽象图所在的层级数。 进一步，混合坍缩方法具体坍缩过程需要满足双射函数和满射函数： 双射函数f: 使得 有 其中C表示网络原图的社 5 CN 111597665 A 说　明　书 3/8 页 区，va表示抽象图的节点，Va表示抽象图节点集，Ci表示网络原图的各个社区， 表示抽象 图节点集的各个节点； 满射函数g: 使得 有 其中G表示网络 原图，V表示网络原图节点集，Ga表示抽象图，Va表示抽象图节点集，vi表示网络原图节点集V 的各个节点， 表示抽象图节点集Va的各个节点。 进一步，步骤3具体为： 通过基线算法Embed( )应用于(GaL,0)进行学习，得到最粗抽象图的表示 GaL 表示最粗抽象图，0表示零矩阵，作为最粗抽象图的初始参照。 进一步，步骤4具体为： 将最粗抽象图的表示 作为最粗抽象图的上一层抽象图GaL-1的参照嵌入，将传 播算法Propagation( )应用于 将基线算法Embed( )应用于 得到最粗抽象图的上一层抽象图的 表示 重复以上步骤，直到嵌入传播得到首层抽象图Ga0的表示 进一步，嵌入传播过程需要满足嵌入函数和传播函数： 传播函数p: 其中GaL-1表示最粗抽象图的上一层抽 象图，GaL表示最粗抽象图， 表示最粗抽象图的表示， 表示最粗抽象图的上一层 抽象图的参照嵌入； 嵌入函数e: 其中GaL-1表示最粗抽象图的上一层抽象图， 表示最粗抽象图的上一层抽象图的参照嵌入，GaL-1表示最粗抽象图的上一层抽象图 的表示。 经由上述的技术方案可知，与现有技术相比，本发明公开提供了一种基于网络分 区的层次网络嵌入方法，本发明方法作为一个嵌套型算法，可嵌套在现有的网络嵌入模型 中，从而提高基线方法的网络表示效果。此外，本方法可以减少阈值设定的人为干预问题， 进一步提高网络表示的准确度，可广泛用于链路预测、多标签节点分类、社区发现、推荐系 统领域。 附图说明 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现 有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本 发明的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据 6 CN 111597665 A 说　明　书 4/8 页 提供的附图获得其他的附图。 图1为本发明方法流程图。 图2为本发明方法的模型图。 图3为本发明方法的网络嵌入应用流程图。 图4为本发明方法在CiteSeer数据集上分别基于DeepWalk、LINE、  Node2Vec的 Macro-F1得分实验结果对比图。 图5为本发明方法在BlogCatalog数据集上分别基于DeepWalk、LINE、  Node2Vec的 Macro-F1得分实验结果对比图。