Spectral Detection of Simplicial Communities via Hodge Laplacians

Abstract

Despite being a source of rich information, graphs are limited to pairwise interactions. However, several real-world networks such as social networks, neuronal networks, etc., involve interactions between more than two nodes. Simplicial complexes provide a powerful mathematical framework to model such higher-order interactions. It is well known that the spectrum of the graph Laplacian is indicative of community structure, and this relation is exploited by spectral clustering algorithms. Here we propose that the spectrum of the Hodge Laplacian, a higher-order Laplacian defined on simplicial complexes, encodes simplicial communities. We formulate an algorithm to extract simplicial communities (of arbitrary dimension). We apply this algorithm to simplicial complex benchmarks and to real higher-order network data including social networks and networks extracted using language or text processing tools. However, datasets of simplicial complexes are scarce, and for the vast majority of datasets that may involve higher-order interactions, only the set of pairwise interactions are available. Hence, we use known properties of the data to infer the most likely higher-order interactions. In other words, we introduce an inference method to predict the most likely simplicial complex given the community structure of its network skeleton. This method identifies as most likely the higher-order interactions inducing simplicial communities that maximize the adjusted mutual information measured with respect to ground-truth community structure. Finally, we consider higher-order networks constructed through thresholding the edge weights of collaboration networks (encoding only pairwise interactions) and provide an example of persistent simplicial communities that are sustained over a wide range of the threshold.

18 pages, 8 figures

References in corpus (10)

• Fast unfolding of communities in large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Community detection in networks: A user guide
• CFinder: Locating cliques and overlapping modules in biological networks
• The physics of higher-order interactions in complex systems
• Clique percolation in random networks
• Higher-order simplicial synchronization of coupled topological signals
• Universal nonlinear infection kernel from heterogeneous exposure on higher-order networks

Cited by in corpus (15)

• Dynamics on higher-order networks: A review
• Inference of hyperedges and overlapping communities in hypergraphs
• Weighted simplicial complexes and their representation power of higher-order network data and topology
• Dirac signal processing of higher-order topological signals
• Dirac synchronization is rhythmic and explosive
• Local Dirac Synchronization on Networks
• Topology and dynamics of higher-order multiplex networks
• Hyperlink communities in higher-order networks
• Higher-order Connection Laplacians for Directed Simplicial Complexes
• Hyper-diffusion on multiplex networks
• Disentangling the Spectral Properties of the Hodge Laplacian: Not All Small Eigenvalues Are Equal
• Eigenvector localization in hypergraphs: pair-wise vs higher-order links
• Community detection in hypergraphs through hyperedge percolation
• Quantum walk on simplicial complexes for simplicial community detection
• Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis