殷澤龍 張煒

摘 要：在進行社交網(wǎng)絡話題傳播時，隨著數(shù)據(jù)量的不斷增大，傳播模型在進行傳播模擬時所花銷的時間更多，程序運行所占用存儲空間也更大。然而，在實際的話題傳播過程中，大多數(shù)話題集中在某些關鍵節(jié)點上，且相當一部分節(jié)點對話題的傳播沒有太大的影響。因此，如果在進行話題傳播時，我們能夠剪掉社交網(wǎng)絡中的某些傳播節(jié)點，這不僅能夠減少程序的運行時間，而且能夠降低數(shù)據(jù)所占用的存儲空間。針對上述問題，我們設計了兩種新穎的圖剪枝算法來減少社交網(wǎng)絡中的節(jié)點數(shù)量。本文所提出的兩種算法是將推薦系統(tǒng)的思想引入到社交網(wǎng)絡傳播模型的剪枝策略研究中，具有一定的新穎性。通過實驗分析，我們對比分析了不同剪枝策略對傳播模型的效果，所占空間，運行時間以及圖的健壯性的影響。

關鍵詞：社交網(wǎng)絡；剪枝策略；傳播模型；話題

中圖分類號：TP391.41 文獻標識號：A

The Research on Pruning Strategies Topic Propagation Model of Social Network

YIN Zelong， TANG Xianglong

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）

Abstract： With the spreading of topics in the social network， topic models would spent more time and more storage space with the increase of the size of data. However， most topics focus on some key nodes and parts of nodes have no significant effect on topic propagation in the real process of topic propagation. If we could reasonably cut some nodes in the social network during the spread of topics， the runtime of the program and the storage space both would be reduced. To solve the above problem， the paper designs two novel graph pruning algorithm to reduce the number of nodes in the social network. The two algorithms presented in this paper introduced the thought of recommend system into the research on pruning strategy of topic propagation models and have a certain novelty. With the analysis and comparison， the paper analyzes the impact of different pruning strategies of propagation model on the effectiveness， the space， running time and the robustness of the graph.

Keywords： Social Network； Pruning Strategy； Propagation Model； Topic

0 引 言

剪枝是一種機器學習技術，通過移除樹的某些節(jié)點來減少決策樹的大小，其中這些節(jié)點對分類實例擁有很小的影響因子[1-2]。剪枝不僅能夠減小算法的復雜性，同時還能夠提高算法的預測準確性。

在決策樹算法中，一個重要的問題就是優(yōu)化最終樹的規(guī)模。如果樹的規(guī)模過大，就會存在訓練數(shù)據(jù)集過度擬合而新樣本概括不準確的問題；樹的規(guī)模過小也會無法把握樣本空間重要的信息結構。同時，也很難分析出算法何時應該停止，因為此時仍無法判斷新加入的節(jié)點能否動態(tài)地減少錯誤，這個問題被稱為視界效應。一個一般化的策略是讓樹自然生長直到停止為止，再使用剪枝策略去移除那些沒有重要作用的節(jié)點。

在本文中，研究擬將將剪枝技術運用到社交網(wǎng)絡話題傳播模型中。在進行社交網(wǎng)絡話題傳播時，話題在不同的用戶之間相互傳播，這些用戶則形成了社交網(wǎng)絡關系圖[3]。當隨著時間不斷向前推移，社交網(wǎng)絡關系圖變得更加復雜，則話題傳播模型在這樣的社交關系圖上模擬將會花費更多的時間和空間。為了節(jié)省空間和時間開銷，本文提出并設計了兩種新穎的圖剪枝策略來減少社交網(wǎng)絡圖中的節(jié)點數(shù)量。文中的算法是將推薦系統(tǒng)的思想引入到社交網(wǎng)絡傳播模型剪枝策略中，具有一定的新穎性。在本文實驗部分，則將本文提出的算法同隨機剪枝策略[4]和基于度的剪枝策略[5]進行比較分析，結果表明本文的算法在剪枝效果上具有明確顯著的優(yōu)越性。

1 問題定義

該小節(jié)介紹了相關概念和符號以及社交網(wǎng)絡話題傳播模型剪枝問題的定義。在此假設給定一個社交網(wǎng)絡關系圖 ， 是社交網(wǎng)絡關系圖中用戶的集合， 是社交網(wǎng)絡關系圖中用戶和用戶關系的集合。同時假設以關鍵詞 作為用戶討論的話題，且在社交網(wǎng)絡關系圖 中存在的話題集合為 ，由于話題在社交網(wǎng)絡中是分布在不同的用戶 上，因此 和 之間存在二元映射關系，如圖1所示。

圖1 話題與用戶的映射關系圖

Fig.1 Mapping relationship between topics and users

一個用戶可以包含多個話題，一個話題也可能對應多個用戶。同時話題對于不同用戶，其權重也是不同的，因此上假設關鍵詞 對于用戶 的權重為 。根據(jù)上述定義，可以抽象出本文的研究問題：已知社交網(wǎng)絡關系圖 和話題集合 ，求出 。為了解決上述問題，本文提出了兩種新穎的圖剪枝算法，根據(jù) 和話題集合 提供的信息，結合圖剪枝算法來獲取 。下面將介紹本文所研究的社交網(wǎng)絡話題模型的剪枝策略。

2 剪枝策略算法研究

本節(jié)介紹了兩種社交網(wǎng)絡話題模型的剪枝策略，基于話題權重和基于用戶興趣相似性的剪枝策略?？偠灾?，這兩種算法均是將推薦系統(tǒng)的思想引入圖剪枝策略中。

2.1 基于用戶話題權重的剪枝策略

基于用戶話題權重的剪枝策略與基于用戶興趣相似度剪枝策略類似，都是利用了話題與用戶之間的關系。不同之處是后者計算與用戶具有共同興趣用戶廣泛度，前者是計算擁有話題的廣泛度。在傳播模型中，如果多個話題出現(xiàn)在某個用戶上，則在一定程度上可以說明話題在傳播過程中頻繁地經(jīng)過該用戶，因此這樣的用戶可以被看作關鍵用戶?；谏鲜龅脑?，研發(fā)設計了一種基于用戶話題權重的剪枝策略算法。

假設社交網(wǎng)絡關系圖為 以及話題集合為 ，每一個話題 被一個或者幾個用戶所擁有，則假設擁有話題 的用戶集合為 ，用戶 擁有話題 的權重為 。首先，對每一個話題 的用戶集合 按照用戶 擁有該話題的權重 進行排序，如圖2所示。

圖 2 基于話題權重的剪枝步驟1

Fig.2 Topic weight pruning step 1

然后，將每個話題的用戶按照從小到大的順序進行編碼，如圖3所示。

圖 3 基于話題權重的剪枝步驟2

Fig.3 Topic weight pruning step 2

最后，循環(huán)遍歷每一個 來統(tǒng)計每一個 的話題權重總和，并排序，如圖4所示。

圖 4 基于話題權重的剪枝步驟3

Fig.4 Topic weight pruning step 3

2.2 基于用戶興趣相似度的剪枝策略

在本節(jié)中，給出了話題集合 與用戶集合 存在映射關系，即同一個用戶可以擁有多個話題，同一個話題可以被多個用戶擁有，因此即以用戶擁有的話題相似性來表示用戶的興趣相似性。在以上研究中，已經(jīng)闡述到用戶的興趣相似度對話題轉(zhuǎn)移概率是有影響的，當用戶間興趣相似度越大，則話題更有可能在同群用戶之間經(jīng)常傳播。如果某個用戶與很多用戶均具有頗高的興趣相似度，則這樣的用戶就是話題傳播過程中的關鍵用戶而應該得到保留。假設用戶 的話題集合分別為 和 ，則采用cosine-index[6]來衡量興趣相似度，即：

（1）

由公式（1）可知，可以計算出 的 。下面將以4個用戶（ ）為例來說明該算法步驟。當計算出所有用戶之間的興趣相似度后，就可以得到如下所示的矩陣圖：

圖 5 基于用戶興趣相似性的剪枝步驟1

Fig.5 Interest similarity pruning step 1

如圖5所示，該圖的前半部分表示用戶興趣相似度的矩陣圖，后半部分即將每一個用戶與之關聯(lián)的用戶興趣相似度進行排序。而后再對排序后的矩陣進行歸一化處理，如圖6所示。

圖 6 基于用戶興趣相似性的剪枝步驟2

Fig.6 Interest similarity pruning step 2

最后，則將歸一化的矩陣中每一個用戶的興趣相似度進行統(tǒng)計，并排序得到綜合結果。具體如圖7所示。

圖 7 基于用戶興趣相似性的剪枝步驟3

Fig.7 Interest similarity pruning step 3

用戶最終得到的權值越大，就說明用戶和周圍用戶有著更為廣泛的興趣相似度，反之亦然。

3 實驗結果與結論分析

本節(jié)主要介紹上述幾種剪枝策略的實驗設計原理以及實驗結果。實驗中采用真實的微博數(shù)據(jù)集來構建社交網(wǎng)絡關系圖和相關話題的提取，并運用上述幾種剪枝策略來對社交網(wǎng)絡關系圖進行剪枝，完成后則將傳播模型的算法在剪枝后的社交網(wǎng)絡關系圖上進行傳播模擬，從而比較不同剪枝策略下傳播模型的預測效果。

3.1 數(shù)據(jù)集

本文采用的是微博數(shù)據(jù)集，抽取的是在某一時間粒度下的數(shù)據(jù)集來構建社交網(wǎng)絡關系圖以及話題的抽取，實驗數(shù)據(jù)及環(huán)境配置如表1所示。

表 1 實驗數(shù)據(jù)及環(huán)境配置

Tab.1 The experimental data and environment configuration

名稱 參數(shù)

實驗數(shù)據(jù) User（節(jié)點）

Connection（邊）

Topic（話題） 11589

72395

107

機器配置 8G RAM，3.40GHZ Core i7 處理器

編程語言 C++

分析工具 Matlab2010，Excel

數(shù)據(jù)庫 Mysql

3.2 實驗設計

本節(jié)從新浪微博數(shù)據(jù)中選取了11 589個節(jié)點以及106 198條邊構成一個社交網(wǎng)絡關系圖，并從中抽取107個話題。首先是將不同的剪枝策略對社交網(wǎng)絡關系圖進行剪枝，然后用傳播模型算法分別在不同的剪枝后的關系圖上模擬話題傳播，比較不同剪枝策略下的預測效果和運行時間。同時，對于每一種剪枝策略，均將會構建實驗并據(jù)此分析不同剪枝程度對傳播模型話題預測效果的影響。

3.3 實驗效果評估

圖8是將準確率和召回率進行結合所得到關于不同剪枝策略對于剪枝比例同傳播模型F1值關系的曲線圖。從圖中可以看出，Degree PruningASC 的F1變化最快也是最低，主要是因為按照節(jié)點度數(shù)從大到小的順序進行剪枝，首先就會剪掉一些關鍵節(jié)點。其次是Random Pruning，然后是Degree PruningDESC。上述三種剪枝方式從某種程度可以反映出節(jié)點的度數(shù)同節(jié)點的影響力之間的正相關性。Interest Similarity Pruning和 Topic Weight Pruning在隨著剪枝比例增大時，前期對傳播模型的準確率并沒有太多的影響。到后期時二者的F1值都會發(fā)生下降，但Interest Similarity Pruning的F1值會出現(xiàn)陡降，因為當剪枝比例越大時，通過Interest Similarity Pruning所剪掉的節(jié)點才是正真意義上的關鍵傳播節(jié)點，因此將會導致話題傳播嚴重受阻，F(xiàn)1急速下降。

圖 8 不同剪枝策略下剪枝比例與F1的關系對比圖

Fig.8 Relation between F1 and pruning proportion based on different pruning strategies

圖9 展示了不同剪枝策略下，剪枝比例同程序運行時間的關系圖。整體上看，隨著剪枝比例增大，所用的時間呈線性下降。Degree PruningDESC的程序運行時間低于其他剪枝策略，因為這具體是按照節(jié)點度數(shù)從大往小進行剪枝，將容易破壞圖的連通性，致使信息傳播受阻。其次是Random Pruning。利用Interest Similarity Pruning，Degree PruningASC 以及Topic Weight Pruning三種剪枝策略剪枝后，傳播模型的運行時間將十分相近，這在某種程度來說如上三種剪枝策略都能夠保證社交網(wǎng)絡中圖的連通性。

圖 9 不同剪枝策略下剪枝比例與運行時間的關系對比圖

Fig.9 Relation between runtime and pruning proportion based on different pruning strategies

4 結束語

本文主要是介紹并研究社交網(wǎng)絡傳播模型剪枝策略。因為在進行社交網(wǎng)絡話題傳播的過程中，數(shù)據(jù)量會不斷地增大，傳播模型在進行傳播模擬時所花銷的時間必將增多，程序運行所占用的空間也會不斷加大，所以本文提出了幾種社交網(wǎng)絡傳播模型的剪枝策略來對社交網(wǎng)絡進行削減，保證在不降低傳播模型預測效果的情況下，能夠減少傳播模型所花銷的時間和空間。首先，本文給出了社交網(wǎng)絡話題傳播模型剪枝策略研究的相關概念和問題定義，主要包括圖的定義，話題定義以及研究的問題描述。其次，本文給出了兩種新穎的剪枝策略，包括基于用戶興趣相似性的剪枝策略和基于用戶話題權重的剪枝策略。最后，本文又給出了上述幾種算法的實驗分析結果，主要從時間的運行效率，所包含節(jié)點比例以及傳播模型的預測效果來進行對比和分析。實驗結果表明，按節(jié)點度大的順序進行剪枝的效果最差，但是模型的運行時間最短；其次是隨機剪枝，效果和運行時間居中；基于用戶話題權重的剪枝策略，預測效果表現(xiàn)最好，同時剪枝策略設計并不復雜。

參考文獻：

[1] HARABOR D， GRASTIEN A. Online graph pruning for pathfinding on grid maps[C]//Association for the Advancement of Artificial Intelligence ，San Francisco， CA， USA：AAAI， 2011.

[2] KRETZSCHMAR H， STACHNISS C， GRISETTI G. Efficient information-theoretic graph pruning for graph-based SLAM with laser range finders[C]//Intelligent Robots and Systems（IROS），San Francisco， CA ：IEEE/RSJ，2011 ：865-871.

[3] DENG H， HAN J， ZHAO B， et al. Probabilistic topic models with biased propagation on heterogeneous information networks[C]// KDD11， New York， NY， USA：ACM， 2011：1271-1279

[4] GOYAL A， BONCHI F， LAKSHMANAN L V S. A Data-Based Approach to Social Influence Maximization[J]. VLDB 2012， 2012，5（1）：73-84

[5] KWAI D， PARHAMI B. A Class of Fixed-Degree Cayley-Graph Interconnection Networks Derived by Pruning k-ary n-cubes[C]// ICPP97 Proceedings of the international Conference on Parallel Processing，Bloomington， IL：IEEE， 1997：92-95.

[6] JOSIFOVSKI V. Comparison of similarity search algorithm over inverted indexes[R]. Stanford：Project for MS&E239 Autum 2010， 2010.