An Introduction to Grids, Graphs, and Networks

An Introduction to Grids, Graphs, and Networks

C. Pozrikidis

Oxford University Press

Available from Amazon

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. The prerequisite is 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 and concepts, and as a resource of topics for further study.

Errata and supplements

1. In Equation (1.7.4), please change "(2j-1)" to "(i-1/2)"
2. On page 8, line after equation (1.3.14): Please cross out the second "K x K (thanks to Eugene Petrov.)
3. On page 8, equation (1.3.15): Please replace the third 0 in the second row with 1. (thanks to Eugene Petrov.)
4. On page 8, line after equation (1.3.15): Please cross out the second "K x K. (thanks to Eugene Petrov.)
5. On page 14, equation (1.6.3): The third diagonal element should b 2. (thanks to Eugene Petrov.)
6. On page 20, equation (1.8.1), please change the "1" to "2" in the third matrix row. (thanks to Charlie Slominski.)
7. On page 25, under equation (1.8.29), please change a_p to b_p. (thanks to Charlie Slominski.)
8. Equation (2.1.15), k on the right-hand side should be d.
9. On page 34, third paragraph, line 3 please change "λ₂ > 0" to "λ₂ = 0". (thanks to Eugene Petrov.)
10. In equation (3.1.6), please change the southeastern element of the matrix E from 4 to 3 (thanks to Charlie Slominski.)
11. In equation (3.1.8), please change the second α to β
12. In equation (3.1.18), please change the second α to β
13. In equation (3.1.27), please change the second α to β
14. In equation (3.2.9), please change the second α to β
15. In equation (3.2.19), please change the second α to β
16. In equation (3.2.28), please change the second α to β
17. Equation (4.1.8): please replace this equation with the equation:
    q_m = c_m (ψ_k-ψ_l) |ψ_k-ψ_l|^q-1
18. The graphs in Figure 5.2.2(b,c) are erroneous. Please download the new graphs .
19. In the matrix (5.2.7), one entry should be -1 instead f 1.
20. In Section 5.2.4, after the first sentence, please add the sentence: ``In graph theory, an isolated one-dimensional network is described by a path graph.''
21. In Section 5.2.5, after the first sentence, please add the sentence: ``The one-dimensional periodic network is also called a ring network described by a cycle graph.''
22. In the line above equation (5.2.32), please change (1.8.27) to (1.8.22) (thanks to Charlie Slominski.)
23. In Equation (5.10.8), the numerical coefficient in front of the integral should be -1/(32 π^3) (thanks to Jeff Davis.)
24. In Equation (5.10.10), the numerical coefficient in front of the integral should be -1/(4 π^3) (thanks to Jeff Davis.)