Computing cliques and cavities in networks

Complex networks, fundamental structures in numerous fields, are characterized by their sub-structures: chains, stars, and cycles. Understanding cycles is crucial because they introduce redundancy in connectivity, leading to feedback and higher-order interactions. The authors previously introduced the concept of totally homogeneous networks, possessing uniform node degree, girth, and path-sum, and noted the importance of network invariants: the number of cliques and cavities, along with the Euler characteristic number (alternating sum of clique numbers) and Betti numbers (number of cavities). Higher-order cycles, including cliques (fully connected sub-networks) and cavities (shortest cycles in equivalent classes), are essential components of these networks. Cliques and cavities are particularly significant in biological systems, especially the brain, where cycles form neural loops mediating information transmission and feedback, potentially underpinning memory and control functions. While cliques might be localized, cavities are widely distributed, connecting diverse brain regions. The vast, unexplored numbers of cliques and cavities in both biological and artificial neural networks, especially the critical role of cavities in brain function, necessitate a computational approach to understand their organization and relationship to network complexity and neural function. This paper aims to address this by providing methods to find cliques and cavities in complex networks, particularly within the context of the *C. elegans* neuronal network and its relevance to artificial intelligence development and ongoing brain initiatives.

The paper references prior work on small-world networks, scale-free networks, and random networks, highlighting the importance of cycle structures in network dynamics and synchronization. It also cites research on simplicial complexes, boundary operators, and equivalent cycles as tools for classifying and analyzing higher-order cycles. The authors refer to previous work that introduced the concept of totally homogeneous networks and the significance of cliques and cavities as network invariants. The critical role of cycles, particularly in the brain's neuronal networks, generating neural loops for information processing and feedback, is discussed with references to studies emphasizing the importance of cyclic structures for brain functions like memory and control. Existing literature on the identification and significance of cliques and cavities in complex systems, specifically the brain connectome, is mentioned, with a focus on the need for efficient computational methods to analyze these structures in large-scale networks.

The paper proposes a computational approach to find higher-order cliques and cavities in complex networks. It begins with k-core decomposition to determine the computability of a given network, based on the available computing resources (a threshold of kmax = 25 is set). For computable networks, a clique-searching method, the 'common-neighbors scheme,' is introduced. This algorithm iteratively identifies cliques of increasing orders (0-cliques, 1-cliques (edges), 2-cliques (triangles), etc.), up to the maximum order. The Euler characteristic number is calculated from the number of cliques of different orders. Betti numbers are then calculated by computing the ranks of boundary matrices (B_k) for each clique order. The boundary matrices are defined such that matrix elements represent the incidence relationships between cliques of adjacent orders. Rank calculations are done in the binary field (1+1=0). The Betti numbers are obtained using the formula β_k = r_k - r_k+1, where r_k is the rank of B_k. The authors describe an optimized algorithm for finding cavities using a combination of techniques: finding a minimum k-order spanning tree using the ranks of boundary matrices; identifying cavity-generating k-cliques (those not part of the spanning tree and not on the boundaries of linearly independent (k+1)-cliques); and formulating the search for cavities as a 0-1 programming problem. This optimization problem minimizes the number of cliques in a cavity, subject to constraints ensuring that it forms a cycle (boundary cliques appear in pairs) and is linearly independent of other cavities. Algorithms are presented for searching specific cycles and checking for k-cavities. The paper also notes that the optimization problem can be challenging due to the non-uniqueness of minimum spanning trees. To address this, the optimization is separated into two parts: finding all possible cycles and checking their linear independence to confirm if they are cavities.

The proposed approach successfully computes higher-order cliques and their associated Euler characteristic number and Betti numbers for computable networks. The methodology was applied to the *C. elegans* neuronal network, a dataset containing 297 neurons and 2148 synapses. The results show significant differences in the numbers of cliques and cavities between the *C. elegans* network and a corresponding Erdös-Rényi random network with the same number of nodes and edges. The *C. elegans* network exhibits a much richer structure in terms of higher-order cliques and cavities. The analysis revealed the presence of four linearly independent three-cavities in the *C. elegans* network, each with specific cavity-generating 3-cliques and different numbers of nodes. The computed Euler characteristic number and Betti numbers for the *C. elegans* network are presented, contrasting them with those of the random network. These findings highlight the non-random topological organization of the *C. elegans* neuronal network, suggesting a potential link between the complex interplay of cliques and cavities and its neural functions. Tables and figures illustrate the network structure, clique counts, Betti numbers, and examples of identified cavities.

The findings demonstrate the effectiveness of the proposed computational framework for analyzing higher-order topological structures in complex networks. The significant difference between the *C. elegans* network and the random network underscores the non-random nature of the brain's organization. The identification of cavities, especially higher-order cavities, offers valuable insights into the brain's functional complexity, hinting at the functional importance of these structures beyond simply considering node degrees. The results support the growing body of research emphasizing the role of higher-order interactions in complex systems. The study addresses the computational challenge of finding cliques and cavities, which are otherwise intractable in large networks, offering a practical method for studying brain networks and advancing understanding of their functions.

This paper presents a novel approach to compute cliques and cavities in complex networks. The use of k-core decomposition for assessing computability, coupled with the proposed algorithms for finding cliques, computing Betti numbers, and identifying cavities, makes the analysis of large-scale networks feasible. The application to the *C. elegans* neuronal network demonstrates the effectiveness of the approach in revealing rich higher-order topological features. Future research could explore the application to other brain networks and delve deeper into the relationship between the topological features revealed by these methods and the network’s functional dynamics. Further investigation into the analysis of directed networks is also warranted.

The study's computability relies on the k-core decomposition and the imposed threshold of kmax=25, limiting the analysis to networks with a certain level of density. While the algorithm can find all cliques up to a computable limit, the cavity search may not find all cavities due to the non-uniqueness of minimum spanning trees and computational complexity of the 0-1 programming problem. The analysis is focused on a single dataset of *C. elegans*, and the generalizability of the findings to other neuronal networks or complex systems needs further investigation.