一種基于節點活躍度的鏈路預測改進算法

王 燁,朱正祥,劉增良,宋文超,黃 勇（.北京科技大學自動化學院，北京,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)