spectral graph theory

Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs

Cut-based directed graph (digraph) clustering often focuses on finding dense within cluster or sparse between-cluster connections, similar to cut-based undirected graph clustering methods. In contrast, for flow-based clusterings the edges between …

Directional Laplacian Centrality for Cyber Situational Awareness

Cyber operations is drowning in diverse, high-volume, multi-source data. To get a full picture of current operations and identify malicious events and actors, analysts must see through data generated by a mix of human activity and benign automated …

Spectral Threshold for Extremal Cyclic Edge-Connectivity

The cyclic edge-connectivity of a graph $G$ is the least $k$ such that there exists a set of $k$ edges whose removal disconnects $G$ into components where every component contains a cycle. We show the cyclic edge-connectivity is defined for graphs …

SpectralFly: Ramanujan Graphs as Flexible and Efficient Interconnection Networks

In recent years, graph theoretic considerations have become increasingly important in the design of HPC interconnection topologies. One approach is to seek optimal or near-optimal families of graphs with respect to a particular graph theoretic …

Hypergraph Random Walks, Laplacians, and Clustering

We propose a flexible framework for clustering hypergraph-structured data based on recently proposed random walks utilizing edge-dependent vertex weights. When incorporating edge-dependent vertex weights (EDVW), a weight is associated with each …

Ramanujan Graphs and the Spectral Gap of Supercomputing Topologies

Graph eigenvalues play a fundamental role in controlling structural properties, such as bisection bandwidth, diameter, and fault tolerance, which are critical considerations in the design of supercomputing interconnection networks. This motivates …

The maximum relaxation time of a random walk

We show the minimum spectral gap of the normalized Laplacian over all simple, connected graphs on $n$ vertices is $(1+o(1))\tfrac{54}{n^3}$. This minimum is achieved asymptotically by a double kite graph. Consequently, this leads to sharp upper …

Extreme values of the stationary distribution of random walks on directed graphs

We examine the stationary distribution of random walks on directed graphs. In particular, we focus on the principal ratio, which is the ratio of maximum to minimum values of vertices in the stationary distribution. We give an upper bound for this …

Graphs with Many Strong Orientations

We establish mild conditions under which a possibly irregular, sparse graph $G$ has “many” strong orientations. Given a graph $G$ on $n$ vertices, orient each edge in either direction with probability $1/2$ independently. We show that if $G$ …