Recommendersystembasedoncouplednetwork作者：陈东瑞1.复杂网络基础知识当我们拿起手机给家人、朋友或同事打电话时，我们不知不觉地参与了形成社交网络当我们登上高铁或飞机时，我们可以享受交通网络带来的便利；即使当我们躺在床上什么都不做时，大脑中的神经元也会形成一个庞大而复杂的网络，相互交互发出信号，帮助我们思考或行动。复杂网络是将现实世界中的各种大规模复杂系统抽象成网络进行研究的理论工具。自然界中大量的复杂系统都可以用各种网络来描述。1.1网络的表示一个典型的网络是由很多节点和节点之间的边组成的，其中节点用来表示现实系统中不同的个体，边用来表示节点之间的关系，往往两个节点之间存在某种关系节点之间有边，否则无连接，由边连接的两个节点被认为在网络中是相邻的。为了计算方便，我们通常使用邻接矩阵来表示网络。根据网络边的类型不同，网络可分为无权无向网络、有向网络和加权网络。对应的邻接矩阵表示如下：1.2网络的统计特征度：与节点直接相连的边数；有向网络可以分为出度和入度。聚合系数：一个节点的邻居之间互为邻居的可能性，衡量网络的分组程度numberofconnectionedgesk_i(k_i-1)/2}$$我们对计算出的聚合系数进行算术平均，得到平均聚合系数，以此来衡量整个网络的聚合程度。最短路径：连接两个节点的最短连接路径介数：介数包括节点介数和边介数。节点介数是指网络中所有经过该节点的最短路径数所占的比例边介数是指网络中所有经过该边的最短路径数所占的比例介数反映了相应节点的作用和影响1.3常见的复杂网络模型常用的网络模型分为四类：规则网络、随机网络、小世界网络和无标度网络。常规网络常规网络是最简单的网络模型。在这种类型的网络中，任意两个节点之间的连接都遵循既定规则，通常每个节点都有相同数量的邻居。随机网络节点之间是否产生边是完全随机的。小世界网络小世界网络模型是由Watts和Strogatz于1998年在《自然》发表的论文《小世界网络的集体动力学》中提出的。距离和较低的聚类。现实世界中的网络既不是完全规则的，也不是完全随机的，而是介于两者之间，因此有学者引入了小世界网络模型。无标度网络无标度网络是大多数节点（小度节点）只与极少数节点相连，极少数节点与非常多节点（大度节点）相连的网络。基于复杂网络的推荐系统背景介绍链接预测是指如何通过已知的网络结构等信息预测网络中两个尚未产生连接的节点之间建立连接的可能性。预测已经存在但未被发现的连接实际上是一个数据挖掘过程，而预测未来可能的连接则与网络的演化有关。链接预测可以应用于电子商务网站。如果把电子商务网站中的商品看成一类节点，把用户看成另一类节点，如果用户A购买了商品b，那么A和b之间就形成了一条边，这条边只存在于不同类型的节点现有网络变成二分网络，二分网络中的链接预测问题实际上是一种推荐系统。下面简单介绍一篇基于复杂网络推荐系统的文章《Information Filtering via Biased Random Walk on Coupled SocialNetwork》。文章通过将用户的社交网络与用户-产品二分图网络耦合，综合用户的社交信息和产品偏好信息，向用户推荐产品。耦合社交网络（CSN）包含耦合节点（用户），它们在社交网络层形成领导者-跟随者关系，在信息网络层形成喜爱关系。下图是耦合社交网络的简单示意图，圆圈代表用户，方块代表对象。上半部分是五个用户的社交网络。$U_4$指向$U_5$，$U_4$是$U_5$的追随者。它们之间存在一定程度的相似性。下部是二分网络。对象$O_5$和用户$U_5$之间有一条边，这意味着用户$U_5$已经收藏了$O_5$。如果只有网络的下部，我们不能向用户$U_4$推荐产品$O_5$。当我们考虑到$U_4$和$U_5$在社交网络中的相似性时，我们可以将对象$O_5$推荐给用户$U_4$。接下来，我们将详细解释此方法在推荐系统中的工作原理。3.模型介绍对于一个推荐系统，我们将其分为两部分，用户集$U=\{U_1,U_2,...,U_m\}$和对象集$O=\{O_1,O_2,...。,O_n\}$,表示有$m$个用户和$n$个对象。定义邻接矩阵$A_{m*n}$表示网络，$$a_{ialpha}=begin{cases}1&userU_ihascollectedobjectsO_alpha\0&userU_ihasnotcollectedobjectsO_alphaend{cases}$$邻接矩阵$B_{m*n}$用来表示用户-对象二分图，$$b_{ij}=begin{cases}1&用户（或对象）i有喜欢的对象（或用户）j\0&otherend{cases}$$3.1Randomwalkonsocialnetwork$P_{ij}'$是社交网络上的转移概率，从用户$U_i$到用户$U_j$:$$P_{ij}'=begin{cases}frac{b_{ij}}{k_j^{out}}&ifk_j^{out}neq0\0&otherwiseend{cases}tag{1}$$$S_i'(t)$表示in的概率其他用户在时间t游荡到用户$U_i$，$$S_i'(t+1)=begin{cases}sum_{j=1}^{m}frac{b_{ij}}{k_j^{out}}&ifk_j^{out}neq0\0&otherwiseend{cases}tag{2}$$目标用户的初始概率$U_i$,$S_i'(0)=1$对于其他用户$U_j$,$S_j'(0)=1$#Walkonsocialnetwork#输入用户ID，概率prob，文中的lama，走步stepuser_id='23298'prob=1step=3#defsocial_network_walk(user_id,prob,step):user_group=trust_df.groupby(trust_df[0])#第一步走id_neighbors=list(user_group.get_group(user_id)[1].values)user_prob_dic={}foruser_idinid_neighbors:user_prob_dic[user_id]=prob/len(id_neighbors)user_dict=user_prob_dic.copy()#Walkingafterfor_inrange(step-2):foriteminuser_dict.items():uesr_id=item[0]prob=item[1]id_neighbors=list(user_group.get_group(user_id)[1].values)foruser_idinid_neighbors:try:user_prob_dic[user_id]+=prob/len(id_neighbors)exceptKeyError:user_prob_dic[user_id]=prob/len(id_neighbors)user_dict=user_prob_dic.copy()#returnuser_dictuser_dict3.2二分图上随机游走用户到产品的转移概率：$$P_{ialpha}'=begin{cases}frac{a_{ialpha}}{k_i}&ifk_ineq0\0&otherwiseend{cases}tag{3}$$商品到用户的转移概率：$$P_{alphaj}''=begin{cases}frac{a_{jalpha}}{k_{alpha}}&ifk_{alpha}neq0\0&otherwiseend{cases}tag{4}$$定义$S_{\alpha}''(t)$和$S_{j}''(t)$为产品$\alpha$和用户$tin二分图$此刻的概率：$$S_i''(t+1)=begin{cases}sum_{alpha=1}^{m}frac{a_{ialpha}}{k_{alpha}}S_{alpha}''(t)&ifk_{alpha}neq0\0&otherwiseend{cases}tag{5}$$$$S_{阿尔普ha}''(t+1)=begin{cases}sum_{j=1}^{m}frac{a_{jalpha}}{k_j}S_j''(t)&ifk_jneq0\0&otherwiseend{cases}tag{6}$$当$t$为奇数且$t\geq3$时，$S_{\alpha}''(t)$表示用户$U_i$（初始值为1)选择不喜欢的物品的概率$O_{\alpha}$#在双部网络的行走#第一步是步行，从用户到产品#defbipartite_walk(user_id,perct):user_id='23298'prob=1objection_group=ratings_df.groupby(ratings_df[0])#with用户没有依据，对对象进行分类，同一个用户收集的对象{}user_dict={}#第一步usertoobjectuser_neighbors=objection_group.get_group(user_id)[1].values#用户的邻居是user_neighbors中objection_id的一个对象:print(objection_id)objection_dict[objection_id]=prob/len(user_neighbors)##第二步objecttouser#objection_lis=objection_dict.keys()foriteminobjection_dict.items():objection_id=item[0]prob=item[1]objection_neighbors=user_group.get_group(objection_id)[0].valuesforuser_idinobjection_neighbors:try:user_dict[user_id]+=prob/len(objection_neighbors)exceptKeyError:user_dict[user_id]=prob/len(objection_neighbors)####第三步，usertoobjectforiteminuser_dict.items():user_id=item[0]prob=item[1]user_neighbor=list(objection_group.get_group(user_id)[1].values)forobj_idinuser_neighbor:try:objection_dict[obj_id]+=prob/len(user_neighbor)exceptKeyError:objection_dict[obj_id]=prob/len(user_neighbor)objection_dict3.3Biasedrandomwalkonthecoupledsocialnetwork在耦合网络中，从社交网络中的用户和二分网络中的产品到二分网络中的用户$$S_{alpha}(t+1)=begin{cases}sum_{j=1}^{m}frac{a_{jalpha}}{k_j}S_j(t)&ifk_jneq0\0&otherwiseend{cases}tag{8}$$初始概率：对于target对于用户$U_i$,$S_i''(0)=1$对于其他用户$U$和项目$\alpha$,$S_j(\alpha)=0$,$S_{\alpha}=0$when$t当$为奇数且$t\geq3$时，$S_{\alpha}''(t)$表示用户$U_i$选择未收集物品$O_{\alpha}$的概率（设targetuser'sinitial值为1单位资源，当$t=1$时，资源从目标用户传播到与目标用户相邻的对象；当$t=2$时，资源再次从对象传播到用户)#耦合网络行走，用户23298在耦合网络中随机行走，步长为三，转移概率为0.7user_id='23298'prob_social=0.7step=3prob_bi=1-prob_socialsocial_user_group=trust_df.groupby(trust_df[0])#WithTheuserhasnobasis,classifytheobject,sameusercollectstheobjectbi_objection_group=ratings_df.groupby(ratings_df[0])#基于对象，对用户进行分类，基于对象，哪些用户收集相同的对象bi_user_group=ratings_df.groupby(ratings_df[1])objection_dict={}user_dict={}#第一步用户去objectuser_neighbors=bi_objection_group.get_group(user_id)[1].values#用户的邻居是user_neighbors中objection_id的对象:objection_dict[objection_id]=prob_social/len(user_neighbors)for_inrange(int((step-1)/2)):#第二步，objecttouserforiteminobjection_dict.items():objection_id=item[0]prob=item[1]objection_neighbors=bi_user_group.get_group(objection_id)[0].valuesforuser_idinobjection_neighbors:try:user_dict[user_id]+=prob/len(objection_neighbors)exceptKeyError:user_dict[user_id]=prob/len(objection_neighbors)user_neighbors=list(social_user_group.get_group(user_id)[1].values)foruser_idinuser_neighbors:try:user_dict[user_id]+=prob_social/len(user_neighbors)除了KeyError:user_dict[user_id]=probuser_social/lenors()##第三步，usertoobjectforiteminuser_dict.items():user_id=item[0]prob=item[1]user_neighbor=list(objection_group.get_group(user_id)[1].values)forobj_idinuser_neighbor:try:objection_dict[obj_id]+=prob/len(user_neighbor)exceptKeyError:objection_dict[obj_id]=prob/len(user_neighbor)objection_dict评价指标：$Precision$accuracy，用户选择的商品在推荐中的比例list$precision^i=N_{rs}^i/L$$N_{rs}^i$：用户$U_i$推荐的产品出现在测试集中的数量，$L$：推荐列表的长度.$Recall$召回率，推荐商品在用户喜爱列表中的比例。$recall^i=N_{rs}^i/N_p^i$,$N_p^i$：用户$U_i$在测试集中收集的item个数$F-measure=\frac{2*Precision\timesRecall}{Precision+Recall}$$HD$海明距离，衡量用户推荐列表的多样性。$HD_{ij}=1-Q_{ij}(L)/L$，$Q_{ij}$是用户$i$和用户$j$的推荐列表中有相同项目的项目数。$RankingScore(r)$：衡量用户对推荐列表的满意度，$r_{i\alpha}=L_{i\alpha}/N_{i}$。$L_{i\alpha}$是用户$i$推荐列表中用户不喜欢的项目$\alpha$的位置。$N_i$是推荐列表的长度。4.结果分析4.1数据描述Epinions和Friendfeed这两个公共数据集都包含一个社会关系数据集和一个评分数据集。下表描述了数据集对应的网络。以Epinions为例，文中随机选取了一部分数据进行分析。样本数据规模为：4066个用户，7649个对象，用户与对象的连接数（收藏夹）为154122，社交网络连接数为217017。网络密度为5x10-3。表1：被测数据集的性质4.2参数$\lambda$和$t$对实验结果的影响$\lambda$是社交网络和二分图网络中资源的分配比例，$t$就是走步长，下图用sortedscore来衡量，值的颜色越冷代表效果越好。从图中可以看出，当$$t=3$$时，预测效果较好。当$\lambda=0$时，预测效果只依赖于二分图网络，随着$\lambda$的增加，逐渐考虑社交网络的信息。图1：Epinions和Friendfeed数据集（ColorOnline）上的排名得分值。对比UCF（user-basedCF）模型的效果。表2推荐列表L=20的Epinions数据集的算法性能表3推荐列表L=20的Friendfeed数据集的算法性能本项目已在mo平台实现，记得fork：https://momodel.cn/explore/5d...[](https://www.yuque.com/docs/sh...[](https://www.yuque.com/docs/sh...莫（网址：https://momodel.cn)是一个支持Python的人工智能在线建模平台，可以帮助您快速开发、训练和部署模型。Mo人工智能俱乐部由网站研发和产品设计团队发起，致力于降低人工智能的使用门槛开发使用俱乐部，团队具有大数据处理分析、可视化和数据建模经验，承担过多领域智能化项目，具备从底层到前端的全线设计开发能力，主要研究方向大数据管理分析和人工智能技术，并以此为基础推动数据驱动的科学研究，目前俱乐部每两周在杭州举办线下论文分享和学术交流活动，希望各界朋友对人工智能感兴趣可以汇聚智慧，共同交流、共同成长，促进人工智能的民主化。普及应用。
