Database Reference
In-Depth Information
8.3.3
GIM-V
anD
D
iameter
e
stimation
Estimating the diameter and radius distribution falls within the framework of itera-
tive matrix-vector computations. In [28], we presented the Hadi algorithm that
estimates the diameter and radius distribution of a large-scale graph. Hadi can be
presented within the framework of PEGASUS, since the number of neighbors reach-
able from vertex
i
within
h
hops is encoded in a probabilistic bitstring
b
i
h
, which is
updated as follows [23]:
{
}
b
h
+
1
=
b
h
BITWISE-OR
bi kE
h
|( ,)
∈
i
i
k
In
GIM-V
, the bitstring update of Hadi is represented by
b
h
+1
=
M
×
G
b
h
where
M
is the adjacency matrix,
b
h
+1
is a vector of length
n
, which is updated by
b
h
+
=
1
(
b
h
,
,
(
{
xj
|
=
1
and
n
x
=
ne2
mb
ij j
(
h
)
}
)
)
, and
assign
combineAll
combi
i
i
j
j
,
the three PEGASUS operations are defined as follows:
1.
combine2
(
m
i,j
,
v
j
) =
m
i,j
×
v
j
.
2.
combineAll
i
(
x
1
,…,
x
n
) = BITWISE-OR{
x
j
|
j
= 1…n}
3.
assign
(
v
i
,
v
new
) = BITWISE-OR(
v
i
,
v
new
).
The ×
G
operation is run iteratively until the bitstring of each vertex remains the
same.
8.3.4
GIM-V
anD
C
onneCteD
C
omPonents
We propose Hcc, a new algorithm for inding connected components in large graphs.
The main idea is as follows: for each vertex
i
in the graph, we maintain a component
identiication number (id)
c
i
h
, which is the minimum vertex id within
h
hops from
i
.
Initially,
c
i
h
of vertex
i
is set to
i
, that is,
ci
0
=
. In each iteration, each vertex sends its
current
c
i
h
to its neighbors. Then
c
i
h
+1
is set to the minimum value among its current
component id and the received component ids from its neighbors. The crucial obser-
vation is that this communication between neighbors can be formulated in
GIM-V
as follows:
i
c
h
+1
=
M
×
G
c
h
where
M
is the adjacency matrix,
c
h
+1
is a vector of length
n
, which is updated by
c
h
+
=
1
(
c
h
,
(
{
xj
|
=
1
and
n
,
x
=
ne2
mc
ij
(
,
,
h
)
}
)
)
, and
assign combineAll
combi
i
i
i
j
j
j
the three PEGASUS operations are defined as follows:
Search WWH ::
Custom Search