PEGASUS - Large Scale and Big Data: Processing and Management - page 266

6

1 2 3 4 9 0 1 2

5

7 8

1−4 5−8 9−12

1−4

B 0,0 B 0,1 B 0,2

5−8

B 1,0 B 1,1 B 1,2

9−12

B 2,0 B 2,1 B 2,2

(a) Example of graph and block adjacency matrix

1
2
3
4
5
6
7
8
9
10
11
12

1
1
2
3
4
5
5
5
5
9
10
11

1
1
1
2
3
4
4
4
4
5
9
10

1
1
1
1
2
3
3
3
3
4
5
9

1
1
1
1
1
2
2
2
2
3
4
5

1
1
1
1
1
1
1
1
1
2
3
4

1
1
1
1
1
1
1
1
1
1
2
3

1
1
1
1
1
1
1
1
1
1
1
2

1
1
1
1
1
1
1
1
1
1
1
1

1
2
3
4
5
6
7
8
9
10
11
12

1
1
1
1
4
5
5
5
5
9
9
9

1
1
1
1
1
4
4
4
4
5
5
5

1
1
1
1
1
1
1
1
1
4
4
4

1
1
1
1
1
1
1
1
1
1
1
1

V 0

V 1

V 2

(b) Component vector in GIM-V BL (c) Component

vector in GIM-V DI

FIGURE 8.4 Propagation of component id(=1) when block width is 4. Each element in
the adjacency matrix of (a) represents a 4 × 4 block; each column in (b) and (c) represents
the vector after each iteration. GIM-V DL finishes in 4 iterations while GIM-V BL requires
8 iterations.

8.4.5 GIM-V nr: n oDe r enumbering
In HCC, the minimum vertex id is propagated to the other parts of the graph
within at most d steps, where d is the diameter of the graph. If the vertex with
the minimum id (which we call “minimum node”) is located at the center of the
graph, then the number of iterations is small, close to d /2. However, if it is located
at the boundary of the network, then the number of iterations can be close to d .
Therefore, if we preprocess the edges so that the minimum vertex id is swapped
to the center vertex id, the number of iterations and the total running time of HCC
would decrease.
Finding the center vertex with the minimum radius could be done with the Hadi
algorithm. However, the algorithm is expensive for the preprocessing step of HCC.