一种基于节点活跃度的链路预测改进算法

王 烨,朱正祥,刘增良,宋文超,黄 勇（.北京科技大学自动化学院，北京,00088；.国防大学信息指挥与作战教研部,北京,0009；.公安部信息安全等级保护评估中心,北京,004）

一种基于节点活跃度的链路预测改进算法

王 烨1,朱正祥2,刘增良2,宋文超3,黄 勇1
（1.北京科技大学自动化学院，北京,100088；2.国防大学信息指挥与作战教研部,北京,100091；3.公安部信息安全等级保护评估中心,北京,100142）

针对赛博空间中的社会舆情数据链路预测的问题，提出将网络节点活跃度作为一个重要的指标整合到预测算法中，以提高链路预测的准确性和科学性。首先定义了节点活跃度并构建三个用于表示节点活跃度的函数，然后以实际数据为样本进行实例验证，最后通过与三个主流算法在使用三个函数前后的准确度进行比较，链路预测的准确度有明显提高。

链路预测；节点活跃度；赛博空间；社会网络；网络舆情

0 引言

随着社交网络对社会生活、国家安全等方面的重要影响，对社交网络舆情传播研究已经引起国内外广大研究者的广泛兴趣。本文拟将近几年新发展起来的链路预测理论与方法应用于社交网络舆情的传播规律研究，以拓宽社交网络舆情传播规律研究的理论与方法，在综合以往研究的基础上，提出将网络节点活跃度作为一个重要的指标整合到预测算法中，提高研究结果的准确性。

1 绪论

链路预测的基本思想是如果两个节点之间相似性（或者相近性）越大，它们之间存在链接的可能性就越大。应注意，相似性并非一般意义上的相似性，而是指一种接近程度（Proximity）。刻画节点的相似性有多种方法，最简单直接的方法就是利用节点的属性，例如在社交网络中，如果两个人具有相同的年龄、性别、职业、兴趣等等，就说他们俩很相似，则他们之间可能存在或产生新链接。利用节点属性的相似性进行链路预测的前提，就是网络中的边本身代表着相似。另外一类相似性的定义完全基于网络的结构信息，称为结构相似性。基于结构相似性的链路预测精度的高低取决于该种结构相似性的定义是否能够很好地抓住目标网络的结构特征。如基于共同邻居的相似性指标，即两个节点如果有更多的共同邻居就更可能连边，在集聚系数较高的网络中表现非常好，有时甚至超过一些更复杂的算法。然而对于集聚系数较低的网络如路由器网络或电力网络等，预测精度就差很多。因此，目前学术界中链路预测的方法研究也是围绕基于节点信息和结构信息这两个方面而展开的研究。

2 基于活跃度的链路预测改进方法

本节提出了一个基于节点活跃度链路预测的改进算法，在原有算法的基础上，将节点的活跃度属性作为一个重要的参数，将节点属性与网络结构进行综合，从而实现更为准确的预测算法。与传统只关注拓扑结构的链路预测算法相比，充分利用节点属性和拓扑结构对于链路预测的优势。

2.1 节点活跃度表示?

定义：节点活跃度（Node Active Degree, NAD），是网络中的节点在时间内与其它节点产生连接的频繁情况。节点活跃度用一个定量值表示，设为,则第节点的活跃度表示为

2.2 常见三种函数

这种函数形式主要表现节点的一种非线性活跃性关系，其活跃性存在一个监界值，当小于该临界值是，其连接信息对于链路预测的作用不大，而一旦突破该临界值，则对进行链路预测的重要性越大。

图2.1 函数形式

图2 .2 函数形式

图2 .3 函数形式

3 实验验证

本节主要利用网络论坛舆论数据进行算法的研究，验证节点活跃度对链路预测准确性的影响，分析节点活跃度是否影响链路预测，以及准确的程度。

3.1 数据源

如图3.1所示，是天涯论坛一个典型的发帖信息。在本文的研究中即以用户编号来标识用户。

图3.1 天涯论坛发帖信息

利用自主开发的网络爬虫，从天涯下载了超过60个回帖数的147个主题。通过对下载数据的结构化并入库，原始数据如下表所示。

表3.1 原始数据

利用这些数据构建一个网民回帖网络，可以看出是一个典型的无向加权网络。但与一般网络不同，在本网络中每个连接会有一个时间属性，用以标识用户在何时进行的连接。

3.2 算法设计与分析比较

构建训练集和测试集时，训练集选择前130个主题，测试集选择后17个主题数据。评价方法采用Precision。下面分别将节点活跃度信息整合到原来的预测算法中，公式分别如下：

An improving method of link prediction based on node active degree

Wang Ye1,Zhu Zhengxiang2,Liu Zengliang2,Song Wenchao3,Huang Yong1
(1.School of Automation and Electrical Engineering,University of Science &Technology Beijing, 100088,China;
2.Institute of Information Operation,National Defense University,Beijing,100091,China; 3.MPS Information Classified Security Protection Evaluation Center，Beijing，100142，China)

This paper derives a new link prediction algorithm that synthesizes network node active degree to improve the accuracy.In this study,a definition of node active degree and three functions was given. Real data from Tianya.cn are used to verify this algorithm and the result of simulation,which is compared to three well-known algorithms.The result shows the accuracy is significantly enhanced,it argues for the importance of applying node link degree on the link prediction algorithms.

link prediction;node active degree;cyber space;social network;network public opinion

TP391

国家自然科学基金(No. 61175122)；广东省重点实验室开放课题基金项目(No. 2011A060901001-14D)