Discrete Calculus - Applied Analysis on Graphs for Computational Science

Preface

Contents

Acronyms

Discrete Calculus: History and Future

Discrete Calculus

Origins of Vector Calculus

Origins of Discrete Calculus

Discrete vs. Discretized

Complex Networks

Content Extraction

Organization of the Book

Intended Audience

A Brief Review of Discrete Calculus

Introduction to Discrete Calculus

Topology and the Fundamental Theorem of Calculus

Differential Forms

Exterior Algebra and Antisymmetric Tensors

The Vector Spaces of p-Vectors and p-Forms

Manifolds, Tangent Spaces, and Cotangent Spaces

The Metric Tensor: Mapping p-Forms to p-Vectors

Differentiation and Integration of Forms

The Exterior Derivative

The Poincaré Lemma

The Hodge Star Operator

The Codifferential Operator and the Laplace-de Rham Operator

Differential Forms and Linear Pairings

Discrete Calculus

Discrete Domains

Orientation

The Incidence Matrix

Chains

The Discrete Boundary Operator

Discrete Forms and the Coboundary Operator

Primal and Dual Complexes

The Role of a Metric: the Metric Tensor, the Discrete Hodge Star Operator, and Weighted Complexes

The Metric Tensor and the Associated Inner Product

The Discrete Hodge Star Operator

Weights

The Volume Cochain

The Dual Coboundary Operator

The Discrete Laplace-de Rham Operator

Structure of Discrete Physical Laws

Examples of Discrete Calculus

Fundamental Theorem of Calculus and the Generalized Stokes' Theorem

Generalized Stokes' Theorem on a 1-Complex

Comparison with Finite Differences Operators

Generalized Stokes' Theorem on a 2-Complex

Generalized Stokes' Theorem on a 3-Complex

The Helmholtz Decomposition

Algorithm for Computing a Helmholtz Decomposition of a Flow Field

Matrix Representation of Discrete Calculus Identities

Integration by Parts

Other Identities

Elliptic Equations

Variational Principles

Diffusion

Advection

Concluding Remarks

Circuit Theory and Other Discrete Physical Models

Circuit Laws

Steady-State Solutions

Dependent Sources

Energy Minimization

Power Minimization with Nonlinear Resistors

AC Circuits

Connections Between Circuit Theory and Other Discrete Domains

Spring Networks

Random Walks

Gaussian Markov Random Fields

Tree Counting

Linear Algebra Applied to Circuit Analysis

The Delta-Wye and Star-Mesh Transforms

Minimum-Degree Orderings

Conclusion

Applications of Discrete Calculus

Building a Weighted Complex from Data

Determining Edges and Cycles

Defining an Edge Set

Edges from an Ambient Metric

Edges by k-Nearest Neighbors

Edges from a Delaunay Triangulation

Adding Edges via the Watts-Strogatz Model

Defining a Cycle Set

Defining Cycles Geometrically: Cycles from an Embedding

Defining Cycles Algebraically

Cycle Sets and Duality

Deriving Edge Weights

Edge Weights to Reflect Geometry

Edge Weights to Penalize Data Outliers

Univariate Data

Computing Weights from Multivariate Data

Edge Weights to Cause Repulsion

Edge Weights to Represent Joint Statistics

Deducing Edge Weights from Observations

The Underdetermined Case

The Overdetermined/Inconsistent Case

Obtaining Higher-Order Weights to Penalize Outliers

Weights Beyond Flows

Metrics Defined on a Complex

Conclusion

Filtering on Graphs

Fourier and Spectral Filtering on a Graph

Graphs that Are Not Shift-Invariant

The Origins of High Frequency Noise

Energy Minimization Methods for Filtering

The Basic Energy Minimization Model

Iterative Minimization

Extended Basic Energy Model

The Total Variation Model

Filtering with Implicit Discontinuities

Filtering with Explicit, but Unknown, Discontinuities

Filtering by Gradient Manipulation

Nonlocal Filtering

Filtering Vectors and Flows

Translating Scalar Filtering to Flow Filtering

Filtering Higher-Order Cochains

Applications

Image Processing

Regular Graphs and Space-Invariant Processing

Space-Variant Imaging

Three-Dimensional Mesh Filtering

Mesh Fairing

Filtering Data on a Surface

Geospatial Data

Filtering Flow Data-Brain Connectivity

Conclusion

Clustering and Segmentation

Targeted Clustering

Primal Targeted Clustering

Probabilities Assigned to a Subset

Known Labels for a Subset of Nodes

Negative Weights

Dual Targeted Clustering

Dual Algorithms in Three Dimensions

Untargeted Clustering

Primal Untargeted Clustering

Dual Untargeted Clustering

Semi-targeted Clustering

The k-Means Model

Clustering Higher-Order Cells

Clustering Edges

Targeted Edge Clustering

Untargeted Edge Clustering

Applications

Image Segmentation

Social Networks

Machine Learning and Classification

Gene Expression

Conclusion

Manifold Learning and Ranking

Manifold Learning

Multidimensional Scaling and Isomap

Laplacian Eigenmaps and Spectral Coordinates

Locality Preserving Projections

Relationship to Clustering

Manifold Learning on Edge Data

Ranking

PageRank

PageRank as Advection

HITS

Applications

Shape Characterization

Point Correspondence

Web Search

Judicial Citation

Conclusion

Measuring Networks

Measures of Graph Connectedness

Graph Distance

Node Centrality

Distance-Based Properties of a Graph

Measures of Graph Separability

Clustering Measures

Small-World Graphs

Topological Measures

Geometric Measures

Discrete Gaussian Curvature

Discrete Mean Curvature

Applications

Social Networks

Chemical Graph Theory

Conclusion

Appendix A Representation and Storage of a Graph and Complex

General Representations for Complexes

Cells List Representation

Operator Representation

Representation of 1-Complexes

Neighbor List Representation

Appendix B Optimization

Real-Valued Optimization

Unconstrained Direct Solutions

Constrained Direct Solutions

Optimization with Boundary Conditions

Optimization with Linear Equality Constraints

Optimization with Linear Inequality Constraints

Ratio Optimization

Descent Methods

Gradient Descent

Newton's Method

Descent Methods for Constrained Optimization

Nonconvex Energy Optimization over Real Variables

Integer-Valued Optimization

Linear Objective Functions

Quadratic Objective Functions

Pure Quadratic

General Pairwise Terms

Higher-Order Terms

General Integer Programming Problems

Appendix C The Hodge Theorem: A Generalization of the Helmholtz Decomposition

The Helmholtz Theorem

The Hodge Decomposition

Summary of Notation

References

Index

Color Plates