Computing cliques and cavities in networks

The paper addresses how to determine and compute higher-order structures—cliques and cavities—in complex networks, with a particular motivation from neuroscience where such structures are implicated in information transmission, feedback, memory, and control. Traditional network analysis emphasizing node degrees (chains and stars) does not fully capture higher-order cycles and cavities that create redundant paths and higher-order interactions. The authors aim to (1) establish a practical notion of network computability for higher-order topology via k-core decomposition, (2) develop algorithms to find all cliques of different orders and compute the Euler characteristic and Betti numbers, and (3) design an optimized method to identify higher-order cavities. This is important for understanding the relationship between higher-order topology and function, exemplified by neuronal networks such as that of C. elegans, and for potentially informing artificial neural network design inspired by biological structures.

Prior work has characterized key network properties such as small-world behavior (average distance and clustering coefficient) and scale-free degree distributions. The authors’ earlier studies introduced totally homogeneous networks and underscored the importance of invariants like the Euler characteristic and Betti numbers for network synchronization and topology. In neuroscience, previous studies reported abundant cliques and cavities in brain networks and suggested their roles in function, but comprehensive methods to extract and organize these structures were lacking. From algebraic topology, relationships between Betti numbers and zero eigenvalues of higher-order Hodge–Laplacian matrices have been established, while computational homology provides tools like simplicial complexes and boundary operators. Algorithmically, Bron–Kerbosch finds undirected cliques and Hasse diagrams have been used for directed cliques, but precise definitions and computation of directed cycles/cavities remain challenging. The maximum clique problem is NP-complete, highlighting the need for practical computability criteria and scalable algorithms.

• Computability via k-core: Use k-core decomposition to assess whether a network is computationally tractable under resource limits. The maximum coreness k_max estimates the potential maximum clique order. With a practical cap on total cliques (e.g., < 10^7 for personal computing), the paper sets a threshold k_max ≤ 25 to deem a network computable.
• Clique-searching (common-neighbors scheme): For undirected graphs, propose an implementable method to enumerate cliques by iteratively expanding from nodes to edges to triangles, etc., using common-neighbor checks constrained by node index ordering to avoid duplicates. Complexity for finding all 2-cliques is O(|E|⟨k⟩), where ⟨k⟩ is average degree. Steps illustrated on a 14-node sample network: list neighbors with higher index, generate edges, find triangles via common neighbors of edge endpoints, extend triangles to tetrahedra via common neighbors of triangle nodes, and continue until no higher-order cliques remain. Compute the Euler characteristic χ = Σ_k (-1)^k m_k.
• Betti numbers from boundary matrices: Construct boundary matrices B_k where entries indicate incidence between (k−1)- and k-cliques. Compute ranks r_k over the binary field (mod 2) via row/column operations. Betti numbers are obtained as β_k = m_k − r_k − r_{k+1} (with conventions for endpoints). Alternatively, compute numbers of zero eigenvalues of higher-order Hodge–Laplacian matrices (requires oriented cliques).
• Cavity-searching framework: Define cavities as shortest representatives in independent cycle-equivalence classes (one per Betti number). Build a minimum k-th order spanning tree by selecting a maximal set of linearly independent columns from B_k (rank r_k). Identify linearly independent (k+1)-cliques via B_{k+1} (rank r_{k+1}), then determine cavity-generating k-cliques: those not in the spanning tree and not on the boundaries of the chosen (k+1)-cliques. Adding any such k-clique to the spanning tree creates an independent k-cavity.
• 0–1 programming for cavities: For each cavity-generating k-clique v, solve a binary optimization to find the minimal-length k-cycle not representable by (k+1)-cliques: • Minimize f(x) = x^T e over x ∈ {0,1}^{m_k} subject to: (i) x_v = 1; (ii) B_k x ≡ 0 (mod 2) to ensure a cycle; (iii) rank([x, B_{k+1}]) = rank(B_{k+1}) to avoid linear combinations of (k+1)-clique boundaries. To obtain β_k independent cavities, additionally enforce linear independence among found cycles. • Reformulation: Introduce auxiliary variables to convert mod-2 constraints into a linear 0–1 system and solve with standard 0–1 linear solvers. Provide Algorithm 1 (find specific cycles of minimal length L_min = 2k+1) and Algorithm 2 (filter cycles by the third constraint to yield all k-cavities).

• Computability: k-core decomposition effectively screens networks for feasible clique enumeration. In real networks where total cliques are capped at < 10^7, the maximum computable clique orders were 9 (USAir), 6 (Jazz), and 4 (Yeast), illustrating rapid growth of cliques with network density and size.
• Sample network (14 nodes): Enumerated cliques m_0=14, m_1=26, m_2=13, m_3=1; Euler characteristic χ = 14 − 26 + 13 − 1 = 0. Boundary matrix ranks yielded Betti numbers β_0=1, β_1=2, β_2=1, β_3=0, satisfying χ = β_0 − β_1 + β_2 − β_3.
• Cavity identification on sample: Two independent 1-cavities found via 0–1 programming; one generated by edge (7,8) forming cycle (3,6,7,8), and another involving edge (5,9) leading to cycles such as (1,5,9,10,14,6,3) and variants of equal length.
• C. elegans neuronal network: For a dataset with 297 neurons and 2148 synapses, the method found all cliques and some higher-order cavities. The highest-order nonzero Betti number is β_3=4, indicating four independent three-cavities. Identified cavity-generating 3-cliques include {164,163,119,118}, {119,167,118,227}, {195,185,119,118}, and {227,195,119,118}. Corresponding three-cavities include node sequences: (85,13,3,164,163,119,118,158); (163,3,162,119,154,167,118,227,85,13,164); (171,13,3,195,185,119,118,173); and (173,13,3,227,195,119,118,185). Compared to an Erdös–Rényi random network with the same numbers of nodes and edges, C. elegans exhibits markedly different counts of cliques and Betti numbers, underscoring distinctive higher-order topology.
• Complexity: The common-neighbors scheme achieves O(|E|⟨k⟩) for enumerating 2-cliques; practical computability is guided by k_max (set to ≤25 in this study).

The study demonstrates a practical pipeline to transition from raw network data to higher-order topological descriptors (Euler characteristic, Betti numbers) and explicit cavity structures. By establishing computability via k-core and then exhaustively enumerating cliques with boundary-matrix rank computations, the approach directly addresses the challenge of extracting higher-order topology at scale. The results on C. elegans, including four independent three-cavities and their explicit structures, suggest that biological neural networks organize nontrivial higher-order connectivity not replicated by random graphs of equal size and density, supporting hypotheses about the functional roles of cavities in feedback, memory, and control. The framework also clarifies algorithmic and theoretical complexities, particularly for directed networks where cavity definitions and minimal lengths deviate from the undirected case, pointing to substantial future work. Non-uniqueness in spanning trees and eigenvector choices for Hodge–Laplacians highlights inherent ambiguities that can affect cavity extraction and necessitate careful algorithmic design and validation.

The paper contributes a comprehensive workflow for computing higher-order structures in networks: (i) assess computability via k-core decomposition; (ii) enumerate cliques by a common-neighbors scheme and compute the Euler characteristic; (iii) derive Betti numbers from boundary-matrix ranks; and (iv) locate minimal cavities via an optimized 0–1 programming approach with supporting algorithms. Applied to the C. elegans neuronal network, the method uncovers extensive higher-order structure and four independent three-cavities, differentiating it from a comparable random network and offering insights relevant to brain function and AI design. Future research directions include formalizing and computing directed cavities, mitigating non-uniqueness in spanning trees and eigenvectors, scaling to denser networks via improved pruning or parallelization, and integrating Hodge–Laplacian eigenstructure to guide cavity detection.

• Computational limits: Clique counts grow exponentially with network size and density; practical enumeration is restricted (e.g., <10^7 cliques), necessitating a computability threshold (k_max ≤ 25) that may exclude dense networks.
• Non-uniqueness: Minimum spanning trees of k-cliques and zero-eigenvalue eigenvectors of Hodge–Laplacians are not unique, which can lead to variability or failure in identifying expected cavities.
• Partial cavity coverage: While all cliques are found for computable networks, only some cavities (e.g., in C. elegans) are extracted due to optimization complexity and constraints; higher-order or longer cavities may be missed without increased search lengths.
• Directed networks: Precise definitions and algorithms for directed cavities remain open, with additional complexity compared to the undirected case.