Introduction to Grids, Graphs, and Networks
Oxford University Press
In production, to appear in the Fall, 2013
In the meanwhile, you may be interested in
(as a pdf)
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.
finite difference and finite element
grids can be regarded as
networks whose link conductance
is determined by the differential equation whose solution
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
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 familiarity with college-level linear algebra,
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.