Detecting highly cyclic structure with complex eigenpairs
arXiv:1609.05740
Abstract
Many large, real-world complex networks have rich community structure that a network scientist seeks to understand. These communities may overlap or have intricate internal structure. Extracting communities with particular topological structure, even when they overlap with other communities, is a powerful capability that would provide novel avenues of focusing in on structure of interest. In this work we consider extracting highly-cyclic regions of directed graphs (digraphs). We demonstrate that embeddings derived from complex-valued eigenvectors associated with stochastic propagator eigenvalues near roots of unity are well-suited for this purpose. We prove several fundamental theoretic results demonstrating the connection between these eigenpairs and the presence of highly-cyclic structure and we demonstrate the use of these vectors on a few real-world examples.
25 pages, 12 figures
References in corpus (17)
- The structure and function of complex networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Community structure in directed networks
- Inferring Network Mechanisms: The Drosophila melanogaster Protein Interaction Network
- LinkRank: Finding communities in directed networks
- Spectral Scaling in Complex Networks
- Tensor Spectral Clustering for Partitioning Higher-order Network Structures
- Cyclic Topology in Complex Networks
- Using Triangles to Improve Community Detection in Directed Networks
- Detecting communities of triangles in complex networks using spectral optimization
- Finding role communities in directed networks using Role-Based Similarity, Markov Stability and the Relaxed Minimum Spanning Tree
- Co-clustering for directed graphs: the Stochastic co-Blockmodel and spectral algorithm Di-Sim
- The inhomogeneous evolution of subgraphs and cycles in complex networks
- Directed closure measures for networks with reciprocity
- Scalable Spectral Algorithms for Community Detection in Directed Networks