论文部分内容阅读
摘 要：针对在线社交网络朋友推荐问题，尝试利用描述多种关系的多子网复合复杂网络构建社交网络的复合网，引入连接度来表示对已连接朋友的喜爱程度，从而为用户提供个性化推荐。本文以微博中为用户推荐关注为例。
关键词：多子网复合复杂网络；连接度；个性化推荐；微博关注
中图分类号：TP301.6
近年来，国内微博快速发展，微博中蕴含大量的信息，而对某一用户而言，大部分信息是他并不感兴趣的，同时不同用户对不同的信息感兴趣，个性化推荐可以部分解决社交网络信息量过载，信息对用户的冗余问题。因此，更加精确地为用户推荐感兴趣的信息成为微博运营商提升用户体验的重要方式，个性化推荐算法发挥了举足轻重的作用。
1 相关工作[1]
对于社交网络的设计者来说，面对大量在线用户、数据的稀疏性[2]以及他们的多样化，如何帮助用户发现新的感兴趣的朋友是一个大的挑战。流行的推荐算法基于假设：两个用户的相似度越高，则他们成为朋友的可能性越大。目前有三种主要的方法用于描述用户的相似度：基于用户的属性特征、基于网络结构的局部特征和基于网络结构的全局特性。
（1）基于用户的属性特征进行朋友推荐的思想：根据的用户年龄、性别、学校、住址等注册信息来计算用户的相似度，注册信息的内容越相似，成为朋友的可能性就越大。
（2）基于网络结构的局部特征的方法利用用户朋友网络结构的局部结构信息。利用多种局部相似性测量指标，如共同邻居，Jaccard，Adamic/Adar等。
（3）基于网络结构的全局特性侦测朋友网络中的所有路径结构，其中Google网页排序算法PageRank的拓展应用重启动随机游走算法（Random Walk With Restart，RWR）。RWR算法是一个基于图的随机游走马尔科夫链模型。
相比于上述方法，本文拓展了单个朋友网络关系，基于多子网复合复杂网络，融合了多种关系，引入连接度来描述用户的相似度，提出了一种面向微博的基于多子网复合复杂网络的推荐算法。
2 基于多子网复合复杂网络的微博关注推荐算法
算法首先构建以用户为顶点的单一关系网络，然后将多个单一关系网络利用多子网复合复杂网络的加载功能复合为一个多子网复合复杂网络，在复合网中，定义连接度，连接度的大小反应了两个用户相似度的大小，从而可根据连接度做朋友推荐。顶点之间的不同关系会影响他们的相似度，所以需要为不同关系设置不同的权重值。
2.1 多子网复合复杂网络模型的构建
实现算法的第一个关键问题是构建一个有意义的网络，使得其能真实反映用户在社交网络中的拓扑关系。构建一个多子网复合复杂网络，融合用户的多种关系。具体构建步骤如下：
（1）以用户名为顶点，分别以关注、@、评论、共同的应用等用户已做出的行为为边构建单一关系的网络，本文构建的单一网络均是无向网。单一关系网以顶点之间的关系命名，比如以关注为边的网称为关注网。
（2）因为每一个网都有共同的顶点（用户），利用多子网复合复杂网络的子网加载功能可以将它们复合成一个网，复合后的网的顶点之间可能有多种关系，至此面向微博的基于多子网复合复杂网络已构建完成。
2.2 连接度的定义
2.3 算法复杂度简化分析
根据“六度分离”[7]的实验结论，当两个顶点之间的最短路径长度大于7时，说明这两个顶点的连接度较小，为进一步降低算法的复杂度，最初执行算法时的候选顶点集合设定为与给定顶点的最短路径长度小于等于4的顶点组成集合。
2.4 算法描述
对于一个特定的用户，其必定对应复合网中的某一顶点，为某一用户设计个性化推荐关注的步骤为：
（1）计算确定复合网中与给定顶点的最短路径长度小于等于4的顶点组成集合S；
（2）删除S中给定用户已关注的顶点：SC=S-给定顶点已关注的顶点。若SC大于或等于需要推荐的关注数目N，则执行步骤（3）；否则增大步骤（1）中的最短路径长度（每次增加1个单位），并从步骤（1）开始重复执行；
（3）根据连接度公式，计算集合SC中所有顶点与给定点的连接度；
（4）根据推荐关注的数目N取出连接度排名（与给顶点的连接度越大，排名越靠前）前N的顶点组成集合TC；
（5）将TC中顶点对应的用户推荐给给定用户。
3 结语和展望
现实的社交网络含有多种对象，呈现出复杂的关系。传统的社交网络推荐仅仅考虑基于一种关系的网络。充分挖掘和使用网络中的多种对象以及多种关系，是提高社交网路的推荐算法精度的一个很好的角度，本文提出了一种基于多子网复合复杂网络的推荐算法，但是没有考虑有向网络，用有向网络来描述社交网络多种关系的拓扑结构并用于个性化推荐是下一步的工作方向。
参考文献：
[1]俞琰，邱广华.基于混合图的在线社交网络朋友推荐算法[J].现代图书情报技术，2011，11.
[2]刘建国，周涛.个性化推荐系统的研究进展[J].自然科学进展，2009，19（1）.
[3]隋毅.多子网复合复杂网络模型及其相关性质的研究[D].青岛：青岛大学，2012，04.
[4]陆锋.最短路径算法-分类体系与研究进展[J].测绘学报，2011，30（2）.
[5]唐晋韬，王挺.适合复杂网络分析的最短路径近似算法[J].软件学报，2011，10.
[6]汪小帆，李翔.复杂网络理论及其应用[M].北京：清华大学出版社，2006，10-45.
[7]朱亚丽.“六度分离”假说的信息学意义[J].图书情报工作，2005，6.
作者简介：孙荣德（1987.03-），男，山东临沂市平邑县地方镇新华村人，研究生，硕士，计算机软件与理论专业，研究方向：数据挖掘。
作者单位：青岛大学 信息工程学院，山东青岛 266071
关键词：多子网复合复杂网络；连接度；个性化推荐；微博关注
中图分类号：TP301.6
近年来，国内微博快速发展，微博中蕴含大量的信息，而对某一用户而言，大部分信息是他并不感兴趣的，同时不同用户对不同的信息感兴趣，个性化推荐可以部分解决社交网络信息量过载，信息对用户的冗余问题。因此，更加精确地为用户推荐感兴趣的信息成为微博运营商提升用户体验的重要方式，个性化推荐算法发挥了举足轻重的作用。
1 相关工作[1]
对于社交网络的设计者来说，面对大量在线用户、数据的稀疏性[2]以及他们的多样化，如何帮助用户发现新的感兴趣的朋友是一个大的挑战。流行的推荐算法基于假设：两个用户的相似度越高，则他们成为朋友的可能性越大。目前有三种主要的方法用于描述用户的相似度：基于用户的属性特征、基于网络结构的局部特征和基于网络结构的全局特性。
（1）基于用户的属性特征进行朋友推荐的思想：根据的用户年龄、性别、学校、住址等注册信息来计算用户的相似度，注册信息的内容越相似，成为朋友的可能性就越大。
（2）基于网络结构的局部特征的方法利用用户朋友网络结构的局部结构信息。利用多种局部相似性测量指标，如共同邻居，Jaccard，Adamic/Adar等。
（3）基于网络结构的全局特性侦测朋友网络中的所有路径结构，其中Google网页排序算法PageRank的拓展应用重启动随机游走算法（Random Walk With Restart，RWR）。RWR算法是一个基于图的随机游走马尔科夫链模型。
相比于上述方法，本文拓展了单个朋友网络关系，基于多子网复合复杂网络，融合了多种关系，引入连接度来描述用户的相似度，提出了一种面向微博的基于多子网复合复杂网络的推荐算法。
2 基于多子网复合复杂网络的微博关注推荐算法
算法首先构建以用户为顶点的单一关系网络，然后将多个单一关系网络利用多子网复合复杂网络的加载功能复合为一个多子网复合复杂网络，在复合网中，定义连接度，连接度的大小反应了两个用户相似度的大小，从而可根据连接度做朋友推荐。顶点之间的不同关系会影响他们的相似度，所以需要为不同关系设置不同的权重值。
2.1 多子网复合复杂网络模型的构建
实现算法的第一个关键问题是构建一个有意义的网络，使得其能真实反映用户在社交网络中的拓扑关系。构建一个多子网复合复杂网络，融合用户的多种关系。具体构建步骤如下：
（1）以用户名为顶点，分别以关注、@、评论、共同的应用等用户已做出的行为为边构建单一关系的网络，本文构建的单一网络均是无向网。单一关系网以顶点之间的关系命名，比如以关注为边的网称为关注网。
（2）因为每一个网都有共同的顶点（用户），利用多子网复合复杂网络的子网加载功能可以将它们复合成一个网，复合后的网的顶点之间可能有多种关系，至此面向微博的基于多子网复合复杂网络已构建完成。
2.2 连接度的定义
2.3 算法复杂度简化分析
根据“六度分离”[7]的实验结论，当两个顶点之间的最短路径长度大于7时，说明这两个顶点的连接度较小，为进一步降低算法的复杂度，最初执行算法时的候选顶点集合设定为与给定顶点的最短路径长度小于等于4的顶点组成集合。
2.4 算法描述
对于一个特定的用户，其必定对应复合网中的某一顶点，为某一用户设计个性化推荐关注的步骤为：
（1）计算确定复合网中与给定顶点的最短路径长度小于等于4的顶点组成集合S；
（2）删除S中给定用户已关注的顶点：SC=S-给定顶点已关注的顶点。若SC大于或等于需要推荐的关注数目N，则执行步骤（3）；否则增大步骤（1）中的最短路径长度（每次增加1个单位），并从步骤（1）开始重复执行；
（3）根据连接度公式，计算集合SC中所有顶点与给定点的连接度；
（4）根据推荐关注的数目N取出连接度排名（与给顶点的连接度越大，排名越靠前）前N的顶点组成集合TC；
（5）将TC中顶点对应的用户推荐给给定用户。
3 结语和展望
现实的社交网络含有多种对象，呈现出复杂的关系。传统的社交网络推荐仅仅考虑基于一种关系的网络。充分挖掘和使用网络中的多种对象以及多种关系，是提高社交网路的推荐算法精度的一个很好的角度，本文提出了一种基于多子网复合复杂网络的推荐算法，但是没有考虑有向网络，用有向网络来描述社交网络多种关系的拓扑结构并用于个性化推荐是下一步的工作方向。
参考文献：
[1]俞琰，邱广华.基于混合图的在线社交网络朋友推荐算法[J].现代图书情报技术，2011，11.
[2]刘建国，周涛.个性化推荐系统的研究进展[J].自然科学进展，2009，19（1）.
[3]隋毅.多子网复合复杂网络模型及其相关性质的研究[D].青岛：青岛大学，2012，04.
[4]陆锋.最短路径算法-分类体系与研究进展[J].测绘学报，2011，30（2）.
[5]唐晋韬，王挺.适合复杂网络分析的最短路径近似算法[J].软件学报，2011，10.
[6]汪小帆，李翔.复杂网络理论及其应用[M].北京：清华大学出版社，2006，10-45.
[7]朱亚丽.“六度分离”假说的信息学意义[J].图书情报工作，2005，6.
作者简介：孙荣德（1987.03-），男，山东临沂市平邑县地方镇新华村人，研究生，硕士，计算机软件与理论专业，研究方向：数据挖掘。
作者单位：青岛大学 信息工程学院，山东青岛 266071