一种基于关联关系的有向网络关键节点挖掘算法

《一种基于关联关系的有向网络关键节点挖掘算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一种基于关联关系的有向网络关键节点挖掘算法梁莹莹黄岚王喆吉林大学计算机科学与技术学院符号计算与知识工程教育部重点实验室（吉林大学）吉林大学珠海学院计算机系教育部符号计算与知识工程实验室关键节点在网络中的重要程度高于其他人部分节点，关键节点挖掘是网络分析的重要研究A容，对网络结构和网络屮的关系等研究而言都具有非常重要的意义。己有的关键节点挖掘算法从不同的侧重点进行节点关键性评价，文中基于网络中节点的局部性信息，结合节点与其一阶邻居节点的关联关系，提出了一种有向网络关键节点挖掘算法。该算法在关注节点所处局部环境的同时考虑关联节点间的关联强度及重要性影响，根据局

2、部重要性和关联重要性共同进行关键节点的评价。在实验网络上的影响力传播实验表明，相比于经典的度屮心性等关键节点评价算法，所提算法挖掘得到的关键节点对影响力的传播能力更强，说明了算法的准确性。关键词：有向网络;屮心性;关联关系;关键节点;影响力传播;在通信网络中，若对其中的关键部分采取预防和保护措施，当网络遭到攻击时，可以最大限度地降低损失，提高网络的抗毁性。在社交M络中，挖掘关键用户可以为高效营销、谣言控制等工作提供帮助，维护网络安全［3-4］。因此，如何识别网络中的关键节点具有非常大的研宂价值和现实意义［5-6］。中心性是度量关键节点的重要指标，是指派给网

3、络中每一个节点数值的函数，可以从许多不同的角度来计算节点的中心性Hf。近年来，结构化中心性方法得到了较多关注，如度中心性m、介数中心性M等，这类中心性计算方法简单直观，利用网络拓扑结构信息挖掘关键节点的方法已经被广泛应用然而，结构化屮心性方法也存在一些不足，如度屮心性III方法由于考虑因素过于局限，因此有些情况下不能有效反映网络中节点的重要程度;介数中心性m的计算复杂度过高，难以用于大规模网络中等。因此，随着研究的深入，研究人员也提出了很多新的结构化中心性方法［11-17］。这些方法都从某一方面对关键节点挖掘工作做出了改进，取得了较好的效果，但也存在一些不

4、足。文献［11］首次提出节点重要性依赖于其在整个网络屮的位置的思想，并提出了k-shcll指标，该指标的计算复杂度低，可应用于大规模网络，但其仅考虑剩余度的影响，将具有和同剩余度的节点看作同等地位，忽略了现实世界中节点的出度和入度分别代表着不同含义，显然在某些情况下不能合理地反映节点在网络中的重要程度。文献［12］提出了一种基于半局部信息的节点重要性排序方法，该方法仅对节点的四阶邻居进行数量统计，对节点间的关联关系没有做深入研究，如关联方向、关联强度等;此外，该方法将不同层次的邻居节点视作同等地位，不能反映出不同层次的邻居节点对节点中心性的影响。文献［13

5、］提出了基于度与聚集系数的算法，综合考虑了节点的度及其邻居节点间的紧密程度，并且只需考虑节点的局部性信息，其适用于人规模网络;但该算法将研究的网络视作无向的,不能反映真实网络屮的情况，影响丫关键节点评价的准确性。文献［14-15］均利用了重耍性贡献矩阵的思想，考虑了关联节点间的重耍性影响，但对节点间重要性贡献比例的计算方法较粗糙。另一方面，在有向网络的关键节点挖掘领域也出现了很多新的算法，著名的PageRank算法认为：从任意网页出发，釆用输入网址来访问其他网贞的概率相同，但这不符合现实中人们在浏览网贞时的访问习惯;此外，PageRank算法屮参数c的选取

6、往往需要通过实验获得，并且在不同的应用背景下最优参数不具有普适性。文献［16］提出了LeaderKank算法，该算法很好地解决了这两个问题M，在相同的实验背景下，LeaderRank算法收敛速度更快，健壮性更强，对网络中关键节点的识别效果更好。文献［17］提出了ClusterRank算法，该算法基于节点的局部性信息，与Page-Rank和LeaderRank相比在运行时间和最终效果上具有明显优势，但是该算法丢失丫节点间的信任程度信息，没有对邻居节点间的关联强度进行深入的研宄和探讨。可以看出，尽管结构化中心性方法在计算复杂度等方面表现突出，但其进行关键节点评

7、价时依赖于网络拓扑结构信息，可用信息有限;部分结构化中心性方法忽略了节点间关联的方向信息或关联强度信息，不能合理地反映现实世界中的真实情况，从而影响了关键节点挖掘的效果。针对这一问题，本文提出了一种基于关联关系的有向网络关键节点挖掘算法，综合考虑节点的局部性信息和节点间的关联关系，并计算关联强度，利用局部中心性和关联中心性共同完成关键节点评价，取得了较好的效果。2基于关联关系的有向网络关键节点挖掘文献［18］提出，网络中节点的行为与其邻居节点密切相关，节点间的关联关系将影响节点的行为及其在网络中的中心性。以社交网络为例，节点的入度代表苏受欢迎程度，出度代表

8、合群程度［19］，这些都将对节点的屮心性产生影响，将其视为无向网络