Discrete Calculus

The goal of this book is to bring together three active areas of current research into a single framework and show how each area benefits from more exposure to the other two. The areas are: discrete calculus, complex networks, and algorithmic content extraction. Although there have been a few intersections in the literature between these areas, they have largely developed independently of one another. However, we believe that researchers working in any one of these three areas can strongly benefit from the tools and techniques being developed in the others. We begin this book by outlining each of these three areas, their history and their relationship to one another. Subsequently, we outline the structure of this work and help the reader navigate its contents.

In this chapter we review conventional vector calculus from the standpoint of a generalized exposition in terms of exterior calculus and the theory of forms. This generalization allows us to distill the important elements necessary to operate the basic machinery of conventional vector calculus. This basic machinery is then redefined in a discrete setting to produce appropriate definitions of the domain, boundary, functions, integrals, metric and derivative. These definitions are then employed to demonstrate how the structure of the discrete calculus behaves analogously to the conventional vector calculus in many different ways.

In this chapter we present linear electric circuit theory as the central physical model for performing calculus on networks. We adopt circuit theory as the central physical model for applying and understanding the concepts of discrete calculus on graphs for three reasons: because much of the progress in graph theory over the last century was created in the context of circuit theory; because of the early connection made between circuit theory and algebraic topology (Branin Jr. in Proc. of Conf. on Neural Networks, pp. 453–491, 1966; Roth in Proceedings of the National Academy of Sciences of the United States of America 41(7):518–521, 1955); and because circuits are physical, realizable systems which need not be seen as discretizations of an underlying continuous domain but rather as a domain unto themselves. Our focus in this chapter will be to cover the main concepts in linear circuit theory from an algebraic standpoint with a focus on operators. This will prepare the reader with notation and concepts that tie naturally to the previous chapter in which the discrete analogues of differential operators were introduced. We begin with definitions of the physical quantities and corresponding quantities in circuit theory, then proceed to define the laws that relate the quantities to each other, treat methods of solving for the unknowns, and end by connecting circuit theory to other discrete processes.

Measured data often includes noise. A data point measured in isolation offers little opportunity to tease signal apart from noise. However, this separation of noise from the signal becomes more possible when multiple data points are acquired which have a relationship with each other. A spatial relationship, such as the edge set of a graph, permits the use of the collective data acquisition to make better decisions about the true data underlying each measurement. This process whereby the spatial relationships of the data are used to provide better estimates of the noiseless data is called a filtering or a denoising process. In this chapter, we outline the assumptions used to justify spatial filtering, describe the equivalent of Fourier analysis on a general graph and discuss how different parameter settings of a small number of variational approaches to filtering lead to a large number of commonly used filters. Although our focus in this chapter is on the filtering of node data (0-cochains), we also discuss how these techniques may be applied to the filtering of edge data (i.e., flows, or 1-cochains) and to the filtering of data associated with higher-dimensional cells.

Clustering algorithms are used to find communities of nodes that all belong to the same group. This grouping process is also known as image segmentation in image processing. The clustering problem is also deeply connected to machine learning because a solution to the clustering problem may be used to propagate labels from observed data to unobserved data. In general network analysis, the identification of a grouping allows for the analysis of the nodes within each group as separate entities. In this chapter, we use the tools of discrete calculus to examine both the targeted clustering problem (i.e., finding a specific group) and the untargeted clustering problem (i.e., discovering all groups). We additionally show how to apply these clustering models to the clustering of higher-order cells, e.g., to cluster edges.

A prominent theme of this book is the spatial analysis of networks and data independent of an embedding in an ambient space. The topology and metric of the network/complex have been sufficient to define the domain upon which we may perform data analysis. However, an intrinsic metric defined on a network may be interpreted as the metric that would have been obtained if the network had been embedded into an ambient space equipped with its own metric. Consequently, it is possible to calculate an embedding map for which the induced metric approximates the intrinsic metric defined on the network. The calculation of such embeddings by manifold learning techniques is one way in which the structure of the network may be examined and visualized. A different method of examining the structure of a network is to calculate an importance ranking for each node. In contrast to the majority of this book, the ranking algorithms are generally used to examine the structure of directed graphs.

We have adopted the view of graphs and, more generally, cell complexes as a domain upon which we may apply the tools of calculus to formulate differential equations and to analyze data. An important aspect of the discrete differential operators is that the operators are defined by the topology of the domain itself. Therefore, in an effort to provide a complete treatment of these differential operators, we examine in this chapter the properties of the network which may be extracted from the structure of these operators. In addition to the network properties extracted directly from the differential operators, we also review other methods for measuring the structural properties of a network. Specifically, the properties of the network that we consider are based on distances, partitioning, geometry, and topology. Our particular focus will be on the measurement of these properties from the graph structure. Applications will illustrate the use of these measures to predict the importance of nodes and to relate these measures to other properties of the subject being modeled by the network.