近几年,基于六度分隔理论(Six Degrees of Separation)^{[ 1]}和150法则(Rule of 150)^{[ 2]},以认识的朋友(一度关系人)为基础,在已有朋友的基础上扩展自己的关系网,从而得到强大而有效的SNS(Social Network Service)网站逐渐成为Web2.0中最受欢迎的应用之一,基于SNS的应用也遍布于互联网的各个角落^{[ 3]}。

社会网络搜索是SNS网站的一个关键技术,目的是帮助用户通过在SNS网站中已构建的社会网络社区,找到想与之建立联系的朋友,使其成为自己的一度好友,然后再通过已经建立联系的一度好友,与其一度好友的朋友建立联系,从而建立用户自己的六度关系群。用户可以通过不定期地更新这种六度关系群进行初步的社会和商业的应用,该部分设计的好坏直接关系到SNS网站的质量和发展。基于上述背景,社会网络搜索技术成为了当今国内外研究的一个热点问题。本文通过分析和研究近几年来国内外的一些理论成果,总结出社会关系网络搜索机制的整体框架、每部分所采用的关键技术及发展方向。笔者着重介绍关键技术和思路,相关技术细节可参考相应的文献。

社会网络搜索是一种以互联网上的海量信息为计算基础,基于传统搜索的信息挖掘技术,以人物为中心的信息聚合的垂直搜索,搜索的目的是将人和人之间的关系抽取出来,针对要查找的目标人物给出围绕该目标人物的丰富信息,包括人物简介、人物关系等内容,并可以根据指定关系查看详情。目前的SNS网站中都把社会关系搜

索作为一项最重要的服务。已经发布的比较著名的社会网络搜索引擎主要包括雅虎人物搜索、微软人立方(EntityCube)、腾讯搜索华尔兹、Ucloo搜人、Spock等。图1是通过人立方搜索出来的“滕桂法”的社会网络关系和六度分隔效果图。社会网络搜索的具体流程如图2所示。

图1

	Figure Option ViewDownloadNew Window
	图1 人立方效果图

图2

	Figure Option ViewDownloadNew Window
	图2 社会网络搜索流程图

社会关系获取是一种将人、团队、部门、企事业和社区等视为“本体”,从相关信息源中抽取各种本体,建立每个本体的信息剖面,通过分析每个本体的各种特征和属性,挖掘各个本体间的各种关系,包括二元关系、多元关系和传递关系,建立本体间的社会关系网络,该部分是整个社会网络关系搜索中的核心部分。关于社会关系的获取可以归纳为确定网络中的节点和边的问题,也就是社会网络中的实体和实体之间的相互关系。目前国内外对社会关系获取的方法主要分为手动获取社会关系和自动获取社会关系两大类。

社会网络可视化的最初研究可以追溯到20世纪30年代, Freeman 阐述了社会网络可视化发展的进程,总结了社会网络在各自时期的显示方法,并提出了进一步的研究方向^{[ 20]}。经过几十年的发展,社会网络的可视化技术已经达到了一个较高的水平,文献[21]-[26]代表了当今国内外发展的现状。但也存在一些问题,主要有:如何显示人物之间的关系及多维属性(包括性别、年龄、职业、兴趣爱好、通讯地址等);如何在有限的页面中显示社会网络的主要结构。解决上述问题的主要方法有树状列表显示和二维图形显示两种形式。

树状列表形式在目前的大多数即时通信软件中被普遍采用,通过对好友分类,把好友以列表或者树状图的形式进行显示。用户通过点击每个类别,该类别中的好友将以树状图的形式进行展开,用户通过点击每个好友的头像可以进一步查看用户的详细信息,该方法的优点是易于实现,简单清晰;缺点是缺乏互动性,不能充分展现出好友之间的亲疏程度和社会网络结构。

二维图形显示则是用节点表示用户和好友,用边表示好友之间的关系。目前使用较普遍的主要有以下几个方向:

(1)六度拓扑显示方法(相关网址参见http://www.6dtop.com/6dtop/)^{[ 29]},该方法以用户为圆心,首先在外围一圈罗列出用户的好友,即一度好友;然后是更外面的一圈,罗列出好友的好友,即二度好友。以此类推,最多可以到六度好友。但是,随着好友度数的上升,好友数量将呈几何级数增加,因此该方法对硬件的要求很高,而且随着好友的不断增减,页面的布局也显得异常凌乱。

(2)一种基于Force-Directed-Layout的算法^{[ 27]},节点之间可以相互挤压,而节点之间的边可以像弹簧一样进行缩短和拉伸,这种算法不仅可以很好地解决页面布局的问题,而且各用户还能够产生动态的效果,使网络更加形象生动。目前比较流行的Douban Link、Facebook Visualiser、Flickr Graph 都是以社交网络为数据基础,以Force-Directed-Layout为核心算法实现的社会网络可视化系统。例如:LinkBar^{[ 28]}就是基于上述算法开发出来的一种社会网络可视化工具。用户可以根据需要在节点中显示出好友上传的头像和昵称,单击好友则在右边的显示面板中显示出他的一些属性信息,此外,用户还可以通过拖动在右上角的好友度数按钮,设定工具只显示用户的一至六度好友。社会网络可视化具体的效果如图3所示:

图3

	Figure Option ViewDownloadNew Window
	图3 社会关系可视化效果图

在社会网络可视化部分,为了避免各个元素出现交叉或重叠的冲突,可以采用三维显示技术代替目前的二维图形显示。三维立体图形可以通过旋转、放大和切换视角来从不同的角度观察单个元素的相关人际关系,这样既能增加每个元素关系的显示数量,又能方便查看和搜索。三维立体可视化技术将是该部分今后的发展方向。

社会关系搜索主要是根据在六度关系中每个人可以看作是关系图中的一个节点,两个节点通过线直接相连表示他们存在相互联系。这样就可以把社会关系网看成是图论中的点和边的相互关系。在路径图中,连接两个节点的一条边可以根据这两个节点的亲疏度赋予权值,通过定义路径上多个边的权值计算规则,这样两节点之间的路径就变成有权值的,最后根据最短路径算法从加权的社会网络图中找到一个用户到达另外一个用户的最少链接。

社会关系搜索主要分为两大部分,即最短加权路径算法和对人际关系的加权处理。目前最常用的最短路径算法主要有:Di jkstra算法、A*算法、 SPFA算法、Bellman-Ford算法、Floyd-Warshall算法等,国内外大量的文献都对上述算法进行了详细的介绍和改进,这些算法已经比较成熟,本文不再具体叙述。在对人际关系的加权处理上,由于加权与朋友间的亲疏程度和他们所处的社会关系密切相关,而他们的亲疏程度和社会环境又随着时间和空间不断动态变化,因此对朋友间的权重很难数值化,目前尚无法很好地解决如何设定用户朋友权重的问题,此领域的研究也很少。

如何利用已经构建的社会关系网络,对人物关系进行精确而有效的分类,并设定不同关系的权重,是社会关系搜索的关键。比较流行的解决办法是事先定义各种关系类型,然后根据人工构建的社会关系体系进行加权。但是构建一个精确全面的关系体系往往是很困难的,甚至是不可能的。例如Relationship^{[ 29]}规定了40多种人物关系,如果对每种关系都设置关系,那么对实例来构建关系体系将是相当大的工作,而且在Web中展示的人物关系往往也不是如文献[29]规定的人物关系。笔者认为,对于人际关系的加权处理,可以根据Web的不同信息源来进行加权。对于BBS、论坛、博客、E-mail等各种自治的社会网络,朋友之间往往越亲密,相互之间的交流也越多,可以通过统计用户一段时间内发起对话的多少(回帖数、消息数、邮件数)进行关系加权。而对于通过特定的数据集在无意间构成的在线论文社会网络,可以根据论文作者之间的共同作者或者排列顺序进行关系加权(往往两个作者共同发表的论文数量越多,他们的关系越紧密;往往第二作者与第一作者要比第三作者与第一作者的关系紧密);而对于根据各种新闻资讯构建的社会网络,对关系进行加权比较复杂,可以根据在一定段落或一句话里同时出现两个以上的人名就认为他们有关系,通过统计两个人名共同出现的频率来进行亲疏度的判断。由于社会关系随着社会环境的变化而变化,今后还可以考虑更多的因素进行研究:

(1)社会关系本身所属的类型:根据不同社会关系类型(血缘关系、同事关系、同乡关系等)其亲密程度是不同的进行加权。

(2)信任的影响:往往对朋友越信任,双方之间的关系也越紧密。

(3) 熟识度:往往双方越熟悉,其关系就越亲密,信任度也越高。

(4)声望和地位:一个人的声望和地位越高,则会吸引他人愿意与其交往,并被赋予较高的信任度。

(5)关系时间量:包括交互频度和持续时间。花在关系上的时间量越多,则关系越亲密,反之则越疏远。

社会网络搜索已经成为SNS服务中的一个非常具有前景和挑战的研究领域。本文从社会关系获取、社会网络可视化和社会关系搜索三个层面,较为系统地梳理并介绍了各部分的主要技术和优缺点,并对其发展方向进行了展望,以期为将来社会网络搜索的进一步研究提供参考。