Graphs and Networks
1st Edition
Published on 27. July 2021
Book
Hardback
256 pages
978-1-118-93718-1 (ISBN)
Description
Network science is applied graph theory, and this book successfully blends essential graph theory topics with practical and relevant network science to illustrate the underlying mathematics. Mathematicians have been relegated to small-time players in a field populated with sociologists, computer scientists, and physicists. On the other hand, graph theory books are written like reference manuals jam-packed with theorems for graph theorists, leading instructors of graph theory courses to tease out their lectures from a plethora of results. This book's combination of theory and modern applications is needed by both practitioners of data science and students of graph theory seeking to learn modern applications. For example, one difference between this book and existing network science books is that network scientists title their chapters based on individual large graphs such as epidemic graphs or web graphs and study all its properties. However, large graphs have a lot of features in common so this book distills those common elements, presents the concepts behind the large graphs, and presents particular large graphs as examples of the underlying mathematics. With a focus on topics most relevant to network science, such as graph structural theory, link analysis, and spectral graph theory, this book contains a host of untapped results for network scientists. In addition, the book is supplemented with a related website and an Instructor's Manual. Topical coverage includes: basic definitions; isomorphism; graph substructures; graph operations; graph statistics; tress; degree sequences; Eulerian circuits; Hamiltonian cycles; planar graphs; colorings; matchings and coverings; graph algorithms; network algorithms; random graphs; spectral graph theory; centrality measures; network flows; network reliability; extremal graph theory; higher connectivity; excluded minors; Tutte's wheels theorem; splitter theorem; and k-sums and decomposition.
More details
Other editions
Additional editions
Content
List of Figures iv
Preface viii
Chapter 1. From Königsberg to Connectomes 1
1.1. Introduction 1
1.2. Isomorphism 18
1.3. Minors and Constructions 25
Chapter 2. Fundamental Topics 39
2.1. Trees 39
2.2. Distance 44
2.3. Degree Sequences 52
2.4. Matrices 56
Chapter 3. Similarity and Centrality 70
3.1. Similarity Measures 70
3.2. Centrality Measures 74
3.3. Eigenvector and Katz Centrality 78
3.4. PageRank 84
Chapter 4. Types of Networks 91
4.1. Small-World Networks 91
4.2. Scale-Free Networks 95
4.3. Assortative Mixing 97
4.4. Covert Networks 102
Chapter 5. Graph Algorithms 107
5.1. Traversal Algorithms 107
5.2. Greedy Algorithms 113
5.3. Shortest Path Algorithms 118
Chapter 6. Structure, Coloring, Higher Connectivity 126
6.1. Eulerian Circuits 126
6.2. Hamiltonian Cycles 131
6.3. Coloring 136
6.4. Higher Connectivity 142
6.5. Menger's Theorem 148
Chapter 7. Planar Graphs 159
7.1. Properties of Planar Graphs 159
7.2. Euclid's Theorem on Regular Polyhedra 167
7.3. The Five Color Theorem 172
7.4. Invariants for Non-Planar Graphs 174
Chapter 8. Flows and Matchings 182
8.1. Flows in Networks 182
8.2. Stable Sets, Matchings, Coverings 188
8.3. Min-Max Theorems 192
8.4. Maximum Matching Algorithm 196
Appendix A. Linear Algebra 211
Appendix B. Probability and Statistics 215
Appendix C. Complexity of Algorithms 218
Appendix D. Stacks and Queues 222
Appendix. Bibliography 226