桂林中学-赣南师范学院图书馆

社会网络中的链接预测问题 

链接预测  
¢  
网络中的
知的网络节点以及网络结构等信息预测网络中尚未产
链接预测(Link Prediction)问题是指通过已
生连边的两个节点之间产生链接的可能性。  
¢ 
这种预测既包含了对
links
）的预测。该问题的研究在理论 和应用两个方面都具
）的预测，也包含了对
未知链接（
未来
existed yet unknown
链接（future links
有重要的意义和价值。  
 

T
EMPORAL
L
INK
P
REDICTION


A
PPLICATIONS

¢ 
To suggest interactions or collaborations that haven’t
yet been utilized within an organization
¢ 
To monitor terrorist networks - to deduce possible
interaction between terrorists (without direct evidence)
¢ 
Used in Facebook and LinkedIn to suggest friends
¢ 
Reduce experimental costs (missing links)
Discovery of linksinteractions of biological networks costs much. Instead
of blindly checking all possible links, to predict in advance and focus on
the most likely existing links can sharply reduce costs if the predictions
are accurate enough.

M
ETHODS

FOR
L
INK
P
REDICTION

¢ 
All the methods assign a connection weight score(x,y)
to pairs of nodes x, y, based on the input graph, and
then produce a ranked list in decreasing order of
score(x, y).
— 
Can be viewed as computing a measure of proximity or
“similarity” between nodes x and y.
¢ 
Existing link prediction models can be categorized
into two large classes: unsupervised learning models
and supervised learning models.

¢ 
Unsupervised learning models compute scores for pairs
of nodes based on the link structure, and do not involve
any learning: node-similarity based methods and path
-dependent methods.
¢ 
Supervised learning models make predictions on the
unobserved relations by learning a supervised model
from the observable data.
— 
Typical supervised models include feature-based
classification methods, probabilistic graphical models, and
matrix factorization based latent factor models.

G
RAPH

DISTANCE
& C
OMMON
N
EIGHBORS

E
B
D
A
C
E
B
D
A
C
 
Graph distance: (Negated) length of
shortest path between x and y
(A, C) 2
(C, D) 2
(A, E) 3
 
Common Neighbors: A and C have
2 common neighbors, more likely to
collaborate
¢


¢

J
ACCARD
’
S

COEFFICIENT

AND
A
DAMIC
A
DAR

E
B
D
A
C
E
B
D
A
C
 
Jaccard’s coefficient: same as
common neighbors, adjusted for degree
 
Adamic Adar: weighting rarer
neighbors more heavily
— 
Neighbors who are linked with only 2 nodes are given
the weight 1log(2) = 1.4
— 
Neighbors who are linked with 5 nodes their weight
drops down to 1log(5) = 0.62
¢
¢

P
REFERENTIAL
A
TTACHMENT

¢ 
Probability that a new collaboration involves x is
proportional to T(x), current neighbors of x.
¢ 
score (x, y) :=
— 
the probability of co- authorship of x and y is correlated
with the product of the number of collaborators of x and y.

C
ONSIDERING

ALL

PATHS
: K
ATZ

¢ 
Katz: measure that sums over the
E
B
D
¢ 
collection of paths, exponentially
damped by length (to count short
paths heavily)
A very small β yields predictions much like
common neighbors, since paths of length three
or more contribute very little to the summation
A
C

H
ITTING

TIME
, P
AGE
R
ANK

¢ 
Hitting time: expected number of steps for a random
walk starting at x to reach y
¢ 
If y has a large stationary probability, H
x,y
is small. To
counter balance, we can normalize
¢ 
PageRank: to cut down on long random walks, walk can
return to x with a probability α at every step y

S
IM
R
ANK

¢ 
Defined by this recursive definition: two nodes are similar
to the extent that they are joined by similar neighbors

F
ACTOR
I
MPROVEMENT

OF

DIFFERENT

MEASURES

R
ELATIVE

PERFORMANCE

VS
. R
ANDOM
P
REDICTIONS

¢ 
AdamicAdar and common neighbors
surprisingly well, despite being simple.
perform
¢ 
The accuracies are generally low à still much to
improve.

D
IRECT ED
G
RAPHICAL
M
ODELS

¢ 
Consider both links that exist and those that do not
exist. Each potential link is associated with a binary
existence attribute Exists.
¢ 
Define a single probabilistic model over the entire
link graph.
¢ 
Train model to maximize the probability of the (object
and) link labels given the known attributes. Use
probabilistic inference to predict and classify links
using any observed attributes and other links.

基于矩阵分解的方法 
¢
¢
¢
信息时 代使得人类面临分析或处理各种大规模数据信息的要求，
如Web上的海量信息等。处理这类信息时，矩 阵是人们最常用的
数学表达方式，比如一幅图像就恰好与一个矩阵对应，矩阵中的
每个位置存放 着图像中一个像素的空间位置和色彩信息；比如社
交网络关系与邻接矩阵对应。
由于实际问题 中这样的矩阵很庞大，其中存放的信息分布往往不
均匀，因此直接处理这样的矩阵效率低下。为高效处理 这些通过
矩阵存放的数据，一个关键的必要步骤便是对矩阵进行分解操作
。通过矩阵分解，一方 面将描述问题的矩阵的维数进行降维，另
一方面也可以对大量的数据进行压缩和概括。
在科学 文献中，讨论利用矩阵分解来解决实际问题的分析方法
很多，如PCA(主成分分析)、ICA(独立成 分分析)、SVD(奇异值
分解)、VQ(矢量量化)等。
 
 
 

奇异值分解 
¢ 
奇异值分解是一个能适用于任意的矩阵的一种分解的
方法：
假设A是一个M x N的矩阵，那么得到的U是一个M x M的方阵（
其向 量是正交的，U里面的向量称为左奇异向量），Σ是一个M x
N的矩阵（除了对角线的元素都是0，对角线上的元素称为奇
异值），V’(V的转置)是一个N xN的矩阵，其向量也是正交的，V
里的向量称为右奇异向量），如下图所示：

奇异值分解 
¢
¢
¢
首先将一个矩阵A的转置 * A，会得到一个方阵，用这个方阵
求特征值可以得到：    
这里得到的v，就是前面的右奇异向量。此外还可以得到：
σ 就是奇异值，u 就是上面说的左奇异向量。奇异值σ 跟特
征值类似，在矩阵Σ中也是从大到小排列，而且σ的减少特< br>别快，在很多情况下，前10%甚至1%的奇异值的和就占了全
部的奇异值之和的99%以上。
 
 
 

¢ 
因此，可以用前r 个奇异值来近似描述矩阵，这里定义部分奇异
值分解如下：
¢ 
r 是一个远小于m、n的数，这样矩阵的分解可以表示如下：






右边的三个矩阵相乘的结果将会是一个接近于A的矩阵，r越接近
于 n，则相乘的结果越接近于A。而这三个矩阵的面积之和（存
储观点来说，矩阵面积越小，存储量就越小 ）要远远小于原始
的矩阵A，如果要压缩空间来表示原矩阵A，只需存储U、Σ
、V。

奇异值的计算 
¢
¢
奇异值的计算是一个 难题，是一个O(N^3)的算法。在单机的情
况下，matlab在一秒钟内就可以算出1000 * 1000的矩阵的所有
奇异值，但是当矩阵的规模增长的时候，计算的复杂度呈3次方
增长，就 需要并行计算。
SVD可以用并行的方式去实现的，在解大规模的矩阵的时候，
一般使用迭代 的方法，当矩阵的规模很大（比如说上亿）的
时候，迭代的次数也可能会上亿次，可以使用Map- Reduce框架
去解。
 
 

奇异值分解的一个示例 
¢ 
潜在语义索引（Latent Semantic Indexing）
每 一行表示一个词在哪些title中出现
了（一维feature），每一列表示一
个titl e中有哪些词，例如T1中有
guide、investing、market、stock
四 个词，各出现了一次。

¢ 
对这个样本矩阵进行SVD，可以得到如下的分解矩阵：
¢  
左奇异向量表示词的一些特性，右奇异向量表示文档的一些特性
，中间的奇异值矩阵表示左奇 异向量的一行与右奇异向量的一列
的重要程序，数字越大越重要。

¢ 
对这个样本矩阵进行SVD，可以得到如下的分解矩阵：
¢  
¢ 
首先，左奇异向量的第一列表示每一个词的出现频繁程度，虽然
不是线性的， 但是可以认为是一个大概的描述，比如book是0.15
对应文档中出现的2次，investing 是0.74对应了文档中出现了9次
，rich是0.36对应文档中出现了3次；
其次，右 奇异向量中的第一行表示每一篇文档中的出现词的个数
的近似，比如说，T6是0.49，出现了5个词 ，T2是0.22，出现了
2个词。

¢ 
可以将左奇异向 量和右奇异向量都取后2维（之前是3维的矩阵），
¢
投影到一个平面上，可以得到： 每一个红色的点表示一个词，每一个蓝色的点表示一篇文档，这样可以对
这些词和文档进行聚类，比 如说stock 和 market可以放在一类，real
和estate可以放在一类，dads， guide这种词就看起来有点孤立了，就不对
它们进行合并了。
 

¢
¢
按这样聚类出现的效果，可以提取文档集合中的近义词，这样当
用户检索文档 的时候，是用语义级别（近义词集合）去检索了，
而不是之前的词的级别。
这样一减少我们的 检索、存储量，二可以提高我们的用户体验，
用户输入一个词，可以在这个词的近义词的集合中去找，这 是传
统的索引无法做到的。
 
 

非负矩阵分解

¢
¢
在所有这些方法中，原始的矩阵V一般被近似分解为低秩的V=W
H形式。这些方法的共同特点是，因子W和H中的元素可为正
或负，即使输入的初始矩阵元素是全正的， 传统的秩削减算法（
或降维）也不能保证原始数据的非负性。
在数学上，从计算的观点看，分 解结果中存在负值是正确的，但
负值元素在实际问题中往往是没有意义的。例如图像数据中不可
能有负值的像素点；在文档统计中，负值也是无法解释的。因此
，探索矩阵的非负分解方法一直是很有意 义的研究问题，正是
如此，Lee和Seung两位科学家提出的非负矩阵分解(Non- negative
Matrix Factorization，NMF)算法才得到关注。
 
 

¢
¢
¢
NMF是一种新的矩阵分解算法 ，它克服了传统矩阵分解的很多
问题，通过寻找上下文有意义的解决方法，提供解释数据的更深
看法。在现实的应用中数字图像中的像素一般为非负数，文本分
析中的单词统计也总是非负数，股票价格 也总是正数等等。
NMF的基本思想可以简单描述为：对于任意给定的一个非负矩
阵V，NM F算法能够寻找到一个非负矩阵W和一个非负矩阵H，
使得满足V=WH，从而将一个非负的矩阵分解为 左右两个非负矩
阵的乘积。由于分解前后的矩阵中仅包含非负的元素，因此，原
矩阵V中的一列 向量可以解释为对左矩阵W中所有列向量(称为基
向量)的加权和，而权重系数为右矩阵H中对应行向量 中的元素。
这种基于基向量组合的表示形式具有很直观的语义解释，它反映
了人类思维中“局部 构成整体”的概念。研究指出，非负矩阵分解
是个NP问题，可以转化为优化问题用迭代方法交替求解W 和H。
 
 
 

¢ 
NMF是在所有矩阵元素非负的约束下的分解方式
，如下所示：
式中 为待分解矩阵，
和 为分解后两个矩阵。这里
表示 。
¢ 
于是分解就面临如下问题：
— 
已知 V如何同时确定W,H ？
— 
分解中 r 为数据降维的重要标志，如何选取？
¢ 

r 的选取一般是人为选定的，例如r=[10,100] ，可以根据实
际情况选取最优值。当原始数据 V为n 维，
时，降维效果才好，数据量才能降下去。

¢  
¢ 
在计算W和H时，一般求解的问题中很难得到”=”，即我们得到的
是近似 解：
其中 E是逼近误差。这样简单的一改，从理解问题的角度，可就
大大的简单化，问题可以转化为：
¢ 
以欧式距离来度量，可以写为：

计算公式
¢< br>¢
NMF算法提供了基于简单迭代的求解W，H的方法，求解方法具
有收敛速度快、左 右非负矩阵存储空间小的特点，它能将高维的
数据矩阵降维处理，适合处理大规模数据。
利用 NMF进行文本、图像大规模数据的分析方法，较传统的处理
算法速度更快、更便捷。NMF思想的提出 迅速得到了很多人的
重视，并有很多将这种思想应用到实际中成功解决具体实际问题
的例子。
 
 

¢ 
NMF得到研究人员的青睐，除了易于获得快速分 解算法之外，主
要归功于其分解结果有较为明确的物理意义。例如在人脸识别中
，分解结果为人 脸的各个局部诸如鼻子、眼睛、嘴巴等，这符合
人类思维中局部构成整体的概念。

L
INK
P
REDICTION
P
ROBLEM


R
EFERENCES

¢
¢
¢
Learning the parts of objects by non-negative matrix
factorization, Daniel D. Lee & H. Sebastian Seung,
Nature 1999
Algorithms for non-negative matrix factorization,
Daniel D. Lee & H. Sebastian Seung
Singular value decomposition and principal
component analysis, Rasmus Elsborg Madsen, Lars Kai
Hansen, Ole Winther