社交網絡數據個性化推薦的可視化方法

李 緒，曹 磊，付 磊

?

社交網絡數據個性化推薦的可視化方法

李 緒1，曹 磊2，付 磊2

(1. 南開大學數學學院，天津 300071；2. 天津大學軟件學院，天津 300072)

針對大規模社交網絡應用中檢索結果過于龐大復雜的問題，將個性化推薦與可視化相結合，用于在大量數據中找到用戶感興趣的信息。在開拓網絡縮放算法的基礎上，提出關鍵信息顯示算法，能夠區別顯示社交網絡關系圖中用戶相對重要的信息和次要信息，增強關聯度較高數據的顯示效果。將帶權值的力導向布局算法應用于用戶關系聚類中，通過在二維顯示空間中合理安排節點布局，達到減少用戶認知負擔和個性化推薦的目的。設計并實現個性化推薦的可視化工具HRVis，在Movielens數據集上進行測試，結果表明，HRVis能夠強調顯示具有良好社會關系的重要用戶以及與用戶相似的關聯用戶，獲得較好的可視推薦效果。

可視化；個性化推薦；力導向算法；社交網絡；多視圖系統；帶權值的力導向算法

1 概述

可視化是一種把抽象信息用圖形表示的技術。借助可視化技術，人們可以直觀分析原本抽象的數據，發現數據中隱藏的模式。信息可視化是可視化的一個重要分支。它是一門集人機交互、圖形學、圖像處理技術、人類認知學、數據挖掘等多學科于一體的交叉學科。

隨著Internet的迅猛發展，社交網絡大規模興起，人們每天閱讀信息、創造信息、傳播信息，使得網絡上的信息數據量以前所未有的速度增長，如Facebook已經擁有上億的用戶，這些用戶每分鐘會發出至少50萬條評論，在網站已經至少上傳了1 400億張照片。面對海量數據，人們迫切希望從中快速找到自己感興趣的內容，但是傳統的信息檢索技術不能直觀地滿足用戶的個性化需求。直到20世紀 90年代，個性化推薦技術才作為一個研究方向被提出[1]。將可視化與個性化推薦技術相結合改進了傳統被檢索被推薦信息的展示方式，降低了用戶觀察解釋數據的難度，在個性化信息檢索技術中具有重要的應用價值和發展潛力。

社交關系網絡數據大多呈現網狀分布的特點，雖然現在已經有很多處理網狀數據可視化的方法[2]，但是這些可視化方法不涉及個性化推薦。當數據量很大時雖然可以很清楚地區分不同類別的信息，但是很難幫助某一特定用戶得到個性化信息。為了解決上述問題，本文將個性化推薦技術與可視化技術相結合，提出面對社交網絡數據的關鍵信息顯示算法，將社交網絡關系圖中相對重要的信息凸顯出來而忽略一些次要信息，并給出針對社交網絡網狀數據的帶權值的力導向布局算法，幫助某一特定用戶快速搜索到與自己相似的用戶，設計與實現了面向社交網絡應用的個性化推薦可視化工具HRVis。

2 相關工作

海量網絡數據可視化技術的研究是信息可視化領域的重要分支。作為一種可以應用于復雜網狀布局的算法，力導向布局算法被廣泛應用于可視化樹狀或者網狀數據[3-4]。隨后，牛頓-拉普森算法、模擬退火算法、GEM算法分別用來改進系統能量方程和最小化能量的選取。文獻[5]指出對于力導向布局算法來說，初始化布局方法的選取很大程度上決定了算法的有效性。文獻[6]受光譜原理的啟迪，提出一個更加簡單有效的初始化方法：當能量方程達到最小化時，每個節點的位置是其鄰域的質心。本文在針對社交網絡的帶權值的力導向布局算法初始化時參考了文獻[6]提出的質心算法，初始化效率較高。

國內外的研究人員在網狀數據的可視化方面做了很多工作，開發了GUESS、yEd和Pajek等可視化分析工具。針對社交網絡可視化，文獻[7]指出社交網絡的分析包括統計回歸分析和可視化這2個方面。在用戶個性化的可視化技術方面，文獻[8]提供了多個基于推薦算法的可視化視圖；文獻[9]在基于用戶行為的推薦可視化領域做出一定貢獻；文獻[10]將聚類分析和可視化相結合；文獻[11]提出網狀數據的推薦可視化系統；文獻[12]幫助用戶進行社交網絡的推薦可視化，從而找到和自己有共同興趣的朋友。文獻[13]將推薦和可視化結合起來用于圖像挖掘，取得較好的效果。

3 基于用戶推薦信息的可視化方法

社交網絡可視化一直是信息可視化的一個難題。本文針對海量社交網絡數據的可視化，提出關鍵信息顯示算法，在有限的空間內高效地展示最重要的信息，從而將關系圖中最重要的信息直觀地推薦給用戶，并提出針對社交網絡數據的帶權值的力導向布局算法，在有限的二維空間上更好地展現了網狀數據的關聯關系，從而可以直觀地向用戶推薦與之類似的用戶。本文使用MovieLens[14]數據集測試取得了很好的效果。

3.1 關鍵信息顯示算法

當社交網絡關系圖中節點的數量非常多(顯示空間已經占滿)時，關系圖呈現出雜亂無章的效果，使得重要的信息隱藏在噪音數據中，推薦算法和可視化布局算法失效，影響推薦效果，因此，需要著重向用戶推薦關鍵信息，忽略意義不大的信息，即去掉一些不太“重要”的顯示部分，僅把關系圖中的重要關系和模式顯示出來。本文針對上述問題，在開拓網絡縮放算法[15]的基礎上提出了關鍵信息顯示算法，取得了比較好的顯示效果。關鍵信息顯示算法的執行是一個迭代的過程，根據信息之間的關聯程度，去掉社交網絡關系圖中不重要的節點，顯著地顯示重要的節點，最終達到向用戶推薦關系圖中關鍵信息的目的。

算法迭代在信息節點的3個集合中完成，3個集合分別為：所有節點的集合-allNode，未訪問節點集合notVisted，已訪問節點集合visited。將notVisted初始化為包含所有節點，visited初始化為空，所有信息節點的初始不透明度值為1，迭代過程如下：

(1)選擇節點：從notVisted中隨機選擇一個節點targetNode(所有節點以均等的概率被選中)，將targetNode從集合notVisted中刪除，放入集合visited中。

(2)尋找鄰居節點：訪問-allNode，找到targetNode的所有鄰居，即所有與targetNode直接或者間接相連的節點，計算節點targetNode到所有鄰居節點的最短距離以及到達步數，節點之間的距離通過節點間連接的相似度之和計算，對于直接相連的節點，其連接步數為1，節點距離為兩節點連接邊的相似度。

(3)調整鄰居節點不透明度：增加targetNode的鄰居節點的顯示不透明度，對于每一個鄰居節點，調節后的不透明度使用式(1)進行計算：

其中，(,)為節點間最短距離；(,)為節點間連接步數。

(4)調節所有節點不透明度：將所有節點的透明度減少(為用戶設定的常量)。

(5)迭代選擇節點直到集合notVisted為空。

當算法結束時，網絡節點關系圖將強化顯示關聯關系較多的節點，而忽略離散出現的節點，在社會關系網絡的應用中，通常認為越多與周圍人群發生關系的人越重要。圖1、圖2是使用關鍵信息顯示算法前后的可視化效果對比。

圖2 使用關鍵信息顯示算法后的可視化效果

從圖2可以看出，采用關鍵信息推薦后大量無關數據已經實現了透明化，而與周圍關聯關系較多的關鍵數據則被保留下來。

3.2 帶權值的力導向布局算法

力導向布局算法適用于表現具有網絡連接特點的數據，社交網絡中節點間的關聯十分密集，并且根據關聯程度不同擁有不同的權值，而經典力導向布局算法忽略了邊的權重。本文在經典力導向算法的基礎上將邊的權重加入到力學模型中，提出一種能夠有效反映節點之間強弱關系的布局算法：帶權值的力導向布局算法。

3.2.1 帶權值的力導向視圖模型定義

與經典力導向算法類似，帶權值的力導向布局算法的力學模型借鑒了物理系統中模擬粒子間的2種力：節點之間的斥力以及相鄰節點之間的引力。在力導向布局算法的模型基礎上，定義帶權值的力導向布局算法的力學模型。

(1)斥力模型公式為：

(2)引力模型公式為：

從斥力模型公式中可以看出，2個節點的距離越近，它們之間的斥力越大，保證了節點分布不會過近，有效地防止了節點重合。在引力模型公式中，節點之間的引力與節點之間距離的平方呈正比，與節點之間權重呈正比。保證相連接的節點不會被斥力排斥的過遠，使得關聯密切的節點在布局上的空間距離較短。

3.2.2 帶權值的力導向視圖初始化

在力導向布局算法中，初始化布局十分重要，影響完成布局的計算時間和所占用的空間面積，本文參考文獻[6]提出的質心算法進行初始化布局，迭代調整節點的位置，使得節點處于其鄰域的質心，質心算法的描述如下：

輸入圖=(,)，迭代次數默認為3

輸出布局分布()=(p)∈V

begin

for i=1 to total iteration do

for each v∈V do

//deg(u)是點u度，N(v)是點v鄰域

end for

end for

end

3.2.3 帶權值的力導向布局算法中邊屬性的選擇

網絡關系圖中邊的屬性能夠反映節點之間關系的強弱，有3種邊屬性可用于反映節點關系的示例：(1)邊的長度；(2)邊的寬度；(3)邊的顏色。

使用邊長度屬性來判斷節點間關系的強弱，如節點間關系越緊密，邊長度越短，反之則長，與力導向布局中的用戶對節點距離的認知保持一致，因此，在本文算法中選用該屬性用于表現節點間關系。

使用邊寬度屬性能夠反映節點關系的強弱，例如線越粗表示關系越密切，線越細代表關系越疏遠。但是可能存在2個問題：(1)邊的寬度不能超過節點的大小，否則圖形會非?；靵y；(2)當所有關系強度差距很小時，人眼無法區別出各節點關系的強弱。

使用邊的顏色能夠鮮明地突出節點關系的強弱，但如果圖中邊的權重是連續分布的，那么就需要為每個權重來分配不同的顏色。然而人眼識別顏色的數量是有限的，并且要記住每種顏色對應的權值，反而增加了用戶的認知負擔。

3.2.4 帶權值的力導向視圖的終止條件

3.2.5 與其他布局算法的比較

將本文提出的帶權值的力導向布局算法與KK布局算法[16]、SM布局算法[17]在Pajek datasets的V379-E914測評數據集上進行比較，如圖3所示。從中可看出，KK算法過于強調節點間的連接，使得節點的信息不夠突出，產生的可視化布局效果不盡理想；SM算法產生的可視化布局圖比較雜亂，無法反映節點之間的聯系，而本文提出的帶權值的力導向布局算法效果比較理想，能夠在體現節點信息、節點之間的聯系和合理的布局這些因素間達到較好的平衡。

圖3 布局算法在數據集V379-E914上的可視化效果比較

4 個性化推薦的可視化工具HRVis

本文提出面向社交網絡個性化推薦的可視化工具：HRVis(Human Relation Visualization)，用來探索社交網絡中最重要的信息以及不同用戶的關聯關系。該系統設計采用多視圖模式，包含關鍵信息視圖、基于帶權值的力導向布局的聚類視圖和高亮視圖，其中，關鍵信息視圖可以向用戶推薦一個關系圖中相對重要的信息；基于帶權值的力導向布局的聚類視圖和高亮視圖可以用來向用戶推薦與自己關系較近的其他用戶。在GroupLens提供的Movielens數據集上進行實驗，獲得了較好的可視效果。

4.1 關鍵信息視圖

關鍵信息視圖采用關鍵信息顯示算法，可以向用戶推薦大規模網絡關系圖中最重要的信息。本文視圖采用MovieLens中前500個用戶的數據作為數據源，顯示結果如圖1、圖2所示，圖1是未經關鍵信息推薦的原始數據可視化，而圖2是使用關鍵信息推薦可視化算法后的可視化效果。從效果對比結果可以看出，關系圖中最為重要的用戶被逐漸突顯出來，實現關系圖中重要信息的顯著性推薦。

4.2 基于帶權值的力導向布局的聚類視圖

對于一個用戶關系網絡，對用戶進行有效的聚類，能夠幫助用戶更好地定位自己的群體，進一步找到自己可能喜歡的內容。k均值算法是一種基于距離的聚類算法，適合對用戶的相似性進行聚類分析，HRVis系統在帶權值的力導向布局的基礎上，實現了k均值聚類算法。本文以MovieLens中的前100個用戶的數據作為數據源，得到當=8時如圖4所示的聚類效果。隨著關系圖中類的數量變化，能在不同范圍內向用戶推薦與之有共同興趣的其他用戶。

圖4 基于帶權值的力導向布局的聚類視圖可視化效果

4.3 基于帶權值的力導向布局的高亮視圖

在一張紛繁復雜的關系圖中，可以使用不同的方式向用戶推薦與之有共同特征的用戶，在HRVis中使用高亮視圖實現用戶推薦。當用戶對某個用戶感興趣時，通過搜索框在關系圖中搜索這個用戶的名字，這時該用戶以及和該用戶相似的用戶會被突顯出來，而其他用戶的不透明度會降低。高亮顯示既找到了用戶感興趣的內容，也沒有破壞關系圖的整體顯示效果，增強了個性化推薦的視覺效果。

在進行節點透明度調整時使用關鍵信息視圖中類似的方法，當用戶選定或者搜索到目標用戶時，與之相連的用戶節點分為以下3種情況進行處理：(1)與該用戶直接相連，則具有與該用戶相同的不透明度1。(2)與該用戶間接相連的用戶節點，其不透明度為兩節點間最短距離除以步數的平方。(3)與節點不相連的其他用戶節點的不透明度為一個較小常量。

以MovieLens中的前100個用戶的數據作為數據源，圖5是搜索用戶“Lily Allen”的可視化結果，“Lily Allen”以及與她相似度較大的用戶以較高的不透明度顯示出來進行強調，而其他用戶作為背景顯示。

圖5 基于帶權值的力導向布局的高亮視圖可視化效果

5 結束語

本文提出一種針對社交網絡的關鍵信息顯示算法和帶權值的力導向布局算法，將顯示方式與數據記錄通過數據集中的關聯度聯系起來，并在此基礎上設計并實現了個性化推薦的可視化工具HRVis，在MovieLens數據上的實驗結果表明，本文方法能夠取得較好的可視化效果，輔助用戶快速找到需要的信息。在今后工作中，將對帶權值的力導向布局算法進行優化，使用更多的節點屬性與連接關系作為相似度評價標準，如邊的平滑度、節點和邊的均勻性等，提高布局算法的性能；同時進一步擴展HRVis在人機交互領域的應用。

[1] Hill W, Stead L, Rosenstein M. Recommending and Evaluat- ing Choices in a Virtual Community of Use[C]//Proc. of SIGCHI Conference on Human Factors in Computing Systems. New York, USA: ACM Press, 1995: 194-201.

[2] Hachul S, Jünger M. Drawing Large Graphs with a Potential- field-based Multilevel Algorithm[C]//Proc. of the 12th International Conference on Graph Drawing. New York, USA: Springer, 2004: 285-295.

[3] 全 武, 黃茂林. 一種用于Marching-Graph圖形繪制的快速收斂布局算法[J]. 軟件學報, 2008, 19(8): 1920-1932.

[4] 吳 鵬, 李思昆.適于社會網絡結構分析與可視化的布局算法[J].軟件學報, 2011, 22(10): 2467-2475.

[5] Fruchterman T M J, Reingold E M. Graph Drawing by Force-directed Placement[J]. Software: Practice & Experience, 1991, 21(11): 1129-1164.

[6] Zhou Weihua, Huang Jingwei. A Fast Multi-level Algorithm for Drawing Large Undirected Graphs[C]//Proc. of International Conference on Internet Computing in Science and Engineering. Harbin, China: [s. n.], 2008: 110-117.

[7] Perer A, Shneiderman B. Integrating Statistics and Visuali- zation: Case Studies of Gaining Clarity During Exploratory Data Analysis[C]//Proc. of SIGCHI Conference on Human Factors in Computing Systems. Florence, Italy: ACM Press, 2008: 265-274.

[8] Koop D, Scheidegger C, Callahan S, et al. VisComplete: Automating Suggestions for Visualization Pipelines[J]. IEEE Transactions on Visualization and Computer Graphics, 2008, 14(6): 1691-1698.

[9] Duval E. Attention Please!: Learning Analytics for Visuali- zation and Recommendation[C]//Proc. of the 1st International Conference on Learning Analytics and Knowledge. Banff, Canada: ACM Press, 2011: 9-17.

[10] Jeffrey H. Vizster: Visualizing Online Social Networks[C]// Proc. of IEEE Symposium on Information Visualization. Minneapolis, USA: IEEE Press, 2005: 32-39.

[11] Crnovrsanin T, Liao I, Wu Yingcai, et al. Visual Recom- mendations for Network Navigation[C]//Proc. of the 13th Eurographics/IEEE-VGTC Conference on Visualization. Bergen, Norway: IEEE Press, 2011: 1081-1090.

[12] Liang Gou, Fang You, Jun Guo, et al. SFViz: Interest-based Friends Exploration and Recommendation in Social Networks[C]//Proc. of 2011 International Symposium on Visual Information Communication. Hong Kong, China: ACM Press, 2011: 15-18.

[13] 衛穎奇, 彭進業, 張漢寧. 個性化圖像推薦及可視化研 究[J]. 計算機工程, 2011, 37(2): 221-223.

[14]Movielens[EB/OL]. (2011-08-11). http://movielens.umn.edu/.

[15] White H D. Pathfinder Networks and Author Cogitation Analysis: A Remapping of Paradigmatic Information Scientists[J]. Journal of the American Society for Information Science and Technology, 2003, 54(5): 423-434.

[16] Kamada T, Kawai S. An Algorithm for Drawing General Undirected Graphs[J]. Information Processing Letters, 1989, 31(1): 7-15.

[17] Hachul S, Junger M. Drawing Large Graphs with a Potential- field-based Multilevel Algorithm[C]//Proc. of the 12th International Conference on Graph Drawing. New York, USA: Springer, 2005: 285-295.

編輯 陸燕菲

Visualization Method of Data Personalized Recommendation in Social Network

LI Xu1, CAO Lei2, FU Lei2

(1. School of Mathematics, Nankai University, Tianjin 300071, China; 2. School of Computer Software, Tianjin University, Tianjin 300072, China)

Aiming at the problem that the search results are too huge and complex in the application of large-scale social networks, the method of combining personalized recommendation with visualization is proposed to find useful information from mass data. This paper proposes a key information display algorithm on the basis of Pathfinder Networks(PFNET) algorithm to display key information by emphasizing important records with high degree of associations. Additionally, an improved weighted force-directed algorithm is applied to cluster user relations to improve displaying layout for the purpose of facilitating users’ cognition and achieving personalized recom- mendation. It designs and implements a visualization of personalized recommendation tool HRVis. The Movielens datasets shows that the HRVis can emphasize important users which have good social relations and associated users which are similar to the users, and it has good visual recommendation effect.

visualization; personalized recommendation; force-directed algorithm; social network; multi-view system; weighted force- directed algorithm

1000-3428(2014)03-0046-05

A

TP391.7

國家自然科學基金資助項目(60373061)；天津市科技支撐計劃基金資助重點項目(11ZCKFGX01200)。

李 緒(1980－)，男，碩士，主研方向：數據挖掘，可視化分析；曹 磊、付 磊，碩士。

2013-02-04

2013-03-12 E-mail：lixu@nankai.edu.cn

10.3969/j.issn.1000-3428.2014.03.009