关系推荐作为信息推荐的一个子课题,主要关注社会网络／在线社交网络中人与人之间关系的推荐。随着社交网络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的链接预测算法应用于关系推荐系统,能够涵盖社交/社会网络的有效特征。实验证明,无论是针对科学家合作数据的关系推荐,还是针对新浪微群的关系推荐,都能获得优于传统方法的效果。