【作者】 吴铭；

【导师】 郭军；

【作者基本信息】 北京邮电大学 ， 信号与信息处理， 2012， 博士

【摘要】 关系推荐作为信息推荐的一个子课题,主要关注社会网络／在线社交网络中人与人之间关系的推荐。随着社交网络facebook,twitter以及微博等的兴起与繁荣,人与人之间的关系推荐广泛应用,此项研究已经发展成为一个相对独立的研究方向。链接预测是图数据挖掘中的一个重要问题,且已得到泛研究。这种方法是通过已知的网络结构等信息预测和估计尚未链接的两个节点存在链接的可能性。社会网络是一种特定类型的复杂网络,具有复杂网络的共性,可用图来表达。本文基于图数据挖掘中链接预测的基本思想,通过计算尚未建立链接的两个人发生链接的概率,实现社会网络中人与人之间的关系推荐。为了能够获得更精确的关系推荐,本文对传统的链接预测方法进行扩展,验证了一种同时考虑网络结构信息和节点属性信息的数学模型——指数随机图模型ERGM/P*(Exponential Random Graph Models,ERGM)在关系推荐中的应用。首先通过ERGM/P*对网络建模,在完成ERGM参数估计之后,再利用估计的参数进行链接预测,进而实现关系推荐。基于上述框架,本文主要进行了如下研究：(1)将ERGM模型引入链接预测。ERGM参数估计中采用的是基于MCMC的最大似然估计,而MCMC本质上就是按照转移概率进行状态转移并采样的过程。如果状态转移的当前网络就是观察网络,那么增加某条链接的条件概率,恰恰就是当前网络增加该链接的转移概率。根据这一原理,本文估计最佳参数η后,结合ERGM模型中转移概率的计算方法,计算基于观察网络的所有节点间建立链接的条件概率,而最终基于条件概率的排序做关系推荐。(2)通过对比试验,证明了基于ERGM的关系推荐算法的优越性。由于ERGM模型不仅涵盖了网络的整体结构特性,还可以包括节点的属性信息,所以从理论上讲,合理的ERGM模型+参数,能够做出更为准确的链接预测。本文也进一步通过对科学家合作数据和新浪微群数据做关系推荐,从实验的角度验证了ERGM与基于节点相似性、基于路径拓扑相似性以及基于概率模型等方法相比,能够实现更准确的关系推荐。(3)提出了ERGM网络参量和参数的平行迁移特性。ERGM是一种理论上能够包含无数个网络参量(包括节点属性信息和网络结构信息)的模型。本文在考虑常用网络参量的基础上,进一步研究将新的高阶网络参量,如gwesp,gwdsp等,应用到ERGM的方法中,并根据不同类型的社会/社交网络从理论上和实验上选取适用的网络参量。本文以科学家合作数据和新浪微博关系数据作为研究对象,分析了使用不同网络结构参量的效果。实验还证明,可以使用同样的网络参量对同类型的社会/社交网络进行ERGM建模,并可以将一个观测网络估计出来的最佳参数用于同类型的其它观测网络。将此特性称之为模型网络参量和参数的平行迁移。ERGM的参数估计和分析本身运算量非常大,正是有了这种平行迁移的特性,才使得基于ERGM的关系推荐算法的实用成为可能。(4)指出ERGM网络建模具有时效性,并给出时效性曲线。ERGM的方法对网络建模的过程,就是输入一个观测网络,输出网络参量和参数的过程。对于社会/社交网络这样一个动态发展网络的建模会有多长的时效性呢?针对这个问题,本文对科学家合作数据进行实验,分别生成人为去掉一条边、两条边至二十条边的缺失观测网络,测试观测网络分别预测一条边、两条边至二十条边的效果。从结果发现,当需要预测的边越多,准确率会有所下降。这为基于ERGM的链路预测方法的应用场景,提供了参考。(5)本文在ERGM理论研究和相关实验的基础上,基于新浪微博数据进行了实用关系推荐系统的研究。该部分的工作分为两部分,一是针对新浪微群这样相对封闭的小群体,建立系推荐系统；二是立足新浪微博全网,在社区划分的基础上,做社区内的关系推荐。基于ERGM的链接预测算法应用于关系推荐系统,能够涵盖社交/社会网络的有效特征。实验证明,无论是针对科学家合作数据的关系推荐,还是针对新浪微群的关系推荐,都能获得优于传统方法的效果。更多还原

【Abstract】 Relationship recommendation is a sub-research field of information recommendation, especially focus on person to person recommendation of social networks. With the development of Facebook, Twitter, Sina weibo, Renren, the relationship between people in the social network is the most important feature for these online platforms. How to recommend the fit people to the others based on the converged different research field is the new challenged direction for all researchers.Link prediction, which is to predict and estimate the unknown or missing link through the node information or network structure, is the most important problem for graph mining. Social network is a specific kind of complex network, but there are many different attributes of social network, such as social behavior or some social characters. The main contribution of this paper is to setup the framework of person to person recommendation based on the graph model, which is always to be used to describe the whole networks. The node social attributes such as gender, personal historical relationship, personal actions are included for the link prediction, as well as the whole social network structure. All the link prediction are developed based on the ERGM/P*(Exponential Random Graph Models, ERGM) models, which is to model and estimate the coefficients of the whole real network, and then use the estimated coefficients and configurations to predict links and recommend the relationships.The main research work and contributions of the paper are listed as followed:(1) The link perdition method based ERGM were introduced to the person to person recommendation system. The ERGM method was usually to describe the network structure. We found the maximum likelihood estimation algorithm based on MCMC sample used to estimate ERGM coefficients was essentially to generate the Markov chain according to transition probability. After estimating the best coefficients η, we can use it to get the link probability rank of the unconnected nodes in the whole network. The recommendation of different people was based on the link probability rank.(2) The great advantage of ERGM for link prediction is not only the whole network description, but also the node attributes included. Compared with the other link prediction method, such as local information method, topology method etc, the ERGM method can give more accuracy result. We collect the real scientist collaboration network data and design the experiment to prove this method is more feasible not only on the theory, but also on the practices. The reasonable configurations of network and the optimal coefficients in ERGM are most important for precise result.(3) There are lots of configurations in the ERGM theoretical framework. The other innovation of our work is to test some new configurations according to the different network, such as gwesp\gwdsp, which are high order structure configurations to describe the details of network. The comparison experiments were carried out based on the scientist collaboration network and the small clique of WEIBO. It proved that we can use the same parameters to simulate the same property social networks; this was called paralleled transition of parameters for different network. The big trouble of ERGM put into the practice is the computation complexity. We can use to the paralleled transition to resolve this problem.(4) The ERGM method is based on the input observed network to get the configurations and coefficients. Because the real social networks are always dynamic, the configurations and coefficients based on observed network can not predict all of the future. We design the experiments to test and resolve this problem. We called this missing link prediction, which is to delete one link of the current networks each time (the test missing link included two and twenty links), and then calculate the accuracy rate of predicting the missing links. As a result, with the increase of missing link, the accuracy of the prediction was dropping down. This will give the significent reference to the application of ERGM in the dynamic network.(5) After the theoretical and experimental research, we use the ERGM link prediction approach to person to person recommendation on Sina WEIBO platform. We fetched the real WEIBO data to test the efficiency of this method. We first used the closed community data to do the recommendation in the small clique. And then we used the ERGM method to predict the potential links in the whole network, but the segmentation of community should be done firstly.The recommendation system based on ERGM link prediction approach can use any attribute of network and nodes to predict links. The research work proved that it is more efficiency than other trational prediction methods.更多还原