Graph algorithms in the language of linear algebra

Cover......Page 1
S Title......Page 2
Editorial Board......Page 3
Title: Graph Algorithms in theLanguage of Linear Algebra......Page 4
ISBN 978-0-898719-90-1......Page 5
Dedication......Page 6
List of Contributors......Page 7
Contents......Page 8
List of Figures......Page 16
List of Tables......Page 20
List of Algorithms......Page 21
Preface......Page 23
Acknowledgments......Page 25
1.1 Motivation......Page 26
1.2.1 Graph adjacency matrix duality......Page 27
1.2.2 Graph algorithms as semirings......Page 28
1.3.1 Simulating power law graphs......Page 29
1.4.1 Graph analysis metrics......Page 30
1.4.2 Sparse matrix storage......Page 31
1.4.4 Parallel programming......Page 32
1.4.5 Parallel matrix multiply performance......Page 33
References......Page 35
2.1 Graph notation......Page 36
2.3.1 Semirings and related structures......Page 37
2.3.3 Vector operations......Page 38
2.4.1 Sparse......Page 39
Cyclic distribution......Page 40
3.1 Introduction......Page 42
3.2 Strongly connected components......Page 43
3.2.1 Nondirected links......Page 44
3.2.2 Computing C quickly......Page 45
3.3 Dynamic programming, minimum paths, and matrix exponentiation......Page 46
3.3.1 Matrix powers......Page 48
3.4 Summary......Page 49
References......Page 50
4.1 Motivation......Page 51
4.2 Sparse matrices and graphs......Page 52
4.2.1 Sparse matrix multiplication......Page 53
4.3.1 Breadth-first search......Page 54
4.3.2 Strongly connected components......Page 55
4.3.3 Connected components......Page 56
4.3.5 Graph contraction......Page 57
4.3.6 Graph partitioning......Page 59
4.4.3 Regular geometric grids......Page 61
References......Page 63
5.1 Shortest paths......Page 66
5.1.1 Bellman–Ford......Page 67
Algebraic Bellman–Ford......Page 68
5.1.2 Computing the shortest path tree (for Bellman–Ford)......Page 69
Computing parent pointers with 3-tuples......Page 70
Computing parent pointers at the end......Page 73
5.1.3 Floyd–Warshall......Page 74
Algebraic Floyd–Warshall......Page 75
5.2.1 Prim’s......Page 76
Computing the tree......Page 78
References......Page 79
6.1.1 Peer pressure clustering......Page 80
Preserving small clusters and unclustered vertices......Page 83
Sample calculation......Page 84
Time complexity......Page 85
Assuring vertices have equal votes......Page 87
6.1.3 Other approaches......Page 88
6.2.1 History......Page 89
Sample calculation......Page 90
Linear algebraic formulation......Page 94
Time complexity......Page 95
6.2.3 Batch algorithm......Page 96
Space complexity......Page 97
Sample calculation......Page 99
Time complexity......Page 102
6.3.2 Block algorithm......Page 104
References......Page 105
Abstract......Page 106
7.1 Introduction......Page 107
7.2.1 Notation......Page 108
7.2.3 Tensor preliminaries......Page 109
7.2.5 CP-ALS algorithm......Page 110
7.3.1 Data as a tensor......Page 112
7.4 Numerical results......Page 114
7.4.1 Community identification......Page 115
7.4.2 Latent document similarity......Page 116
7.4.3 Analyzing a body of work via centroids......Page 118
7.4.4 Author disambiguation......Page 119
7.4.5 Journal prediction via ensembles of tree classifiers......Page 124
7.5.1 Analysis of publication data......Page 127
7.5.2 Higher order analysis in data mining......Page 128
7.6 Conclusions and future work......Page 129
References......Page 131
8.1 Graph model......Page 136
8.1.1 Vertex/edge schema......Page 137
8.2.1 Path moments......Page 139
Expected paths......Page 140
8.4.1 Background: Power law......Page 141
8.4.3 Detection problem......Page 142
8.4.4 Degree distribution......Page 144
8.5 SNR, PD, and PFA......Page 145
8.5.2 Second neighbors......Page 146
8.5.4 First neighbor leaves......Page 147
8.5.5 First neighbor branches......Page 148
8.5.6 SNR hierarchy......Page 149
8.6.2 Eliminate high degree nodes......Page 150
8.6.4 Find high probability nodes......Page 151
8.6.5 Find high degree nodes......Page 152
8.7 Results and conclusions......Page 153
References......Page 154
Abstract......Page 155
9.1 Introduction......Page 156
9.2.1 Graph patterns......Page 158
9.2.3 Parameter estimation of network models......Page 160
9.3.1 Main idea......Page 161
Degree distribution......Page 165
Spectral properties......Page 166
Connectivity of Kronecker graphs......Page 167
Temporal properties of Kronecker graphs......Page 168
9.3.3 Stochastic Kronecker graphs......Page 170
9.3.4 Additional properties of Kronecker graphs......Page 172
9.3.5 Two interpretations of Kronecker graphs......Page 173
9.3.6 Fast generation of stochastic Kronecker graphs......Page 175
9.3.7 Observations and connections......Page 176
9.4.1 Comparison to real graphs......Page 177
9.4.2 Parameter space of Kronecker graphs......Page 179
9.5 Kronecker graph model estimation......Page 181
9.5.1 Preliminaries......Page 183
9.5.2 Problem formulation......Page 184
Sampling permutations......Page 187
Speeding up the likelihood ratio calculation......Page 189
9.5.4 Efficiently approximating likelihood and gradient......Page 190
9.5.6 Determining the size of an initiator matrix......Page 191
Convergence of the log-likelihood and the gradient......Page 192
Different proposal distributions......Page 194
Properties of the permutation space......Page 196
9.6.2 Properties of the optimization space......Page 198
9.6.4 Fitting to real-world networks......Page 199
Fitting to autonomous systems network......Page 200
Choice of the initiator matrix size N......Page 202
Network parameters over time......Page 204
9.6.5 Fitting to other large real-world networks......Page 205
9.6.6 Scalability......Page 208
9.7 Discussion......Page 211
9.8 Conclusion......Page 213
Appendix: Table of networks......Page 214
References......Page 215
10.1 Introduction......Page 223
10.2 Overview of results......Page 224
10.3.1 Explicit adjacency matrix......Page 226
10.3.2 Stochastic adjacency matrix......Page 227
10.4 A simple bipartite model of Kronecker graphs......Page 229
10.4.1 Bipartite product......Page 230
10.4.2 Bipartite Kronecker exponents......Page 231
10.4.3 Degree distribution......Page 233
10.4.4 Betweenness centrality......Page 234
10.4.5 Graph diameter and eigenvalues......Page 236
10.4.6 Iso-parametric ratio......Page 237
10.5.2 Permutations......Page 238
10.5.5 Recursive bipartite permutation......Page 239
10.5.6 Bipartite index tree......Page 242
10.6 A more general model of Kronecker graphs......Page 243
10.6.1 Sparsity analysis......Page 244
10.6.2 Second order terms......Page 245
10.6.3 Higher order terms......Page 248
10.6.5 Graph diameter and eigenvalues......Page 249
10.6.6 Iso-parametric ratio......Page 251
10.7.1 Relation between explicit and instance graphs......Page 252
10.7.2 Clustering power law graphs......Page 255
10.8 Conclusions and future work......Page 256
References......Page 257
11.1 Introduction......Page 259
11.2 Kronecker graph model......Page 260
11.4.1 Graph metrics......Page 261
11.4.3 Organic growth simulation......Page 263
11.5 Visualizing Kronecker graphs in 3D......Page 264
11.5.2 Visualizing Kronecker graphs on parallel system......Page 265
References......Page 268
Abstract......Page 269
12.1 Introduction......Page 270
12.2 Centrality metrics......Page 271
Closeness centrality......Page 272
Betweenness centrality......Page 273
12.3 Parallel centrality algorithms......Page 274
Closeness centrality......Page 275
Stress and betweenness centrality......Page 276
12.3.1 Optimizations for real-world graphs......Page 278
12.4.1 Experimental setup......Page 280
Network data......Page 281
12.4.2 Performance results......Page 282
12.5 Case study: Betweenness applied to protein-interaction networks......Page 284
12.6 Integer torus: Betweenness conjecture......Page 288
12.6.1 Proof of conjecture when n is odd......Page 290
12.6.2 Proof of conjecture when n is even......Page 292
References......Page 296
13.1 Introduction......Page 302
13.2 Key primitives......Page 306
13.3 Triples......Page 308
13.3.1 Unordered triples......Page 309
Indexing and SpMV with row ordered triples......Page 313
The sparse accumulator......Page 314
SpAdd and SpGEMM with row ordered triples......Page 315
13.3.3 Row-major ordered triples......Page 317
13.4.1 CSR and adjacency lists......Page 320
13.4.2 CSR on key primitives......Page 321
13.5.1 Sparse matrices in Star-P......Page 323
Sparse matrix-dense vector multiplication (SpMV)......Page 324
References......Page 325
14.1 Introduction......Page 329
14.2 Sequential sparse matrix multiply......Page 331
14.2.1 Layered graphs for different formulations of SpGEMM......Page 332
14.2.2 Hypersparse matrices......Page 334
14.2.3 DCSC data structure......Page 335
14.2.4 A sequential algorithm to multiply hypersparse matrices......Page 336
14.3.2 2D decomposition......Page 340
14.3.4 Sparse Cannon......Page 341
14.4 Analysis of parallel algorithms......Page 342
14.4.1 Scalability of the 1D algorithm......Page 343
14.4.2 Scalability of the 2D algorithms......Page 344
14.5 Performance modeling of parallel algorithms......Page 345
References......Page 348
15.1 Introduction......Page 352
15.2 Lincoln Laboratory mapping and optimization environment......Page 353
15.2.1 LLMOE overview......Page 354
15.2.2 Mapping in LLMOE......Page 356
Co-optimization of mapping and routing......Page 357
Outer GA......Page 358
Search space......Page 359
Machine model......Page 360
Sparsity patterns......Page 362
Results......Page 363
References......Page 365
Abstract......Page 366
16.2 Time evolution......Page 367
16.4 Algorithm scaling......Page 368
16.5 Computer architecture......Page 369
Index......Page 371