Published on Sun Jan 03 2021

Computing Cliques and Cavities in Networks

Dinghua Shi, Zhifeng Chen, Xiang Sun, Qinghua Chen, Chuang Ma, Yang Lou, Guanrong Chen
0
0
0
Abstract

Complex networks have complete subgraphs such as nodes, edges, triangles, etc., referred to as cliques of different orders. Notably, cavities consisting of higher-order cliques have been found playing an important role in brain functions. Since searching for the maximum clique in a large network is an NP-complete problem, we propose using k-core decomposition to determine the computability of a given network subject to limited computing resources. For a computable network, we design a search algorithm for finding cliques of different orders, which also provides the Euler characteristic number. Then, we compute the Betti number by using the ranks of the 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 in one dataset, and find all of its cliques and some cavities of different orders therein, providing a basis for further mathematical analysis and computation of the structure and function of the C. elegans neuronal network.

Wed Jun 23 2021
Machine Learning
Weisfeiler and Lehman Go Cellular: CW Networks
Graph Neural Networks (GNNs) are limited in their expressive power, struggle with long-range interactions and lack a principled way to model higher-order structures. The recently proposed Message Passing Simplicial Networks naturally decouple these elements by performing message passing on the clique complex of the graph.
4
43
202
Fri Aug 18 2017
Machine Learning
Two provably consistent divide and conquer clustering algorithms for large networks
divide-and-conquer strategies for solving the community detection problem in networks. We propose two algorithms which perform clustering on a number of small subgraphs and finally patches the results into a single clustering. The main advantage of these algorithms is that they bring down significantly the computational
0
0
0
Tue Aug 18 2020
Machine Learning
Mining Large Quasi-cliques with Quality Guarantees from Vertex Neighborhoods
Mining dense subgraphs is an important primitive across a spectrum of graph-mining tasks. Two recurring characteristics of real-world graphs, namely heavy-tailed degree distributions and large clustering coefficients, imply the existence of substantially large neighborhoods.
0
0
0
Wed Apr 27 2011
Machine Learning
Finding Dense Clusters via "Low Rank + Sparse" Decomposition
Finding "densely connected clusters" in a graph is in general an important and well studied problem in the literature. In this paper, inspired by these results, we view "imperfect cliques" as imperfect cliques, where imperfections correspond to missing edges, which are relatively sparse.
0
0
0
Wed Apr 12 2017
Machine Learning
Higher-order clustering in networks
A fundamental property of complex networks is the tendency for edges to cluster. The extent of the clustering is typically quantified by a clustering coefficient. Here we introduce higher-order clustering coefficients that measure the closure probability of higher- order network cliques.
0
0
0
Mon Apr 15 2019
Machine Learning
The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
In this paper we study the computational-statistical gap of the planted clique problem. A clique of size is planted in an Erdos Renyi graph. The goal is to recover the planted clique vertices by observing their overlap. We establish the first, to the best of our knowledge, concentration results for the $K-densest subgraph problem for the Erdos-Renyi model.
0
0
0