Computing Cliques and Cavities in Networks

• URL: http://arxiv.org/abs/2101.00536v3
• Date: Mon, 1 Nov 2021 02:07:00 GMT
• Title: Computing Cliques and Cavities in Networks
• Authors: Dinghua Shi, Zhifeng Chen, Xiang Sun, Qinghua Chen, Chuang Ma, Yang Lou and Guanrong Chen
• Abstract summary: 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. We apply the algorithm to the neuronal network of C. elegans with data from one typical dataset.
• Score: 19.17379757727846
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Structured search algorithm: A quantum leap [0.0]
  Grover's quantum search algorithm showcases the prowess of quantum algorithms. This letter advances Grover's algorithm using a structured search method to attain an unbounded search speed.
  arXiv  Detail & Related papers  (2025-04-04T13:16:53Z)
• Unsupervised Ordering for Maximum Clique [30.652280460904375]
  We transform the constraints into geometric relationships such that the ordering of vertices aligns with the clique structures. By integrating this clique-oriented ordering into branch-and-bound search, we improve search efficiency and reduce the number of computational steps.
  arXiv  Detail & Related papers  (2025-03-25T18:28:49Z)
• Provable Data Subset Selection For Efficient Neural Network Training [73.34254513162898]
  We introduce the first algorithm to construct coresets for emphRBFNNs, i.e., small weighted subsets that approximate the loss of the input data on any radial basis function network. We then perform empirical evaluations on function approximation and dataset subset selection on popular network architectures and data sets.
  arXiv  Detail & Related papers  (2023-03-09T10:08:34Z)
• Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networks [0.0]
  We determine the regions and facets of all dimensions of the canonical polyhedral complex. We present an algorithm which calculates this full canonical structure. The resulting algorithm is numerically stable, time in the number of intermediate neurons, and obtains accurate information across all dimensions.
  arXiv  Detail & Related papers  (2022-07-15T18:36:12Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• Sub-Setting Algorithm for Training Data Selection in Pattern Recognition [0.0]
  This paper proposes a training data selection algorithm that identifies multiple subsets with simple structures. A sub-setting algorithm identifies multiple subsets with simple local patterns by identifying similar instances in the neighborhood of an instance. Our bottom-up sub-setting algorithm performed on an average 15% better than the top-down decision tree learned on the entire dataset.
  arXiv  Detail & Related papers  (2021-10-13T06:42:41Z)
• Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond [98.92725321081994]
  State-of-the-art solvers integrate a myriad of cutting-plane techniques to speed up the underlying tree-search algorithm. We prove the first guarantees for learning high-performing cut-selection policies tailored to the instance distribution.
  arXiv  Detail & Related papers  (2021-06-08T00:57:59Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  Adversarial examples are a widely studied phenomenon in machine learning models. We propose an algorithm for evaluating the adversarial robustness of $k$-nearest neighbor classification.
  arXiv  Detail & Related papers  (2020-11-19T08:49:10Z)
• Online Sequential Extreme Learning Machines: Features Combined From Hundreds of Midlayers [0.0]
  In this paper, we develop an algorithm called hierarchal online sequential learning algorithm (H-OS-ELM) The algorithm can learn chunk by chunk with fixed or varying block size.
  arXiv  Detail & Related papers  (2020-06-12T00:50:04Z)
• DC-NAS: Divide-and-Conquer Neural Architecture Search [108.57785531758076]
  We present a divide-and-conquer (DC) approach to effectively and efficiently search deep neural architectures. We achieve a $75.1%$ top-1 accuracy on the ImageNet dataset, which is higher than that of state-of-the-art methods using the same search space.
  arXiv  Detail & Related papers  (2020-05-29T09:02:16Z)
• Neural Bipartite Matching [19.600193617583955]
  This report describes how neural execution is applied to a complex algorithm. It is achieved via neural execution based only on features generated from a single GNN. The evaluation shows strongly generalising results with the network achieving optimal matching almost 100% of the time.
  arXiv  Detail & Related papers  (2020-05-22T17:50:38Z)
• Novel Machine Learning Algorithms for Centrality and Cliques Detection in Youtube Social Networks [0.0]
  This research project is to analyze the dynamics of social networks using machine learning techniques. The Bron-Kerbosch algorithm is used effectively in this research to find maximal cliques. The experimental results show that we were able to successfully find central nodes through clique-centrality and degree centrality.
  arXiv  Detail & Related papers  (2020-02-10T16:05:09Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  We study the problem of clustering a set of items from binary user feedback. We devise an algorithm with a minimal cluster recovery error rate. For adaptive selection, we develop an algorithm inspired by the derivation of the information-theoretical error lower bounds.
  arXiv  Detail & Related papers  (2019-10-14T09:18:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.