Introduction to Grids, Graphs, and Networks

Introduction to Grids, Graphs, and Networks

C. Pozrikidis

Oxford University Press

In production, to appear in the Fall, 2013

In the meanwhile, you may be interested in XML

Contents (as a pdf)

Preface

Cartesian, curvilinear, and other unstructured grids are used for the numerical solution of ordinary and partial differential equations using finite difference, finite element, finite volume and related methods. Graphs are broadly defined as finite or infinite sets of vertices connected by edges in structured or unstructured configurations. Infinite lattices and tiled surfaces are described by highly ordered graphs parametrized by an appropriate number of indices. Networks consist of nodes connected by physical or abstract links with an assigned conductance in spontaneous or engineered configurations. In physical and engineering applications, networks are venues for conducting or convecting a transported entity, such as heat, mass, or digitized information according to a prevailing transport law. The performance of networks is an important topic in the study of complex systems with applications in energy, material, and information transport.

The analysis of grids, graphs, and networks involves overlapping and complementary topics that benefit from a unified discussion. For example, finite difference and finite element grids can be regarded as networks whose link conductance is determined by the differential equation whose solution is sought as well as by the chosen finite difference or finite element approximation. Particular topics of interest include the properties of the node adjacency, Laplacian, and Kirchhoff matrices; the evaluation of percolation thresholds for infinite, periodic, and finite systems; the computation of the regular and generalized lattice Green's function describing the response to a nodal source; the pairwise resistance of any two nodes; the overall characterization of the network robustness; and the performance of damaged networks with reference to operational and percolation thresholds.

My goal in this text is to provide a concise and unified introduction to grids, graphs, and networks to a broad audience in the engineering, physical, biological, and social sciences. The approach is practical, in that only the necessary theoretical and mathematical concepts are introduced. Theory and computation are discussed alongside and formulas amenable to computer programming are provided. Prerequisites are familiarity with college-level linear algebra, calculus, and elementary numerical methods.

One important new concept is the distinction between isolated and embedded networks. The former stand in isolation as though they were suspended in vacuum, whereas the latter are connected to exterior nodes where a nodal potential, such as temperature, pressure, or electrical voltage, is specified. Regular Green's functions describing the discrete field due to a nodal impulse are available in the case of embedded or infinite networks, whereas generalized Green's functions describing the discrete field due to a nodal impulse in the presence of distributed sinks are available in the case of isolated networks. Discrete Green's functions can be used as building blocks for computing general solutions subject to given constraints.

This book is suitable for self-study and as a text in an upper-level undergraduate or entry-level graduate course in sciences, engineering, and applied mathematics. The material serves as a reference of terms, concepts, and as a resource of topics for further study.