首页> 中国专利> 一种社交网络中的基于朋友关系传播的朋友推荐方法

一种社交网络中的基于朋友关系传播的朋友推荐方法

页面导航

摘要
著录项
法律信息
说明书
相似文献

摘要

本发明涉及一种社交网络中的基于朋友关系传播的朋友推荐方法，属于计算机数据挖掘技术领域。为每个自我节点创建潜在朋友关系传播网络。在每个时间段，建立兴趣感知的社交行为概率生成模型，迭代更新候选中介人和候选兴趣领域，根据迭代结果设定潜在朋友关系传播网络中的边及边的权重。对于每个自我节点，在其潜在朋友关系传播网络的局部层上进行随机游走计算选择每个朋友作为中介人的概率，在其潜在朋友关系传播网络的全局层上进行随机游走计算选择每个节点作为新朋友的概率，然后将概率最高的新朋友作为推荐的朋友列表。本发明方法通过构造潜在朋友关系传播网络，从用户行为的角度深入分析社交网络的成因与结构，进而提供准确的朋友推荐服务。

著录项

公开/公告号CN103345513A

专利类型发明专利
公开/公告日2013-10-09

原文格式PDF
申请/专利权人清华大学;
展开▼

申请/专利号CN201310287059.9
发明设计人王建民;王朝坤;张君;
展开▼

申请日2013-07-09
分类号G06F17/30(20060101);
代理机构北京清亦华知识产权代理事务所(普通合伙);
代理人罗文群
地址 100084 北京市海淀区清华园1号
入库时间 2024-02-19 20:03:36

法律信息

法律状态公告日

法律状态信息

法律状态
2017-07-18

授权

授权
2013-11-06

实质审查的生效 IPC(主分类):G06F17/30 申请日:20130709

实质审查的生效
2013-10-09

公开

公开

说明书

技术领域

本发明涉及一种社交网络中的基于朋友关系传播的朋友推荐方法，属于计算机数据挖掘技术领域。

背景技术

社交网络在近些年得到了飞速的发展，也受到了许多研究人员的重视。朋友推荐是交友网站中的一项重要的功能，许多交友网站依靠为用户推荐好友来吸引用户、增强用户对交友网站的依赖性。

目前研究者已经提出了许多算法来解决好友推荐的问题，其中最普遍的朋友推荐方法是基于网络拓扑结构的相似度度量，包括局部结构相似度度量和全局相似度度量。学者 Liben-Nowell和Kleinberg归纳了流行的局部结构相似度度量方法，包括公共朋友数、 Jaccard系数、Adamic/Adar度量等等。全局相似度度量方法则再整个网络上度量两个用户的相似度，流行的方法包括Katz相似度度量、SimRank算法、随机游走算法等。也有研究者提出随机游走算法的改进算法，包括随机化最短路径(RSP)相异度、最大熵随机游走算法等，通过调整随机游走的迁移概率来改善算法性能。然而这些算法都把社交网络当作一个图来处理，并没有考虑到用户的动机和行为在朋友推荐中的重要作用，无法对用户的交友行为进行合理建模，也就不能为用户提供精准的朋友推荐服务。

本申请人于2013年1月17日提出了专利申请号为201310026965.3、发明名称为“一种社交网络中朋友关系传递树的建立方法”，该方法通过对用户的行为进行建模，基于朋友关系的传递性来推测和表达社交网络的形成和演化过程，但是没有考虑用户兴趣的影响，也没有考虑用户的朋友圈对于用户交友行为的协同影响，也没有提供用于社交网络中朋友推荐的具体方法。

发明内容

本发明的目的是提出一种社交网络中的基于朋友关系传播的朋友推荐方法，对已有的社交网络中朋友关系传递树的建立方法进行改进，通过建立兴趣感知的潜在朋友关系传播网络，推测和表达社交网络的形成和演化过程，为用户提供精准的朋友推荐。

本发明提出的社交网络中的基于朋友关系传播的朋友推荐方法，包括以下步骤：

(1)设社交网络中有多个用户，每个用户有多个朋友，将用户记为自我节点u_i，将该用户的朋友记为朋友节点v_i；为社交网络中的自我节点u_i，创建一个属于自我节点u_i的潜在朋友关系传播网络，该网络包括三层：自我层E(u_i)、局部层L(u_i)和全局层G(u_i)，在自我层E(u_i)中添加自我节点u_i，在局部层L(u_i)中添加自我节点u_i的所有朋友节点，在全局层 G(u_i)中添加社交网络中的所有节点；每个用户建立一个兴趣领域集合K；

(2)按照时间，将自我节点与朋友节点之间的交互数据按交互的时间划分为N段，对于与第t段交互相对应的时间段T_t，执行步骤(3)-(10)，t＝1，2，……，N；

(3)建立如下兴趣感知的社交行为概率生成模型：

(3-1)设社交网络中每个自我节点u_i的交互行为数为社交网络中每个自我节点u_i的新交朋友数为

(3-2)分别用先验参数为的狄利克雷分布表示社交网络中每个自我节点u_i的朋友关系强度分布的先验分布，从该狄利克雷分布中采样得到社交网络中自我节点u_i在时间段 T_t的朋友关系强度分布

(3-3)从上述朋友关系强度分布中，采样得到社交网络中每个自我节点u_i的每次交互对象x；

(3-4)分别用先验参数为的狄利克雷分布表示社交网络中每个自我节点u_i的中介偏好概率分布的先验分布，从该狄利克雷分布中采样得到社交网络中自我节点u_i在时间段 T_t的中介偏好概率分布

(3-5)分别用先验参数为的狄利克雷分布表示社交网络中每个自我节点u_i的兴趣偏好概率分布的先验分布，从该狄利克雷分布中采样得到社交网络中自我节点u_i在时间段 T_t的兴趣偏好概率分布

(3-6)分别用先验参数为的狄利克雷分布表示社交网络中兴趣领域的用户声望概率分布的先验分布，从该狄利克雷分布中采样得到社交网络中每个兴趣领域c_i在时间段T_t的用户声望概率分布

(3-7)从上述用户兴趣概率分布中采样得到社交网络中每个自我节点u_i的兴趣领域c_i，分别从上述中介偏好概率分布和用户声望概率分布的联合分布中采样得到社交网络中每个自我节点u_i的中介人z_i，从与中介人z_i对应的朋友关系强度分布和用户声望概率分布的联合分布中采样得到社交网络中自我节点u_i的新朋友节点y_i；

(3-8)用U表示社交网络中用户的集合，用K表示社交网络中用户兴趣领域的集合，用表示社交网络中自我节点u_i在时间段T_t的朋友节点集合，用表示社交网络中自我节点u_i在时间段T_t的新朋友节点集合，用表示社交网络中自我节点u_i在时间段T_t的交互节点集合，用表示在时间段T_t社交网络中自我节点u_i选择z_i作为中介人的次数，用表示在时间段T_t社交网络中中介人z_i将朋友y_i推荐给别人的次数，用表示在时间段T_t社交网络中自我节点u_i和朋友y_i交互的次数，用表示在时间段T_t社交网络中z_i在兴趣领域c_i中被选为中介人的次数，用表示在时间段T_t社交网络中y_i在兴趣领域c_i中被推荐给别人的次数，用表示在时间段T_t社交网络中自我节点u_i在兴趣领域c_i中选择新朋友的次数；

(4)对时间段T_t的时间序号t进行判断：

若t≥1，则先验参数分别为：

$α_{u_{i}, z_{i}}^{(T_{t})} = λ \cdot α_{u_{i}, z_{i}}^{(T_{t - 1})} + Ω_{u_{i}, z_{i}}^{(uz) (T_{t - 1})}$

$β_{z_{i}, y_{i}}^{(T_{t})} = λ \cdot β_{z_{i}, y_{i}}^{(T_{t - 1})} + Ω_{z_{i}, y_{i}}^{(uv) (T_{t - 1})} + Ω_{z_{i}, y_{i}}^{(zy) (T_{t - 1})}$

$δ_{u_{i}, c_{i}}^{(T_{t})} = λ \cdot δ_{u_{i}, c_{i}}^{(T_{t - 1})} + Ω_{u_{i}, c_{i}}^{(uc) (T_{t - 1})}$

$γ_{c_{i}, u_{i}}^{(T_{t})} = λ \cdot γ_{c_{i}, u_{i}}^{(T_{t - 1})} + Ω_{c_{i}, u_{i}}^{(cy) (T_{t - 1})}$

其中，表示在时间段T_t-1社交网络中自我节点u_i选择z_i作为中介人的次数，表示在时间段T_t-1社交网络中中介人z_i将朋友y_i推荐给别人的次数，表示在时间段T_t-1社交网络中中介人z_i和朋友y_i交互的次数，表示在时间段T_t-1社交网络中u_i在兴趣领域c_i中被推荐给别人的次数，用表示在时间段T_t-1社交网络中自我节点u_i在兴趣领域c_i中选择新朋友的次数；

若t＝0，则先验参数分别为：

$α_{u_{i}, z_{i}}^{(T_{t})} = α_{0}$

$β_{z_{i}, y_{i}}^{(T_{t})} = β_{0}$

$δ_{u_{i}, c_{i}}^{(T_{t})} = δ_{0}$

$γ_{c_{i}, u_{i}}^{(T_{t})} = γ_{0}$

其中α₀，β₀，δ₀，γ₀分别为先验参数的预设值，α₀，β₀，δ₀，γ₀分别为正数；

(5)当自我节点u_i和自我节点u_i的新朋友节点y_i有共同朋友时，则从共同朋友中随机选择共同朋友z_i作为自我节点u_i与新朋友节点y_i之间的候选中介人，记录共同朋友z_i被选为自我节点u_i与新朋友节点y_i之间的候选中介人的次数为1，当自我节点u_i和自我节点u_i的新朋友节点y_i没有共同朋友时，则选择自我节点u_i作为自我节点u_i与新朋友节点y_i之间的候选中介人；

(6)从用户建立的兴趣领域集合K中随机选择一个兴趣领域c_i作为自我节点u_i与新朋友节点y_i之间的候选兴趣领域，记录兴趣领域c_i被选为自我节点u_i与新朋友节点y_i之间的候选兴趣领域的次数为1；

(7)当自我节点u_i和自我节点u_i的新朋友节点y_i有共同朋友时，则按照下式计算兴趣领域为c_i的共同朋友z′，作为自我节点u_i与新朋友节点y_i之间的中介人z_i的概率 $p^{(T_{i})} (z_{i} =$ $z^{'} | u_{i}, y_{i}, c_{i}) :$

$p^{(T_{i})} (z_{i} = z^{'} | u_{i}, y_{i}, c_{i})$

$= \frac{α_{u_{i}, z^{'}}^{(T_{t})} + Ω_{u_{i}, z^{'}}^{(uz) (T_{t})} - 1}{Σ_{v_{i} \in F^{(T_{i})} (u)} (α_{u_{i}, v_{i}}^{(T_{t})} + Ω_{u_{i}, v_{i}}^{(uz) (T_{t})}) - 1}$

$\cdot \frac{β_{z^{'}, y_{i}}^{(T_{t})} + Ω_{z^{'}, y_{i}}^{(uv) (T_{t})} + Ω_{z^{'}, y_{i}}^{(zy) (T_{t})} - 1}{Σ_{v_{i} \in F^{(T_{i})} (y_{i})} (β_{v_{i}, y_{i}}^{(T_{t})} + Ω_{v_{i}, y_{i}}^{(uv) (T_{t})} + Ω_{v_{i}, y_{i}}^{(zy) (T_{t})}) - 1}$

$\cdot \frac{γ_{c_{i}, z^{'}}^{(T_{t})} + Ω_{c_{i}, z^{'}}^{(cy) (T_{t})} + Ω_{c_{i}, z^{'}}^{(cz) (T_{t})} - 1}{Σ_{v_{i} \in F^{(T_{i})} (u)} (γ_{c_{i}, v_{i}}^{(T_{t})} + Ω_{c_{i}, v_{i}}^{(cy) (T_{t})} + Ω_{c_{i}, v_{i}}^{(cz) (T_{t})}) - 1}$

其中，表示在时间段T_t社交网络中自我节点u_i选择z′作为中介人的次数，表示在时间段T_t社交网络中中介人z′将朋友y_i推荐给别人的次数，表示在时间段T_t社交网络中中介人z′和朋友y_i交互的次数，表示在时间段T_t社交网络中z′在兴趣领域c_i中被选为中介人的次数，表示在时间段T_t社交网络中z′在兴趣领域c_i中被推荐给别人的次数，表示在时间段T_t社交网络中自我节点u_i选择v_i作为中介人的次数，表示在时间段T_t社交网络中中介人v_i将朋友y_i推荐给别人的次数，表示在时间段T_t社交网络中中介人v_i和朋友y_i交互的次数，表示在时间段T_t社交网络中v_i在兴趣领域c_i中被选为中介人的次数，表示在时间段T_t社交网络中v_i在兴趣领域c_i中被推荐给别人的次数，为在T_t时间段自我节点u_i偏好概率分布的先验参数中与共同朋友z′相应的先验值，为在T_t时间段z′的朋友关系强度分布先验参数中与朋友节点y_i相应的先验值，为在T_t时间段兴趣领域c_i的用户声望概率分布的先验参数中与z′相应的先验值，为在T_t时间段自我节点u_i偏好概率分布的先验参数中与共同朋友v_i相应的先验值，为在T_t时间段v_i的朋友关系强度分布先验参数中与朋友节点y_i相应的先验值，为在T_t时间段兴趣领域c_i的用户声望概率分布的先验参数中与v_i相应的先验值；

根据得到的概率，采样确定自我节点u_i与新朋友节点y_i之间的新候选中介人z_i，并在记录中介人z_i被选为自我节点u_i与新朋友节点y_i之间的候选中介人的次数上增加1，进行步骤(8)；

当自我节点u_i和自我节点u_i的新朋友节点y_i没有共同朋友时，则保持步骤(5)的候选中介人不变，进行步骤(8)；

(8)按照下式计算中介人为z_i时，自我节点u_i与新朋友节点y_i的共同兴趣领域c_i为c′的概率 $p^{(T_{i})} (c_{i} = c^{'} | u_{i}, y_{i}, z_{i}) :$

$p^{(T_{i})} (c_{i} = c^{'} | u_{i}, y_{i}, z_{i}) = \frac{γ_{c^{'}, z_{i}}^{(T_{t})} + Ω_{c^{'}, y_{i}}^{(cy) (T_{t})} + Ω_{c^{'}, z_{i}}^{(cz) (T_{t})} - 1}{Σ_{c_{i} \in K} (γ_{c_{i}, y_{i}}^{(T_{t})} + Ω_{c_{i}, y_{i}}^{(cy) (T_{t})} + Ω_{c_{i}, z_{i}}^{(cz) (T_{t})}) - 1} \cdot \frac{δ_{u_{i}, c^{'}}^{(T_{t})} + Ω_{u_{i}, c^{'}}^{(uc) (T_{t})} - 1}{Σ_{c_{i} \in K} (δ_{u_{i}, c_{i}}^{(T_{t})} + Ω_{u_{i}, c_{i}}^{(uc) (T_{t})}) - 1} \cdot$

其中，表示在时间段T_t社交网络中z_i在兴趣领域c′中被选为中介人的次数，用表示在时间段T_t社交网络中y_i在兴趣领域c′中被推荐给别人的次数，表示在时间段T_t社交网络中自我节点u_i在兴趣领域c′中选择新朋友的次数，表示在时间段 T_t社交网络中z_i在兴趣领域c_i中被选为中介人的次数，用表示在时间段T_t社交网络中z_i在兴趣领域c_i中被推荐给别人的次数，表示在时间段T_t社交网络中自我节点u_i在兴趣领域c_i中选择新朋友的次数，为在T_t时间段自我节点u_i的用户兴趣概率分布的先验参数中与c′相应的先验值，为在T_t时间段兴趣领域c′的用户声望概率分布的先验参数中与z_i相应的先验值，为在T_t时间段自我节点u_i的用户兴趣概率分布的先验参数中与c_i相应的先验值，为在T_t时间段兴趣领域c_i的用户声望概率分布的先验参数中与z_i相应的先验值；

根据得到的概率，采样确定自我节点u_i与新朋友节点y_i之间的新候选兴趣领域c_i，并在记录兴趣领域c_i被选为自我节点u_i与新朋友节点y_i之间的候选兴趣领域的次数上增加1； (9)按照下式，分别计算自我节点u_i的中介偏好概率分布朋友关系强度分布和兴趣偏好概率分布以及兴趣领域c_i的用户声望概率分布

$θ_{u_{i}, z_{i}}^{(T_{t})} = \frac{α_{u_{i}, z_{i}}^{(T_{t})} + Ω_{u_{i}, z_{i}}^{(uz) (T_{t})}}{Σ_{v \in F^{(T_{t})} (u_{i})} (α_{u_{i}, v}^{(T_{t})} + Ω_{u_{i}, v}^{(uz) (T_{t})})}$

$φ_{z_{i}, y_{i}}^{(T_{t})} = \frac{β_{z_{i}, y_{i}}^{(T_{t})} + Ω_{z_{i}, y_{i}}^{(uv) (T_{t})} + Ω_{z_{i}, y_{i}}^{(zy) (T_{t})}}{Σ_{v \in F^{(T_{t})} (z_{i})} (β_{z_{i}, v}^{(T_{t - 1})} + Ω_{z_{i}, v}^{(uv) (T_{t})} + Ω_{z_{i}, v}^{(zy) (T_{t})})}$

$χ_{u_{i}, c_{i}}^{(T_{t})} = \frac{δ_{u_{i}, c_{i}}^{(T_{t})} + Ω_{u_{i}, c_{i}}^{(uc) (T_{t})}}{Σ_{c \in K} (δ_{u_{i}, c}^{(T_{t})} + Ω_{u_{i}, c}^{(uc) (T_{t})})}$

$ψ_{c_{i}, u_{i}}^{(T_{t})} = \frac{γ_{c_{i}, u_{i}}^{(T_{t})} + Ω_{c_{i}, u_{i}}^{(cy) (T_{t})} + Ω_{c_{i}, u_{i}}^{(cz) (T_{t})}}{Σ_{u \in U} (γ_{c_{i}, u}^{(T_{t})} + Ω_{c_{i}, u}^{(cy) (T_{t})} + Ω_{c_{i}, u}^{(cz) (T_{t})})}$

其中，表示在时间段T_t社交网络中自我节点u_i选择z_i作为中介人的次数，表示在时间段T_t社交网络中中介人z_i将朋友y_i推荐给别人的次数，表示在时间段T_t社交网络中自我节点u_i和朋友y_i交互的次数，表示在时间段T_t社交网络中u_i在兴趣领域c_i中被选为中介人的次数，用表示在时间段T_t社交网络中u_i在兴趣领域 c_i中被推荐给别人的次数，用表示在时间段T_t社交网络中自我节点u_i在兴趣领域c_i中选择新朋友的次数，表示在时间段T_t社交网络中自我节点u_i选择v作为中介人的次数，表示在时间段T_t社交网络中中介人z_i将朋友v推荐给别人的次数，表示在时间段T_t社交网络中自我节点u_i和朋友v交互的次数，表示在时间段T_t社交网络中u在兴趣领域c_i中被选为中介人的次数，用表示在时间段T_t社交网络中u在兴趣领域c_i中被推荐给别人的次数，用表示在时间段T_t社交网络中自我节点u_i在兴趣领域c 中选择新朋友的次数，为在T_t时间段自我节点u_i偏好概率分布的先验参数中与共同朋友z_i相应的先验值，为在T_t时间段z_i的朋友关系强度分布的先验参数中与朋友节点y_i相应的先验值，为在T_t时间段自我节点u_i偏好概率分布的先验参数中与共同朋友v相应的先验值，为在T_t时间段z_i的朋友关系强度分布的先验参数中与朋友节点v相应的先验值，为在T_t时间段自我节点u_i的用户兴趣概率分布的先验参数中与c_i相应的先验值，为在T_t时间段兴趣领域c_i的用户声望概率分布的先验参数中与 u_i相应的先验值，为在T_t时间段自我节点u_i的用户兴趣概率分布的先验参数中与c 相应的先验值，为在T_t时间段兴趣领域c_i的用户声望概率分布的先验参数中与u相应的先验值；

根据以上得到的自我节点u_i的中介偏好概率分布朋友关系强度分布和兴趣偏好概率分布以及兴趣领域c_i的用户声望概率分布和上一轮迭代后计算所得到的中介偏好概率分布朋友关系强度分布兴趣偏好概率分布和用户声望概率分布分别计算中介偏好概率分布变化量Δ_θ，朋友关系强度分布变化量Δ_φ，兴趣偏好概率分布变化量Δ_χ和用户声望概率分布变化量Δ_ψ：

$Δ_{θ} = \underset{u}{Σ} \underset{v \in F^{(T_{i})} (u)}{Σ} {(θ_{u, v}^{(T_{i})} - {θ^{'}}_{u, v}^{(T_{i})})}^{2}$

$Δ_{φ} = \underset{u}{Σ} \underset{v \in F^{(T_{i})} (u)}{Σ} {(φ_{u, v}^{(T_{i})} - {φ^{'}}_{u, v}^{(T_{i})})}^{2}$

$Δ_{χ} = \underset{u}{Σ} \underset{c}{Σ} {(χ_{u, c}^{(T_{i})} - {χ^{'}}_{u, c}^{(T_{i})})}^{2}$

$Δ_{ψ} = \underset{c}{Σ} \underset{u}{Σ} {(ψ_{c, u}^{(T_{i})} - {ψ^{'}}_{c, u}^{(T_{i})})}^{2}$

设定一个变化量阈值，该变化量阈值的取值范围为0-0.1，若Δ_θ，Δ_φ，Δ_χ和Δ_ψ同时小于该阈值，则进行步骤(10)；若Δ_θ，Δ_φ，Δ_χ和Δ_ψ中的任何一个大于或等于该阈值，则设 ${θ^{'}}_{u, v}^{(T_{i})} = θ_{u, v}^{(T_{i})},$ ${φ^{'}}_{u, v}^{(T_{i})} = φ_{u, v}^{(T_{i})},$ ${χ^{'}}_{u, c}^{(T_{i})} = χ_{u, c}^{(T_{i})},$ ${ψ^{'}}_{c, u}^{(T_{i})} = ψ_{c, u}^{(T_{i})},$ 并返回步骤(7)；

(10)对于自我节点u_i与自我节点u_i的新朋友节点y_i，以及步骤(7)迭代过程中被采样到的候选中介人z_i，在自我节点u_i的朋友关系传播网络的局部层L(u_i)中添加一条边 z_i→y_i，一条边z_i→y_i的权重等于z_i被采样作为自我节点u_i与自我节点u_i的新朋友节点y_i的候选中介人的概率，即：

$w_{z_{i}, y_{i}}^{L (u_{i})} = p (z_{i} | u_{i}, y_{i})$

在自我节点u_i的朋友关系传播网络的全局层G(u_i)中添加一条边z_i→y_i，一条边 z_i→y_i的权重为：

$w_{z_{i}, y_{i}}^{G (u_{i})} = φ_{z_{i}, y_{i}} \cdot \underset{c \in K}{Σ} (χ_{u_{i}, c} \cdot ψ_{c, u_{i}})$

对于自我节点u_i的朋友关系传播网络的局部层L(u_i)中的每个节点z_i，添加从自我节点 u_i到z_i的一条边u_i→z_i，一条边u_i→z_i的权重为：

$w_{u_{i}, z_{i}}^{E (u_{i})} = θ_{u_{i}, z_{i}}$

(11)遍历自我节点与朋友节点之间交互数据的所有时间段，得到社交网络中每个自我节点u_i的朋友关系传播网络；

(12)对于社交网络中自我节点u_i和自我节点u_i的朋友关系传播网络的局部层L(u_i)上的任意节点z_i，用表示u_i在交朋友过程中选择z_i作为其中介人的概率，初始化为0，对于社交网络中自我节点u_i和自我节点u_i的朋友关系传播网络的全局层G(u_i)上的任意节点 v_i，用表示u_i在交朋友过程中选择v_i作为其新朋友的概率，初始化为0；

(13)对于社交网络中自我节点u_i和自我节点u_i的朋友关系传播网络的局部层L(u_i)上的任意节点z_i，按照如下公式更新u_i在交朋友过程中选择z_i作为其中介人的概率

$r_{z_{i}}^{L (u_{i})} = (1 - μ) \cdot \underset{z \in F (u_{i}, z_{i})}{Σ} w_{z, z_{i}}^{L (u_{i})} \cdot {r^{'}}_{z}^{L (u_{i})} + μ \cdot w_{u_{i}, z_{i}}^{E (u_{i})}$

其中表示在本轮迭代开始前的值，是自我节点u_i的朋友关系传播网络的局部层L(u_i)中边z→z_i的权重，是自我节点u_i到自我节点u_i的朋友关系传播网络的局部层L(u_i)中的节点z_i的边u_i→z_i的权重，F(u_i，z_i)表示u_i和z_i的公共朋友集合，μ是取值为0-1的参数；

(14)对于社交网络中自我节点u_i，计算中介选择概率变化量

${Δr}^{L (u_{i})} = \underset{z_{i} \in L (u_{i})}{Σ} (r_{z_{i}}^{L (u_{i})} - {r^{'}}_{z_{i}}^{L (u_{i})})$

设定一个变化量阈值，该变化量阈值的取值范围为0-0.1，若小于设定阈值，则进行步骤(15)；若大于或等于设定阈值，则对于社交网络中自我节点u_i的朋友关系传播网络的局部层L(u_i)上的任意节点z_i，设并返回步骤(13)；

(15)对于社交网络中自我节点u_i和自我节点u_i的朋友关系传播网络的全局层G(u_i)上的任意节点v_i，按照如下公式更新u_i在交朋友过程中选择v_i作为其新朋友的概率

$r_{v_{i}}^{G (u_{i})} = (1 - μ) \cdot \underset{v \in F (v_{i})}{Σ} w_{v, v_{i}}^{G (u_{i})} \cdot {r^{'}}_{v}^{G (u_{i})} + μ \cdot r_{v_{i}}^{L (u_{i})}$

其中表示在本轮迭代开始前的值，是自我节点u_i的朋友关系传播网络的全局层G(u_i)中边v→v_i的权重，是自我节点u_i在交朋友过程中选择v_i作为其中介人的概率，F(v_i)表示v_i的朋友集合，μ是取值为0-1的参数；

(16)对于社交网络中自我节点u_i，计算朋友选择概率变化量

${Δr}^{G (u_{i})} = \underset{v_{i} \in G (u_{i})}{Σ} (r_{v_{i}}^{G (u_{i})} - {r^{'}}_{v_{i}}^{G (u_{i})})$

设定一个变化量阈值，该变化量阈值的取值范围为0-0.1，若小于指定阈值，则进行步骤(17)；若大于或等于指定阈值，则对于社交网络中自我节点u_i的朋友关系传播网络的全局层G(u_i)上的任意节点v_i，设并返回步骤(15)；

(16)对于社交网络中自我节点u_i，将自我节点u_i的朋友关系传播网络的全局层G(u_i)上的所有节点v_i，按照与节点相对应的值从大到小排序，作为向u_i推荐的朋友列表。

本发明提出的社交网络中的基于朋友关系传播的朋友推荐方法，其优点是：

1、本发明方法基于社会学中的传递性原理，对用户在社交网络中的社交行为进行合理建模，同时考虑用户对于朋友的偏好、对于中介人的偏好、兴趣领域的偏好以及朋友圈地相互影响作用，可以更准确地预测用户未来的交友行为，从而可以为交友网站提供更准确的好友推荐结果。

2、本发明方法构造的社交网络中的潜在朋友关系传播网络，从朋友关系传递性的角度出发，对社交网络的演化过程提供了层次化、因果式的可视化呈现与解释，便于深入分析社交网络的成因与内在结构，以及预测社交网络未来的发展与变化，从而为交友网站的设计与运营提供参考。

3、本发明方法不需要额外的训练数据，避免了训练数据中的不平衡问题，适用性强，便于应用。

附图说明

图1是本发明方法涉及的社交网络中潜在朋友关系传播网络的部分示意图。

图2是本发明方法涉及的社交网络中潜在朋友关系传播网络的整体示意图。

图3是本发明方法中建立的兴趣感知的社交行为概率生成模型示意图。

具体实施方式

本发明提出的社交网络中的基于朋友关系传播的朋友推荐方法，包括以下步骤：

(1)设社交网络中有多个用户，每个用户有多个朋友，将用户记为自我节点u_i，将该用户的朋友记为朋友节点v_i；为社交网络中的自我节点u_i，创建一个属于自我节点u_i的潜在朋友关系传播网络，创建的潜在朋友关系传播网络如图1所示，该网络包括三层：自我层E(u_i)、局部层L(u_i)和全局层G(u_i)，在自我层E(u_i)中添加自我节点u_i，在局部层L(u_i)中添加自我节点u_i的所有朋友节点，在全局层G(u_i)中添加社交网络中的所有节点；每个用户建立一个兴趣领域集合K；

(2)按照时间，将自我节点与朋友节点之间的交互数据按交互的时间划分为N段，对于与第t段交互相对应的时间段T_t，执行步骤(3)-(10)，t＝1，2，……，N；

(3)建立如下兴趣感知的社交行为概率生成模型，模型的图形化表示如图3所示：

(3-1)设社交网络中每个自我节点u_i的交互行为数为社交网络中每个自我节点u_i的新交朋友数为

(3-3)从上述朋友关系强度分布中，采样得到社交网络中每个自我节点u_i的每次交互对象x；

(4)对时间段T_t的时间序号t进行判断：

若t≥1，则先验参数分别为：

$α_{u_{i}, z_{i}}^{(T_{t})} = λ \cdot α_{u_{i}, z_{i}}^{(T_{t - 1})} + Ω_{u_{i}, z_{i}}^{(uz) (T_{t - 1})}$

$β_{z_{i}, y_{i}}^{(T_{t})} = λ \cdot β_{z_{i}, y_{i}}^{(T_{t - 1})} + Ω_{z_{i}, y_{i}}^{(uv) (T_{t - 1})} + Ω_{z_{i}, y_{i}}^{(zy) (T_{t - 1})}$

$δ_{u_{i}, c_{i}}^{(T_{t})} = λ \cdot δ_{u_{i}, c_{i}}^{(T_{t - 1})} + Ω_{u_{i}, c_{i}}^{(uc) (T_{t - 1})}$

$γ_{c_{i}, u_{i}}^{(T_{t})} = λ \cdot γ_{c_{i}, u_{i}}^{(T_{t - 1})} + Ω_{c_{i}, u_{i}}^{(cy) (T_{t - 1})}$

若t＝0，则先验参数分别为：

$α_{u_{i}, z_{i}}^{(T_{t})} = α_{0}$

$β_{z_{i}, y_{i}}^{(T_{t})} = β_{0}$

$δ_{u_{i}, c_{i}}^{(T_{t})} = δ_{0}$

$γ_{c_{i}, u_{i}}^{(T_{t})} = γ_{0}$

其中α₀，β₀，δ₀，γ₀分别为先验参数的预设值，α₀，β₀，δ₀，γ₀分别为正数；

(7)当自我节点u_i和自我节点u_i的新朋友节点y_i有共同朋友时，则按照下式计算兴趣领域为c_i的共同朋友z′，作为自我节点u_i与新朋友节点y_i之间的中介人z_i的概率 $p (T_{i}) (z_{i} =$ $z^{'} | u_{i}, y_{i}, c_{i}) :$

$p^{(T_{i})} (z_{i} = z^{'} | u_{i}, y_{i}, c_{i})$

$= \frac{α_{u_{i}, z^{'}}^{(T_{t})} + Ω_{u_{i}, z^{'}}^{(uz) (T_{t})} - 1}{Σ_{v_{i} \in F^{(T_{i})} (u)} (α_{u_{i}, v_{i}}^{(T_{t})} + Ω_{u_{i}, v_{i}}^{(uz) (T_{t})}) - 1}$

其中，表示在时间段T_t社交网络中自我节点u_i选择z′作为中介人的次数，表示在时间段T_t社交网络中中介人z′将朋友y_i推荐给别人的次数，表示在时间段T_t社交网络中中介人z′和朋友y_i交互的次数，表示在时间段T_t社交网络中z′在兴趣领域c_i中被选为中介人的次数，表示在时间段T_t社交网络中z′在兴趣领域c_i中被推荐给别人的次数，表示在时间段T_t社交网络中自我节点u_i选择v_i作为中介人的次数，表示在时间段T_t社交网络中中介人v_i将朋友y_i推荐给别人的次数，表示在时间段T_t社交网络中中介人v_i和朋友y_i交互的次数，表示在时间段T_t社交网络中v_i在兴趣领域c_i中被选为中介人的次数，表示在时间段T_t社交网络中v_i在兴趣领域c_i中被推荐给别人的次数，为在T_t时间段自我节点u_i偏好概率分布的先验参数中与共同朋友z′相应的先验值，为在T_t时间段z′的朋友关系强度分布光验参数中与朋友节点y_i相应的先验值，为在T_t时间段兴趣领域c_i的用户声望概率分布的先验参数中与z′相应的先验值，为在T_t时间段自我节点u_i偏好概率分布的先验参数中与共同朋友v_i相应的先验值，为在T_t时间段v_i的朋友关系强度分布先验参数中与朋友节点y_i相应的先验值，为在T_t时间段兴趣领域c_i的用户声望概率分布的先验参数中与v_i相应的先验值；

当自我节点u_i和自我节点u_i的新朋友节点y_i没有共同朋友时，则保持步骤(5)的候选中介人不变，进行步骤(8)；

(8)按照下式计算中介人为z_i时，自我节点u_i与新朋友节点y_i的共同兴趣领域c_i为c′的概率 $p^{(T_{i})} (c_{i} = c^{'} | u_{i}, y_{i}, z_{i}) :$

根据得到的概率，采样确定自我节点u_i与新朋友节点y_i之间的新候选兴趣领域c_i，并在记录兴趣领域c_i被选为自我节点u_i与新朋友节点y_i之间的候选兴趣领域的次数上增加1；

(9)按照下式，分别计算自我节点u_i的中介偏好概率分布朋友关系强度分布和兴趣偏好概率分布以及兴趣领域c_i的用户声望概率分布

$θ_{u_{i}, z_{i}}^{(T_{t})} = \frac{α_{u_{i}, z_{i}}^{(T_{t})} + Ω_{u_{i}, z_{i}}^{(uz) (T_{t})}}{Σ_{v \in F^{(T_{t})} (u_{i})} (α_{u_{i}, v}^{(T_{t})} + Ω_{u_{i}, v}^{(uz) (T_{t})})}$

$χ_{u_{i}, c_{i}}^{(T_{t})} = \frac{δ_{u_{i}, c_{i}}^{(T_{t})} + Ω_{u_{i}, c_{i}}^{(uc) (T_{t})}}{Σ_{c \in K} (δ_{u_{i}, c}^{(T_{t})} + Ω_{u_{i}, c}^{(uc) (T_{t})})}$

$Δ_{θ} = \underset{u}{Σ} \underset{v \in F^{(T_{i})} (u)}{Σ} {(θ_{u, v}^{(T_{i})} - {θ^{'}}_{u, v}^{(T_{i})})}^{2}$

$Δ_{φ} = \underset{u}{Σ} \underset{v \in F^{(T_{i})} (u)}{Σ} {(φ_{u, v}^{(T_{i})} - {φ^{'}}_{u, v}^{(T_{i})})}^{2}$

$Δ_{χ} = \underset{u}{Σ} \underset{c}{Σ} {(χ_{u, c}^{(T_{i})} - {χ^{'}}_{u, c}^{(T_{i})})}^{2}$

$Δ_{ψ} = \underset{c}{Σ} \underset{u}{Σ} {(ψ_{c, u}^{(T_{i})} - {ψ^{'}}_{c, u}^{(T_{i})})}^{2}$

$w_{z_{i}, y_{i}}^{L (u_{i})} = p (z_{i} | u_{i}, y_{i})$

在自我节点u_i的朋友关系传播网络的全局层G(u_i)中添加一条边z_i→y_i，一条边 z_i→y_i的权重为：

$w_{z_{i}, y_{i}}^{G (u_{i})} = φ_{z_{i}, y_{i}} \cdot \underset{c \in K}{Σ} (χ_{u_{i}, c} \cdot ψ_{c, u_{i}})$

对于自我节点u_i的朋友关系传播网络的局部层L(u_i)中的每个节点z_i，添加从自我节点 u_i到z_i的一条边u_i→z_i，一条边u_i→z_i的权重为：

$w_{u_{i}, z_{i}}^{E (u_{i})} = θ_{u_{i}, z_{i}}$

(11)遍历自我节点与朋友节点之间交互数据的所有时间段，得到社交网络中每个自我节点u_i的朋友关系传播网络，得到的整体潜在朋友关系传播网络如图2所示；

$r_{z_{i}}^{L (u_{i})} = (1 - μ) \cdot \underset{z \in F (u_{i}, z_{i})}{Σ} w_{z, z_{i}}^{L (u_{i})} \cdot {r^{'}}_{z}^{L (u_{i})} + μ \cdot w_{u_{i}, z_{i}}^{E (u_{i})}$

(14)对于社交网络中自我节点u_i，计算中介选择概率变化量

${Δr}^{L (u_{i})} = \underset{z_{i} \in L (u_{i})}{Σ} (r_{z_{i}}^{L (u_{i})} - {r^{'}}_{z_{i}}^{L (u_{i})})$

$r_{v_{i}}^{G (u_{i})} = (1 - μ) \cdot \underset{v \in F (v_{i})}{Σ} w_{v, v_{i}}^{G (u_{i})} \cdot {r^{'}}_{v}^{G (u_{i})} + μ \cdot r_{v_{i}}^{L (u_{i})}$

(16)对于社交网络中自我节点u_i，计算朋友选择概率变化量

${Δr}^{G (u_{i})} = \underset{v_{i} \in G (u_{i})}{Σ} (r_{v_{i}}^{G (u_{i})} - {r^{'}}_{v_{i}}^{G (u_{i})})$

去获取专利，查看全文>

相似文献

专利
中文文献
外文文献

1. 一种社交网络中的基于朋友关系传播的朋友推荐方法 [P] . 中国专利： CN103345513B . 2017.07.18
2. 一种基于社会关系主题模型的社交网络朋友推荐方法 [P] . 中国专利： CN105740342A . 2016-07-06
3. Social network service system and method for recommending friend of friend based on intimacy between users [P] . 美国专利： US9104681B2 . 2015-08-11

机译：基于用户之间的亲密关系推荐朋友的朋友的社交网络服务系统和方法
4. SOCIAL NETWORK CAPABLE OF RECOMMENDING FRIENDS AND FRIEND RECOMMENDATION METHOD [P] . 美国专利： US2015095803A1 . 2015-04-02

机译：推荐朋友的社交网络和朋友推荐方法
5. ONLINE SOCIAL NETWORK SERVICE PROVIDING DEVICE FOR PROVIDING FRIENDS RECOMMENDATION SERVICE THROUGH VARIOUS RELATIONSHIPS WITH AN ADDRESS BOOK AND A COMMUNICATION HISTORY AND A METHOD THEREOF [P] . 韩国专利： KR20100130003A . 2010-12-10

机译：通过与地址簿和通信历史的各种关系来提供朋友推荐服务的在线社交网络服务提供设备及其方法