基于用户聚类的异构社交网络推荐算法
2022-06-09
【论文摘要】相比传统的社交网络，基于弱关系的微博类社交网络具有显著的异构特征.根据特征可以将节点分为用户（消息订阅者）和主题（消息发布者）两类，面向用户推荐其感兴趣的主题成为了该类社交网络中推荐系统的主要目标之一，同时该类社交网络中普遍存在的数据稀疏性和冷启动现象成为了推荐系统面临的主要问题.文中提出一种基于两阶段聚类的推荐算法GCCR，将图摘要方法和基于内容相似度的算法结合，实现基于用户兴趣的主题推荐.与以往方法相比，该方法在稀疏数据和冷启动的情况下具有更好的推荐效果，此外，通过对数据集进行大量的离线处理，使得其较以往推荐方法具有更好的在线推荐效率.最后通过真实社交网络的数据对本方法进行了验证，同时分析了各参数对推荐效果的影响.
1引言
社交网络（SocialNetworksServices,SNS)随着Internet用户的普及呈现出飞速发展的趋势，不仅用户数量爆炸性地增长，其服务形态也在发生急剧的变化.近年来，大量新型的社交网络服务不断地涌现，其中以国外Twitter和国内新浪微博为代表的弱关系社交网络微博服务（McroBlog)正成为一种主要的社交网络形态.与传统的社交网络不同，由于弱关系的单向性，基于弱关系（即单向关注关系）的社交网络中的节点呈现出明显的异构性特征，包括大量以自然人为主体的用户节点（如“张三”）和以媒体、机构以及各类消息源为主体的主题节点（如“北京天气”、“南方周末”、“热门视频”等）.其中，用户节点，通常作为消息订阅者，单向关注大量主题节点，这些单向订阅关系，往往基于用户对于不同类型主题的兴趣倾向；同时用户节点常常与其它用户节点形成双向关注关系，这通常基于用户的真实社会关系.相反，主题节点，作为消息的发布者，被大量的用户节点订阅，而其主动关注和双向关注关系数量远远小于其被订阅的数量.图1(a)展示了一个典型基于强关系的社交网络结构，网络中的节点呈现出同构性.图1(b)为从新浪微博中提取出的一个典型异构弱关系社交网络（黑点为用户节点，白点为主题节点，虚线为单向订阅关系，实线为互关注关系）.
自然的，异构社交网络中的推荐系统所服务对象是用户节点，其推荐的内容主要分为两类：向用户推荐其它用户节点（如向“张三”推荐“李四”和推荐主题节点（如向“张三”推荐“北京天气”），即面向互关注关系的推荐和面向订阅关系的推荐.对于互关注关系和订阅关系的推荐需要基于不同因素：对于互关注关系的推荐，通过共同好友、联系人、通讯录等真实社交信息的方法通常就达到很好的效果[1];对于订阅关系，需要基于用户的兴趣进行推荐，这与推荐系统中常见的商品推荐、文档推荐等场景类似.关于这类推荐问题，有学者也进行了充分的研究[2-4]，提出了协同过滤、基于内容等方法.
然而，社交网络上的推荐问题，特别是对订阅关系的推荐，不同于传统的推荐系统，其一大挑战在于它极端的数据稀疏性.Mislove等人[5]指出，Internet上的社交网络呈现出Scale-freeNetwork的特点，极少量的用户拥有较多的关系连接，而大量的用户仅具有少量的关系连接.由于大量主题节点的存在，这一现象在弱关系社交网络中更加显著.如图2所示，根据对新浪微博中抽样的500个用户和50个主题的统计，仅有20%的用户对10%以上的主题有订阅关系，而关注主题数量低于总主题数量5%的用户占了超过一半的比例.而对于如此稀疏的数据，协同过滤等单纯基于二元关系的方法不能达到理想的推荐效果．
此外，社交网络随着新用户的不断加入，往往面临着冷启动（ColdStart)的问题.新加入的用户往往体现出很少的兴趣倾向，而基于内容的推荐方法往往不具有足够的多样性，使得推荐结果会很快地收敛于一个小范围的集合，从而丧失对更多用户感兴趣内容产生推荐的可能.
本文所解决的问题是在微博类的异构社交网络中对用户进行主题节点的推荐（即订阅推荐），并处理社交网络中普遍存在的数据稀疏性和冷启动场景.对此，本文提出了一种基于两阶段的用户聚类的主题推荐的方法GCCR(Graph-ContentClusteringRecommendation).首先，选取用户节点中关注数量较高的节点，从而抽取出稀疏数据中的一个密集子集，利用图摘要（GraphSummarization)的方法，对此密集子集形成关注兴趣相似的核心聚类.然后，提取种子聚类的微博内容特征和整个数据集中其它用户的内容特征，基于内容相似度对整个用户群进行聚类，最后将聚类结果用于主题推荐.
通过对密集数据子集和全数据集的两阶段聚类过程，提高对极端稀疏数据集的聚类效果.同时，由于图摘要聚类中的类模糊性，可以在对用户兴趣聚类的过程中保留一定的多样性，从而避免冷启动时收敛过快.
1引言
社交网络（SocialNetworksServices,SNS)随着Internet用户的普及呈现出飞速发展的趋势，不仅用户数量爆炸性地增长，其服务形态也在发生急剧的变化.近年来，大量新型的社交网络服务不断地涌现，其中以国外Twitter和国内新浪微博为代表的弱关系社交网络微博服务（McroBlog)正成为一种主要的社交网络形态.与传统的社交网络不同，由于弱关系的单向性，基于弱关系（即单向关注关系）的社交网络中的节点呈现出明显的异构性特征，包括大量以自然人为主体的用户节点（如“张三”）和以媒体、机构以及各类消息源为主体的主题节点（如“北京天气”、“南方周末”、“热门视频”等）.其中，用户节点，通常作为消息订阅者，单向关注大量主题节点，这些单向订阅关系，往往基于用户对于不同类型主题的兴趣倾向；同时用户节点常常与其它用户节点形成双向关注关系，这通常基于用户的真实社会关系.相反，主题节点，作为消息的发布者，被大量的用户节点订阅，而其主动关注和双向关注关系数量远远小于其被订阅的数量.图1(a)展示了一个典型基于强关系的社交网络结构，网络中的节点呈现出同构性.图1(b)为从新浪微博中提取出的一个典型异构弱关系社交网络（黑点为用户节点，白点为主题节点，虚线为单向订阅关系，实线为互关注关系）.
自然的，异构社交网络中的推荐系统所服务对象是用户节点，其推荐的内容主要分为两类：向用户推荐其它用户节点（如向“张三”推荐“李四”和推荐主题节点（如向“张三”推荐“北京天气”），即面向互关注关系的推荐和面向订阅关系的推荐.对于互关注关系和订阅关系的推荐需要基于不同因素：对于互关注关系的推荐，通过共同好友、联系人、通讯录等真实社交信息的方法通常就达到很好的效果[1];对于订阅关系，需要基于用户的兴趣进行推荐，这与推荐系统中常见的商品推荐、文档推荐等场景类似.关于这类推荐问题，有学者也进行了充分的研究[2-4]，提出了协同过滤、基于内容等方法.
然而，社交网络上的推荐问题，特别是对订阅关系的推荐，不同于传统的推荐系统，其一大挑战在于它极端的数据稀疏性.Mislove等人[5]指出，Internet上的社交网络呈现出Scale-freeNetwork的特点，极少量的用户拥有较多的关系连接，而大量的用户仅具有少量的关系连接.由于大量主题节点的存在，这一现象在弱关系社交网络中更加显著.如图2所示，根据对新浪微博中抽样的500个用户和50个主题的统计，仅有20%的用户对10%以上的主题有订阅关系，而关注主题数量低于总主题数量5%的用户占了超过一半的比例.而对于如此稀疏的数据，协同过滤等单纯基于二元关系的方法不能达到理想的推荐效果．
此外，社交网络随着新用户的不断加入，往往面临着冷启动（ColdStart)的问题.新加入的用户往往体现出很少的兴趣倾向，而基于内容的推荐方法往往不具有足够的多样性，使得推荐结果会很快地收敛于一个小范围的集合，从而丧失对更多用户感兴趣内容产生推荐的可能.
本文所解决的问题是在微博类的异构社交网络中对用户进行主题节点的推荐（即订阅推荐），并处理社交网络中普遍存在的数据稀疏性和冷启动场景.对此，本文提出了一种基于两阶段的用户聚类的主题推荐的方法GCCR(Graph-ContentClusteringRecommendation).首先，选取用户节点中关注数量较高的节点，从而抽取出稀疏数据中的一个密集子集，利用图摘要（GraphSummarization)的方法，对此密集子集形成关注兴趣相似的核心聚类.然后，提取种子聚类的微博内容特征和整个数据集中其它用户的内容特征，基于内容相似度对整个用户群进行聚类，最后将聚类结果用于主题推荐.
通过对密集数据子集和全数据集的两阶段聚类过程，提高对极端稀疏数据集的聚类效果.同时，由于图摘要聚类中的类模糊性，可以在对用户兴趣聚类的过程中保留一定的多样性，从而避免冷启动时收敛过快.