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.
|Number of pages||8|
|Early online date||25 Nov 2021|
|Publication status||Published - 1 Dec 2021|
Bibliographical noteFunding Information:
The authors would like to thank the research supports by the National Natural Science Foundation of China (Grants no. 61174160, 12005001), the Natural Science Foundation of Fujian Province (Grant no. 2019J01427), the Program for Probability and Statistics: Theory and Application (no. IRTL 1704), and by the Hong Kong Research Grants Council through General Research Funds (Grant CityU11206320).
© 2021, The Author(s).