Spectral detection of simplicial communities via Hodge Laplacians

While the study of graphs has been very popular, simplicial complexes are relatively new in the network science community. 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.

Figure 1

A simplicial complex and its decomposition in $d$-dimensional simplices. The number of $k$-simplices in the top simplicial complex are listed.

Figure 2

Illustrative example of the support of the eigenvectors with nonzero eigenvalues $L_1^u$ and $L_2^d$ for a given simplicial complex. Top: Three eigenvectors with nonzero eigenvalues of $L_1^u$ (encoding diffusion between edges that are upper adjacent) with localized support on 1-simplicial communities. The values of the eigenvector elements are listed (color coded) next to the simplex (edge) to which they correspond. Arrows indicate orientation. Bottom: Eigenvectors with nonzero eigenvalues of $L_2^d$ (encoding diffusion amongst 2-simplices that are lower adjacent) with localized support on the 2-simplices (i.e., filled triangles) of 1-simplicial communities. Circular arrows indicate orientation (clockwise or anticlockwise). Eigenvector elements are listed within the 2-simplex (filled triangle) they correspond to. Simplices (with localized support) are color coded by their community. $\lambda$ indicates corresponding eigenvalues.

Figure 3

Color-coded 2-down communities obtained from the spectrum of the 2-down Laplacian. All edges have unit weight.

Figure 4

Color-coded communities for three different dimensions. 1-clique communities obtained from the spectrum of the 0-up Laplacian color coded on the 1-simplices (edges). Four 2-clique communities obtained from the spectrum of the 1-up Laplacian color coded on the 2-simplices (filled triangles). One 3-clique community obtained from the spectrum of the 2-up Laplacian marked through dashed edges. All edges have unit weight.

Figure 5

(a) AMI plotted across several cases of unfilled 2-simplices (each unfilled triangle is labeled by a collection of 3-nodes on the $x$ axis). The highest AMI was obtained on removing the simplex 2-8-32. AMI is averaged over 100 samples for each configuration. The standard error is of the order 0.0001. (b) The configuration with the highest AMI is shown here. The removed simplex (unfilled triangle) is marked with red edges. The 2-down simplicial communities of the Zachary Karate Club network are color coded. The first part of the label indicates the club affiliation (clubs are indicated by M and O), and the second part is a numerical identifier of the individual. Hence simplex removed (2-8-32) was a three-way connection between player 2 in club M, player 8 in club M, and player 32 in Club O. Note that the labels of the nodes in the $x$ axis are the numerical identifier of each node, e.g., M16 is uniquely identified by its numerical part 16. Node positions are determined through the Kamada Kawai layout for weighted graphs.

Figure 6

Number of 1-simplicial communities as a function of filtration parameter $\nu$.

Figure 7

Illustrative visualization of the 2-simplicial communities of the Les Miserable word network. The figure is illustrative and the labels of the nodes are not listed (see Appendix pp2 for list of character affiliations). Plots are presented for various dimensional simplicial communities from $k=1$ up to $k=6$.

Figure 8

Orientation on simplices determined through labeling the vertices. The triangle is a filled 2-simplex.