Graphs and Matrices


Book Description

This new edition illustrates the power of linear algebra in the study of graphs. The emphasis on matrix techniques is greater than in other texts on algebraic graph theory. Important matrices associated with graphs (for example, incidence, adjacency and Laplacian matrices) are treated in detail. Presenting a useful overview of selected topics in algebraic graph theory, early chapters of the text focus on regular graphs, algebraic connectivity, the distance matrix of a tree, and its generalized version for arbitrary graphs, known as the resistance matrix. Coverage of later topics include Laplacian eigenvalues of threshold graphs, the positive definite completion problem and matrix games based on a graph. Such an extensive coverage of the subject area provides a welcome prompt for further exploration. The inclusion of exercises enables practical learning throughout the book. In the new edition, a new chapter is added on the line graph of a tree, while some results in Chapter 6 on Perron-Frobenius theory are reorganized. Whilst this book will be invaluable to students and researchers in graph theory and combinatorial matrix theory, it will also benefit readers in the sciences and engineering.




Applications of Combinatorial Matrix Theory to Laplacian Matrices of Graphs


Book Description

On the surface, matrix theory and graph theory seem like very different branches of mathematics. However, adjacency, Laplacian, and incidence matrices are commonly used to represent graphs, and many properties of matrices can give us useful information about the structure of graphs.Applications of Combinatorial Matrix Theory to Laplacian Matrices o




Graph Theory and Sparse Matrix Computation


Book Description

When reality is modeled by computation, matrices are often the connection between the continuous physical world and the finite algorithmic one. Usually, the more detailed the model, the bigger the matrix, the better the answer, however, efficiency demands that every possible advantage be exploited. The articles in this volume are based on recent research on sparse matrix computations. This volume looks at graph theory as it connects to linear algebra, parallel computing, data structures, geometry, and both numerical and discrete algorithms. The articles are grouped into three general categories: graph models of symmetric matrices and factorizations, graph models of algorithms on nonsymmetric matrices, and parallel sparse matrix algorithms. This book will be a resource for the researcher or advanced student of either graphs or sparse matrices; it will be useful to mathematicians, numerical analysts and theoretical computer scientists alike.




Graph Algorithms in the Language of Linear Algebra


Book Description

The current exponential growth in graph data has forced a shift to parallel computing for executing graph algorithms. Implementing parallel graph algorithms and achieving good parallel performance have proven difficult. This book addresses these challenges by exploiting the well-known duality between a canonical representation of graphs as abstract collections of vertices and edges and a sparse adjacency matrix representation. This linear algebraic approach is widely accessible to scientists and engineers who may not be formally trained in computer science. The authors show how to leverage existing parallel matrix computation techniques and the large amount of software infrastructure that exists for these computations to implement efficient and scalable parallel graph algorithms. The benefits of this approach are reduced algorithmic complexity, ease of implementation, and improved performance.




Graph Representation Learning


Book Description

Graph-structured data is ubiquitous throughout the natural and social sciences, from telecommunication networks to quantum chemistry. Building relational inductive biases into deep learning architectures is crucial for creating systems that can learn, reason, and generalize from this kind of data. Recent years have seen a surge in research on graph representation learning, including techniques for deep graph embeddings, generalizations of convolutional neural networks to graph-structured data, and neural message-passing approaches inspired by belief propagation. These advances in graph representation learning have led to new state-of-the-art results in numerous domains, including chemical synthesis, 3D vision, recommender systems, question answering, and social network analysis. This book provides a synthesis and overview of graph representation learning. It begins with a discussion of the goals of graph representation learning as well as key methodological foundations in graph theory and network analysis. Following this, the book introduces and reviews methods for learning node embeddings, including random-walk-based methods and applications to knowledge graphs. It then provides a technical synthesis and introduction to the highly successful graph neural network (GNN) formalism, which has become a dominant and fast-growing paradigm for deep learning with graph data. The book concludes with a synthesis of recent advancements in deep generative models for graphs—a nascent but quickly growing subset of graph representation learning.




Erdös on Graphs


Book Description

This book is a tribute to Paul Erdos, the wandering mathematician once described as the "prince of problem solvers and the absolute monarch of problem posers." It examines the legacy of open problems he left to the world after his death in 1996.




Algebraic Graph Theory


Book Description

Graph models are extremely useful for almost all applications and applicators as they play an important role as structuring tools. They allow to model net structures – like roads, computers, telephones – instances of abstract data structures – like lists, stacks, trees – and functional or object oriented programming. In turn, graphs are models for mathematical objects, like categories and functors. This highly self-contained book about algebraic graph theory is written with a view to keep the lively and unconventional atmosphere of a spoken text to communicate the enthusiasm the author feels about this subject. The focus is on homomorphisms and endomorphisms, matrices and eigenvalues. It ends with a challenging chapter on the topological question of embeddability of Cayley graphs on surfaces.




Algorithmic Graph Theory and Perfect Graphs


Book Description

Algorithmic Graph Theory and Perfect Graphs provides an introduction to graph theory through practical problems. This book presents the mathematical and algorithmic properties of special classes of perfect graphs. Organized into 12 chapters, this book begins with an overview of the graph theoretic notions and the algorithmic design. This text then examines the complexity analysis of computer algorithm and explains the differences between computability and computational complexity. Other chapters consider the parameters and properties of a perfect graph and explore the class of perfect graphs known as comparability graph or transitively orientable graphs. This book discusses as well the two characterizations of triangulated graphs, one algorithmic and the other graph theoretic. The final chapter deals with the method of performing Gaussian elimination on a sparse matrix wherein an arbitrary choice of pivots may result in the filling of some zero positions with nonzeros. This book is a valuable resource for mathematicians and computer scientists.




Fundamentals of Brain Network Analysis


Book Description

Fundamentals of Brain Network Analysis is a comprehensive and accessible introduction to methods for unraveling the extraordinary complexity of neuronal connectivity. From the perspective of graph theory and network science, this book introduces, motivates and explains techniques for modeling brain networks as graphs of nodes connected by edges, and covers a diverse array of measures for quantifying their topological and spatial organization. It builds intuition for key concepts and methods by illustrating how they can be practically applied in diverse areas of neuroscience, ranging from the analysis of synaptic networks in the nematode worm to the characterization of large-scale human brain networks constructed with magnetic resonance imaging. This text is ideally suited to neuroscientists wanting to develop expertise in the rapidly developing field of neural connectomics, and to physical and computational scientists wanting to understand how these quantitative methods can be used to understand brain organization. - Winner of the 2017 PROSE Award in Biomedicine & Neuroscience and the 2017 British Medical Association (BMA) Award in Neurology - Extensively illustrated throughout by graphical representations of key mathematical concepts and their practical applications to analyses of nervous systems - Comprehensively covers graph theoretical analyses of structural and functional brain networks, from microscopic to macroscopic scales, using examples based on a wide variety of experimental methods in neuroscience - Designed to inform and empower scientists at all levels of experience, and from any specialist background, wanting to use modern methods of network science to understand the organization of the brain




Sparsity


Book Description

This is the first book devoted to the systematic study of sparse graphs and sparse finite structures. Although the notion of sparsity appears in various contexts and is a typical example of a hard to define notion, the authors devised an unifying classification of general classes of structures. This approach is very robust and it has many remarkable properties. For example the classification is expressible in many different ways involving most extremal combinatorial invariants. This study of sparse structures found applications in such diverse areas as algorithmic graph theory, complexity of algorithms, property testing, descriptive complexity and mathematical logic (homomorphism preservation,fixed parameter tractability and constraint satisfaction problems). It should be stressed that despite of its generality this approach leads to linear (and nearly linear) algorithms. Jaroslav Nešetřil is a professor at Charles University, Prague; Patrice Ossona de Mendez is a CNRS researcher et EHESS, Paris. This book is related to the material presented by the first author at ICM 2010.