We introduce community trees to summarize network structures.
problem Stability of community structures in networks.
method Clique percolation method (CPM) and persistent diagrams.
result Total star number (TSN) provides an upper bound on community tree changes.
New method tightens spectral bounds for percolation in clustered networks.
problem Tight spectral bounds for percolation in sparse networks with clustering.
method Message passing algorithm on triangle-non-backtracking matrix.
result Method gives tighter lower-bound to percolation transition.
First-passage percolation affects graph properties like curvature and geodesics.
problem Effect of first-passage percolation on graph curvature and geodesics.
method Randomly perturbs the metric of a graph by assigning random edge lengths.
result Non-positive curvature and geodesic properties are not preserved by first-passage percolation.
Study on dropout in neural networks using percolation theory.
problem Understanding dropout's effect on neural network training.
method Investigates percolation models mimicking dropout in neural networks.
result Dropout can cause a breakdown in neural networks.
Percolation study in non-hyperbolic groups proves non-uniqueness phase.
problem Percolation in acylindrically hyperbolic groups.
method Analyzing Bernoulli bond percolation on Cayley graphs of groups.
result Non-uniqueness phase in percolation on Cayley graphs of acylindrically hyperbolic groups.
Study reveals how dengue spread patterns vary across different years in Recife, Brazil.
problem Understanding spatial organization of dengue transmission in urban areas.
method Spatial analysis of dengue cases using topological data analysis and Vietoris-Rips filtrations.
result Critical percolation thresholds define distinct geometric regimes of dengue spread.
New dimension concept for groups based on percolation probability.
problem Defining a new dimension for groups using percolation probability.
method Introducing percolation dimension pdim(G) for groups G using symmetric probability measures. result The percolation dimension pdim(G) has natural properties like monotonicity and coincides with growth rate exponents for various groups. FPP preserves sublinear Morse boundaries in geodesic graphs.
problem Preserving sublinear Morse boundaries in FPP.
method First passage percolation on geodesic graphs with i.i.d. passage times.
result Sublinear Morse boundaries are invariant under FPP.
Proposes using continuum percolation to analyze data manifolds and improve generative models.
problem Disentangling geometric support from probability distributions in high-dimensional data.
method Establishes a correspondence between topological phase transitions of random geometric graphs and data manifolds, using Percolation Shift metric.
result Demonstrates that Percolation Shift metric captures structural pathologies like mode collapse and guides training to prevent manifold shrinkage and improve fidelity.
The maximum number of maximum cliques in a graph is determined for graphs with at least 15 vertices.
problem Determining the maximum number of maximum cliques in a graph with n vertices.
method Defining prime and composite graphs, analyzing edge bounds, and using combinatorial arguments.
result For graphs with at least 15 vertices, the graph with the maximum number of maximum cliques is composite.
Unified method detects and localizes anomalous cliques in inhomogeneous networks.
problem Detect and localize anomalous cliques in inhomogeneous networks.
method Unified method based on egonets for detection and localization.
result Unified method can detect and localize anomalous cliques in inhomogeneous networks.
Paper explores embedding methods for detecting pseudo-cliques in random graphs, showing limitations and potential.
problem Detecting planted pseudo-cliques in random dot product graphs.
method Adjacency Spectral Embedding (ASE) and Graph Encoder Embedding (GEE).
result These methods can localize pseudo-cliques with additional clean network data, but not without it.
Solves partial assignment problems using random clique complexes.
problem Partial assignment problems, especially with severe occlusions and distortions.
method Formulate as matching random clique complexes, analyze k-skeletons, match adjacency matrices, consider geometric neighbourhoods.
result Outperforms diverse matching algorithms significantly.
We present a plausible micro-founded model for the previously postulated power law finite time singular form of the crash hazard rate in the Johansen-Ledoit-Sornette model of rational expectation bubbles. The model is based on a percolation picture of the network of traders and the concept that clusters of connected tr…
Infinite clique of rays in plane minus Cantor set.
problem Understanding the mapping class group of plane minus Cantor set.
method Using a graph of loops and cliques of high-filling rays.
result Construction of an infinite clique of high-filling rays.
Percolation on complex networks has been used to study computer viruses, epidemics, and other casual processes. Here, we present conditions for the existence of a network specific, observation dependent, phase transition in the updated posterior of node states resulting from actively monitoring the network. Since tradi…
Machine learning predicts critical points for directed percolation models.
problem Determining critical points for directed percolation models.
method Supervised and unsupervised machine learning algorithms (CNN and DBSCAN) were used.
result Machine learning accurately predicts critical points for both models.
Research uses machine learning to find central nodes and cliques in YouTube social networks.
problem Identifying central nodes and cliques in YouTube social networks.
method Unsupervised machine learning, Python programming, Bron-Kerbosch algorithm.
result Successfully found central nodes through clique-centrality and degree centrality.
A novel approach selects EEGs for better brain disease diagnosis.
problem Invalid/noisy EEGs degrade diagnosis performance.
method mwcEEGs: maximum weight clique-based approach.
result Improves classification performance by selecting intra-clique and inter-clique EEGs.
Tackles the computational hardness of HPC detection, conjecturing equivalence to PC detection.
problem Computational hardness of hypergraphic planted clique detection.
method No specific method mentioned; focuses on conjecturing equivalence.
result Equivalence of computational hardness between HPC and PC detection.
Study of first passage percolation on hyperbolic groups, showing velocity and coalescence.
problem Understanding the geometry and dynamics of first passage percolation on hyperbolic groups.
method Investigation of first passage times on Cayley graphs of Gromov-hyperbolic groups with i.i.d. random passage times.
result Existence and almost sure constancy of velocity in almost every direction on the boundary of the group.
We introduce Clique Matrices as an alternative representation of undirected graphs, being a generalisation of the incidence matrix representation. Here we use clique matrices to decompose a graph into a set of possibly overlapping clusters, de ned as well-connected subsets of vertices. The decomposition is based on a s…
Riemannian first-passage percolation (FPP) is a continuum model, with a distance function arising from a random Riemannian metric in Rd. Our main result is a shape theorem for this model, which says that large balls under this metric converge to a deterministic shape under rescaling. As a consequence, we show that …
Sublinear algorithms detect cliques in graphs with high probability.
problem Detecting a planted clique in random graphs efficiently.
method Non-adaptive low-degree polynomial queries of adjacency matrix entries.
result Sublinear time detection is possible for a specific range of clique sizes.
New insights link diverse statistical problems via secret leakage planted clique.
problem Statistical-computational gaps in inference problems.
method Secret leakage planted clique as a new hardness assumption for reductions.
result Establishes tight statistical-computational tradeoffs for various problems.
Bayesian method for high-dimensional categorical data analysis.
problem Difficulties in probability modeling for high-dimensional data.
method Bayesian learning of clique tree structure.
result Optimal clique tree structure for probability modeling.
Neural networks predict shapes of first passage percolation sets.
problem Predicting the shape of first passage percolation sets.
method Used a neural network to predict the shape of the set of discovered sites from the distribution of passage times.
result Neural networks can quickly predict the shape of the set of discovered sites from the distribution of passage times.
Proposes clique pooling for graph classification.
problem Graph classification challenges.
method Clique-based graph pooling within GCN and GraphSAGE.
result Competitive performance on graph classification benchmarks.
We propose a novel probabilistic method for detection of objects in noisy images. The method uses results from percolation and random graph theories. We present an algorithm that allows to detect objects of unknown shapes in the presence of random noise. The algorithm has linear complexity and exponential accuracy and …
MFCF algorithm learns conditional dependency structure from sparse data.
problem Learning conditional dependency structure from sparse and noisy data.
method Repeated application of clique expansion to produce clique forest and MRF.
result MFCF outperforms Graphical Lasso for covariance selection models.
We present a set of models of the main stylized facts of market price fluctuations. These models comprise dynamical evolution with threshold dynamics and Langevin price equation with multiplicative noise, percolation models to describe the interaction between traders and hierarchical cascade models to unravel the possi…
Develops a method to efficiently learn causal DAGs using directed clique trees.
problem Efficiently learning causal DAGs in the presence of large cliques.
method Decomposes DAGs into independently orientable components using directed clique trees and designs a two-phase intervention algorithm.
result Proves that the number of single-node interventions necessary to orient any DAG in an EC is at least the sum of half the size of the largest cliques in each chain component of the essential graph.
Random trees emerge from geodesics in hyperbolic groups.
problem Understanding geodesics in hyperbolic groups.
method Surveying known properties and constructing random trees.
result Rich random geometry of emerging trees.
This paper proposes a percolation-based model of new-product diffusion in the spirit of Solomon et al. (2000) and Goldenberg et al. (2000). A consumer buys the new product if she has formed her individual valuation of the product (reservation price) and if this valuation is greater or equal than the price of the produc…
A tutorial on using MDL for graph analysis, focusing on clique size.
problem Analyzing the size of the largest clique in graphs.
method MDL principle applied to graph analysis.
result Interpretation of MDL results and common pitfalls.
Study on connectivity and geometry of random Coxeter groups.
problem Connectivity threshold for square percolation on random graphs.
method Probabilistic combinatorics and techniques from geometric group theory.
result Determines connectivity threshold and cubical coarse median structure for random Coxeter groups.
The study extends stochastic block models to geometric settings, focusing on community detection and information flow.
problem Generalizing community detection and information flow models to geometric settings.
method Considered a geometric random graph over a homogeneous metric space, defined a geometric counterpart of flow of information on trees.
result Sufficient conditions for recovering locations and for percolation of information in geometric settings.
Study geodesics on graphs with random lengths, proving bi-infinite paths exist.
problem Existence of bi-infinite geodesic paths on graphs with random edge lengths.
method Sublinear Morse geodesics and first passage percolation analysis.
result Proves the existence of bi-infinite geodesic paths in graphs with specific properties.
Artin groups not free of infinity are shown to have finite centers.
problem Characterizing Artin groups with finite centers.
method Reduced clique-cube complexes and actions on them.
result Artin groups not free of infinity have finite centers, and are trivial in many cases.
Square percolation determines threshold for group divergence in random graphs.
problem Threshold for quadratic divergence in random right-angled Coxeter groups.
method Square-graph analysis of random graphs to determine connectivity and divergence.
result Threshold probability for quadratic divergence is \( p_c(n) = \sqrt{\sqrt{6}-2}/\sqrt{n} \).
We develop an unsupervised, nonparametric, and scalable statistical learning method for detection of unknown objects in noisy images. The method uses results from percolation theory and random graph theory. We present an algorithm that allows to detect objects of unknown shapes and sizes in the presence of nonparametri…
The question we address here is of whether phenomena of collective bankruptcies are related to self-organized criticality. In order to answer it we propose a simple model of banking networks based on the random directed percolation. We study effects of one bank failure on the nucleation of contagion phase in a financia…
Study evaluates methods for expanding communities in hypergraphs using random walks.
problem Expanding communities in hypergraphs using random walks.
method Clique-expansion and tensor methods evaluated; hybrid method proposed.
result Parameter regimes identified where methods outperform each other.
In financial markets, abnormal trading behaviors pose a serious challenge to market surveillance and risk management. What is worse, there is an increasing emergence of abnormal trading events that some experienced traders constitute a collusive clique and collaborate to manipulate some instruments, thus mislead other …
Modeling Bitcoin Lightning Network emergence as percolation process.
problem Feasibility of the Lightning Network's emergence.
method Fitness-dependent network model based on percolation theory.
result Phase transition delineating sustainable vs. unsustainable Lightning Network states.
Discover novel multivariate relationships in time series data.
problem Capturing novel relationships between time series in complex systems.
method Introducing multipoles as linear relationships among more than two time series, identifying them as cliques of negative correlations in a correlation network.
result Almost all multipoles can be efficiently found using a clique-enumeration approach.
Maximal knotless graphs have at least 74% of their vertices' edges.
problem Characterizing maximal knotless graphs and understanding their edge constraints.
method Analyzing edge maximality and constructing graphs to meet constraints.
result There exists an infinite family of maximal knotless graphs with fewer edges than previously thought.
Estimates log-concave densities in graphical models using tent functions.
problem Maximum likelihood estimation of log-concave densities in undirected graphs.
method MLE as product of tent functions corresponding to maximal cliques.
result MLE can be found via convex optimization.