Database Reference
In-Depth Information
In the following sections, we show how we can customize
GIM-V
to handle
important graph mining operations including PageRank, Random Walk with Restart,
diameter estimation, and connected components.
8.3
PROPOSED METHOD
8.3.1
GIM-V
anD
P
age
r
ank
Our first warm-up application of
GIM-V
is PageRank, a famous algorithm that was
used by Google to calculate relative importance of web pages [15]. The PageRank
vector
p
of
n
web pages satisfies the following eigenvector equation:
p
= (
cE
T
+ (1 − c)
U
)
p
where
c
is a damping factor (usually set to 0.85),
E
is the row-normalized adjacency
matrix (source, destination), and
U
is a matrix with all elements set to 1/
n
.
To calculate the eigenvector
p
we can use the power method, which multiplies an
initial vector with the matrix, several times. We initialize the current PageRank vector
p
cur
and set all its elements to 1/
n
. Then the next PageRank
p
next
is calculated by
p
next
=
(
cE
T
+ (1 −
c
)
U
)
p
cur
. We continue to perform the multiplication until
p
converges.
PageRank is a direct application of
GIM-V
, that is,
p
next
= M ×
G
p
cur
. Matrix
M
is
E
T
, that is, the column-normalized version of the adjacency matrix. The three opera-
tions are defined as follows:
1.
combine2
(
m
i,j
,
v
j
) = c ×
m
i,j
×
v
j
)
(
1
−
c
)
∑
n
2.
combineAlli(
i
(, ,
x
=
x
+
x
1
n
j
n
j
=
1
3.
assign
(
v
i
, v
new
) =
v
new
8.3.2
GIM-V
anD
r
anDom
w
alk
with
r
estart
Random Walk with Restart (RWR) is closely related to Personalized PageRank [43],
a popular algorithm to measure the relative proximity of vertices with respect to a
given vertex. In RWR, the proximity vector
r
k
of vertex
k
satisfies the equation:
r
k
=
cMr
k
+ (1 −
c
)
e
k
where
e
k
is the
k
th unit vector in
n
,
c
is a restart probability parameter, which is
typically set to 0.85 [43], and
M
is as in Section 8.3.1. In
GIM-V
, RWR is formulated
by
r
next
cur
=×
where the three operations are defined as follows:
Mr
k
Gk
1.
combine2
(
m
i,j
,
v
j
) =
c
×
m
i,j
×
v
j
∑
n
2.
combineAlli(
i
(, ,) (
x
=− +
x
1
c
)
δ
x
, where δ
ik
is the
Kronecker
1
ik
j
j
=
1
delta
, equal to 1 if
i
=
k
and 0 otherwise
3.
assign
(
v
i
,
v
new
) =
v
new
Search WWH ::
Custom Search