Computing cliques and cavities in networks

Dinghua SHI*, Zhifeng CHEN, Xiang SUN, Qinghua CHEN*, Chuang MA, Yang LOU, Guanrong CHEN*

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)peer-review

3 Citations (Scopus)

Abstract

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.
Original languageEnglish
Article number249
Number of pages8
JournalCommunications Physics
Volume4
Issue number1
Early online date25 Nov 2021
DOIs
Publication statusPublished - 1 Dec 2021

Bibliographical note

Funding 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).

Publisher Copyright:
© 2021, The Author(s).

Fingerprint

Dive into the research topics of 'Computing cliques and cavities in networks'. Together they form a unique fingerprint.

Cite this