社交网络数据个性化推荐的可视化方法

李 绪，曹 磊，付 磊



社交网络数据个性化推荐的可视化方法

李 绪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)边的宽度不能超过节点的大小，否则图形会非常混乱；(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