vi MANAGING AND MINING GRAPH DATA
2.1 Power Laws and Heavy-Tailed Distributions 72
2.2 Small Diameters 77
2.3 Other Static Graph Patterns 79
2.4 Patterns in Evolving Graphs 82
2.5 The Structure of Specific Graphs 84
3. Graph Generators 86
3.1 Random Graph Models 88
3.2 Preferential Attachment and Variants 92
3.3 Optimization-based generators 101
3.4 Tensor-based 108
3.5 Generators for specific graphs 113
3.6 Graph Generators: A summary 115
4. Conclusions 115
References 117
4
Query Language and Access Methods for Graph Databases
125
Huahai He and Ambuj K. Singh
1. Introduction 126
1.1 Graphs-at-a-time Queries 126
1.2 Graph Specific Optimizations 127
1.3 GraphQL 128
2. Operations on Graph Structures 129
2.1 Concatenation 130
2.2 Disjunction 131
2.3 Repetition 131
3. Graph Query Language 132
3.1 Data Model 132
3.2 Graph Patterns 133
3.3 Graph Algebra 134
3.4 FLWR Expressions 137
3.5 Expressive Power 138
4. Implementation of the Selection Operator 140
4.1 Graph Pattern Matching 140
4.2 Local Pruning and Retrieval of Feasible Mates 142
4.3 Joint Reduction of Search Space 144
4.4 Optimization of Search Order 146
5. Experimental Study 148
5.1 Biological Network 148
5.2 Synthetic Graphs 150
6. Related Work 152
6.1 Graph Query Languages 152
6.2 Graph Indexing 155
7. Future Research Directions 155
8. Conclusion 156
Appendix: Query Syntax of GraphQL 156
References 157
5
Graph Indexing
161
Xifeng Yan and Jiawei Han
1. Introduction 161
