Graphs and Networks

ISBN-13: 9781118937181 / Angielski / Twarda / 2022 / 288 str.

Sandra Kingan

Opis

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.

Spis treści

List of Figures ivPreface viiiChapter 1. From Königsberg to Connectomes 11.1. Introduction 11.2. Isomorphism 181.3. Minors and Constructions 25Chapter 2. Fundamental Topics 392.1. Trees 392.2. Distance 442.3. Degree Sequences 522.4. Matrices 56Chapter 3. Similarity and Centrality 703.1. Similarity Measures 703.2. Centrality Measures 743.3. Eigenvector and Katz Centrality 783.4. PageRank 84Chapter 4. Types of Networks 914.1. Small-World Networks 914.2. Scale-Free Networks 954.3. Assortative Mixing 974.4. Covert Networks 102Chapter 5. Graph Algorithms 1075.1. Traversal Algorithms 1075.2. Greedy Algorithms 1135.3. Shortest Path Algorithms 118Chapter 6. Structure, Coloring, Higher Connectivity 1266.1. Eulerian Circuits 1266.2. Hamiltonian Cycles 1316.3. Coloring 1366.4. Higher Connectivity 1426.5. Menger's Theorem 148Chapter 7. Planar Graphs 1597.1. Properties of Planar Graphs 1597.2. Euclid's Theorem on Regular Polyhedra 1677.3. The Five Color Theorem 1727.4. Invariants for Non-Planar Graphs 174Chapter 8. Flows and Matchings 1828.1. Flows in Networks 1828.2. Stable Sets, Matchings, Coverings 1888.3. Min-Max Theorems 1928.4. Maximum Matching Algorithm 196Appendix A. Linear Algebra 211Appendix B. Probability and Statistics 215Appendix C. Complexity of Algorithms 218Appendix D. Stacks and Queues 222Appendix. Bibliography 226

O autorze

S. R. Kingan is an Associate Professor of Mathematics at Brooklyn College and the Graduate Center of The City University of New York. Dr. Kingan's research interests include graph theory, matroid theory, combinatorial algorithms, and their applications.