法律状态公告日
法律状态信息
法律状态
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)设社交网络中有多个用户,每个用户有多个朋友,将用户记为自我节点ui,将该 用户的朋友记为朋友节点vi;为社交网络中的自我节点ui,创建一个属于自我节点ui的潜 在朋友关系传播网络,该网络包括三层:自我层E(ui)、局部层L(ui)和全局层G(ui),在自 我层E(ui)中添加自我节点ui,在局部层L(ui)中添加自我节点ui的所有朋友节点,在全局层 G(ui)中添加社交网络中的所有节点;每个用户建立一个兴趣领域集合K;
(2)按照时间,将自我节点与朋友节点之间的交互数据按交互的时间划分为N段, 对于与第t段交互相对应的时间段Tt,执行步骤(3)-(10),t=1,2,……,N;
(3)建立如下兴趣感知的社交行为概率生成模型:
(3-1)设社交网络中每个自我节点ui的交互行为数为社交网络中每个自我节点ui的新交朋友数为
(3-2)分别用先验参数为的狄利克雷分布表示社交网络中每个自我节点ui的朋友 关系强度分布的先验分布,从该狄利克雷分布中采样得到社交网络中自我节点ui在时间段 Tt的朋友关系强度分布
(3-3)从上述朋友关系强度分布中,采样得到社交网络中每个自我节点ui的每次 交互对象x;
(3-4)分别用先验参数为的狄利克雷分布表示社交网络中每个自我节点ui的中介 偏好概率分布的先验分布,从该狄利克雷分布中采样得到社交网络中自我节点ui在时间段 Tt的中介偏好概率分布
(3-5)分别用先验参数为的狄利克雷分布表示社交网络中每个自我节点ui的兴趣 偏好概率分布的先验分布,从该狄利克雷分布中采样得到社交网络中自我节点ui在时间段 Tt的兴趣偏好概率分布
(3-6)分别用先验参数为的狄利克雷分布表示社交网络中兴趣领域的用户声望概 率分布的先验分布,从该狄利克雷分布中采样得到社交网络中每个兴趣领域ci在时间段Tt的用户声望概率分布
(3-7)从上述用户兴趣概率分布中采样得到社交网络中每个自我节点ui的兴趣领 域ci,分别从上述中介偏好概率分布和用户声望概率分布的联合分布中采样得到 社交网络中每个自我节点ui的中介人zi,从与中介人zi对应的朋友关系强度分布和用户 声望概率分布的联合分布中采样得到社交网络中自我节点ui的新朋友节点yi;
(3-8)用U表示社交网络中用户的集合,用K表示社交网络中用户兴趣领域的集合, 用表示社交网络中自我节点ui在时间段Tt的朋友节点集合,用表示社交网 络中自我节点ui在时间段Tt的新朋友节点集合,用表示社交网络中自我节点ui在时 间段Tt的交互节点集合,用表示在时间段Tt社交网络中自我节点ui选择zi作为中介 人的次数,用表示在时间段Tt社交网络中中介人zi将朋友yi推荐给别人的次数,用 表示在时间段Tt社交网络中自我节点ui和朋友yi交互的次数,用表示在时间 段Tt社交网络中zi在兴趣领域ci中被选为中介人的次数,用表示在时间段Tt社交网 络中yi在兴趣领域ci中被推荐给别人的次数,用表示在时间段Tt社交网络中自我节 点ui在兴趣领域ci中选择新朋友的次数;
(4)对时间段Tt的时间序号t进行判断:
若t≥1,则先验参数分别为:
其中,表示在时间段Tt-1社交网络中自我节点ui选择zi作为中介人的次数, 表示在时间段Tt-1社交网络中中介人zi将朋友yi推荐给别人的次数,表 示在时间段Tt-1社交网络中中介人zi和朋友yi交互的次数,表示在时间段Tt-1社交 网络中ui在兴趣领域ci中被推荐给别人的次数,用表示在时间段Tt-1社交网络中 自我节点ui在兴趣领域ci中选择新朋友的次数;
若t=0,则先验参数分别为:
其中α0,β0,δ0,γ0分别为先验参数的预设值,α0,β0,δ0,γ0分别为正数;
(5)当自我节点ui和自我节点ui的新朋友节点yi有共同朋友时,则从共同朋友中随机 选择共同朋友zi作为自我节点ui与新朋友节点yi之间的候选中介人,记录共同朋友zi被选为 自我节点ui与新朋友节点yi之间的候选中介人的次数为1,当自我节点ui和自我节点ui的新 朋友节点yi没有共同朋友时,则选择自我节点ui作为自我节点ui与新朋友节点yi之间的候选 中介人;
(6)从用户建立的兴趣领域集合K中随机选择一个兴趣领域ci作为自我节点ui与新朋 友节点yi之间的候选兴趣领域,记录兴趣领域ci被选为自我节点ui与新朋友节点yi之间的候 选兴趣领域的次数为1;
(7)当自我节点ui和自我节点ui的新朋友节点yi有共同朋友时,则按照下式计算兴趣 领域为ci的共同朋友z′,作为自我节点ui与新朋友节点yi之间的中介人zi的概率
其中,表示在时间段Tt社交网络中自我节点ui选择z′作为中介人的次数, 表示在时间段Tt社交网络中中介人z′将朋友yi推荐给别人的次数,表示在时 间段Tt社交网络中中介人z′和朋友yi交互的次数,表示在时间段Tt社交网络中z′在 兴趣领域ci中被选为中介人的次数,表示在时间段Tt社交网络中z′在兴趣领域ci中 被推荐给别人的次数,表示在时间段Tt社交网络中自我节点ui选择vi作为中介人的 次数,表示在时间段Tt社交网络中中介人vi将朋友yi推荐给别人的次数,表 示在时间段Tt社交网络中中介人vi和朋友yi交互的次数,表示在时间段Tt社交网络 中vi在兴趣领域ci中被选为中介人的次数,表示在时间段Tt社交网络中vi在兴趣领 域ci中被推荐给别人的次数,为在Tt时间段自我节点ui偏好概率分布的先验参数 中与共同朋友z′相应的先验值,为在Tt时间段z′的朋友关系强度分布先验参数中与 朋友节点yi相应的先验值,为在Tt时间段兴趣领域ci的用户声望概率分布的先验参 数中与z′相应的先验值,为在Tt时间段自我节点ui偏好概率分布的先验参数中与 共同朋友vi相应的先验值,为在Tt时间段vi的朋友关系强度分布先验参数中与朋 友节点yi相应的先验值,为在Tt时间段兴趣领域ci的用户声望概率分布的先验参数 中与vi相应的先验值;
根据得到的概率,采样确定自我节点ui与新朋友节点yi之间的新候选中介人zi,并在 记录中介人zi被选为自我节点ui与新朋友节点yi之间的候选中介人的次数上增加1,进行步 骤(8);
当自我节点ui和自我节点ui的新朋友节点yi没有共同朋友时,则保持步骤(5)的候选 中介人不变,进行步骤(8);
(8)按照下式计算中介人为zi时,自我节点ui与新朋友节点yi的共同兴趣领域ci为c′的 概率
其中,表示在时间段Tt社交网络中zi在兴趣领域c′中被选为中介人的次数,用 表示在时间段Tt社交网络中yi在兴趣领域c′中被推荐给别人的次数,表示在 时间段Tt社交网络中自我节点ui在兴趣领域c′中选择新朋友的次数,表示在时间段 Tt社交网络中zi在兴趣领域ci中被选为中介人的次数,用表示在时间段Tt社交网络 中zi在兴趣领域ci中被推荐给别人的次数,表示在时间段Tt社交网络中自我节点ui在兴趣领域ci中选择新朋友的次数,为在Tt时间段自我节点ui的用户兴趣概率分布的先验参数中与c′相应的先验值,为在Tt时间段兴趣领域c′的用户声望概率分布的 先验参数中与zi相应的先验值,为在Tt时间段自我节点ui的用户兴趣概率分布的先 验参数中与ci相应的先验值,为在Tt时间段兴趣领域ci的用户声望概率分布的先验 参数中与zi相应的先验值;
根据得到的概率,采样确定自我节点ui与新朋友节点yi之间的新候选兴趣领域ci,并 在记录兴趣领域ci被选为自我节点ui与新朋友节点yi之间的候选兴趣领域的次数上增加1; (9)按照下式,分别计算自我节点ui的中介偏好概率分布朋友关系强度分布和兴趣偏好概率分布以及兴趣领域ci的用户声望概率分布
其中,表示在时间段Tt社交网络中自我节点ui选择zi作为中介人的次数, 表示在时间段Tt社交网络中中介人zi将朋友yi推荐给别人的次数,表示在时 间段Tt社交网络中自我节点ui和朋友yi交互的次数,表示在时间段Tt社交网络中ui在兴趣领域ci中被选为中介人的次数,用表示在时间段Tt社交网络中ui在兴趣领域 ci中被推荐给别人的次数,用表示在时间段Tt社交网络中自我节点ui在兴趣领域ci中选择新朋友的次数,表示在时间段Tt社交网络中自我节点ui选择v作为中介人的 次数,表示在时间段Tt社交网络中中介人zi将朋友v推荐给别人的次数,表 示在时间段Tt社交网络中自我节点ui和朋友v交互的次数,表示在时间段Tt社交网络 中u在兴趣领域ci中被选为中介人的次数,用表示在时间段Tt社交网络中u在兴趣领 域ci中被推荐给别人的次数,用表示在时间段Tt社交网络中自我节点ui在兴趣领域c 中选择新朋友的次数,为在Tt时间段自我节点ui偏好概率分布的先验参数中与共 同朋友zi相应的先验值,为在Tt时间段zi的朋友关系强度分布的先验参数中与朋 友节点yi相应的先验值,为在Tt时间段自我节点ui偏好概率分布的先验参数中与共 同朋友v相应的先验值,为在Tt时间段zi的朋友关系强度分布的先验参数中与朋友 节点v相应的先验值,为在Tt时间段自我节点ui的用户兴趣概率分布的先验参数中 与ci相应的先验值,为在Tt时间段兴趣领域ci的用户声望概率分布的先验参数中与 ui相应的先验值,为在Tt时间段自我节点ui的用户兴趣概率分布的先验参数中与c 相应的先验值,为在Tt时间段兴趣领域ci的用户声望概率分布的先验参数中与u相 应的先验值;
根据以上得到的自我节点ui的中介偏好概率分布朋友关系强度分布和兴趣 偏好概率分布以及兴趣领域ci的用户声望概率分布和上一轮迭代后计算所得到 的中介偏好概率分布朋友关系强度分布兴趣偏好概率分布和用户声望概 率分布分别计算中介偏好概率分布变化量Δθ,朋友关系强度分布变化量Δφ,兴趣 偏好概率分布变化量Δχ和用户声望概率分布变化量Δψ:
设定一个变化量阈值,该变化量阈值的取值范围为0-0.1,若Δθ,Δφ,Δχ和Δψ同时小 于该阈值,则进行步骤(10);若Δθ,Δφ,Δχ和Δψ中的任何一个大于或等于该阈值,则设
(10)对于自我节点ui与自我节点ui的新朋友节点yi,以及步骤(7)迭代过程中被采 样到的候选中介人zi,在自我节点ui的朋友关系传播网络的局部层L(ui)中添加一条边 zi→yi,一条边zi→yi的权重等于zi被采样作为自我节点ui与自我节点ui的新朋友节 点yi的候选中介人的概率,即:
在自我节点ui的朋友关系传播网络的全局层G(ui)中添加一条边zi→yi,一条边 zi→yi的权重为:
对于自我节点ui的朋友关系传播网络的局部层L(ui)中的每个节点zi,添加从自我节点 ui到zi的一条边ui→zi,一条边ui→zi的权重为:
(11)遍历自我节点与朋友节点之间交互数据的所有时间段,得到社交网络中每个自 我节点ui的朋友关系传播网络;
(12)对于社交网络中自我节点ui和自我节点ui的朋友关系传播网络的局部层L(ui)上 的任意节点zi,用表示ui在交朋友过程中选择zi作为其中介人的概率,初始化为0,对 于社交网络中自我节点ui和自我节点ui的朋友关系传播网络的全局层G(ui)上的任意节点 vi,用表示ui在交朋友过程中选择vi作为其新朋友的概率,初始化为0;
(13)对于社交网络中自我节点ui和自我节点ui的朋友关系传播网络的局部层L(ui)上 的任意节点zi,按照如下公式更新ui在交朋友过程中选择zi作为其中介人的概率
其中表示在本轮迭代开始前的值,是自我节点ui的朋友关系传播网络 的局部层L(ui)中边z→zi的权重,是自我节点ui到自我节点ui的朋友关系传播网络的 局部层L(ui)中的节点zi的边ui→zi的权重,F(ui,zi)表示ui和zi的公共朋友集合,μ是取值 为0-1的参数;
(14)对于社交网络中自我节点ui,计算中介选择概率变化量
设定一个变化量阈值,该变化量阈值的取值范围为0-0.1,若小于设定阈值, 则进行步骤(15);若大于或等于设定阈值,则对于社交网络中自我节点ui的朋友关 系传播网络的局部层L(ui)上的任意节点zi,设并返回步骤(13);
(15)对于社交网络中自我节点ui和自我节点ui的朋友关系传播网络的全局层G(ui)上 的任意节点vi,按照如下公式更新ui在交朋友过程中选择vi作为其新朋友的概率
其中表示在本轮迭代开始前的值,是自我节点ui的朋友关系传播网 络的全局层G(ui)中边v→vi的权重,是自我节点ui在交朋友过程中选择vi作为其中介 人的概率,F(vi)表示vi的朋友集合,μ是取值为0-1的参数;
(16)对于社交网络中自我节点ui,计算朋友选择概率变化量
设定一个变化量阈值,该变化量阈值的取值范围为0-0.1,若小于指定阈值, 则进行步骤(17);若大于或等于指定阈值,则对于社交网络中自我节点ui的朋友关 系传播网络的全局层G(ui)上的任意节点vi,设并返回步骤(15);
(16)对于社交网络中自我节点ui,将自我节点ui的朋友关系传播网络的全局层G(ui)上 的所有节点vi,按照与节点相对应的值从大到小排序,作为向ui推荐的朋友列表。
本发明提出的社交网络中的基于朋友关系传播的朋友推荐方法,其优点是:
1、本发明方法基于社会学中的传递性原理,对用户在社交网络中的社交行为进行合 理建模,同时考虑用户对于朋友的偏好、对于中介人的偏好、兴趣领域的偏好以及朋友圈 地相互影响作用,可以更准确地预测用户未来的交友行为,从而可以为交友网站提供更准 确的好友推荐结果。
2、本发明方法构造的社交网络中的潜在朋友关系传播网络,从朋友关系传递性的角 度出发,对社交网络的演化过程提供了层次化、因果式的可视化呈现与解释,便于深入分 析社交网络的成因与内在结构,以及预测社交网络未来的发展与变化,从而为交友网站的 设计与运营提供参考。
3、本发明方法不需要额外的训练数据,避免了训练数据中的不平衡问题,适用性强, 便于应用。
附图说明
图1是本发明方法涉及的社交网络中潜在朋友关系传播网络的部分示意图。
图2是本发明方法涉及的社交网络中潜在朋友关系传播网络的整体示意图。
图3是本发明方法中建立的兴趣感知的社交行为概率生成模型示意图。
具体实施方式
本发明提出的社交网络中的基于朋友关系传播的朋友推荐方法,包括以下步骤:
(1)设社交网络中有多个用户,每个用户有多个朋友,将用户记为自我节点ui,将该 用户的朋友记为朋友节点vi;为社交网络中的自我节点ui,创建一个属于自我节点ui的潜 在朋友关系传播网络,创建的潜在朋友关系传播网络如图1所示,该网络包括三层:自我 层E(ui)、局部层L(ui)和全局层G(ui),在自我层E(ui)中添加自我节点ui,在局部层L(ui)中 添加自我节点ui的所有朋友节点,在全局层G(ui)中添加社交网络中的所有节点;每个用户 建立一个兴趣领域集合K;
(2)按照时间,将自我节点与朋友节点之间的交互数据按交互的时间划分为N段, 对于与第t段交互相对应的时间段Tt,执行步骤(3)-(10),t=1,2,……,N;
(3)建立如下兴趣感知的社交行为概率生成模型,模型的图形化表示如图3所示:
(3-1)设社交网络中每个自我节点ui的交互行为数为社交网络中每个自我节点ui的新交朋友数为
(3-2)分别用先验参数为的狄利克雷分布表示社交网络中每个自我节点ui的朋友 关系强度分布的先验分布,从该狄利克雷分布中采样得到社交网络中自我节点ui在时间段 Tt的朋友关系强度分布
(3-3)从上述朋友关系强度分布中,采样得到社交网络中每个自我节点ui的每次 交互对象x;
(3-4)分别用先验参数为的狄利克雷分布表示社交网络中每个自我节点ui的中介 偏好概率分布的先验分布,从该狄利克雷分布中采样得到社交网络中自我节点ui在时间段 Tt的中介偏好概率分布
(3-5)分别用先验参数为的狄利克雷分布表示社交网络中每个自我节点ui的兴趣 偏好概率分布的先验分布,从该狄利克雷分布中采样得到社交网络中自我节点ui在时间段 Tt的兴趣偏好概率分布
(3-6)分别用先验参数为的狄利克雷分布表示社交网络中兴趣领域的用户声望概 率分布的先验分布,从该狄利克雷分布中采样得到社交网络中每个兴趣领域ci在时间段Tt的用户声望概率分布
(3-7)从上述用户兴趣概率分布中采样得到社交网络中每个自我节点ui的兴趣领 域ci,分别从上述中介偏好概率分布和用户声望概率分布的联合分布中采样得到 社交网络中每个自我节点ui的中介人zi,从与中介人zi对应的朋友关系强度分布和用户 声望概率分布的联合分布中采样得到社交网络中自我节点ui的新朋友节点yi;
(3-8)用U表示社交网络中用户的集合,用K表示社交网络中用户兴趣领域的集合, 用表示社交网络中自我节点ui在时间段Tt的朋友节点集合,用表示社交网 络中自我节点ui在时间段Tt的新朋友节点集合,用表示社交网络中自我节点ui在时 间段Tt的交互节点集合,用表示在时间段Tt社交网络中自我节点ui选择zi作为中介 人的次数,用表示在时间段Tt社交网络中中介人zi将朋友yi推荐给别人的次数,用 表示在时间段Tt社交网络中自我节点ui和朋友yi交互的次数,用表示在时间 段Tt社交网络中zi在兴趣领域ci中被选为中介人的次数,用表示在时间段Tt社交网 络中yi在兴趣领域ci中被推荐给别人的次数,用表示在时间段Tt社交网络中自我节 点ui在兴趣领域ci中选择新朋友的次数;
(4)对时间段Tt的时间序号t进行判断:
若t≥1,则先验参数分别为:
其中,表示在时间段Tt-1社交网络中自我节点ui选择zi作为中介人的次数, 表示在时间段Tt-1社交网络中中介人zi将朋友yi推荐给别人的次数,表 示在时间段Tt-1社交网络中中介人zi和朋友yi交互的次数,表示在时间段Tt-1社交 网络中ui在兴趣领域ci中被推荐给别人的次数,用表示在时间段Tt-1社交网络中 自我节点ui在兴趣领域ci中选择新朋友的次数;
若t=0,则先验参数分别为:
其中α0,β0,δ0,γ0分别为先验参数的预设值,α0,β0,δ0,γ0分别为正数;
(5)当自我节点ui和自我节点ui的新朋友节点yi有共同朋友时,则从共同朋友中随机 选择共同朋友zi作为自我节点ui与新朋友节点yi之间的候选中介人,记录共同朋友zi被选为 自我节点ui与新朋友节点yi之间的候选中介人的次数为1,当自我节点ui和自我节点ui的新 朋友节点yi没有共同朋友时,则选择自我节点ui作为自我节点ui与新朋友节点yi之间的候选 中介人;
(6)从用户建立的兴趣领域集合K中随机选择一个兴趣领域ci作为自我节点ui与新朋 友节点yi之间的候选兴趣领域,记录兴趣领域ci被选为自我节点ui与新朋友节点yi之间的候 选兴趣领域的次数为1;
(7)当自我节点ui和自我节点ui的新朋友节点yi有共同朋友时,则按照下式计算兴趣 领域为ci的共同朋友z′,作为自我节点ui与新朋友节点yi之间的中介人zi的概率
其中,表示在时间段Tt社交网络中自我节点ui选择z′作为中介人的次数, 表示在时间段Tt社交网络中中介人z′将朋友yi推荐给别人的次数,表示在时 间段Tt社交网络中中介人z′和朋友yi交互的次数,表示在时间段Tt社交网络中z′在 兴趣领域ci中被选为中介人的次数,表示在时间段Tt社交网络中z′在兴趣领域ci中 被推荐给别人的次数,表示在时间段Tt社交网络中自我节点ui选择vi作为中介人的 次数,表示在时间段Tt社交网络中中介人vi将朋友yi推荐给别人的次数,表 示在时间段Tt社交网络中中介人vi和朋友yi交互的次数,表示在时间段Tt社交网络 中vi在兴趣领域ci中被选为中介人的次数,表示在时间段Tt社交网络中vi在兴趣领 域ci中被推荐给别人的次数,为在Tt时间段自我节点ui偏好概率分布的先验参数 中与共同朋友z′相应的先验值,为在Tt时间段z′的朋友关系强度分布光验参数中与 朋友节点yi相应的先验值,为在Tt时间段兴趣领域ci的用户声望概率分布的先验参 数中与z′相应的先验值,为在Tt时间段自我节点ui偏好概率分布的先验参数中与 共同朋友vi相应的先验值,为在Tt时间段vi的朋友关系强度分布先验参数中与朋 友节点yi相应的先验值,为在Tt时间段兴趣领域ci的用户声望概率分布的先验参数 中与vi相应的先验值;
根据得到的概率,采样确定自我节点ui与新朋友节点yi之间的新候选中介人zi,并在 记录中介人zi被选为自我节点ui与新朋友节点yi之间的候选中介人的次数上增加1,进行步 骤(8);
当自我节点ui和自我节点ui的新朋友节点yi没有共同朋友时,则保持步骤(5)的候选 中介人不变,进行步骤(8);
(8)按照下式计算中介人为zi时,自我节点ui与新朋友节点yi的共同兴趣领域ci为c′的 概率
其中,表示在时间段Tt社交网络中zi在兴趣领域c′中被选为中介人的次数,用 表示在时间段Tt社交网络中yi在兴趣领域c′中被推荐给别人的次数,表示在 时间段Tt社交网络中自我节点ui在兴趣领域c′中选择新朋友的次数,表示在时间段 Tt社交网络中zi在兴趣领域ci中被选为中介人的次数,用表示在时间段Tt社交网络 中zi在兴趣领域ci中被推荐给别人的次数,表示在时间段Tt社交网络中自我节点ui在兴趣领域ci中选择新朋友的次数,为在Tt时间段自我节点ui的用户兴趣概率分布的先验参数中与c′相应的先验值,为在Tt时间段兴趣领域c′的用户声望概率分布的 先验参数中与zi相应的先验值,为在Tt时间段自我节点ui的用户兴趣概率分布的先 验参数中与ci相应的先验值,为在Tt时间段兴趣领域ci的用户声望概率分布的先验 参数中与zi相应的先验值;
根据得到的概率,采样确定自我节点ui与新朋友节点yi之间的新候选兴趣领域ci,并 在记录兴趣领域ci被选为自我节点ui与新朋友节点yi之间的候选兴趣领域的次数上增加1;
(9)按照下式,分别计算自我节点ui的中介偏好概率分布朋友关系强度分布和兴趣偏好概率分布以及兴趣领域ci的用户声望概率分布
其中,表示在时间段Tt社交网络中自我节点ui选择zi作为中介人的次数, 表示在时间段Tt社交网络中中介人zi将朋友yi推荐给别人的次数,表示在时 间段Tt社交网络中自我节点ui和朋友yi交互的次数,表示在时间段Tt社交网络中ui在兴趣领域ci中被选为中介人的次数,用表示在时间段Tt社交网络中ui在兴趣领域 ci中被推荐给别人的次数,用表示在时间段Tt社交网络中自我节点ui在兴趣领域ci中选择新朋友的次数,表示在时间段Tt社交网络中自我节点ui选择v作为中介人的 次数,表示在时间段Tt社交网络中中介人zi将朋友v推荐给别人的次数,表 示在时间段Tt社交网络中自我节点ui和朋友v交互的次数,表示在时间段Tt社交网络 中u在兴趣领域ci中被选为中介人的次数,用表示在时间段Tt社交网络中u在兴趣领 域ci中被推荐给别人的次数,用表示在时间段Tt社交网络中自我节点ui在兴趣领域c 中选择新朋友的次数,为在Tt时间段自我节点ui偏好概率分布的先验参数中与共 同朋友zi相应的先验值,为在Tt时间段zi的朋友关系强度分布的先验参数中与朋 友节点yi相应的先验值,为在Tt时间段自我节点ui偏好概率分布的先验参数中与共 同朋友v相应的先验值,为在Tt时间段zi的朋友关系强度分布的先验参数中与朋友 节点v相应的先验值,为在Tt时间段自我节点ui的用户兴趣概率分布的先验参数中 与ci相应的先验值,为在Tt时间段兴趣领域ci的用户声望概率分布的先验参数中与 ui相应的先验值,为在Tt时间段自我节点ui的用户兴趣概率分布的先验参数中与c 相应的先验值,为在Tt时间段兴趣领域ci的用户声望概率分布的先验参数中与u相 应的先验值;
根据以上得到的自我节点ui的中介偏好概率分布朋友关系强度分布和兴趣 偏好概率分布以及兴趣领域ci的用户声望概率分布和上一轮迭代后计算所得到 的中介偏好概率分布朋友关系强度分布兴趣偏好概率分布和用户声望概 率分布分别计算中介偏好概率分布变化量Δθ,朋友关系强度分布变化量Δφ,兴趣 偏好概率分布变化量Δχ和用户声望概率分布变化量Δψ:
设定一个变化量阈值,该变化量阈值的取值范围为0-0.1,若Δθ,Δφ,Δχ和Δψ同时小 于该阈值,则进行步骤(10);若Δθ,Δφ,Δχ和Δψ中的任何一个大于或等于该阈值,则设
(10)对于自我节点ui与自我节点ui的新朋友节点yi,以及步骤(7)迭代过程中被采 样到的候选中介人zi,在自我节点ui的朋友关系传播网络的局部层L(ui)中添加一条边 zi→yi,一条边zi→yi的权重等于zi被采样作为自我节点ui与自我节点ui的新朋友节 点yi的候选中介人的概率,即:
在自我节点ui的朋友关系传播网络的全局层G(ui)中添加一条边zi→yi,一条边 zi→yi的权重为:
对于自我节点ui的朋友关系传播网络的局部层L(ui)中的每个节点zi,添加从自我节点 ui到zi的一条边ui→zi,一条边ui→zi的权重为:
(11)遍历自我节点与朋友节点之间交互数据的所有时间段,得到社交网络中每个自 我节点ui的朋友关系传播网络,得到的整体潜在朋友关系传播网络如图2所示;
(12)对于社交网络中自我节点ui和自我节点ui的朋友关系传播网络的局部层L(ui)上 的任意节点zi,用表示ui在交朋友过程中选择zi作为其中介人的概率,初始化为0,对 于社交网络中自我节点ui和自我节点ui的朋友关系传播网络的全局层G(ui)上的任意节点 vi,用表示ui在交朋友过程中选择vi作为其新朋友的概率,初始化为0;
(13)对于社交网络中自我节点ui和自我节点ui的朋友关系传播网络的局部层L(ui)上 的任意节点zi,按照如下公式更新ui在交朋友过程中选择zi作为其中介人的概率
其中表示在本轮迭代开始前的值,是自我节点ui的朋友关系传播网络 的局部层L(ui)中边z→zi的权重,是自我节点ui到自我节点ui的朋友关系传播网络的 局部层L(ui)中的节点zi的边ui→zi的权重,F(ui,zi)表示ui和zi的公共朋友集合,μ是取值 为0-1的参数;
(14)对于社交网络中自我节点ui,计算中介选择概率变化量
设定一个变化量阈值,该变化量阈值的取值范围为0-0.1,若小于设定阈值, 则进行步骤(15);若大于或等于设定阈值,则对于社交网络中自我节点ui的朋友关 系传播网络的局部层L(ui)上的任意节点zi,设并返回步骤(13);
(15)对于社交网络中自我节点ui和自我节点ui的朋友关系传播网络的全局层G(ui)上 的任意节点vi,按照如下公式更新ui在交朋友过程中选择vi作为其新朋友的概率
其中表示在本轮迭代开始前的值,是自我节点ui的朋友关系传播网 络的全局层G(ui)中边v→vi的权重,是自我节点ui在交朋友过程中选择vi作为其中介 人的概率,F(vi)表示vi的朋友集合,μ是取值为0-1的参数;
(16)对于社交网络中自我节点ui,计算朋友选择概率变化量
设定一个变化量阈值,该变化量阈值的取值范围为0-0.1,若小于指定阈值, 则进行步骤(17);若大于或等于指定阈值,则对于社交网络中自我节点ui的朋友关 系传播网络的全局层G(ui)上的任意节点vi,设并返回步骤(15);
(16)对于社交网络中自我节点ui,将自我节点ui的朋友关系传播网络的全局层G(ui)上 的所有节点vi,按照与节点相对应的值从大到小排序,作为向ui推荐的朋友列表。
机译: 基于用户之间的亲密关系推荐朋友的朋友的社交网络服务系统和方法
机译: 推荐朋友的社交网络和朋友推荐方法
机译: 通过与地址簿和通信历史的各种关系来提供朋友推荐服务的在线社交网络服务提供设备及其方法