- 1 -
基于链接模式的社会化网络链接预测
张宗宇*
（北京邮电大学信息与通信工程学院，北京 100876）
摘要：随着互联网的发展，社会化网络已经深入人心，人们通过网络可以建立更加广泛的联
系。每个人都有扩大自己交际圈的愿望，因此，作为社会化网络分析子任务之一的链接预测
任务也就变得越来越重要。传统的链接预测模型局限于一种关系，而现实中的人与人之间的
关系是多元化的，因此，考虑到不同的关系之间的影响，本文使用链接模式对社会化网络的
链接进行预测，并使用 Tensor 来构建对象之间的多种关系。最后通过在 Enron 电子邮件数
据集上的实验，验证了该方法的正确性和有效性。
关键词： 数据挖掘；社会化网络；链接预测数据挖掘
Link Prediction in Social Network based on Link Pattern
Zhang Zongyu
(School of Information and Communication Engineering, Beijing University of Posts and
Telecommunications, Beijing 100876)
Abstract: With the development of Internet technology, social network has become more and more
popular, and it helps people make friends easier. Everyone wants to make more friends, so the link
prediction task in social network has become more and more important. Traditional link prediction
models are limited to single-type link prediction, while there are multiple relation types between people,
so this paper use link pattern to predict the link in social network, and also use Tensor figure out the
multiple relationship. The experiments on Enron email dataset shows that this method outperforms
traditional link prediction models.
Key words: Data Mining; Social Network; Link Prediction
0 引言
互联网已成为当今信息产生、传播和分享的重要途径，正是由于互联网的便捷，信息产
生和传播的成本大大下降，于是信息的数量呈几何倍数的增长，互联网每天都会出现数以亿
计的网页、邮件、博客等等，而这其中的很多数据都可以被描述为相互关联的对象的集合，
这些对象的集合便构成一个巨大的网络，网络的结点就是对象本身，而网络的边就是对象的
链接（link，或称为对象的关系）。例如最近几年非常流行的社会化网络（social network），
人就是网络中的结点，而人与人之间的联系就是链接，这其中有 Facebook，人人网等等。
有时，我们需要系统为我们提供潜在的朋友来扩大我们的交际圈，这也就产生了链接预测的
任务。Lise Getoor和 Christopher P. Diehl在[1]中说道，链接是无处不在的，这些链接通常能
够展现出数据的重要性、排名或者对象的类别。通常情况下，并不是所有的链接都是已知的，
因此，我们会关注如何预测对象之间是否存在链接关系，或者随着时间的推移，我们会预测
两个对象在未来是否会建立链接关系。此外，链接预测还可以应用到生物医学信号处理，网
络流量分析，生物化学，计算机视觉，通信网络等等。
- 2 -
1 社会化网络链接预测
1967年，哈佛大学的心理学教授 Stanley Milgram（1934~1984）创立了六度分割理论，
简单地说：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个
人你就能够认识任何一个陌生人。”按照六度分割理论，每个个体的社交圈都不断放大，最
后成为一个大型网络，这就是人们对社会化网络（Social Network）的早期理解。后来人们
根据这种理论，创立了面向社会化网络的互联网服务（Social Network Service），通过“熟人
的熟人”来进行网络社交拓展，例如 Facebook，人人，YouTube，Linkedin等等。
社会化网络的定义
社会化网络（social network），或社交网络，是由许多结点构成的一种社会结构，结点
通常是指个人或组织，社交网络代表各种社会关系，经由这些社会关系，把从偶然相识的泛
泛之交到紧密结合的家庭关系的各种人们或组织串联起来。社交网络由一个或多个特定类型
的关系维系，如价值观、理想、观念、金融交流、友谊、血缘关系、不喜欢、冲突或贸易。
由此产生的图形结构往往是非常复杂的。
社会化网络的链接预测
社会化网络的链接预测是数据挖掘领域的一个非常重要的部分，也是社会化网络分析中
的一个子任务，在社会化网络分析、信息检索、推荐系统等等都有所体现。社会化网络的链
接预测任务即预测社会化网络在未来可能存在的链接。它关心的是对象之间的关系，而传统
的数据挖掘关心的是对象本身。
链接预测的任务可以定义为：
给定对象集合 1{ }ni iV v == ，这些对象（点）以及他们之间的链接（边）构成了社会化网
络 ( , )G V E= ，其中 E 代表已观测到的边的集合，那么社会化网络链接预测的任务就是任
给两个结点 ,i jv v ，如果他们当前不存在链接，则预测他们之间存在链接的可能性有多大。
链接预测的基本方法
对于链接分析，目前应用底层方法均为计算网络拓扑图中结点 x与结点 y之间的相似程
度，我们使用 score(x,y)来表示图中<x,y>这一对结点的链接关系，并使用降序排列 score(x,y)。
因此，可以理解为计算图中任意两结点的“相似程度”，相似程度越大，拥有的共性越多，具
有链接关系的更能性也就越大。当然，这种“相似程度”可以是两结点的共同邻居的数目，也
可以是两结点可到达的路径数目等等。
基于结点邻居的算法
对于结点 x，定义 Γ(x)为 x在图 G 中拥有邻居（在图 G 中与某一结点存在一条边）的
集合。即对于无向图，|Γ(x)|的值即为 x 结点的度。当 x和 y结点的邻居集合 Γ(x)和 Γ(y)的
重复度很大时，即使 x和 y之间没有直接的边，我们也可以认为 x和 y结点很可能存在某种
关系。在实践中，可以理解为 x和 y拥有很多共同的同事，因此，他们也非常可能互相认识。
（1） 共同邻居（common neighbors）
共同邻居即根据输入的连接矩阵 M，计算出两个结点 x,y 用户的共同邻居数，即 Γ(x)
和 Γ(y)的交集的元素数，并将这个数作为 x和 y结点的相似度，公式为
( , ) | ( ) ( ) |S x y x y= Γ ∩Γ
- 3 -
（2）Jaccard系数和 Adamic/Adar[6]
Jaccard系数被广泛应用于信息检索领域，它通过计算 x和 y同时含有某一特征 f的概率
来衡量 x和 y的相似度，这里，我们使用邻居作为特征，因此衡量 x和 y相似度的公式为
| ( ) ( ) |( , )
| ( ) ( ) |
x yS x y
x y
Γ ∩Γ= Γ ∪Γ
基于路径集合的算法
在最短路径算法的基础上，通过计算两结点间全路径的集合来衡量两结点的相似度。
（1）Katz算法[7]
Katz 定义了一种将全部路径直接求和作为结点相似度的方法，通过指数衰减使得短路
径的权重更高，而长路径的权重更低，公式为
( ) ,
1
Score x, y | |x ypathsβ
∞ < >
=
= ⋅∑ A A
A
其中 ,x ypaths
< >A
表示从 x到 y的长度为 A的路径集合。
高阶方法
下面所列的方法是在基于结点邻居和基于路径算法基础上应用的算法，它们是矩阵运算
的一些通用算法，对于数据稀疏度较高以及数据量庞大的链接预测问题，这些方法有助于我
们去掉噪声、提纯数据，帮助我们得到更好的预测结果。
（1）低秩估计（Low-rank approximation）
由于可以用链接矩阵 M 表示图 G，我们可以用矩阵奇异值分解（singular value
decomposition）选择一个小的数值 k，计算出秩为 k 的矩阵 kM ，使得 kM 近似于 M，进而使
用 kM 来替代M来完成链接预测的任务。矩阵奇异值分解（singular value decomposition）的
方法是信息检索中浅层语义分析（latent semantic analysis）的核心方法。从直观上讲，使用 kM
代替M达到了降噪的效果。
矩阵奇异值分解：设 A为 m*n阶复矩阵，则存在 m阶酉阵 U和 n阶酉阵 V，使得：
A = U*S*V’
其中 S=diag(σi,σ2,……,σr)，σi>0，σi为矩阵的奇异值，(i=1,…,r)，r=rank(A)。
（2）聚类方法
我们可以先对图 G中的边进行聚类，将图 G划分为不同的子图，在每个子图中应用上
面提到的基于邻居和基于路径的算法。由于聚类划分后的子图具有一定的共同特征，因此相
当于对图 G进行了一次提纯，相信在子图中应用相似度算法时准确率会有所提升。
（3）张量（Tensor）模型
本文重点采用张量模型，在后面具体介绍。
2 基于链接模式的社会化网络链接预测
传统的链接预测模型局限于一种关系，而现实中的人与人之间的关系是多元化的，例如
某两个人之间可能是同学，可能是同事，或者可能同是某个俱乐部的会员，因此，我们考虑
不同的关系之间的影响，使用链接模式的方式来描述人与人之间的关系，把预测一种关系扩
展到多个维度，从而预测一种链接模式。
- 4 -
中国科技论文在线
链接模式的定义
传统的链接预测模型局限于一种关系，如果 A 与 B为对象，则在图模型中，他们只存
在一条边，而在链接模式中，我们使用多种关系描述 A 与 B，则在图模型中，他们之间存
在多条边，他们的边构成一个集合。
Tensor
对于对象间的单一关系，我们可以使用邻接矩阵来表达，而对于对象间的多种关系，我
们则可以对矩阵进行扩充，使用 Tensor来表达。
Tensor的定义
一个 Tensor就是一个多维数组[2]。我们将 Tensor的维度定义为 Tensor的阶（order）。
通常，我们称一维的 Tensor为向量（vector），二维的 Tensor为矩阵（Matrix），三维和三
维以上的 Tensor为高阶 Tensor。图 1显示了一个三维的 Tensor。
图 1三维 Tensor R I J KX × ×∈
Three order Tensor R I J KX × ×∈
假设存在一个三维 Tensor——X，我们可以用 ijkx 来表示它其中的一个元素。固定其中
一维，遍历其他两维所有索引值所得到的元素的集合称为片（Slice），如图 2所示，分别为
垂直方向、水平方向和前后方向的 Slice。
图 2 三维 Tensor的 Slice
Slice of three order Tensor
利用 Tensor 的维度特性，我们可以将元素的不同层次的关系用不同维度表达，同时利
用 Tensor 的近似算法将不同的维度联系起来，挖掘出不同层次之间的影响，展现元素之间
深层次的关系。
- 5 -
中国科技论文在线
Tensor因子化分解
类似于矩阵的因子化分解[3]，Tensor因子化分解可以用来对未知值进行预测。当前比较
常用的因子化分解方法包括 CANDECOMP/PARAFAC 因子化，它是由 Carroll 和 Chang 提
出的 CANDECOMP与 Harshman提出的 PARAFAC组成的，我们简称 CP因子化。
CP因子化将一个Tensor表示为一系列秩为1的Tensor的和。例如给定一个三阶的Tensor
I J KX × ×∈\ ，我们希望用公式 1来表达它。
1
R
r r r
r
X
=
≈ ∑a b cD D 其中 R为一个正整数， Ir ∈a \ ， Jr ∈b \ ， Kr ∈c \ ，r = 1,…,R。（公式 1）
对于近似后的 Tensor X中的每一个元素，有下面的公式 2。
1
R
ijk ir jr kr
r
x a b c
=
≈ ∑
i=1,…,I, j=1,…,J k=1,…,K。（公式 2）
链接预测模型
当我们得到了相关对象的潜在因子矩阵 N KU ×∈\ ， N KV ×∈\ 以及关系类型的潜在因子
T KR ×∈\ ，则两个对象间存在关系的可能性就取决于三阶 Tensor的因子化结果。在该模型中，
我们认为未观测到的数据对预测没有贡献，因此我们加入权重矩阵。
我们定义 N NW ×∈\ ， 2, [1.. ]i j N∀ ∈ ，
i
i
1 x x
, 0 x x{
j
ji j
W = 如果 和 之间的链接模式已观测到如果 和 之间的链接模式未观测到
我们预测的任务就是将权重矩阵中那些值为 0 的链接模式预测出来，我们通过 CP
Tensor因子化来找到一个 X，让它近似现在的 Y。
我们的近似采用的是交替最小平方误差法（alternating least squares）[4][5]，即 CP-ALS，
公式 3为最小平方误差法的目标函数。
2
, , ,: , ,:
1 1
( )
N N
i j i j i j
i j
L X W y x
= =
= −∑∑ （公式 3）
进而我们的问题可以表达为找到
* arg min ( )
X
X L X= ，使得
*
, , , , ,
1
K
i j t i k j k t k
k
X U V R
=
=∑ ，其中 K为 Tensor
因子的数量，也可以理解为 Tensor的秩，U,V和 R为 Tensor的潜在因子。我们相信，具有
相同特征的对象之间更容易产生链接，因此对于预测未观测到的链接的值，我们可以利用已
观测到的对象特征进行预测。
实验
实验数据
我们使用的实验数据是 Enron[6]的电子邮件数据，Enron 公司是美国能源业巨头，成立
于 1985年，总部设在德克萨斯州的休斯顿。该公司曾是世界上最大的天然气交易商和最大
的电力交易商，鼎盛时期其年收入达 1000亿美元，雇佣 2万多名员工，其业务遍布欧洲、
亚洲和世界其他地区。但是在 2002年 1月 2日，该公司宣布申请破产保护，于是联邦能源
规划委员会开始对安然公司进行财务调查。联邦能源规划委员会于 2003年 10月 14日把他
们调查分析的安然公司员工的邮件公布在网上，并说他们是根据安然公司员工的邮件来调查
公司的财务的，所以为了以示公正把它放到网上让大家都可以看到，可以研究。于是，从事
数据挖掘和社会化网络研究的人员便利用这些公开的邮件进行社会网络分析、邮件分类、数
据挖掘、文本分析等工作。
我们选择的 Enron电子邮件数据是CMU提供的 2009版本，包含 280个文件夹，共 20581
- 6 -
中国科技论文在线
个文件，每个文件均包含了发送和接收的电子邮件地址、抄送和密送的电子邮件地址、日期
和时间、主题、正文以及其他电子邮件细节。我们将数据进行预处理，选取出活跃用户 161
名，并选取以下 5种关系：
（1）邻接关系：如果两个对象间具有发送和接收关系，则他们具有该链接。
（2）共同发送关系：如果两个对象向同一个对象发送邮件，则他们具有该链接。
（3）共同接收关系：如果两个对象共同接收来自同一对象的邮件，则他们具有该链接。
（4）共同抄送关系：如果两个对象共同抄送邮件给一个相同的对象，则他们具有该链
接。
（5）职位关系：如果两个对象具有相同的职位，则他们具有该链接。
实验框架
我们将得到的每种关系的数据储存进 Tensor 的每个 slice，分别选择 20%，40%，60%
的比例将已观测到的链接值置为 0，假设 Tensor的大小为 N*N*K，其中 N为对象的数量，
K为关系的数量，则我们共拥有 N*N=M个链接模式，于是，我们分别随机将 20%M，40%M
和 60%M 个链接模式的值隐去，以作为我们的测试数据，同时将作为测试集的链接模式在
权重矩阵中标记为 0，其他则标记为 1。
在我们进行了 Tensor因子化得出估计值的结果后，我们将所有结果与真实值进行比较，
并得出该预测模型的 ROC 曲线，通过计算 AUC 值进行评价。该实验与 SVD[3]进行对比，
即使用 SVD的方法分别对 Tensor的每个 slice（即矩阵）进行因子化，得出估计结果，同时
也与真实值进行比较，并得出 ROC曲线和其 AUC值。
实验评价标准
我们使用 ROC曲线的 AUC值作为对模型性能的评价标准。ROC曲线即接受者操作特
性曲线（receiver operating characteristic curve，简称 ROC曲线），又称为感受性曲线（sensitivity
curve）。可以理解为横坐标表示假阳率，纵坐标表示真阳率。当我们得出链接的估计值后，
通过设定不同的阈值，可以得出结果的真阳率和假阳率，进而描绘出 ROC曲线，曲线与水
平坐标轴之间的面积越大，则表明模型的区分度越高，准确性也就越高。
实验结果
图 3从左至右显示了 20%，40%，60%比例的 ROC曲线。
图 3 ROC曲线
ROC Curve
表 1列出了每个 ROC曲线的 AUC值。
- 7 -
中国科技论文在线
表 1 ROC曲线的 AUC值
Tab. 1 AUC Value of ROC Curve
20% 40% 60%
CP-ALS
SVD
实验分析和讨论
从上面的数据中可以看出，基于链接模式的链接挖掘（CP-ALS）在效果上要明显好于
单独考虑每种关系（SVD）所得的预测结果。因此，这表明了考虑了多元关系之间的相互影
响会提升链接预测的性能。相反，SVD 这一组实验仅仅考虑了特定的每种关系，而忽略了
关系之间的联系和影响，因此效果并不理想。
3 结论
本文对社会化网络的链接预测任务进行深入分析，讨论并介绍了链接预测的方法。因为
人与人之间的关系是多种形式的，因此本文考虑了多种关系之间的影响，并使用链接模式对
对象间的关系进行分析，通过使用 Tensor 的因子化分解，得到了对象的特征，从而对未知
关系进行预测。通过在 Enron电子邮件数据集上的实验可以看出，考虑了多种关系的预测结
果比单纯考虑某一种关系所得的预测结果要更加准确。
[参考文献] (References)
[1] L. Getoor and C. P. Diehl, Link mining: a survey. ACM SIGKDD Explorations Newslett. Vol. 7, pp. 3-12,
2005
[2] T. G. Kolda and B. W. Bader, “Tensor decompositions and applications”, SIAM Rev., vol. 51(3), pp. 455–500,
2009.
[3] N. Srebro and T. Jaakkola, “Weighted low-rank approximations,” ICML, pp. 720–727, 2003.
[4] R. A. Harshman, “Foundations of the parafac procedure: Models and conditions for an explanatory
multi-modal factor analysis”, UCLA working papers in phonetics, pp. 1–84, 1970.
[5] [8] J. D. Carroll and J. J. Chang, “Analysis of individual differences in multidimensional scaling via an n-way
generalization of eckart-young decomposition”, Psychometrika, vol. 35, pp. 283–319, 1970.
[6]
