彩印SNS的用户亲密度算法*

赵天宸，朱晓民，王纯

（1 北京邮电大学网络与交换技术国家重点实验室，北京 100876；2 东信北邮信息技术有限公司，北京 100191）

彩印SNS的用户亲密度算法*

赵天宸1，2，朱晓民1，2，王纯1，2

（1 北京邮电大学网络与交换技术国家重点实验室，北京 100876；2 东信北邮信息技术有限公司，北京 100191）

在彩印业务SNS用户亲密度模型中，用户的亲密度计算是核心问题。社交网络的核心价值就是再现用户现实人际关系，如今多种多样的社交网络服务中对于用户关系的展现大都是粗粒度的。本文以六度分割理论为理论基础，结合彩印业务的特点，对SNS用户关系建模分析，进行用户间的距离量化计算，展现SNS用户的亲密度，从而提高社交网络服务的业务扩展性，实现SNS用户价值。

六度分割；彩印业务；亲密度

在社交网络发展如火如荼的今天，人们越来越倾向用新媒介进行交往和对话，而不是传统意义上的面对面交流。在社交网络中，个人既是网络的中心，又是一个节点。SNS(Social Networking Services)社交网络的理论基础是哈佛大学心理学教授StanleyMilgram 1967年创立的六度分割理论，即“你和任何一个陌生人之间所间隔的人不会超过6个，也就是说，最多通过6个人你就能够认识任何一个陌生人。”SNS的主要功能就是为用户提供通过互联网所联结的人际关系网络，并帮助用户通过其个人人际关系网络实现其它方面要求。在聚合广大相应类型受众后，增加自己所具有的固定用户的用户黏性，并对其提供精细化服务，从而得到这一部分用户所具有的资源，并吸引越来越多的互联网受众群体，达到精细化服务的效果，从而扩大规模，进一步巩固和发展自己，这就是SNS的发展模式。在这个过程中，用户之间的网状关系链的扩张是一切的基础。比起构建新的关系而言，社交网络服务在过去主要被用于强化与已熟识的人之间的关系，但近年来开始提供便捷地服务以方便与素不相识的陌生人建立关系网。

彩印业务是一项在用户通话过程中附加信息传递的增值业务。在用户进行通话的过程中，由系统自动将用户预先设定好的彩印信息（笑话、心情、商情等）推送到对方手机上，使对方用户在通话结束后看到彩印信息，以达到彰显个性、分享心情、商情传递、营销推广等目的。传统增值业务用户量很大，但业务活动率不高。究其原因，是因为传统增值业务的系统仅停留在人机交互的层次。人们需要的是更有人情味的交互方式，更放松的方式去参与业务的二次活动。同时，在互联网已经渗入到人们生活每个角落的今天，传统电信增值业务需要渗透到互联网领域中，开拓新的业务模式，以实现更好地为人们生活服务的同时业务本身价值的最大化。根据六度空间理论可知，人与人之间的距离是有限的，即是可度量的。本文根据用户信息的各个维度，建立量化的用户亲密度模型，提出彩印SNS中用户亲密度的算法，更加细粒度地反映出用户的现实亲密度，提高业务可拓展性。

1 彩印业务用户亲密度模型

1.1 基本亲密度

在彩印SNS中，用户与联系人间具有基本的现实关系，具体为家人、同学、朋友、同事、商务伙伴等。这些基本的现实关系构成了用户间的基本亲密度B(F，N)，且Bfamily＞Bfriend＞Bschoolmate＞Bcolleague＞Bbusiness。同时具有多重关系的时候，基本亲密度其中kj为Bj对应的重要系数。互不相识的用户间亲密度B为0。

1.2 互动亲密度

用户在社交网站上会进行留言、邀请、分享等互动活动。这些互动活动的频繁度可以真实地展示用户之间的亲密程度，这就是互动亲密度C(F，N)。

SNS网络中用户的关系可以通过有向带权图G（N，E，W）表示。N为网络中的节点集合，表示所有用户；E为网络中节点间的有向边，表示用户间的交流互动行为，节点之间有边表示用户间有交流互动行为，边的弧头指向表示交流行为的接受方；W为有向边的权重，表示互动行为的值，值越大表示互动的越多。另一方面，由于交流是双向的，一味单方面的交流行为不能代表用户真的很亲密，所以取两节点间双向权值的较小值E(X，Y)= min(W(X，Y)，W(Y，X))用以表示用户的互动亲密度。

1.3 相似亲密度

在SNS网络中，有些没有直接连接的节点也许会在现实中具有一定的亲密度，比如校友、同行、老乡等。这种亲密度就是相似亲密度，我们将其定义为S(F，N)。在彩印SNS中，影响S的属性有年龄、所属地、行业。本文视这3种属性同等重要，所以S(F，N)=Sa（A，N）+Sl（L，N）+Sp（P，N）。

2 亲密度计算

2.1 基本亲密度设定

根据SNS中用户现实关系，将用户基本亲密度分类为以下5种： Bfamily（X，Y）、Bfriend（X，Y）、Bschoolmate（X，Y）、Bcolleague（X，Y）、Bbusiness（X，Y）。分别取值为B（family）=1， B（friend）=0.8，B（schoolmate）=0.6，B（colleague）=0.4，B（business）=0.2。用户间基本亲密度B（X，Y）=k1×Bfamily（X，Y）+k2×Bfriend（X，Y）+k3×Bschoolmate（X，Y）+k4×Bcolleague（X，Y）+k5×Bbusiness（X，Y）），其中ki(i=1，2，3，4，5)取值为{当X与Y具有对应关系i时取1，否则取0}。

2.2 互动亲密度设定

用一张有向带权图图1表示SNS网络中用户交流行为，权重表示互动交流量，方向指向表示交流行为的接受方。

图1 SNS用户交流行为统计图

然后取两个节点间最小的权重作为新权重构成新的无向带权图，如图2所示，用以表示SNS网络中用户间的交流量。

图2 SNS用户间最小交流量统计图

则两用户间的互动亲密度结果为：C（X，Y）=E（X，Y）/10（参数10的确定取决于彩印SNS网络用户的平均互动交流量）。其中，E(X，Y)= min(W(X，Y)，W(Y，X))。

2.3 相似亲密度设定

相似亲密度取决于用户3个属性：年龄、所属地、行业，S（X，Y）=Sa（X，Y）+Sl（X，Y）+Sp（X，Y）。

Sa（X，Y）取决于用户的年龄差，Sa（X，Y）的取值为

Sl（X，Y）取决于用户所属地的共性大小，在彩印SNS中具体分为省份、城市、区县镇、小区/学校，取值为：

当X和Y处于同一小区/学校时，Sl（X，Y）=0.8；

当X和Y只同处于一个区县镇时，Sl（X，Y）=0.4；

当X和Y只同处于一个城市时，Sl（X，Y）=0.2；

当X和Y只同属于一个省份时，Sl（X，Y）=0.1；

否则Sl（X，Y）=0。

Sp（X，Y）取决于用户的行业/专业共性，取值为：

当X和Y属于同一行业/专业时，Sp（X，Y）=1；

否则，Sp（X，Y）=0。

2.4 综合亲密度计算

下面根据上述3种亲密度计算两个相连接节点用户X和用户Y的综合亲密度F（X，Y）=a1B（X，Y）+a2C（X，Y）+（1-a1-a2）S（X，Y）。其中，a1＞0，a2＞0，a1+a2≤1。a1和a2的确定为SNS网络中用户行为和基本属性真实性及重要性所决定，在彩印SNS中，取a1为0.3，a2为0.5。

定义用户间的距离L为亲密度的倒数1/F，则网络中任何两个用户间的距离都可以计算。算法如下：

For网络中所有节点，计算其与相邻节点的亲密度，并计算其倒数作为距离的初始值，不相邻的用户间初始亲密度为0，距离为无穷大；

End for

For网络中节点A

For剩下的节点B

若A与B不直接连接，则通过Dijkstra算法计算A通过可能的路径到达B的最短距离L(A，B)；则F（A，B）=1/L(A，B)；

End。

3 可行性和有效性分析

通过研究当今主流社交网站的用户关系模型，确立用户基本信息内容和活动内容，并针对调查各社交网站的用户特性与服务类型，获取用户行为的规律。通过对数据挖掘中相关技术的研究，包括关联规则和分类技术，建立合理科学的亲密度模型和关联算法。常见的关联规则挖掘算法基于数据集中每个属性都有相同的重要性，但在实际的应用情况中，往往是某些属性的重要度比普通属性大、而有些属性的重要性比普通属性小，这就需要针对应用讨论各属性权值的合理确立。通过对彩印业务的用户活动内容的统计数据进行分析和预测，可以总结出彩印用户的特性，基于特性可以把握用户行为的规律。这样可以为关联规则中的属性权值的确立提供合理的依据。

4 结论

本文提出了一种彩印SNS中用户间关系亲密度的量化模型和计算方法，算法基于带权图中用户最短距离的Dijkstra算法。在计算用户间最短距离之前，通过用户间的初始亲密度初始化用户间的距离，然后进行遍历计算。

算法中各权重参数的取值通过对彩印业务现网用户的统计数据进行分析确定，能有效展现用户间真实的关系。

Algorithm of users’ friendliness in Caiyin SNS

ZHAO Tian-chen1,2, ZHU Xiao-min1,2, WANG Chun1,2
(1 State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China; 2 EBUPT Information Technology Co., Ltd., Beijing 100191, China)

The calculation of users’ friendliness in Caiyin social networking services is the key for the user friendliness model. SNS counts for revelation of persons’ relation in real life.However, the revelation between people in SNS may always be out of focus. This paper will introduce the model for SNS users’relation based on the users character in caiyin SNS, and will tell how to calculate the distance bewteen users in caiyin SNS based on the six degrees of separation,which will improve the value of the service.

six degrees of separation; the service of Caiyin; user friendliness

TN929.5

A

1008-5599（2012）10-0078-04

2012-09-16

国家自然科学基金（No. 61072057，61101119，61121001，60902051）；长江学者和创新团队发展计划资助（No. IRT1049）；国家科技重大专项（No. 2011ZX03002-001-01，移动互联网总体架构研究）。