融合社区连接信息的网络嵌入方法.pdf

第 卷第 期重庆邮电大学学报(自然科学版).年 月 ().:./.融合社区连接信息的网络嵌入方法收稿日期:修订日期:通讯作者:胡 军 .基金项目:国家自然科学基金()重庆市自然科学基金()重庆市教委重点合作项目():()()()宋振寰胡 军(.重庆邮电大学 计算智能重庆市重点实验室 重庆.重庆邮电大学 计算机科学与技术学院 重庆)摘 要:网络嵌入旨在学习节点的低维稠密向量同时保留原始网络的结构和属性信息 现有的网络表示方法大多未考虑网络中的社区信息和社区间的信息难以有效地学习网络的低维表示 为有效保留网络中的社区信息和社区间信息提出了一种融合社区连接信息的网络嵌入方法()该方法基于不同社区的亲密程度捕捉网络中社区间的关系采用自定义游走的方式得到融合局部结构、社区信息以及社区间信息的游走序列通过 模型得到与之对应的网络嵌入结果 在 个公开数据集的实验结果表明 相比基准方法在链接预测上的 值和 都有一定程度的提升关键词:网络嵌入 模型社区发现社区连接链接预测中图分类号:文献标志码:文章编号:()(.):.().:引 言网络在现实生活中无处不在常见的如生物蛋白质系统、社交系统、交通系统等都可以抽象为网络的形式 通过分析这些网络结构可从中提取有价值的信息比如用户间的好友关系蛋白质网络中单独蛋白的相互作用关系等 传统的网络表示方法常基于网络的拓扑结构通过图的邻接矩阵或相似矩阵进行表示但是这些表示方法在面对大规模网络时存在高维稀疏的问题且可能包含噪声和冗余信息 针对这一问题近年来学者们提出了网络嵌入方法其通过将原始网络映射到向量空间得到节点嵌入表示从而有利于结合机器学习模型高效处理网络分析的下游任务如节点分类推荐链接预测等 现有的网络嵌入方法主要分为基于随机游走的方法、基于深度神经网络的方法和基于矩阵分解的方法 这些方法大多仅考虑了节点的局部结构信息忽略了网络中的社区信息为解决网络嵌入中社区信息缺失的问题.等基于高斯混合分布提出了融合社区信息()的算法.等对随机游走进行扩展提出了融合社区信息的随机游走()算法主要依据阈值选择社区节点进行游走.等提出了一种在学习节点嵌入的同时进行节点聚类()算法主要通过在学习节点嵌入过程中考虑节点聚类损失融合社区信息 等提出一种考虑社区节点游走的同时结合注意力机制增强语义信息的()算法 然而这些融合社区信息的方法仅对社区内的节点信息进行了加强没有考虑网络中的社区间信息在现实生活中社区信息和社区间的关系都至关重要因为不仅同一社区的节点有大概率产生联系不同社区的成员也可能产生联系如图 所示在实验室社交网络中每个节点代表一个学生或老师每条边表示相连的 个节点间存在联系不同颜色代表不同的实验室社区 其中学生 和 在社交网络中虽然没有连边但由于它们属于同一实验室社区它们之间大概率会存在连边关系 而 两实验室社区因为存在多个共有的老师作为团队指导则 节点有更大的概率和 节点存在链接 因此融合社区信息的过程中有必要考虑社区间的关系在保留节点间的连接信息和社区信息的同时保留社区间的连接信息图 社区之间关系.基于上述分析本文提出一种融合社区连接信息的网络嵌入方法()该方法首先结合社区发现算法获得网络的社区结构然后基于不同社区的亲密度捕捉网络中社区间关系接着采用有偏游走的方式保留网络局部信息并采用社区游走的方式保留网络社区内信息和社区间信息最后通过负采样优化的 模型得到与之对应的网络表示结果 在 个公开数据集上的实验结果表明该方法相比基准方法在链接预测实验的效果有一定程度的提升 相关工作网络嵌入旨在提取网络中节点、边的低维信息表示 一个网络可以表示为一个图 ()其中 表示图中的节点集合 是边的集合网络嵌入的目标是通过一个映射函数为每个节点 学习低维稠密的实数向量:是嵌入向量的维数并在低维空间中保存网络的拓扑结构信息如点和边的邻近关系以及社区信息等近年来兴起的网络嵌入研究起源于自然语言处理领域的表示学习受词向量嵌入方法的启发方法提出其基于随机游走的策略每个节点随机从邻居集合中选择一个节点加入节点序列对该序列使用 模型进行学习得到嵌入结果 在随机游走的过程中加入了超参数 改变游走概率可选择深度优先遍历或广度优先遍历从而保存网络的同质性和同构性大规模信息网络嵌入方法()则是利用丰富的二阶 重 庆 邮 电 大 学 学 报(自然科学版)第 卷邻域来弥补一阶邻居的稀疏性 并且随着深度学习的发展深层神经网络模型也逐步应用于网络嵌入技术中主要用于提取网络中的非线性信息 基于深层神经网络模型的嵌入方法()基于深层神经网络模型使用深度自动编码器来保持节点的一阶邻居相似度和二阶邻居相似度然后联合优化这两个近似值再通过非线性的函数获得节点的表示 此外基于矩阵分解的网络嵌入方法()其通过对节点不同 步距离内的网络拓扑信息进行奇异值分解并将每一步的结果相连得到节点嵌入结果 首先通过将任务定义为稀疏矩阵分解有效地初始化网络嵌入然后通过在频谱调制空间中传播来增强嵌入 但是这些方法都没有考虑网络中的社区信息为在网络嵌入中融合社区信息 定义了节点嵌入、社区检测、社区嵌入的方法流程 但是其假设嵌入空间中社区是拟合高斯分布的并通过高斯混合模型进行建模 使用 算法检测出社区网络结构利用社区信息指导随机游走在生成节点序列时根据阈值 从社区中随机选择一个节点加入序列进而融合社区信息到最后的嵌入结果中 通过在学习节点嵌入的过程中添加节点到聚类中心的聚类损失以融合网络中的社区信息 在获取节点周围的局部结构时还捕捉了节点的社区信息并且通过注意力机制对节点之间的语义信息进行了加强 通过模块化非负矩阵分解来保存网络的微观和宏观结构从而在最终的节点嵌入结果保留社区信息 融合 步社区的网络嵌入方法(定义了 步社区的概念通过部分社区结构对随机游走进行指导以保存更高质量的社区信息从上述方法来看现有的嵌入方法多仅采用不同的方式在嵌入结果中融合社区信息但只强调了社区内节点的关系忽略了社区间的信息 为此研究一种融合网络社区间信息的网络嵌入方法具有十分重要的意义 融合社区连接信息的网络嵌入融合社区连接信息的网络嵌入方法 主要思想:首先对输入的网络使用 算法进行社区发现得到输入网络的所有社区然后根据发现的社区得到社区间的亲密度()并结合 对网络中的每一个节点 生成融合局部结构、社区信息和社区间信息的节点序列捕捉网络的局部信息和全局信息最后使用 模型最大化节点在定义的窗口中出现的条件概率从节点序列中学习出节点的嵌入结果方法的主要思想如图 所示图 融合社区连接信息网络嵌入.社区生成由于 算法可快速有效地发现网络中的社区结构因此本文使用该算法来生成社区信息该算法首先将每一个节点单独划分为一个社区然后尝试把每个节点分配到邻居节点所在的社区并计算模块度的变化最后选择模块度最大的社区进行加入 模块度计算公式为()()()式中:表示图中边的权重之和表示所有与第 期 宋振寰等:融合社区连接信息的网络嵌入方法节点 相连的边的权重之和表示节点 所属的社区 是一个增量函数当社区相等时返回 模块度优化完成后该算法另一阶段是聚集已发现的社区建立一个新的社区网络 然后不断重复上述过程直至模块度不再增加.有偏游走序列生成本文采用 获取节点邻居结构具体步骤如算法 所示该方法对初始节点 通过有偏游走的方式生成长度为 的游走序列以更好地保留网络中的结构信息 具体地通过控制 两个超参数可以实现深度优先遍历和广度优先遍历其中 用于控制是否重复游走即是否返回已经走过的节点 用于控制游走的方向是倾向深度优先遍历还是广度优先遍历算法 有偏游走输入:网络()参数 节点游走的路径长度 节点的游走路径数量 输出:有偏游走序列:有偏游走序列 网络节点.():通过 值计算每个节点的别名采样概率:/从最新加入的节点出发:()/通过别名采样获取下一节点:/加入节点到游走序列中作为下一个初始节点:/所有游走序列:.社区游走序列生成本文使用 相似度作为 个社区之间亲密度的关系度量其物理意义是不同社区以及其邻居节点中产生交集的部分越多则 个社区之间的联系越紧密定义为()()()()()()()()()()()式中:()表示社区 的邻居节点集合()表示社区 中的节点集合社区亲密度计算示意图如图 所示 给定一个无向无权图()其中()()()()由公式()可得社区 和社区 之间的 亲密度为/同理可得社区 和社区 之间 亲密度为/社区 和社区 之间亲密度为/图 社区亲密度计算示意图.社区游走序列生成步骤如算法 第 行所示首先以 为初始节点根据发现的社区信息确定当前节点的所属社区 接着将社区抽象为节点计算 亲密度作为网络中社区节点之间的跳跃概率结合别名采样法确定下一跳社区并从下一跳社区中随机选择节点加入游走序列直至游走序列长度达到 特别地的时候 值为 因此初始节点选择同一社区的节点进行游走的概率更高其次才是其他相似度高的社区中的节点 可以看出社区游走序列中既保存了网络中节点的社区内信息也基于社区相似度捕捉了网络中社区间的关系弥补了有偏游走序列中全局信息的缺失可更好地对网络结构进行表示算法 社区游走输入:网络()社区信息 社区游走路径数量 社区游走的路径长度 输出:社区游走序列:社区游走序列 网络中节点.():通过 计算每个社区的别名采样概率:/将节点 作为初始节点:重 庆 邮 电 大 学 学 报(自然科学版)第 卷:()/当前节点所属社区:()/别名采样法获取下一跳社区:():.模型 模型如图 所示对每个节点得到有偏游走和社区游走的序列 后 使用 模型来学习网络的节点嵌入 具体地从得到的序列中任选一个节点 根据窗口大小 获得 的上下文节点将节点的独热编码输入神经网络模型通过正向运算和反向传播更新权重矩阵最大化序列 中节点共现的概率为()()()()()式中:分别表示中心节点和上下文节点和 分别表示节点 的嵌入向量和节点 的上下文嵌入向量图 模型.为降低()式的计算复杂度这里采用负采样进行优化表达式为()()()()()()式中:为负采样个数()为负采样概率分布 实验分析对于本文提出的网络嵌入方法将得到的表示向量运用于链接预测任务以验证其有效性并通过参数敏感性实验进行参数分析.数据集实验选用了 个真实数据集来进行测试数据集的具体信息如表 所示表 数据集.数据集节点数边个数社区标签数 :每个节点代表 篇机器学习论文一共可分为 个类别 网络中存在 个节点以及 个链接:每个节点代表 个用户每 条边则代表 个用户之间的友情 该网络一共存在 个节点和 条边:每个节点代表维基百科中的文章每条边的连接表示 篇文章之间的引用该网络一共存在 个节点以及 条边共 个种类.对比方法和评价指标实验对比的方法包括以下 种网络嵌入方法):利用随机游走生成节点序列获得局部信息并通过 模型学习节点的表示):种在随机游走过程中通过 个超参数 考虑深度优先搜索和广度优先搜索的网络嵌入表示方法):采用混合高斯分布作为社区表示的模型并假设节点表示是由这样的社区分布生成的):种基于已知社区进行随机游走的网络嵌入方法能在嵌入结果中考虑网络中的社区第 期 宋振寰等:融合社区连接信息的网络嵌入方法信息):种基于层次聚类的网络嵌入方法能在嵌入结果中考虑不同层级的社区信息其中、和 是融合了社区信息的方法 和 是没有融合社区信息的方法实验 使 用 的 评 价 指 标 有 (曲线下面积)和 值其中 计算方式为 ()()()()()式中:、分别为预测结果中真阳性、假阴性和假阳性样本 为真阳样本和预测为阳的样本占比 为真阳样本和真实为阳的样本占比.实验设置所有方法在游走的过程中进行统一的参数设置 具体地设置滑动窗口大小为 嵌入维度为游走路径数量为 游走长度为 对比方法的参数均按照相应论文中描述进行设置 特别地本文提出的方法负采样个数为 的聚类数根据网络中的真实类别数进行设置无类别信息的 数据集则使用社区发现算法发现的社区个数作为聚类数 方法 值设置为.网络嵌入方法仅仅为每个节点生成嵌入向量因此本文参照 使用多种操作运算符计算边的嵌入()具体定义如下:()()()()():()()()()():()()()()():()()()()().链接预测分析.全局链接预测在全局链接预测任务中首先将网络中的一些边随机删除然后通过各种方法预测这些缺失的边具体实验采用了生成带标签的数据集方式在不影响网络连通性的情况下从网络存在的边中随机移除、的边作为正样本从节点间无连接的节点对当中采集负样本最后利用剩余的网络进行网络嵌入得到嵌入结果 和 指标用于评估该任务的准确性取 次实验的平均值作为最终结果更高的 值和 值意味着更好的模型性能 个数据集上 运算符实验结果(百分制)如表 所示表 链接预测结果.数据集算法.重 庆 邮 电 大 学 学 报(自然科学版)第 卷续表数据集算法.从实验结果可以看出本文提出的方法 在大多数情况下比只考虑局部结构信息的方法在 有较大提升且对于只考虑社区信息的方法也有一定的提升 具体地在 和 数据集中优于所有方法并且在 数据集上比仅考虑局部结构信息的方法(、)的效果提升了 与融合社区信息的方法(、)相比效果有一定优势但在边删除过多时社区划分不准确对实验结果有一定影响对于 在绝大部分情况下都优于其他对比方法具有良好的模型性能另外实验将各个方法通过不同运算符得到的边嵌入运用在 数据集的链接预测实验中以验证方法得到的节点嵌入是否具有适用性 实验结果如图 所示 从图 可以看出 在、和 运算符下获得的边嵌入向量在链接预测实验中效果较好其中 运算符的效果优于其他所有方法说明 获得的节点嵌入在大多数运算符下都具有适用性综上所述本文提出的方法相对 和在嵌入结果中保留了社区信息和社区间信息同时与融合了社区信息的方法、以及 相比在嵌入结果中保留了网络中的社区间信息从而预测性能有一定的优势图 数据集各运算方法结果.第 期 宋振寰等:融合社区连接信息的网络嵌入方法.社区间的链接预测实验在社区间链接预测中选择网络 的边进行删除原因在于删除过多的边会使网络结构发生巨大变化导致社区发现效果不佳 具体地随机遍历网络中的边通过判断边的社区属性以及删除后网络的连通性进行筛选使得删除的边中社区内的边(边的两端节点属于同一社区)分别占总删除边数的 从而判断嵌入方法是否对网络社区间的关系进行保留在 个数据集上进行实验实验结果 和(百分制)如表 所示表 数据集上社区间链接预测结果.评价指标算法社区内边所占比例.表 数据集上社区间链接预测结果.评价指标算法社区内边所占比例.从实验结果可以看出本文提出的方法在社区间边多的情况下 和 相比其他对比方法有一定的提升 产生以上实验效果的原因主要是 和 随机生成游走序列没有融合社区信息 虽然 考虑了深度优先搜索和广度优先搜索但是 参数并不能提取网络中的社区信息 和 虽然都考虑了社区信息但它们更关注于社区内部的信息提取而忽略了社区之间的信息保留 方法虽然考虑了不同层次的社区信息但是一些社区可能联系不大 重 庆 邮 电 大 学 学 报(自然科学版)第 卷但也被归属到同一层级进行强化从而导致错误判别节点间是否存在链接 本文提出的方法在游走序列中加入了融合社区信息和社区间信息的社区游走且由超参数 控制迭代次数社区间亲密关系控制社区游走概率表 数据集上社区间链接预测结果.评价指标算法社区内边所占比例.只考虑社区信息的方法 在部分结果中依然表现出良好性能的原因在于它在形成嵌入信息的过程中形成了一个闭环不断地优化节点嵌入信息和社区嵌入信息对它们进行一个平衡因此弥补了只考虑社区信息的不足但是本文提出的方法从社区间关系的角度对只考虑社区信息的方法进行优化提升了链接预测实验的 分数 同时通过各方法在不同数据集上的 对比可以发现 在大多数情况下都优于其他对比方法在社区内的边少且社区间的边多的情况下 相比其他方法有着更好的性能并且随着社区内的边不断增加 的效果与基准方法相比也有一定优势 这说明 在保留网络中的社区信息时考虑比其余方法更加充分同时保留了社区内信息和社区间信息.参数敏感性分析为了评估 中不同的参数值是如何影响不同数据集上的结果实验在删除 边的情况下的链接预测任务上进行实验结果如图 所示从实验结果可以发现在 数据集中随着 值的改变实验结果的精度有先上升再下降的趋势在 时获得最好的结果 数据集中最好的结果在 时得到且随着 值的增加链接预测的效果呈下降趋势而 数据集的表现与 数据集类似在 的情况下效果最佳 产生上述实验结果的原因可能在于 数据集中每个社区平均 条边此时对社区中的节点进行游走有很大概率无法走出社区即节点游走在刻画网络结构的过程中已保留了部分社区信息 而 作为社区游走的迭代次数每次迭代都可强化网络社区信息及社区间关系但迭代次数过多可能会导致同一社区的节点嵌入趋于一致从而将原本没有边连接的节点预测为有边相连所以在 数据集一次迭代效果最佳 对于 和 数据集它们社区中平均连边分别为 条和 条 节点游走出社区对网络结构进行刻画的概率更大从而导致社区信息保留较少故可增大 值强化社区信息总的来说在大规模稠密网络(网络中边集远大于点集社区中边集远大于游走序列长度)中 值设置偏小稀疏网络(网络中边集与点集相差不大社区中边集不多)中 值可适当增大然后实验分析了网络表示结果的嵌入维度和游走路径数量对链接预测结果的影响 在 和 数据集中随着 的改变实验结果有先上升后下降的趋势在 时获得最好的结果 数据集则是在 时获得最好的结果 产生上述实验结果的原因可能是不同的数据集适合的嵌入维度各不相同但是过低第 期 宋振寰等:融合社区连接信息的网络嵌入方法或者过高的维度会导致模型欠拟合或过拟合 此外通过实验分析可以发现对于稠密数据集 实验效果随着 的增加而增加在达到一定规模后产生轻微波动原因可能在于该数据集规模较大因此需要多次游走才能更好地学习网络的结构而对于 和 数据集由于网络规模较小不需要多次 就可以完成网络结构的学习实验效果随着 的改变产生轻微波动但过多的游走次数会产生一定噪声使实验效果降低最后从滑动窗口的实验结果可以看出网络中的一阶邻居和二阶邻居的重要性通常大于高阶邻居的重要性但是在 这类有明显节点标签信息的网络中高阶信息对嵌入结果有一定提升图 参数敏感性实验结果示意图.结束语为融合社区信息和社区间信息更好地对网络进行嵌入表示本文提出了一种融合社区连接信息的网络嵌入方法 该方法通过 算法得到网络中的社区划分然后通过不同社区之间的亲密关系对节点生成融合局部结构、社区信息和社区间信息的特定节点序列作为上下文信息以捕捉网络中的局部拓扑信息和全局信息该方法丰富了嵌入结果的社区信息和社区间信息 在 个真实数据集的实验结果验证了模型的有效性和优越性在全局链接预测以及社区间的链接预测任务中 和 相比基准方法都有一定提升本文中所提出的算法主要基于网络的拓扑结构无法处理网络中的其他辅助信息因此得到的网络嵌入不适用于网络中的边或点含有多种属性的复杂网络未来将考虑融合各种辅助信息的网络嵌入方法参考文献:.:/.:.重 庆 邮 电 大 学 学 报(自然科学版)第 卷 ():.():.:.():.:.():.:.():.():.:.():.吕琳媛.复杂网络链路预测.电子科技大学学报(自然科学版)():.():.:/.:.:/.:.:/.:./.:.:/.:.:/.:.:./.:.():.:/.:.():.():.:():./.:().():.():.():.():.:/.第 期 宋振寰等:融合社区连接信息的网络嵌入方法:/./.:.():.:/.:.作者简介:宋振寰()男四川成都人硕士主要研究方向为机器学习、智能信息处理:.胡 军()男湖北荆州人教授博士博士生导师 高级会员主要研究方向为粒计算、粗糙集、智能信息处理:.(编辑:刘 勇)重 庆 邮 电 大 学 学 报(自然科学版)第 卷