Theory of percolation on hypergraphs

Heterogeneous K-core percolation on hypergraphs

In complex systems, there are pairwise and multiple interactions among elements, which can be described as hypergraphs. K-core percolation is widely utilized in the investigation of the robustness of systems subject to random or targeted attacks. However, the robustness of nodes usually correlates with their characteristics, such as degree, and exhibits heterogeneity while lacking a theoretical study on the K-core percolation on a hypergraph. To this end, we constructed a hyperedge K-core percolation model that introduces heterogeneity parameters to divide the active hyperedges into two parts, where hyperedges are inactive unless they have a certain number of active nodes. In the stage of pruning process, when the number of active nodes contained in a hyperedge is less than its set value, it will be pruned, which will result in the deletion of other hyperedges and ultimately trigger cascading failures. We studied the magnitude of the giant connected component and the percolation threshold of the model by mapping a random hypergraph to a factor graph. Subsequently, we conducted a large number of simulation experiments, and the theoretical values matched well with the simulated values. The heterogeneity parameters of the proposed model have a significant impact on the magnitude of the giant connected component and the type of phase transition in the network. We found that decreasing the value of heterogeneity parameters renders the network more fragile, while increasing the value of heterogeneity parameters makes it more resilient under random attacks. Meanwhile, as the heterogeneity parameter decreases to 0, it may cause a change in the nature of network phase transition, and the network shows a hybrid transition.

Analysis of the inference of ratings and rankings in complex networks using discrete exterior calculus on higher-order networks

The inference of rankings plays a central role in the theory of social choice, which seeks to establish preferences from collectively generated data, such as pairwise comparisons. Examples include political elections, ranking athletes based on competition results, ordering web pages in search engines using hyperlink networks, and generating recommendations in online stores based on user behavior. Various methods have been developed to infer rankings from incomplete or conflicting data. One such method, HodgeRank, introduced by Jiang et al. [Math. Program. 127, 203 (2011) 10.1007/s10107-010-0419-x], utilizes Hodge decomposition of cochains in Higher-Order Networks to disentangle gradient and cyclical components contributing to rating scores, enabling a parsimonious inference of ratings and rankings for lists of items. This paper presents a systematic study of HodgeRank's performance under the influence of quenched disorder and across networks with complex topologies generated by four different network models. The results reveal a transition from a regime of perfect retrieval of true rankings to one of imperfect retrieval as the strength of the quenched disorder increases. A range of observables is analyzed, and their scaling behavior with respect to the network model parameters is characterized. This work advances the understanding of social choice theory and the inference of ratings and rankings within complex network structures.

Cascading failure dynamics on higher-order networks with load redistribution

The phenomenon of load redistribution in complex networks has garnered extensive attention due to its profound impact and widespread occurrence. In recent years, higher-order structures have offered new insights into understanding the structures and dynamic processes of complex networks. However, the influence of these higher-order structures on the dynamics of load redistribution, cascade failures, and recovery processes remains to be fully explored. In this study, we propose the load redistribution model with higher-order structures and recovery strategies of cascade failure based on functional upgrading and reconstruction mechanisms. In the cascading failure process with load redistribution and higher-order recovery strategies, we find that higher-order structures can induce a discontinuous phase transition at the low proportion of load redistribution, and the dynamic process displays a dual character of being robust yet fragile. These findings have been examined in both real and classical modeled networks. Interestingly, the largest connected component exhibits three distinct modes as the attack ratio increases at high densities of higher-order structures and recovery mechanisms.

Explicit solutions of the Bass and susceptible-infected models on hypernetworks

We analyze the Bass model and the susceptible-infected model on hypernetworks with three-body interactions. We derive the master equations for general hypernetworks and use them to obtain explicit expressions for the expected adoption-infection level on infinite complete hypernetworks, infinite Erdős-Rényi hypernetworks, and on infinite hyperlines. These expressions are exact, as they are derived without making any approximation.

General theory for extended-range percolation on simple and multiplex networks

Extended-range percolation is a robust percolation process that has relevance for quantum communication problems. In extended-range percolation nodes can be trusted or untrusted. Untrusted facilitator nodes are untrusted nodes that can still allow communication between trusted nodes if they lie on a path of distance at most R between two trusted nodes. In extended-range percolation the extended-range giant component (ERGC) includes trusted nodes connected by paths of trusted and untrusted facilitator nodes. Here, based on a message-passing algorithm, we develop a general theory of extended-range percolation, valid for arbitrary values of R as long as the networks are locally treelike. This general framework allows us to investigate the properties of extended-range percolation on interdependent multiplex networks. While the extended-range nature makes multiplex networks more robust, interdependency makes them more fragile. From the interplay between these two effects a rich phase diagram emerges including discontinuous phase transitions and reentrant phases. The theoretical predictions are in excellent agreement with extensive Monte Carlo simulations. The proposed exactly solvable model constitutes a fundamental reference for the study of models defined through properties of extended-range paths.

Borromean hypergraph formation in dense random rectangles

We develop a minimal model to study the stochastic formation of Borromean links within topologically entangled networks without requiring the use of knot invariants. Borromean linkages may form in entangled solutions of open polymer chains or in Olympic gel systems such as kinetoplast DNA, but it is challenging to investigate this due to the difficulty of computing three-body link invariants. Here, we investigate rectangles randomly oriented in three Cartesian planes and densely packed within a volume, and evaluate them for Hopf linking and Borromean link formation. We show that dense packings of rectangles can form Borromean triplets and larger clusters, and that in high enough density the combination of Hopf and Borromean linking can create a percolating hypergraph through the network. We present data for the percolation threshold of Borromean hypergraphs, and discuss implications for the existence of Borromean connectivity within kinetoplast DNA.

Global topological synchronization of weighted simplicial complexes

Higher-order networks are able to capture the many-body interactions present in complex systems and to unveil fundamental phenomena revealing the rich interplay between topology, geometry, and dynamics. Simplicial complexes are higher-order networks that encode higher-order topology and dynamics of complex systems. Specifically, simplicial complexes can sustain topological signals, i.e., dynamical variables not only defined on nodes of the network but also on their edges, triangles, and so on. Topological signals can undergo collective phenomena such as synchronization, however, only some higher-order network topologies can sustain global synchronization of topological signals. Here we consider global topological synchronization of topological signals on weighted simplicial complexes. We demonstrate that topological signals can globally synchronize on weighted simplicial complexes, even if they are odd-dimensional, e.g., edge signals, thus overcoming a limitation of the unweighted case. These results thus demonstrate that weighted simplicial complexes are more advantageous for observing these collective phenomena than their unweighted counterpart. In particular, we present two weighted simplicial complexes: the weighted triangulated torus and the weighted waffle. We completely characterize their higher-order spectral properties and demonstrate that, under suitable conditions on their weights, they can sustain global synchronization of edge signals. Our results are interpreted geometrically by showing, among the other results, that in some cases edge weights can be associated with the lengths of the sides of curved simplices.

Nature of hypergraph k-core percolation problems

Hypergraphs are higher-order networks that capture the interactions between two or more nodes. Hypergraphs can always be represented by factor graphs, i.e., bipartite networks between nodes and factor nodes (representing groups of nodes). Despite this universal representation, here we reveal that k-core percolation on hypergraphs can be significantly distinct from k-core percolation on factor graphs. We formulate the theory of hypergraph k-core percolation based on the assumption that a hyperedge can be intact only if all its nodes are intact. This scenario applies, for instance, to supply chains where the production of a product requires all raw materials and all processing steps; in biology it applies to protein-interaction networks where protein complexes can function only if all the proteins are present; and it applies as well to chemical reaction networks where a chemical reaction can take place only when all the reactants are present. Formulating a message-passing theory for hypergraph k-core percolation, and combining it with the theory of critical phenomena on networks, we demonstrate sharp differences with previously studied factor graph k-core percolation processes where it is allowed for hyperedges to have one or more damaged nodes and still be intact. To solve the dichotomy between k-core percolation on hypegraphs and on factor graphs, we define a set of pruning processes that act either exclusively on nodes or exclusively on hyperedges and depend on their second-neighborhood connectivity. We show that the resulting second-neighbor k-core percolation problems are significantly distinct from each other. Moreover we reveal that although these processes remain distinct from factor graphs k-core processes, when the pruning process acts exclusively on hyperedges the phase diagram is reduced to the one of factor graph k-cores.