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