Hypergraphs describe higher-order interactions that involve more than a pair of nodes. A characteristic feature of hypergraphs is that their robustness can be strongly affected by the different roles of the nodes. Indeed, some nodes might be essential for a hyperedge's function, while others might not be. The loss of a single essential node completely destroys the hyperedge it belongs to, while the loss of a non-essential node has a buffering effect, inducing the hyperedge to simply reduce its size. In order to capture this phenomenology, we formulate a comprehensive theoretical framework for $(k,n)$-core percolation models on hypergraphs, where each node of a hyperedge is an anchor with probability $\theta$, and a hyperedge fails if an anchor node fails. Hypergraph $(k,n)$-core percolation problems can be classified as first-neighbor and second-neighbor problems, indicating that in the pruning process the connectivity is ensured only by the state of the first neighbors or the second neighbors, respectively. We derive self-consistency equations for first-neighbor and second-neighbor (node- and hyperedge-based) pruning processes, and obtain the size of the giant $(k,n)$-core. We obtain the phase diagram, including continuous and discontinuous transitions, and confirm our theory on random hypergraphs using numerical simulations. The results show how the heterogeneity of the nodes'functional roles and the extended range of the interactions affect the robustness of higher-order networks.
We study the problem of estimating the number of hyperedges in an arbitrary $n$-vertex hypergraph using sublinear in $n$ queries. Note that the number of hyperedges, $m$, can be exponential in $n$. For $k$-uniform hypergraphs, estimating $m$ is equivalent to estimating the average vertex degree, a problem studied in Barhum's Master's thesis (Weizmann Inst., 2007) under the standard access model of sampling random vertices, querying vertex degrees, and accessing incident hyperedges. Barhum's techniques do not extend to arbitrary hypergraphs, and simple lower-bound examples show that the standard access model cannot yield strongly sublinear algorithms when hyperedges have unbounded size. To obtain non-trivial sublinear bounds, we consider a natural generalization of the access model called the \emph{dual access model}, which allows sampling (labels of) random hyperedges, querying edge sizes, and accessing vertices in a hyperedge. In this model, we give a randomized algorithm that returns a $(1+\varepsilon)$-approximation to $m$ with high probability, making $O(\varepsilon^{-2}\sqrt{n} + \sqrt{n}\log n)$ queries. Complementing our algorithm, we prove a nearly matching lower bound showing that $\Omega(\sqrt{n})$ queries are necessary for any algorithm that obtains a constant factor approximation to $m$.
Deeparnab Chakrabarty, Cooper LaPorte, C. Seshadhri· 0 citations
This work generalizes three distance-based topological measures, namely closeness centrality, betweenness centrality and node eccentricity, using this new hypergraph distance, and shows that hypergraphs can be divided into three distinct classes, corresponding to the possible dominance of specific orders of interaction over their general metric structure.
E. Vasilyeva, L. Tupikina, D. Musatov et al.· Chaos, Solitons & Fracta...· 0 citations
Higher-order networks, represented as hypergraphs, enable direct modeling of multi-body interactions of arbitrary size. Hypergraph representations of real-world systems have been observed to exhibit high \emph{simpliciality} --- the tendency for subsets of hyperedges to also appear as hyperedges --- yet the generative mechanisms responsible for this structure are poorly understood. We introduce a generalized preferential attachment hypergraph model in which both hyperedge size $Y_t$ and the number of new nodes per step $X_t$ are drawn from arbitrary distributions, and derive analytically, using a mean-field approximate master equation approach, that the stationary hyperdegree distribution follows a power law whose exponent depends only on the ratio $p = E[X_t]/E[Y_t]$, independent of the shapes of the underlying distributions. Crucially, both $X_t$ and $Y_t$ can be estimated directly from any timestamped hypergraph dataset via a backward-stepping procedure, enabling the model to be fit without parametric assumptions. Applying a nonlinear extension of the model to eight real-world hypergraph datasets, we find that the simplicial fraction increases monotonically with the strength of preferential attachment up to the gelation transition at $\alpha>1$, establishing preferential attachment as a simpliciality-enforcing mechanism.
In a $k$-uniform hypergraph, the minimum $d$-degree for some $0\le d\le k-1$ is the minimum number of edges containing any given $d$-set of vertices. An extension of the classical Dirac theorem guarantees that whenever the minimum $d$-degree of a $k$-uniform $n$-vertex hypergraph, $k\mid n$, is larger than a certain Dirac threshold, it contains at least one perfect matching. Moreover, it has been known for some time, due to Kwan, Safavi, and Wang, that for $d\ge k/2$ such hypergraphs contain not only one, but ``many''perfect matchings, that is, at least as many as are expected in a random hypergraph with the same edge density. However, it has also been known that such a result could not be hoped for in general, as it already fails for $(d,k)=(1,3)$. In this paper we introduce new notions of the \emph{counting thresholds} and \emph{approximate counting thresholds}, above which a hypergraph is guaranteed to have at least this many perfect matchings. We show that these thresholds are well-defined and nontrivial for all $d,k,n$, that they are asymptotically related, and finally, we derive improved upper bounds by reducing to cases with smaller $d$ and $k$.
We study the Max-$k$-Cut problem from a node-feature perspective, where each vertex is associated with a feature vector and edge weights are given by pairwise inner products. We first examine the semidefinite relaxation of Max-$k$-Cut from this perspective. Using a normal-cone argument, we derive a general sufficient condition for exactness of the Frieze--Jerrum relaxation and show that it is satisfied in two feature-structural regimes: perfect feature balance, where the aggregate feature vectors of the parts are equal, and feature dominance, where a small set of large nonnegative feature vectors determines the structure of an optimal partition. We then show that the Max-$k$-Cut objective is equivalent to minimizing the sum of squared norms of the aggregate feature vectors assigned to the $k$ parts, thereby connecting the problem to vector balancing. Motivated by this observation, we show that a greedy feature-balancing algorithm retains the classical $1-1/k$ worst-case approximation guarantee and recovers an optimal partition under feature dominance. For rank-$1$ feature graphs with nonnegative features, classical bounds of Chandra and Wong for greedy load balancing yield a computable \emph{a posteriori} optimality-gap certificate that depends only on the returned partition and requires no knowledge of the optimum.
Hypergraphs extend ordinary graphs by allowing a hyperedge to connect more than two vertices. A hypergraph is k -uniform when each hyperedge contains exactly k vertices, and it is loose cyclic when the hyperedges are arranged cyclically so that consecutive hyperedges share exactly one vertex while non-consecutive hyperedges are disjoint. This study examines the possible k-uniform loose cyclic hypergraphs in relation to the number of vertices and develops a computational procedure for determining their spectral properties. For a loose cyclic hypergraph H = (V, E) with n vertices and m hyperedges, the relation n = m (k-1) is used to describe admissible configurations. An adjacency matrix is formed by assigning each off-diagonal entry according to the number of hyperedges containing the corresponding pair of vertices. A Python-based procedure is then used to construct the adjacency matrix for admissible parameter choices and to compute its eigenvalues and eigenvectors. The method is illustrated using a 4-uniform loose cyclic hypergraph on 15 vertices with five hyperedges. The resulting 15 × 15 adjacency matrix and its eigenvalues demonstrate the computational implementation of the procedure. The study provides a systematic matrix-based approach for obtaining the eigen spectrum of uniform loose cyclic hypergraphs when closed-form expressions are difficult to derive, while retaining the structural conditions that define the loose cyclic arrangement.
Santhosh Kumar N., S. P., Sujisha Manattukundayil· Journal of Advances in Mathe...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
