殷澤龍 張煒

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

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

中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)識(shí)號(hào)：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 引 言

剪枝是一種機(jī)器學(xué)習(xí)技術(shù)，通過(guò)移除樹(shù)的某些節(jié)點(diǎn)來(lái)減少?zèng)Q策樹(shù)的大小，其中這些節(jié)點(diǎn)對(duì)分類實(shí)例擁有很小的影響因子[1-2]。剪枝不僅能夠減小算法的復(fù)雜性，同時(shí)還能夠提高算法的預(yù)測(cè)準(zhǔn)確性。

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

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

1 問(wèn)題定義

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

圖1 話題與用戶的映射關(guān)系圖

Fig.1 Mapping relationship between topics and users

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

2 剪枝策略算法研究

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

2.1 基于用戶話題權(quán)重的剪枝策略

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

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

圖 2 基于話題權(quán)重的剪枝步驟1

Fig.2 Topic weight pruning step 1

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

圖 3 基于話題權(quán)重的剪枝步驟2

Fig.3 Topic weight pruning step 2

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

圖 4 基于話題權(quán)重的剪枝步驟3

Fig.4 Topic weight pruning step 3

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

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

（1）

由公式（1）可知，可以計(jì)算出 的 。下面將以4個(gè)用戶（ ）為例來(lái)說(shuō)明該算法步驟。當(dāng)計(jì)算出所有用戶之間的興趣相似度后，就可以得到如下所示的矩陣圖：

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

Fig.5 Interest similarity pruning step 1

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

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

Fig.6 Interest similarity pruning step 2

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

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

Fig.7 Interest similarity pruning step 3

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

3 實(shí)驗(yàn)結(jié)果與結(jié)論分析

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

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

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

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

Tab.1 The experimental data and environment configuration

名稱 參數(shù)

實(shí)驗(yàn)數(shù)據(jù) User（節(jié)點(diǎn)）

Connection（邊）

Topic（話題） 11589

72395

107

機(jī)器配置 8G RAM，3.40GHZ Core i7 處理器

編程語(yǔ)言 C++

分析工具 Matlab2010，Excel

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

3.2 實(shí)驗(yàn)設(shè)計(jì)

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

3.3 實(shí)驗(yàn)效果評(píng)估

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

圖 8 不同剪枝策略下剪枝比例與F1的關(guān)系對(duì)比圖

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

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

圖 9 不同剪枝策略下剪枝比例與運(yùn)行時(shí)間的關(guān)系對(duì)比圖

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

4 結(jié)束語(yǔ)

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

參考文獻(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.