Co-clustering for directed graphs: the Stochastic co-Blockmodel and spectral algorithm Di-Sim
arXiv:1204.2296
Abstract
Directed graphs have asymmetric connections, yet the current graph clustering methodologies cannot identify the potentially global structure of these asymmetries. We give a spectral algorithm called di-sim that builds on a dual measure of similarity that correspond to how a node (i) sends and (ii) receives edges. Using di-sim, we analyze the global asymmetries in the networks of Enron emails, political blogs, and the c elegans neural connectome. In each example, a small subset of nodes have persistent asymmetries; these nodes send edges with one cluster, but receive edges with another cluster. Previous approaches would have assigned these asymmetric nodes to only one cluster, failing to identify their sending/receiving asymmetries. Regularization and "projection" are two steps of di-sim that are essential for spectral clustering algorithms to work in practice. The theoretical results show that these steps make the algorithm weakly consistent under the degree corrected Stochastic co-Blockmodel, a model that generalizes the Stochastic Blockmodel to allow for both (i) degree heterogeneity and (ii) the global asymmetries that we intend to detect. The theoretical results make no assumptions on the smallest degree nodes. Instead, the theorem requires that the average degree grows sufficiently fast and that the weak consistency only applies to the subset of the nodes with sufficiently large leverage scores. The results results also apply to bipartite graphs.
References in corpus (11)
- Stochastic blockmodels and community structure in networks
- Community structure in directed networks
- Consistency of spectral clustering
- Graph limits and exchangeable random graphs
- Stochastic blockmodels with growing number of classes
- Empirical graph Laplacian approximation of Laplace--Beltrami operators: Large sample results
- Manifold Learning: The Price of Normalization
- Data spectroscopy: Eigenspaces of convolution operators and clustering
- Co-clustering separately exchangeable network data
- Impact of regularization on Spectral Clustering
- Convex optimization for the planted k-disjoint-clique problem
Cited by in corpus (15)
- Tensor Spectral Clustering for Partitioning Higher-order Network Structures
- Guaranteed clustering and biclustering via semidefinite programming
- Optimal Estimation and Completion of Matrices with Biclustering Structures
- Co-clustering separately exchangeable network data
- Convergence of the groups posterior distribution in latent or stochastic block models
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting
- The blessing of transitivity in sparse and stochastic networks
- Optimal Bipartite Network Clustering
- Randomized spectral co-clustering for large-scale directed networks
- Scalable Spectral Algorithms for Community Detection in Directed Networks
- Inferring structure in bipartite networks using the latent block model and exact ICL
- Detecting highly cyclic structure with complex eigenpairs
- Distributed Community Detection for Large Scale Networks Using Stochastic Block Model
- BATS: A Spectral Biclustering Approach to Single Document Topic Modeling and Segmentation
- Fast Network Community Detection with Profile-Pseudo Likelihood Methods