Title: Spectral Graph Analysis: A Unified Explanation and Modern Perspectives,
Abstract: Complex networks or graphs are ubiquitous in sciences and engineering:
biological networks, brain networks, transportation networks, social networks,
and the World Wide Web, to name a few. Spectral graph theory provides a set of
useful techniques and models for understanding `patterns of interconnectedness'
in a graph. Our prime focus in this paper is on the following question: Is
there a unified explanation and description of the fundamental spectral graph
methods? There are at least two reasons to be interested in this question.
Firstly, to gain a much deeper and refined understanding of the basic
foundational principles, and secondly, to derive rich consequences with
practical significance for algorithm design. However, despite half a century of
research, this question remains one of the most formidable open issues, if not
the core problem in modern network science. The achievement of this paper is to
take a step towards answering this question by discovering a simple, yet
universal statistical logic of spectral graph analysis. The prescribed
viewpoint appears to be good enough to accommodate almost all existing spectral
graph techniques as a consequence of just one single formalism and algorithm.