The Spectrum of High Dimensional Networks

Supervisor(s): Dr. Omer Bobrowski, Dr. Emil Saucan

Abstract:

The graph Laplacian and its spectrum have been proven to be powerful mathematical tools that reveal fundamental properties about the structure and functionality of networks. Spectral analysis has conduced a variety of applications in Computer Science and related fields, such as clustering algorithms, randomized approximation methods, error correcting codes, and studying computational complexity. The most significant and abundant applications are in Communication Networks and related problems. In particular, in the analysis of routing algorithms, for minimizing congestion and devising efficient parallel architectures.

One of the main limitations of the graph Laplacian is that it only uses information about pairwise interactions in networks (see Figure (a)). However, in modern networks one can often find connections of higher degrees, that cannot be encoded by a graph. Consider, for example, the case of a social network. Using a graph, we can represent the information that Alice and Bob are friends, Bob and Carol are friends, and Carol and Alice are friends. We cannot say, however, whether Alice, Bob, and Carol, all get together as a group.

Simplicial complexes are high-dimensional generalizations of graphs, that in addition to vertices and edges, may also contain triangles, tetrahedra, and higher dimensional simplexes. These objects provide a natural way to represent such high-degree interactions in network (see Figure (b)). Simplicial complexes have their own notion of Laplacian, and the goal of this project is to study its spectrum. The main question we are interested is: “What can we learn about the structure of such high-dimensional networks, by analyzing their Laplacians”? We will consider both simulated as well as real-world networks, and examine both the spectrum and its corresponding harmonics. Our goal is to look for insights about the network behavior, as well as study the potential of signal processing on such high-dimensional objects (in a similar spirit to signal processing on graphs).