Computing Cliques and Cavities in Networks
This work provides a computational method for identifying higher-order network structures like cliques and cavities, which are relevant for the mathematical analysis of brain functions, particularly for researchers studying neuronal networks.
This paper addresses the challenge of identifying cliques and cavities in complex networks, which are important for understanding brain functions. It proposes a search method and algorithm, using k-core decomposition for network computability, to find cliques and compute Betti numbers, and an optimized algorithm for cavities. The method was applied to the C. elegans neuronal network, successfully identifying all its cliques and some cavities.
Complex networks contain complete subgraphs such as nodes, edges, triangles, etc., referred to as simplices and cliques of different orders. Notably, cavities consisting of higher-order cliques play an important role in brain functions. Since searching for maximum cliques is an NP-complete problem, we use k-core decomposition to determine the computability of a given network. For a computable network, we design a search method with an implementable algorithm for finding cliques of different orders, obtaining also the Euler characteristic number. Then, we compute the Betti numbers by using the ranks of boundary matrices of adjacent cliques. Furthermore, we design an optimized algorithm for finding cavities of different orders. Finally, we apply the algorithm to the neuronal network of C. elegans with data from one typical dataset, and find all of its cliques and some cavities of different orders, providing a basis for further mathematical analysis and computation of its structure and function.