spectral graph theory

Directional Laplacian Centrality for Cyber Situational Awareness

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 …

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 …

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$ …