Community detection for directed networks revisited using bimodularity

Abstract

Community structure is a key feature omnipresent in real-world network data. Plethora of methods have been proposed to reveal subsets of densely interconnected nodes using criteria such as the modularity index. These approaches have been successful for undirected graphs, but directed edge information has not yet been dealt with in a satisfactory way. Here, we revisit the concept of directed communities as a mapping between sending and receiving communities. This translates into a new definition that we term bimodularity. Using convex relaxation, bimodularity can be optimized with the singular value decomposition of the directed modularity matrix. Subsequently, we propose an edge-based clustering approach to reveal the directed communities including their mappings. The feasibility of the new framework is illustrated on a synthetic model and further applied to the neuronal wiring diagram of the \textit{C. elegans}, for which it yields meaningful feedforward loops of the head and body motion systems. This framework sets the ground for the understanding and detection of community structures in directed networks.

8 pages, 4 figures, 12 supplementary pages with 10 figures. Code and data are available at https://github.com/MIPLabCH/Bimodularity

References in corpus (21)

• Fast unfolding of communities in large networks
• The structure and function of complex networks
• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Resolution limit in community detection
• Link communities reveal multiscale complexity in networks
• Community detection in networks: A user guide
• Community structure in directed networks
• Structural Properties of the Caenorhabditis elegans Neuronal Network
• Nonoptimal Component Placement, but Short Processing Paths, due to Long-Distance Projections in Neural Systems
• Line Graphs, Link Partitions and Overlapping Communities
• Clustering and Community Detection in Directed Networks: A Survey
• Size reduction of complex networks preserving modularity
• Graph Representation Learning in Biomedicine
• LinkRank: Finding communities in directed networks
• Communities, Knowledge Creation, and Information Diffusion
• Bayesian stochastic blockmodeling
• Statistical inference of assortative community structures
• Symmetry group factorization reveals the structure-function relation in the neural connectome of Caenorhabditis elegans
• Spectral Algorithms for Community Detection in Directed Networks
• A hierarchy index for networks in the brain reveals a complex entangled organizational structure