两阶段量子行走算法在社区检测中的应用.pdf

收稿日期：；修回日期：基金项目：吉林省科技发展计划资助项目（）作者简介：梁文（），男，吉林梅河口人，博士，主要研究方向为量子计算与复杂网络；闫飞（），男（通信作者），吉林舒兰人，副教授，博导，博士，主要研究方向为量子计算和图像处理（）；陈柏圳（），男，广东湛江人，硕士，主要研究方向为社交网络分析两阶段量子行走算法在社区检测中的应用梁文，闫飞，陈柏圳（长春理工大学 计算机科学技术学院，长春 ；江西理工大学 信息工程学院，江西 赣州 ）摘要：已有基于量子行走的社区检测算法存在计算开销过大或对时间参数过于敏感的问题。针对此问题，提出两阶段量子行走（，）算法。算法第一阶段为无测量量子行走，此阶段融合节点的邻域拓扑信息将节点表达为向量，第二阶段利用 方法聚类上一阶段得到的节点向量以划分网络社区。通过仿真网络和空手道俱乐部网络的验证，该算法能够准确地检测网络社区结构。进一步，提出 的扩展（）算法，该算法依据节点的社区信息增加或删除原始网络的连边并实现社区隐藏。根据互信息指标和调整兰德系数下的实验表现，算法使已有社区检测算法的平均识别精度分别下降 和 ，对网络社区结构的破坏效果最好。关键词：复杂网络；量子行走；社区检测；社区隐藏中图分类号：文献标志码：文章编号：（）：，（，；，）：，（），：；引言量子算法的出现为图像处理和机器学习等诸多领域的研究任务提供了新颖且高效的解决方案 ，。在诸多量子算法中，量子行走（）显得与众不同，因可用于实现其他量子算法而被视为一种通用计算（）模型 ，并逐渐成为信息安全通信 、空间搜索 和图数据挖掘 领域的关键技术。笼统地讲，量子行走研究的是粒子在图数据结构上的运动以及粒子在图上测量结果的分布特点。当量子行走发生在以复杂网络为代表的不规则图上时，其主要应用为捕捉网络中具有特殊含义的节点和边。譬如，网络的中心节点、关键边和网络中丢失的边等 。年 等人 提出幺正膨胀演化的连续时间量子行走模型算法构造有向复杂网络上的幺正演化，实验表明该算法能有效地排序有向网络的中心节点。年，国防科技大学团队 设计了一种由 算符驱动的离散时间量子行走算法，该算法能以高精度评估网络节点间的相似性。年，等人 针对网络关键边识别问题提出复杂网络上的 量子行走，并进一步将其应用于动态无人机通信网络挖掘关键无人机节点。上述成果共同表明量子行走的测量结果可以有效地反映网络拓扑结构特征，为量子行走在复杂网络结构挖掘中的应用提供了有力支撑。以上针对节点和边的发现工作仅为微观尺度上对网络结构信息的挖掘，量子行走测量结果所捕捉的目标还可以是中观尺度上具有高度聚集特征的子图结构，即社区。目前，已知的基于量子行走的复杂网络社区检测方法有两种。一种是由 等人 提出的利用 硬币驱动的离散时间量子行走（）算法，以下简称 量子行走。由于量子计算中的演化算符多为幺正矩阵，其特征值按实部和虚部分解后能以单位圆的形状投射在一个单位复平面上。文献 研究发现在极限行走步长下 量子行走演化算符所分解出的特征值在单位圆上的分布较均匀，适宜挖掘复杂网络的社区结构，并利用空手道俱乐部和美国航空航线网络验证 量子行走在社区检测中的有效性。另一项工作是 等人 提出的基于连续时间量子行走（）的社区检测算法。基于社区内部连接紧密的特点，文献 中假设社区内节点的信息交互频率更高，令某个时段内粒子在社区内节点上测量概率的变化幅值尽可能地大，而考虑到社区外部连接相对稀疏的特点，令同时段内粒子在社第 卷第 期 年 月计 算 机 应 用 研 究 区间节点上测量概率的变化幅值尽可能地小，最后基于紧密性指标（）优化社区结构的划分结果。上述基于量子行走的社区检测算法在应用层面存在诸多限制，例如前者因需仿真无限次演化而取平均导致计算开销过大；而后者因无法确定最佳的时间参数导致社区检测结果的不稳定。为减少量子行走反复测量带来的计算消耗并提高量子行走对复杂网络社区的检测精度，本文提出两阶段量子行走（，）算法。实验表明该算法可以准确划分网络的社区结构。进一步，本文扩展 算法并使其应用于社区隐藏，实验表明扩展后的 算法能够有效避免其他社区检测算法识别网络的社区结构。两阶段量子行走算法为规避量子行走测量结果存在震荡的问题，并使得量子行走在复杂网络结构挖掘任务上发挥应用价值，本章提出两阶段量子行走（）算法。在 算法的第一阶段，设计了一种无测量量子行走（），将复杂网络的全部节点表示为向量，并融入节点的局部拓扑特征；第二阶段使用 算法聚类第一阶段得到的向量，聚类结果即 算法检测到的社区结构。两阶段量子行走算法的框架参考图 。图 两阶段量子行走算法的框架 用于节点向量表征的无测量量子行走本节提出并定义 第一阶段的无测量量子行走。对照已有的量子行走，无测量量子行走省略了量子测量过程。这样使得粒子在复杂网络节点上的演化结果对应演化算符中的每个分量，并且减少了量子行走在测量过程产生的计算消耗。给定任意复杂网络（，），表示网络节点集，表示网络边的集合，且 。当无测量量子行走发生在复杂网络 上时，中全部节点均采用标准正交基（）表示（类似于 的编码方式），例如不同编号节点的标准基表示为 ，（）其中：的长度为 。已有量子行走的空间维度均大于网络节点的规模，为将空间维度压缩至 ，本节将重新定义无测量量子行走的态向量和演化算符。换言之，无测量量子行走不等同于对已有量子行走模型的删减或简化，其量子态由不同节点标准正交基复合而成，每一个节点有一个独立的态向量，节点 （）的态向量被定义为 （）（）（）其中：（）表示节点 的邻域节点集；代表集合 （）中的任意节点。对集合 中的全部节点执行式（）的计算，则可以得到 个独立的态向量。拼接 ，个态向量，可以进一步得到复杂网络的总量子态，的计算方法为（，）（）与已有量子行走的态向量表达方式不同，式（）将量子态编码为 矩阵。综合式（）和（），无测量量子行走中的包含了网络的连通信息和节点的度信息。节点间的相似性是社区检测的一项核心依据，因此，考虑在无测量量子行走演化算符的构造过程中加入节点间的共同邻居信息。设复杂网络 的邻接矩阵为 ，则全部节点的共同邻居矩阵定义为，节点 和 间的共同邻居数则表示为 ，。以节点间共同邻居信息作为启发，并参照 算符的构造形式，将无测量量子行走的演化算符定义为（）其中：矩阵定义为 （，），（，）（）其中：矩阵和态向量 的计算方法分别参考式（）和（）。由此，演化算符中的第 行则对应节点 的 维表征向量。已有量子行走测量结果虽能有效包含节点的结构特征 ，但其测量结果的振荡现象会对社区检测问题带来不稳定因素。无测量量子行走省略该过程，确保 算法依据节点的结构特征来划分网络社区。用于向量聚类的 社区检测 算法的第二阶段利用 算法聚类由第一阶段式（）得到的 个 维向量。首先，指定 个目标社区，即 算法的质心（）数量，?，质心则代表一个社区的中心节点。设质心为 ，且每个质心均采用 维向量的形式表达，?，算法逐个计算节点的向量与质心向量间的欧氏距离，使节点与对应质心的距离尽可能地短。以节点 为例，算法的计算过程定义为（），（）其中：，表示演化算符中的第 行分量；表示向量间的欧氏距离。以上为 算法的定义和计算方法。算法具有如下优势。首先，算法的无测量量子行走阶段省略量子测量过程，减少了计算开销。其次，算法将态空间的维度定义为 ，而量子网页排序算法 的空间维度等于，文献 中的量子行走和简化量子行走 的空间维度均等于 ，量子行走算法 的空间维度等于 。一般地，对于任意非稀疏网络，。由此可见，算法的空间维度极低，这意味着算法的复杂度也随之急剧下降。此外，对比基于连续时间量子行走的社区检测算法 ，算法无须考虑参数优化问题。算法在社区检测中的应用 社区检测及评价指标在小说 笑傲江湖 中，不同派系均以地域、武功招式和人物形象而划分，这种人以群分的划分思想便是对社区的简单概括。从图结构的视角来看，社区内部的节点连接紧密而社区外部（社区之间）连接稀疏。因社区是对具有相似结构特征节点的聚类任务，社区检测常在蛋白质功能模块挖掘、社交网络信息传播等领域发挥积极作用。复杂网络社区检测的研究目标为：划分节点集 中的全部节点至 个独立非空子集 中，每个独立非空子集代表一个社区，其中?，。当社区为非重叠社区时，个独立非空子集满足 且 。在具体问题中，社区的数量和社区的划分方式并不唯一，因此不同算法的划分结果并不计 算 机 应 用 研 究 第 卷相同。图 给出了一个随机生成复杂网络的社区划分结果，该网络被划分为两个社区，然而若以节点的颜色为划分依据，可以得到九个小规模社区。为尽可能客观地评价算法的社区检测结果，研究者通常同时采用内部评价方法和外部评价方法来量化算法对社区检测结果的精度，其中内部评价方法特指以模块化函数为代表的度量指标，外部评价方法依靠网络已有的真实社区数据量化社区检测结果 。图 复杂网络社区结构的图示 设复杂网络 的邻接矩阵为 ，模块化函数量化的是社团内部边的数量在整个网络中的总占比，其计算方法为 ，（）（）()（，）（）其中：（）为 函数，仅当节点 和 隶属同一个社区时，（，），否则 （，），其中，且 ；，为矩阵 中第 行第 列的元素。大量已有工作表明，模块化函数的度量值多在 。归一化互信息（，）为常见的外部评价方法，将已知的真实社区数据记为一个序列，将序列中每个元素代表节点所在社区的编号，设社区检测算法的检测序列为 ，则 的计算方法被定义为 （，）（）（）（，）（）（）（）其中：（）为社区序列的信息熵；（），其值越大表明算法的社区检测精度越好。算法在仿真网络上的社区检测为验证 算法在社区检测中的效果，本节给出一个具有明显社区结构特征的仿真网络，作为 算法的测试数据，此仿真网络如图 所示。该网络具有三个特征明显的社区结构，算法的划分结果必须准确划分三个无重叠社区才能反映出其在社区检测中的效果。由于任意节点在 算法中均以 维向量的形式表达，当全部向量投影在二维平面上，则 算法对图 网络的社区检测结果如图 所示。在图 中，每个散点均对应图 网络中的节点，根据图中浅蓝、浅红、浅绿的三个色域以及节点的聚集情况可以发现，算法能够准确划分具有明显社区结构的复杂网络（见电子版）。图 具有显著社区结构的仿真网络 图 两阶段量子行走算法对图 网络的社区检测结果 算法对 网络的社区检测结果为进一步验证 算法在社区检测中的效果，本节采用著名开源小世界网络 空手道俱乐部（）作为测试数据，该网络由 个节点和 条边组成。由于该俱乐部存在是否提高收费的争议而瓦解为两个不同社区，两社区分别由编号为 和编号为 的节点领导。网络带有标准的真实社区数据，在图 中分别以不同颜色区分（见电子版），其中编号为 和编号为 的节点较容易被社区检测算法错误划分，因为两者的邻域节点分别从属于不同社区，且数量相同。图 网络及其真实社区结构 本节实验的对比算法可分为两组，第 组为非量子的经典社区检测算法，包括 、的模块化算法（，）、自旋玻璃（）、信息熵编码（）、基于节点稳定性和邻域相似性的社区发现算法（）以及改进布谷鸟搜索优化算法（）；第 组为量子衍生群体智能算法，包括量子蚁群优化算法（，）、量子离散多目标的粒子群优化算法（，）以 及 量 子 遗 传 算 法（，）。以模块化函数 和 指标为评价标准，上述算法同 算法对 网络的社区检测结果参考表 。表 函数和 指标下的社区检测结果 算法类别对比算法模块化 非量子的经典算法 量子衍生群体智能算法 本文算法 根据表 ，算法的社区检测结果同 网络真实社区数据完全相同，并且量子算法普遍优于非量子的经典算法。在表 中，和 算法均为较新颖的社区检测算法，两者的模块度值虽然均与标准 值相等或高度近似，但两者的社区检测结果与真实社区间差距极大，不及本文提出的 算法。此外，无论非量子的经典算法还是量子衍生的社区检测算法，它们在模块化函数和 指标下的表现共同说明：对于具有真实社区数据的网络而言，模块化函数度量值的最大化并不意味着算法的社区检测结果更贴合真实社区。具体而言，算法在全部对比方法中的模块化函数度量值最高，但其对 网络的社区划分精度很低。同理，也可以解释 算法虽准确划分了 网络的社区（根据其 指标），但其模块化度量值（）大于 网络真实社区对应的模块化函数度量值（）。在表 的非量子经典算法中，前五种算法极具代表性，诸多社区检测算法均基于其而设计改进算法，但此五者在 指标下呈现出的社区检测精度均不及 算法。相比之下，仅 和本文的 算法能够完全准确地划分网络的社区结构。第 期梁文，等：两阶段量子行走算法在社区检测中的应用 扩展算法在社区隐藏中的应用鉴于 算法在社区检测中的优异表现，本章提出 的扩展算法，用于修改网络连边信息达到隐藏网络的社区结构的目的。社区隐藏问题描述鉴于 算法在社区检测中的优异表现，本节考虑进一步扩展 算法，使应用于社区检测的反问题 社区隐藏。社区隐藏的研究目标是通过破坏网络的原始结构，使已有社区检测算法无法准确识别网络的社区结构特征，以达到隐藏社区结构的目的。针对给定的复杂网络 和社区检测算法 ，设 （）为社区检测结果的评价指标函数，则有效的社区隐藏结果应满足如下关系：（）（）（）其中：网络 由修改后的节点集 和边集 构成，定义为 （，）。式（）的含义为：在利用社区隐藏算法破坏网络结构后，社区检测算法 在评价指标 （）的社区检测精度应下降，才能反映社区隐藏的效果，且两者的差值越大越好。社区隐藏在图数据层面的操作可理解为对社区特征的逆运算，即，使社区内部连接变得稀疏而使社区间的连接变得紧密，这也是破坏网络原有社区结构的核心思想。因此，隐藏社区的方法主要包括增添或移除网络的节点和边。以图 （）具有两个社区的网络为例，当移除每个社区的中心节点时，社区检测算法无法再识别原有的社区结构，图 （）给出了一种网络结构被破坏后的社区检测结果，即社区隐藏效果。显然，基于节点层面的社区隐藏方法虽直观有效，但对整个网络变动极大，在实际应用中容易引起攻击者的警觉。本节所设定的被破坏对象仅为网络的边，且移除边和新增边的数量相等，尽可能地在保持网络原有的基本统计特征基础上实现对社区的隐藏。图 社区隐藏方法的图示 在本节实验中，社区隐藏的评价指标有两项，包括归一化互信息 （详见 节）和调整兰德系数（，）。和 指标均依赖真实社区的序列（或其他算法的社区检测结果）作为评价依据，设 和 分别为真实社区 和算法 测得的社区结构 组成的列联表中第 行元素的和以及第 列元素的和，代表社区 和社区 中重合节点的数量，则 指标的计算方法为 （，）（）其中：（）。的扩展算法根据 和 节的实验可知，算法能够有效地捕捉到网络的社区结构。在此基础上，本节对 算法增设一个节点评分环节作为移除网络连边的依据，提出 的扩展（，）算法，该算法的实现流程如图 所示。图 算法的流程 给定复杂网络 ，首先利用 节的 算法得到网络的社区检测结果，而后 算法将式（）中每个节点向量的元素累加，并存储在序列 中。此节点评分过程可以参考图 的第步，由此 定义为 ，（）其中：中第 个元素值代表节点 在整个网络系统中的评分。节提到，社区特征的反运算便是社区隐藏的核心思想，因此对 中的元素降序排列后，删掉排名靠前且处于相同社区一对节点对应的边，以此降低社区内部节点连接的紧密性，其计算方法为 （，），（，）（）其中：（，）代表移除边集 中已有的边，其中（，），（，）表示节点 和 间的连边；（，）表示公式的运算仅在节点 和 属于同一社区时有效，当两者属同一个社区则等于 ，反之为 ；的社区划分结果由 算法得到。图 的第步给出了通过删除原网络的边而破坏网络社区结构的过程和原理。同理，若对 顺序排列，在排名靠前且处于不同社区的一对节点间添边，则可以提高不同社区间连接的紧密性，其计算方法定义为 （，），（，）（）其中：（，）表示向集合 中添加一条新边，且该条边不属于边集 ，即 （，），图的第步给出了该计算步骤的原理。从图 的结果可以发现，算法的最终目的是通过破坏网络的社区结构避免已有社区检测算法识别网络的社区结构，并且当对原始网络的边删减或添加后，网络的社区结构将发生明显的改变。算法的社区隐藏实验本节实验以 、以及 算法作为式（）中的社区检测算法 ，并选择如下算法作为用于破坏网络结构的社区隐藏对比方法，包括随机（）算法、社区检测攻击（，）算法、基于度的攻击（，）算法，其中 和 算法因包含随机性而重复运行 次后取均值。在使用上述社区隐藏算法后，将得到修改的复杂网络，即式（）中的 。进一步，根据式（）的描述关系可知，社区检测算法 对网络 的社区检测精度越小则社区隐藏效果越佳。本节实验仍以 空手道俱乐部为测试网络，并考虑对该网络仅移除或添加 的连边或节点（）。基于 和 指标，上述社区隐藏算法及本节提出的 算法的社区隐藏结果分别参考图 和 。在图 和 中，水平方向表示不同社区检测算法，竖直方向表示破坏网络社区结构的方法，每一个方块表示网络被破坏后某算法的社区检测精度。当网络结构未经破坏时，原始 值及 值默认为 ，并用 标记。图中右侧色带代表 和 度量值的高低，浅颜色代表高精度隐藏结果。根据图 和 的社区隐藏实验结果可以发现，无论基于何种指标，本文提出的 算法的社区检测效果均为最佳。相比之下，算法因随机地移除集合 中的边，导致其隐计 算 机 应 用 研 究 第 卷藏效果在对比算法中最差；算法虽以感知网络社区结构作为移除网络边的前提，但其在节点选择上没有可依赖的启发信息并具有随机性，导致社区隐藏精度不稳定；算法以最大度节点作为修改网络的启发信息，其在 和 指标下的隐藏效果整体上优于 算法。为量化不同算法的社区隐藏效果，此处逐一计算图 和 中纵方向算法对经典社区检测算法造成的精度损失，精度损失的值越大越能表明算法在社区隐藏任务上的有效性。以图中 算法为例，算法使水平方向五种经典社区检测算法的平均精度下降了（）。依此类推，在 指标下，、以及 算法使五种社区检测算法的精度分别平均下降了 、以及 ；而根据图 ，在 指标下，三种对比算法和 算法使社区检测精度分别平均下降了 、以及 。由此可见，无论采用何种评价指标，算法的社区隐藏效果在对比算法中最佳。图 基于 指标的社区隐藏结果 图 基于 指标的社区隐藏结果 此外，社区隐藏效果的优劣同样与所使用的社区检测算法 存在明显相关关系。以图 中 算法的社区隐藏结果为例，分别使用 算法和 算法计算社区序列时，两者对由 算法修改后得到的网络 的社区隐藏结果差距较大，前者等于 而后者等于 。说明社区隐藏的效果高度依赖所使用的社区检测算法 。而相比之下，本文提出的 算法能有效地避免不同类型社区检测算法准确识别网络原有的社区结构。结束语本文提出一种用于社区检测的两阶段量子行走算法，该算法的无测量量子行走能有效地融合节点的局部拓扑特征信息将节点向量化表达。相比已有量子行走算法，两阶段量子行走算法压缩了态向量的维度并省略了测量过程，极大节省了计算过程中的空间占用。实验表明，两阶段量子行走算法能在社区检测和社区隐藏两项应用中同时发挥显著作用，具有高度灵活性和可扩展性。本文的应用场景仅针对无重叠的社区检测任务，未来计划将量子行走扩展至高维的线图上，线图中的节点与原网络中的边相对应，而每条边关联两个不同的节点。因此量子行走对线图上每个节点的表征结果包含网络连边的信息，当基于连边信息来划分网络的社区结构时，自然而然能够得到重叠的社区结构。结合本文算法在无重叠社区检测上的表现可以推断，两阶段量子行走算法未来在重叠社区检测中有望发挥新的积极作用。参考文献：，：，：，（）：，：，：李萌，尚云两硬币量子游走模型中的相干动力学 计算机研究与发展，（）：（，（）：），：，（）：，（）：，：，（）：，（）：，（）：，（）：，（）：韩忠明，刘雯，李梦琪，等基于节点向量表达的复杂网络社团划分算法 软件学报，（）：（，（）：），（）：，：，：，（）：，（）：郑文萍，刘美麟，杨贵一种基于节点稳定性和邻域相似性的社区发现算法 计算机科学，（）：（，（）：），（）：，：，：，（）：李阳阳，焦李成，张丹，等量子计算智能 北京：科学出版社，：（，：，：）第 期梁文，等：两阶段量子行走算法在社区检测中的应用