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