基于改进K-Shell的社会网络关键节点挖掘算法.pdf

第 卷第 期计算机应用与软件 年 月 基于改进 的社会网络关键节点挖掘算法李蜜佳卫红权李英乐刘树新（中国人民解放军战略支援部队信息工程大学河南 郑州 ）收稿日期：。李蜜佳，硕士生，主研领域：数据挖掘和分析。卫红权，教授。李英乐，副研究员。刘树新，助理研究员。摘要传统的 分解法具有时间复杂度低的特点，但其划分结果普遍粗粒化，难以满足精细化节点重要性划分的实际需求。基于 分解法，提出一种改进的重要节点挖掘算法。在充分利用节点的网络位置信息的基础上，考虑节点的度数和节点被删除时所处的迭代层数，提出改进的 方法；在用改进的 对节点排名并提取核心网络后，结合节点的 值，定量分析网络核心层的节点，形成多层级的节点重要性划分。在三种真实网络数据集中的实验验证表明，该方法能显著提高 分解法的分辨率，并且时间复杂度低，适用于大规模网络的应用。关键词关键节点社会网络核 中图分类号 文献标志码 ：（，），引言对复杂网络进行深度挖掘和分析在理论和现实中具有重要意义 。社会网络是复杂网络的一个领域，包括人际关系网、网和论文合著网等。社会网络中的各个节点，由于在网络中的结构地位以及活跃度的不同，所起的作用也不同，其中有一部分节点对网络局部或者全局影响较大，这类节点就叫做关键节点。通过挖掘社会网络中的关键节点，可以满足我们的很多实际需求。比如在产品推销网络中，商家可以消耗最少的资源实现产品最高效的推广；在舆论传播网络中，政府可以使用最少的干预手段去宣传舆论或者禁止谣言；在犯罪嫌疑人关系网络中，警察可以快速锁定团伙头目，进而集中警力抓捕。目前，在关键节点挖掘方面，研究人员已经从不同 计算机应用与软件 年的角度探索了很多算法。在基于邻居节点中心性的方法中，度中心性的方法用节点的邻居节点数量来衡量节点重要性，计算复杂度低，但是仅考虑了节点局部重要性，没有考虑节点的网络位置及其他全局信息，准确性不高。等 提出了一种半局部中心性方法，该方法只统计节点的四层邻居的信息，比局部中心性的方法更准确且计算复杂度低，适合于大规模网络，但是由于该方法没有考虑邻居节点所处的不同层次，影响了关键节点挖掘的准确性。之后，等 综合考虑了度中心性与聚集系数，又提出 中心性，该方法适用于大规模网络，但把网络视为无向的，与多数现实情况不符。赵晓晖 综合考虑节点的半局部中心性和聚类系数，提出了一种归一化的局部中心性节点影响力度量算法。等 认为节点距离网络核心越近，所产生的影响力也就越大，由此提出 分解法，该方法计算复杂度低，在分析大规模网络方面应用较多，但是仅对节点进行粗粒度划分，准确性不高。对此，严沛 在 的基础上，使用双向搜索树方法提高算法准确性。在基于路径中心性的方法中，等 认为节点的影响力与节点到其他节点的距离有关，提出离心中心性，该算法很容易受到特殊值的影响。提出接近中心性（），节点的紧密度越大，越靠近网络中心，也就越重要。提出介数中心性（），将节点的重要性由通过该节点的最短路径数目来表示，这两种算法准确度高但计算复杂度也高。与介数中心性仅考虑最短路径不同，中心性 考虑节点对之间的所有路径，并根据路径长度对路径加权，这种算法的时间复杂度也比较高。在基于特征向量的方法中，提出特征向量中心性（），认为一个节点的重要性要综合考虑其邻居节点的数量和质量。等 假设每个节点都在社会网络中被提名，节点的重要性与节点本身及其邻居节点被提名次数有关，由此提出一种累计提名中心性（），该算法比特征向量中心性收敛要快。引擎使用的 算法 是特征向量中心性的变体，该算法综合考虑指向该节点的邻居节点数目和邻居节点自身的重要性。等 提出 方法，引入背景节点使原网络变为强连通网络，从而替代了 算法中的跳转概率 ，性能较 有较大提升。基于路径和特征向量中心性的关键节点挖掘算法虽然准确度高，但是普遍时间复杂度高，无法在大规模网络上进行应用；度中心性、分解法等时间复杂度低的算法虽然适用于大型网络，但是其准确度又不理想，其划分结果难以满足精细化节点重要性划分的实际需求。基于此，本文对 分解法进行改进，在分解过程中综合考虑节点的度数与节点被删除时所处的迭代层次，以解决 划分结果粗粒化的问题。随后采用一种用微观结构去替代原有完整网络的算法，根据改进的 节点排名提取核心网络，并结合 值对核心网络中所有节点做定量分析，找出影响较大的节点，最终形成分层次的重要节点划分。在三个实际网络中进行实验验证，结果表明本文方法具有较低的时间复杂度，计算结果也更准确。算法设计本文分析的社会网络属于有向无权网络，有向网络中，出度 表示以节点 为起始点的边的数目，入度 表示以节点 作为终点的边的总数目。，（）图 的邻接矩阵（），（）是一个 阶方阵，其中：（）节点 与节点 相连 节点 与节点 不相连（）式中：为节点 与 连接。分解法 等 指出在度量节点重要性时，需要考虑节点在整个网络中的位置，他们认为处在网络核心位置的节点会产生较大的影响力，并提出了 分解法。例如，图 是一个由 个节点和 条边组成的无权无向网络图。图 无向网络针对图 所示的无向网络，具体分解过程如下：删第 期李蜜佳，等：基于改进 的社会网络关键节点挖掘算法 除网络中所有度为 的节点及连边，记迭代层数为 。观察剩余网络中是否仍有度为 的节点，如果有，删除节点及连边，迭代层数记作 。循环去除，直至网络中没有度为 的节点，此时将所有被删除节点 值记作 。依次迭代，删除网络中度为 、的节点，直至所有节点都被删除。图 为按照 分解法对网络中所有节点的划分结果。图 分解对图 网络记录 分解全过程如表 所示。表 分解过程迭代层数删除节点 值，改进的 分解法 方法计算复杂度低，在分析大规模网络方面应用较多，但也存在不足。第一，分解法不区分入度与出度，而社交网络基本都属于有向网络 ，节点受关注的程度由节点的入度表示，节点的合群程度由出度表示，忽略入度与出度的不同，会使一些节点以较小的代价通过建立与核心位置节点的单向连边来提高自身核数，从而导致挖掘结果出现较大偏差。第二，分解法属于粗粒度划分，把属于同一层的节点都看作同等地位，忽略了节点度和节点被删除时所处迭代层数的影响，导致大量节点被划分到同一层。如在图 的网络中，节点 和节点 被 分解法划分到同一层，值相同，但显然节点 比节点 重要。对此，本文对算法作如下改进：（）针对社交网络多为有向网络的特点，将传统的 在分解过程中不区分节点入度出度的做法，改为仅考虑入度对节点进行剥离。（）针对传统 划分结果粗粒化，综合考虑节点度和节点被删除时所处迭代层次，例如，图 中的节点 和节点 在被删除时所处的迭代层数不同，度中心性也不同。本文将节点的 值与迭代层数、度值融合得到节点最终的 值。详细分解步骤为：把网络中入度 的节点及其连边删掉，迭代层次记为 。若剩余的网络中仍存在 的节点，再去掉这些节点及其连边，迭代层数记为 。继续删除，直至网络中不存在入度为 的节点。将所有这一层被剥离的节点核数记作 ，值为 。按照 的方法剥离网络中入度 的节点及连边，并将所有这一层被剥离节点的 值记作 。令 ，迭代执行上述步骤，直到网络中所有节点都被删除。此时，改进后的节点核数为 ：（）（）式中：为节点的 值；为节点的度数；为节点被删除时的迭代层数。在图 中，节点 的迭代层数为 ，度为 ，值为，计算得到 值为 。节点 的迭代层数为 ，度为，值为 ，计算得到 值为 。可见，改进的 方法分辨能力更强。伪代码如下：输入：，。输出：节点核数 ，迭代次数 。；（）（，）（）（）；（）；算法 算法 是谷歌搜索引擎的核心算法。计算机应用与软件 年它认为一个节点的重要性取决于指向它的节点的数目和质量。该算法作为有向网络节点排序最经典的算法，被广泛应用于对网页的排序、对社交网络上用户的排序等。作为全局性算法，计算结果较准确，但时间复杂度高于 分解法。由于两种算法相关性不大，本文综合了两种算法的优势，构建关键节点挖掘模型的步骤如下：（）根据社会网络相关数据，构建邻接矩阵。（）用改进的 分解法对网络所有节点快速打分。（）按照得分高低，依次删除外围大约 的不重要的节点及其连边，减小网络规模。（）对步骤（）中提取的核心网络，运用 算法计算出每个节点的 值，并进行归一化和无量纲化处理。（）将经过归一化和无量纲化处理的 值与 值相乘得出结果并排序，挖掘重要节点：（）（）（）（）本文算法框架被称作 算法。社会网络中重要节点一般都是位于网络核心且 值也靠前的节点，因此，在第三步中，对归一化后的 值和 值采取相乘的方法计算最终得分，有助于过滤掉一些起干扰作用的大度节点以及其他一些处于网络核心位置但 值却很低的异常点。评估标准及数据集介绍 评估标准本文采用 （）模型 ，将节点的最大传播力作为节点重要性评价标准。模型是 等提出的传染病模型中最经典的模型，现在普遍应用于疾病传播、谣言传播等领域。图 模型状态转移 模型将网络节点分为三类：易感状态 ，指个体可能会被处于感染状态的邻居节点感染；感染状态，指节点已被感染且具备感染力；免疫状态 ，指节点失去感染其他节点的能力。刚开始传播时，处在感染状态 的节点，以 的概率感染处在 状态的邻居节点，随后，处在 状态的节点以概率 转变成为 状态，不再参与传染。重复上述步骤直至网络到达稳态。模型可用微分方程表示如下：（）（）（）（）（）（）（）（）（）（）在 模型中，全部节点的数量 （）（）（），其中 （）、（）、（）分别为在 时刻网络中三种状态节点的数量。不同挖掘算法的优劣可通过各算法挖掘的重要节点在 模型上的传播范围来衡量。设置一个（组）重要节点为 状态在 模型上进行传播，观察最终稳态时处于 状态的节点数量。如果一种算法的挖掘结果可使网络流传播地又快又广，即可说明该算法挖掘效果优于其他算法。数据集科布伦茨数据资料库是公布在网上，供从事大规模数据处理的人员用来进行网络科学及相关领域研究的工具。本文选取了该资料库三个有向无权的网络数据集作为实验网络，数据集信息如表 所示。（）社交网络数据集：节点代表医生，边表示一位医生遇到问题会向另一位医生求助。（）超链接数据集：节点代表用户，边表示一个用户链接了另一个用户。（）数据集：节点表示一个机场，边表示从一个机场到另一个机场的航班。这三个数据集的基本情况如表 所示，稀疏性表示网络中任意两个节点间存在连边的概率，即网络中存在的连边数量占网络中所有可能连边数的比例。在有向无环网络中，网络的稀疏性 （），其中：为网络中边的数目；为网络中节点数。表 数据集的基本特性数据集用户数连边数稀疏性 仿真验证 实验设计为了验证本文方法的有效性，选取 种排序方法对比分析，分别是度中心性、算法、算法。第 期李蜜佳，等：基于改进 的社会网络关键节点挖掘算法 本文采用单一节点传播的方式，分别对排名前（为了分析方便，设置 ）的节点进行 模型检测，每个节点都作为单一感染源进行传播，运行 次取均值，每种算法的有效性由该算法挖掘出的排名前 的节点传播能力总和来表示。这里将免疫率 取为 。对于感染概率 ，如该值太小，很难在一个较小的网络区域中区分开不同算法 。当 非常高，不管是从哪个节点开始传播，最后传播范围都将覆盖几乎整个网络，导致无法区分节点的作用。对此，本文使用一个温和的感染概率 。实验结果如图 所示，将免疫状态的节点的累计数量绘制成时间的函数，累计免疫节点随时间增加，最终达到稳定状态。在网络规模较小时（如 数据集），度中心性的表现要优于 算法和 算法，但是度中心性算法的准确率与网络规模有关，当网络中节点数增多时，准确率呈现显著下降趋势。这种现象与度中心性本身的算法有关，度中心性仅以节点的局部信息作为衡量标准，而没有考虑节点所处位置、更高阶邻居等因素，这就导致一些边缘节点可以通过与大量普通节点建立连边来提高度值，而这样的算法，在 算法中完全占不到优势，算法以节点入度为参考值去提取核心网络，既删除了大量非核心节点，同时也确保了一些节点无法通过仅仅依靠增加出度而进入到核心网络中。网络上，度中心性算法和 算法、算法曲线近乎一致，即由这三种算法挖掘的前 名重要节点在网络中的传播能力基本相同。算法和 算法在准确度方面的稳定性较佳但算法复杂度高。算法的准确率始终优于 算法，这是因为需要大量实验才能获取 算法中的阻尼系数 ，且会改变原来的矩阵结构。而 在 的基础上，加入一个与其他节点都有双向连边的节点，实现网络的强连通，以此得到一个无参数的算法。实验证明，这种算法比 算法更准确。算法在网络规模小的时候准确率比较低，这是因为 算法对网络中的节点只能做粗粒度的划分。节点的 值越大，节点就越重要 。但具体到两个节点，只有 值相差很大，比如在 倍以上时，节点影响力才有显著差距。而在小规模网络中，节点的 值相差都不大，这就导致部分重要节点在用 分解法提取核心网络时被删除。在本文的实验中可以看到，随着网络规模变大，这种算法的准确度也越高。在 网络中，算法的准确率甚至优于 算法，这是因为 分解法可以有效剔除一些大度节点的干扰。（）网络（）网络（）网络图 各评价方法在不同社会网络中的传播能力对比 准确率分析本文将各算法挖掘出的 节点与 模型挖掘出的 节点进行对比，比值为各算法挖掘 节点的准确率。表 的结果表明，网络规模越大，度中心性挖掘算法的准确性越低。相比，在不同规 计算机应用与软件 年模的网络中，算法和 算法具有更好的稳定性。本文提出的 算法随着网络规模增大，准确率也越高。但由于 模型每一次传播到达稳态需要的时间比较长，本文最大只选取节点数为 多的社交网络进行计算。从实验结果可以预见，网络规模越大，算法挖掘重要节点的效果会更好。表 各算法挖掘出的 节点准确率与 模型对比数据集（，）（，）（，）（，）时间复杂度分析本文提出的 算法是在 分解法的基础上进行改进的，可近似看作 （），与 分解法相同。的计算复杂度为 （），度中心性的时间复杂度为 （），介数中心性的时间复杂度为 （），其中：和 分别为网络中的节点和边的数量；为迭代次数。从表 可以看出，本文所提出的 算法计算复杂度相对较低。表 部分重要节点挖掘算法时间复杂度算法时间复杂度 （）（本文算法）（）（）（）（）（）结语针对传统 分解法划分结果粗粒化的问题，本文提出改进的节点核数指标 ，通过考虑节点被删除时所处迭代层数和节点度来进一步区分不同节点的重要性，使排序结果的分辨能力和准确性都得到提高。随后采用以微观结构代替宏观结构的框架，在用 指标提取核心网络后，综合节点的 值和 值找出关键节点。本文选取三种现实社交网络作为实验数据集，通过在 模型上的仿真实验，验证了 算法在大规模网络中挖掘得到的关键节点准确度更高，在网络中传播能力更强，即挖掘效果更为准确。对比分析表明，本文算法时间复杂度较低，适用于大规模社交网络的应用。参考文献刘树新，李星，陈鸿昶，等 基于资源传输匹配度的复杂网络链路预测方法 通信学报，（）：，（）：，：，（）：赵晓晖 社交网络节点影响力度量及最大化问题研究 济南：山东师范大学，（）：严沛 基于 的多维网络最短路径近似算法研究 沈阳：辽宁大学，（）：，（）：，（）：，：，（）：，：，（）：李治成，吉立新，刘树新，等 基于拓扑稳定性的有向网络链路预测方法 计算机应用研究，（）：，（）：，（）：，（）：