Database Reference
In-Depth Information
8
PEGASUS
A System for Large-Scale
Graph Processing
Charalampos E. Tsourakakis
CONTENTS
8.1 Introduction .................................................................................................. 256
8.2 Related Work ................................................................................................ 256
8.2.1 Structure of Real-World Networks ................................................... 257
8.2.1.1 Bow-Tie Structure of the Web Graph ................................ 257
8.2.1.2 Six Degrees of Separation.................................................. 258
8.2.2 Graph Theoretic Definitions ............................................................. 258
8.2.3 Computing Radius and Diameter ..................................................... 259
8.2.4 Distinct Elements in Multisets .......................................................... 259
8.3 Proposed Method .......................................................................................... 261
8.3.1
GIM-V
and PageRank ....................................................................... 261
8.3.2
GIM-V
and Random Walk with Restart ........................................... 261
8.3.3
GIM-V
and Diameter Estimation ...................................................... 262
8.3.4
GIM-V
and Connected Components ................................................. 262
8.4 Hadoop Implementation ............................................................................... 263
8.4.1
GIM-V
BASE: Naive Multiplication ................................................. 263
8.4.2
GIM-V
BL: Block Multiplication ...................................................... 263
8.4.3
GIM-V
CL: Clustered Edges ............................................................. 265
8.4.4
GIM-V
DI: Diagonal Block Iteration ................................................ 266
8.4.5
GIM-V
NR: Node Renumbering ....................................................... 267
8.4.6 Analysis ............................................................................................ 268
8.5 Scalability ..................................................................................................... 268
8.5.1 Results ............................................................................................... 268
8.6
PEGASUS at Work ....................................................................................... 271
8.6.1
Connected Components of Real-World Networks ............................ 272
8.6.1.1
Power Laws in Connected Components Distributions ...... 272
8.6.1.2
Absorbed Connected Components and Dunbar's Number .....274
8.6.1.3
“Anomalous” Connected Components .............................. 274
8.6.2
PageRank Scores of Real-World Networks ...................................... 274
8.6.3
Diameter of Real-World Networks ................................................... 275
255
Search WWH ::
Custom Search