title: Co-clustering directed graphs to discover asymmetries and directional communities.
abstract: In directed graphs, relationships are asymmetric and these asymmetries contain essential structural information about the graph. Directed relationships lead to a new type of clustering that is not feasible in undirected graphs. We propose a spectral co-clustering algorithm called di-sim for asymmetry discovery and directional clustering. A Stochastic co-Blockmodel is introduced to show favorable properties of di-sim To account for the sparse and highly heterogeneous nature of directed networks, di-sim uses the regularized graph Laplacian and projects the rows of the eigenvector matrix onto the sphere. A nodewise asymmetry score and di-sim are used to analyze the clustering asymmetries in the networks of Enron emails, political blogs, and theCaenorhabditiseleganschemical connectome. In each example, a subset of nodes have clustering asymmetries; these nodes send edges to one cluster, but receive edges from another cluster. Such nodes yield insightful information (e.g., communication bottlenecks) about directed networks, but are missed if the analysis ignores edge direction.
authors: Department of Statistics, University of Wisconsin-Madison, Madison, WI 53706; KarlRohe@stat.wisc.edu binyu@stat.berkeley.edu.
authors: Karl
authors: K
authors: Rohe
authors: Department of Statistics, University of Wisconsin-Madison, Madison, WI 53706.
authors: Tai
authors: T
authors: Qin
authors: Department of Statistics, University of California, Berkeley, CA 94720; KarlRohe@stat.wisc.edu binyu@stat.berkeley.edu.|Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA 94720.
authors: Bin
authors: B
authors: Yu
keywords: SVD; Stochastic Blockmodel; spectral clustering