Classical graph theory represents pairwise relationships using vertices and edges, while hypergraphs extend this model by allowing hyperedges to join any number of vertices, enabling complex multi‐way connections. SuperHyperGraphs further generalize hypergraphs through iterated powerset constructions, capturing hierarchical relationships at multiple layers. Weighted and signed graph models assign numerical weights or positive/negative signs to edges, respectively, and these concepts have been lifted to hypergraphs and, more recently, to SuperHyperGraphs. In this paper, we systematically develop the definitions and core properties of weighted SuperHyperGraphs and signed SuperHyperGraphs. We provide detailed examples to illustrate their structure and discuss potential applications in modeling layered networks with quantitative and polarity annotations. Our results lay a foundation for future theoretical and algorithmic advances in this emerging area.
Classical graph theory represents pairwise relationships among entities using vertices (nodes) and edges (links), providing an intuitive framework that has found applications across numerous domains [1, 2].
However, classical graphs can struggle to capture more intricate or higher-order relationships. A hypergraph extends this framework by allowing hyperedges to connect any number of vertices, making it well suited for modeling complex, multi-way interactions [3–7]. Although hypergraphs improve expressiveness over classical graphs, they still face limitations when representing deeply hierarchical structures.
To overcome these limitations, the concept of a SuperHypergraph has been introduced. A SuperHypergraph incorporates recursive, hierarchical relationships by drawing both vertices and hyperedges from iterated powersets of a base set [8–12]. In essence, SuperHypergraphs generalize hypergraphs into multi-layered networks, capturing relationships at multiple scales [8, 13]. We also note that hypergraphs are closely related to the theory of hyperstructures, and SuperHypergraphs likewise correspond to SuperHyperstructures in algebraic hyperstructure theory [14, 15].
In many applications, edges carry additional information. A weighted graph assigns each edge a nonnegative value such as cost, distance, or capacity enabling quantitative analyses of paths and flows [16–18]. A signed graph instead labels edges with positive or negative signs to model cooperative versus adversarial interactions [19, 20]. These ideas have been lifted to hypergraphs yielding weighted hypergraphs and signed hypergraphs and most recently to SuperHypergraphs, giving rise to weighted SuperHypergraphs and signed SuperHyperGraphs [21]. Such extensions support refined network analyses that account for both hierarchical structure and edge-level annotations.
Although the theory and applications of graphs, hypergraphs, weighted graphs, and signed graphs are well established, the exploration of weighted and signed SuperHyperGraphs remains in its infancy. In this paper, we develop rigorous mathematical foundations for these two novel classes, derive their key structural properties, and demonstrate their relevance through concrete examples. We further anticipate that weighted and signed SuperHyperGraphs will enable clearer, multi-layered schematic representations of complex hierarchical systems encountered in practice. Our work thus advances hierarchical network modeling and lays the groundwork for future algorithmic and application-driven research in multi-layered graph systems.
The remainder of this paper is organized as follows. In §2, we review the fundamental definitions of hypergraphs and SuperHypergraphs. §3 introduces weighted SuperHypergraphs and examines their key properties. §4 explores signed SuperHyperGraphs, focusing on their definitions and structural characteristics. Finally, §5 concludes the paper and outlines directions for future research.
This section provides an introduction to the foundational concepts and definitions required for the discussions in this paper. Throughout this paper, all sets and structures are assumed to be finite. Unless otherwise specified, the symbol n denotes a non-negative integer. Readers who wish to explore the detailed operations on each graph structure are encouraged to consult the relevant references as needed.
Let H be a nonempty set and let n ∈ N. We first recall the iterated powerset construction and then define SuperHyperGraphs. Powerset collects all subsets of a set; the n-th iterated powerset repeatedly applies powerset operation n times recursively.
Definition 1 (Powerset). (cf. [22, 23]) Let S be any set. The powerset of S, denoted P(S), is the collection of all subsets of S:
\[ P(S) = \{ A \mid A \subseteq S \}. \]
In particular, ∅ ∈ P(S) and S ∈ P(S).
Definition 2 (Nonempty Powerset). Let S be any set. The nonempty powerset of S, denoted P∗(S), is
\[ P^{\ast}(S) = \{ A \mid A \subseteq S,\, A \neq \varnothing \}. \]
Definition 3 (n-th Iterated Powerset). (cf. [24–27]) For a set H and integer n ≥ 1, the n-th iterated powerset of H, denoted Pn(H), is defined recursively by
\[ P_1(H) = P(H), \quad P_{n+1}(H) = P\!\big(P_n(H)\big). \]
Its nonempty analogue is given by
\[ P^{\ast}_{1}(H) = P^{\ast}(H), \quad P^{\ast}_{n+1}(H) = P^{\ast}\!\big(P^{\ast}_{n}(H)\big). \]
Example 1 (Iterated Powersets in a Smart-Building Sensor Hierarchy). Consider a smart building with three sensors:
\[ H = \{SA, SB, SC\}. \]
The definition of a Hypergraph is given below.
Definition 4 (Hypergraph [28, 29]). A hypergraph is an ordered pair \(G = (V, E)\) where
The definition of a SuperHyperGraph is given below [30, 31]. SuperHyperGraphs constitute an important area of research, as they have been studied both for applications in decision science and for investigations across various classes of graphs [32–35]. While some definitions of a SuperHyperGraph assume both the vertex set V and the edge set E lie in the same n-th iterated powerset Pn, in this paper we adopt
V ⊆ Pn, E ⊆ Pn+1.
Definition 5 (SuperHyperGraph [8, 36]). Let H be a nonempty set and n ∈ N. A SuperHyperGraph of depth n is an ordered pair
\[ H = (V, E), \]
satisfying
\[ V \subseteq P_n(H), \quad E \subseteq P_{n+1}(H). \]
Here \(P_n(H)\) and \(P_{n+1}(H)\) denote the n-th and (n + 1)-th iterated powersets of H, respectively. In particular, vertices lie in the n-th layer, while hyperedges lie one layer higher, ensuring a proper hierarchy:
\[ V \subseteq P(P(\cdots P\underbrace{}_{n}(H)\cdots)), \quad E \subseteq P(P(\cdots P\underbrace{}_{n+1}(H)\cdots)). \]
Example 2 (Real-World Example of a 2-SuperHyperGraph: Corporate Collaboration Network). Consider a corporate collaboration network in which individual employees form project teams, and project teams form divisions. We model this as a 2-SuperHyperGraph
\[ SuHyG(2) = (V, E) \]
over a finite base set \(V_0\) of employees.
Example 3 (SuperHyperGraph Modeling a LAN Hierarchy). Let the base set of network elements be
\[ H = \{PCA, PCB, PCC, PCD, \text{Printer}, \text{Server}\}. \]
Subnets correspond to first-level subsets:
\[ S_1 = \{PCA, PCB\},\; S_2 = \{PCC, PCD\},\; S_3 = \{\text{Printer}, \text{Server}\}, \]
so \(\{S_1, S_2, S_3\} \subseteq P_1(H)\). VLANs are second-level subsets of subnets:
\[ V_1 = \{S_1, S_3\},\; V_2 = \{S_2, S_3\},\; V_3 = \{S_1, S_2\}, \]
hence \(\{V_1, V_2, V_3\} \subseteq P_2(H)\). Trunk links between VLANs define third-level hyperedges:
\[ e_1 = \{V_1, V_2\},\; e_2 = \{V_2, V_3\},\; e_3 = \{V_1, V_3\}, \]
so \(\{e_1, e_2, e_3\} \subseteq P_3(H)\). Collecting these, the 2-depth SuperHyperGraph \(H(2) = (V, E)\) is
\[ V = \{V_1, V_2, V_3\}, \quad E = \{e_1, e_2, e_3\}. \]
In this model:
This SuperHyperGraph captures the hierarchical structure of a LAN—from devices through subnets and VLANs to trunk segments—within a unified mathematical framework.
The following shows that the concept of a SuperHyperGraph in this paper generalizes the classical notion of a HyperGraph.
Proposition 1 (Hypergraphs as Depth-0 SuperHyperGraphs). Every hypergraph \(G = (V, E)\) can be realized as a SuperHyperGraph of depth 0. Concretely, set the base set \(H = V\). Then
\[ P_0(H) = H, \quad P_1(H) = P(H), \]
so
\[ V \subseteq P_0(H), \quad E \subseteq P_1(H). \]
Thus \(H = (V, E)\) is a SuperHyperGraph of depth 0 whose vertex set and edge set coincide with those of the original hypergraph.
Proof. Let \(G = (V, E)\) be any hypergraph, so by definition \(E \subseteq P(V)\). Take \(H = V\). Since \(P_0(H) = H\), we have \(V \subseteq P_0(H)\). Likewise \(P_1(H) = P(H) = P(V)\), so \(E \subseteq P_1(H)\). These inclusions exactly match the requirements for a SuperHyperGraph of depth 0. Hence \(H = (V, E)\) satisfies
\[ V \subseteq P_0(H), \quad E \subseteq P_1(H), \]
and is therefore a depth-0 SuperHyperGraph. This construction is bijective: any SuperHyperGraph of depth 0 on \(H\) yields a hypergraph on the same \(V\) and \(E\).
For use in the subsequent theorems, we define the concepts of walk, path, and cycle in a SuperHyperGraph.
Definition 6 (Walk, Path, and Cycle in a SuperHyperGraph). Let \(H = (V, E)\) be a SuperHyperGraph of depth n, where \(V \subseteq P_n(H)\) and \(E \subseteq P_{n+1}(H)\).
A walk of length k in H is an alternating sequence
\[ v0, e1, v1, e2, \ldots, ek, vk, \]
such that for each \(i = 1, \ldots, k\),
\[ ei \in E \text{ and } \{\,vi-1,\, vi\,\} \subseteq ei. \]
A path is a walk in which all vertices \(v0, v1, \ldots, vk\) are distinct and all hyperedges \(e1, e2, \ldots, ek\) are distinct. A cycle is a closed walk of length \(k \ge 2\), namely
\[ v0, e1, v1, \ldots, ek, vk \text{ with } v0 = vk, \]
such that
Example 4 (Walk, Path, and Cycle in a Smart-Building Hierarchy). Let the set of sensors be
\[ H = \{SA, SB, SC\}. \]
Rooms are first-level subsets:
\[ R_1 = \{SA, SB\}, \quad R_2 = \{SB, SC\}, \quad R_3 = \{SC, SA\}, \]
so \(\{R_1, R_2, R_3\} \subseteq P_1(H)\). Floors are second-level subsets:
\[ F_1 = \{R_1, R_2\}, \quad F_2 = \{R_2, R_3\}, \quad F_3 = \{R_3, R_1\}, \]
hence \(\{F_1, F_2, F_3\} \subseteq P_2(H)\). Buildings are third-level subsets:
\[ B_1 = \{F_1, F_2\}, \quad B_2 = \{F_2, F_3\}, \quad B_3 = \{F_3, F_1\}, \]
giving \(\{B_1, B_2, B_3\} \subseteq P_3(H)\). Thus we obtain a 2-SuperHyperGraph \(H = (V, E)\) with
\[ V = \{F_1, F_2, F_3\}, \quad E = \{B_1, B_2, B_3\}. \]
A weighted graph is a graph in which each edge is assigned a numerical weight representing cost, distance, capacity, or strength between its two vertices [16–18]. A weighted hypergraph is a hypergraph whose hyperedges carry numerical weights indicating the strength, cost, or importance of multi-vertex connections [37–39]. A weighted n–SuperHyperGraph extends this concept by assigning numerical weights to n-superedges, thereby capturing connection strengths at each hierarchical layer [40].
In this section, we review the definition, properties, and potential applications of weighted n-SuperHyperGraphs as outlined below.
Definition 7 (Weighted n-SuperHyperGraph [40])Let V0 be a finite base set of vertices, and define the iterated powersets:
\[ \mathcal{P}^0(V_0) = V_0,\quad \mathcal{P}^{k+1}(V_0) = \mathcal{P}(\mathcal{P}^k(V_0)) \quad (k \geq 0). \]
A weighted n–SuperHyperGraph is a triple:
\[ \text{WSuHyG}^{(n)} = (V, E, w), \]
where …
In particular, vertices inhabit the nth layer of the iterated powerset, while hyperedges inhabit the (n + 1)th layer, ensuring a proper hierarchical distinction.
Example 5 (Weighted 2-SuperHyperGraph: Team Collaboration Network)Let the base set of individuals be:
\[ V_0 = \{\text{Hiroko}, \text{Yutaka}, \text{Shinya}\}. \]
Then
\[ \mathcal{P}^1(V_0) = \{\{\text{Hiroko}\}, \{\text{Yutaka}\}, \{\text{Shinya}\}, \{\text{Hiroko}, \text{Yutaka}\}, \{\text{Hiroko}, \text{Shinya}\}, \{\text{Yutaka}, \text{Shinya}\}, \varnothing, V_0\}, \]
and \[ \mathcal{P}^2(V_0) = \mathcal{P}(\mathcal{P}^1(V_0)), \quad \mathcal{P}^3(V_0) = \mathcal{P}(\mathcal{P}^2(V_0)). \]
Define three 2-supervertices:
\[ v_1 = \{\{\text{Hiroko}\}, \{\text{Yutaka}\}\}, \quad v_2 = \{\{\text{Yutaka}\}, \{\text{Shinya}\}\}, \quad v_3 = \{\{\text{Hiroko}, \text{Yutaka}\}, \{\text{Yutaka}, \text{Shinya}\}\}. \]
Thus
\[ V = \{v_1, v_2, v_3\} \subseteq \mathcal{P}^2(V_0). \]
Next, each 2-superedge is a subset of the 2-supervertices, hence lies in:
\[ \mathcal{P}(\mathcal{P}^2(V_0)) = \mathcal{P}^3(V_0): \]
\[ e_1 = \{v_1, v_2\}, \quad e_2 = \{v_2, v_3\}, \quad e_3 = \{v_1, v_3\}, \]
so
\[ E = \{e_1, e_2, e_3\} \subseteq \mathcal{P}^3(V_0). \]
Finally, assign weights reflecting collaboration strength:
\[ w(e_1) = 10,\quad w(e_2) = 5,\quad w(e_3) = 8. \]
Collecting these, the weighted 2-SuperHyperGraph is
\[ \text{WSuHyG}^{(2)} = (V, E, w), \]
with \( V \subseteq \mathcal{P}^2(V_0) \) and \( E \subseteq \mathcal{P}^3(V_0) \).
Example 6 (Weighted 2-SuperHyperGraph: Navigation Route in a LAN)Consider a navigation app connecting four locations:
\[ V_0 = \{\text{Airport}, \text{Station}, \text{Museum}, \text{Hotel}\}, \]
with direct distances (in km):
\[ d(\text{Airport}, \text{Station}) = 30,\quad d(\text{Station}, \text{Museum}) = 10,\quad d(\text{Museum}, \text{Hotel}) = 20. \]
First-level subsets (\(\mathcal{P}^1(V_0)\)) represent direct legs. At the second level, define two 2-supervertices in \(\mathcal{P}^2(V_0)\):
\[ v_1 = \{\{\text{Airport}, \text{Station}\}, \{\text{Station}, \text{Museum}\}\},\quad v_2 = \{\{\text{Museum}, \text{Hotel}\}\}. \]
Thus \[ V = \{v_1, v_2\} \subseteq \mathcal{P}^2(V_0). \]
At the third level, connect these supervertices: \[ e_1 = \{v_1, v_2\} \subseteq \mathcal{P}^3(V_0), \]
so \[ E = \{e_1\}. \]
Assign the travel distance as a weight:
\[ w(e_1) = d(\text{Airport}, \text{Station}) + d(\text{Station}, \text{Museum}) + d(\text{Museum}, \text{Hotel}) = 30 + 10 + 20 = 60. \]
Collecting these,
\[ \text{WSuHyG}^{(2)} = (V, E, w), \]
models the two-leg route from Airport to Hotel via Station and Museum, with total distance 60 km.
Example 7 (Weighted 3-SuperHyperGraph: Global Supply Network)Let \[ V_0 = \{\text{Supplier}, \text{Manufacturer}, \text{Distributor}\}. \]
Form \[ \mathcal{P}^1(V_0),\quad \mathcal{P}^2(V_0) = \mathcal{P}(\mathcal{P}^1(V_0)),\quad \mathcal{P}^3(V_0) = \mathcal{P}(\mathcal{P}^2(V_0)),\quad \mathcal{P}^4(V_0) = \mathcal{P}(\mathcal{P}^3(V_0)). \]
Define three 3-supervertices in \(\mathcal{P}^3(V_0)\):
\[ X_1 = \{\{\text{Supplier}\}, \{\text{Manufacturer}\}\},\quad X_2 = \{\{\text{Manufacturer}\}, \{\text{Distributor}\}\},\quad X_3 = \{\{\text{Supplier}, \text{Manufacturer}\}, \{\text{Distributor}\}\}, \]
\[ v_1 = \{X_1, X_2\},\quad v_2 = \{X_2, X_3\},\quad v_3 = \{X_1, X_3\}. \]
so
\[ V = \{v_1, v_2, v_3\} \subseteq \mathcal{P}^3(V_0). \]
Each 3-superedge lies in \(\mathcal{P}(\mathcal{P}^3(V_0)) = \mathcal{P}^4(V_0)\):
\[ e_1 = \{v_1, v_2\},\quad e_2 = \{v_2, v_3\},\quad E = \{e_1, e_2\} \subseteq \mathcal{P}^4(V_0). \]
Assign weights representing annual transaction volumes (in millions USD):
\[ w(e_1) = 150,\quad w(e_2) = 200. \]
Hence the weighted 3-SuperHyperGraph is:
\[ \text{WSuHyG}^{(3)} = (V, E, w), \]
with \(V \subseteq \mathcal{P}^3(V_0)\) and \(E \subseteq \mathcal{P}^4(V_0)\).
Example 8 (Weighted 3-SuperHyperGraph: Metropolitan Train Lines)Let the set of stations be:
\[ V_0 = \{A, B, C, D, E\}. \]
Define the direct track segments (first-level subsets) with their lengths (in km):
\[ s_1 = \{A, B\},\quad d(s_1) = 5,\quad s_2 = \{B, C\},\quad d(s_2) = 4, \]
\[ s_3 = \{C, D\},\quad d(s_3) = 3,\quad s_4 = \{D, E\},\quad d(s_4) = 6. \]
Form three routes (second-level subsets):
\[ r_1 = \{s_1, s_2\},\quad r_2 = \{s_2, s_3\},\quad r_3 = \{s_3, s_4\}. \]
Then \(\{r_1, r_2, r_3\} \subseteq \mathcal{P}^2(V_0)\).
Group routes into two train lines (third-level subsets):
\[ \ell_1 = \{r_1, r_2\},\quad \ell_2 = \{r_2, r_3\}, \]
so \(\{\ell_1, \ell_2\} \subseteq \mathcal{P}^3(V_0)\), and set \[ V = \{\ell_1, \ell_2\}. \]
Finally, connect these lines by a superedge (fourth-level subset):
\[ e = \{\ell_1, \ell_2\} \subseteq \mathcal{P}^4(V_0), \]
and let \[ E = \{e\}. \]
Define the weight \(w(e)\) to be the length of the shared segment \(s_2\), representing the overlap where passengers transfer between lines:
\[ w(e) = d(s_2) = 4. \]
Thus the weighted 3-SuperHyperGraph
\[ \text{WSuHyG}^{(3)} = (V, E, w), \]
models two overlapping train lines, capturing both the hierarchical structure (stations → segments → routes → lines → network) and the quantitative overlap of 4 km where line transfers occur.
Definition 8 (Weighted Degree)Let \(\text{WSuHyG}^{(n)} = (V, E, w)\) be a weighted n-SuperHyperGraph. The weighted degree of a supervertex \(v \in V\) is
\[ \deg(v) = \sum_{e \in E : v \in e} w(e). \]
Example 9 (Weighted Degree in a Team Collaboration Network)Consider the weighted 2-SuperHyperGraph \[ \text{WSuHyG}^{(2)} = (V, E, w), \]
where \[ V = \{v_1, v_2, v_3\},\quad E = \{e_1, e_2, e_3\}, \]
with \[ e_1 = \{v_1, v_2\},\quad e_2 = \{v_2, v_3\},\quad e_3 = \{v_1, v_3\}, \]
and weights \[ w(e_1) = 10,\quad w(e_2) = 5,\quad w(e_3) = 8. \]
By Definition 8, the weighted degree of each supervertex is:
\[ \deg(v_1) = w(e_1) + w(e_3) = 10 + 8 = 18,\quad \deg(v_2) = w(e_1) + w(e_2) = 10 + 5 = 15, \]
\[ \deg(v_3) = w(e_2) + w(e_3) = 5 + 8 = 13. \]
Theorem 1 (Degree–Edge-Weight Sum)In any weighted n-SuperHyperGraph \(\text{WSuHyG}^{(n)} = (V, E, w)\),
\[ \sum_{v \in V} \deg(v) = \sum_{e \in E} w(e) \cdot |e|. \]
Proof.Interchange the order of summation over the finite sets \(V\) and \(E\):
\[ \sum_{v \in V} \deg(v) = \sum_{v \in V} \sum_{e \in E: v \in e} w(e) = \sum_{e \in E} \sum_{v \in e} w(e) = \sum_{e \in E} w(e) \cdot |e|. \]
Definition 9 (Weighted Coverage Function)Let \(\text{WSuHyG}^{(n)} = (V, E, w)\). Define
\[ f : 2^V \longrightarrow \mathbb{R}_{\geq 0}, \quad f(X) = \sum_{e \in E: e \cap X \neq \varnothing} w(e), \quad \forall X \subseteq V. \]
Example 10 (Weighted Coverage Function in the Team Collaboration Network)Let \(\text{WSuHyG}^{(2)} = (V, E, w)\) be as in Example 5, with
\[ V = \{v_1, v_2, v_3\},\quad E = \{e_1, e_2, e_3\},\quad w(e_1) = 10,\quad w(e_2) = 5,\quad w(e_3) = 8. \]
Then for any \(X \subseteq V\), the coverage function \[ f(X) = \sum_{e \in E: e \cap X \neq \varnothing} w(e) \] takes the values:
\[ f(\varnothing) = 0, \\ f(\{v_1\}) = 0, \\ f(\{v_1, v_2\}) = w(e_1) = 10, \\ f(\{v_2, v_3\}) = w(e_2) = 5, \\ f(\{v_1, v_3\}) = w(e_3) = 8, \\ f(\{v_1, v_2, v_3\}) = w(e_1) + w(e_2) + w(e_3) = 23. \]
Theorem 2 (Monotonicity of the Coverage Function)Let \(\text{WSuHyG}^{(n)} = (V, E, w)\) be a weighted n-SuperHyperGraph with coverage function
\[ f(X) = \sum_{e \in E: e \cap X \neq \varnothing} w(e),\quad X \subseteq V. \]
Then for any \(X, Y \subseteq V\) with \(X \subseteq Y\),
\[ f(X) \leq f(Y). \]
Proof.If \(e \cap X \neq \varnothing\), then certainly \(e \cap Y \neq \varnothing\). Hence the index set \(\{e \in E : e \cap X \neq \varnothing\}\) is contained in \(\{e \in E : e \cap Y \neq \varnothing\}\), and since all weights \(w(e)\) are nonnegative, it follows that
\[ f(X) = \sum_{e \in E: e \cap X \neq \varnothing} w(e) \leq \sum_{e \in E: e \cap Y \neq \varnothing} w(e) = f(Y). \]
Theorem 3 (Modularity of the Coverage Function)With \(f\) as above, for all \(X, Y \subseteq V\), one has the exact relation:
\[ f(X) + f(Y) = f(X \cup Y) + f(X \cap Y). \]
In particular, \(f\) is both submodular and supermodular.
Proof.Partition the index set \(E\) into three disjoint parts:
\[ E_1 = \{e : e \subseteq X \cap Y\},\quad E_2 = \{e : e \subseteq X \cup Y,\ e \not\subseteq X \cap Y\},\quad E_3 = E \setminus (E_1 \cup E_2). \]
Then
\[ f(X) = \sum_{e \in E_1 \cup E_2} w(e),\quad f(Y) = \sum_{e \in E_1 \cup E_2} w(e), \]
\[ f(X \cap Y) = \sum_{e \in E_1} w(e),\quad f(X \cup Y) = \sum_{e \in E_1 \cup E_2} w(e). \]
Adding the first two sums gives
\[ f(X) + f(Y) = 2 \sum_{e \in E_1 \cup E_2} w(e) = \sum_{e \in E_1} w(e) + \sum_{e \in E_1 \cup E_2} w(e) = f(X \cap Y) + f(X \cup Y), \]
as required. □
Definition 10 (Marginal Gain)Let \(\text{WSuHyG}^{(n)} = (V, E, w)\) be a weighted n-SuperHyperGraph with coverage function \(f\). For any \(X \subseteq V\) and \(v \in V \setminus X\), the marginal gain of adding \(v\) to \(X\) is
\[ \Delta_v(X) = f(X \cup \{v\}) – f(X). \]
Example 11 (Marginal Gain in the Team Collaboration Network)Recall the weighted 2-SuperHyperGraph \(\text{WSuHyG}^{(2)} = (V, E, w)\), with
\[ V = \{v_1, v_2, v_3\},\quad E = \{e_1, e_2, e_3\},\quad w(e_1) = 10,\quad w(e_2) = 5,\quad w(e_3) = 8, \]
and coverage function \[ f(X) = \sum_{e \in E: e \cap X \neq \varnothing} w(e). \]
\[ f(\{v_1\}) = 0,\quad f(\{v_1, v_2\}) = w(e_1) = 10, \]
hence \[ \Delta_{v_2}(\{v_1\}) = f(\{v_1, v_2\}) – f(\{v_1\}) = 10 – 0 = 10. \]
\[ f(\{v_1, v_2\}) = 10,\quad f(\{v_1, v_2, v_3\}) = w(e_1) + w(e_2) + w(e_3) = 23. \]
hence \[ \Delta_f(v_3 \mid \{v_1, v_2\}) = 23 – 10 = 13. \]
Theorem 4 (Diminishing Marginal Returns)Let \(X, Y \subseteq V\) satisfy \(X \subseteq Y \subseteq V\), and let \(v \in V \setminus Y\). Then
\[ \Delta_f(v \mid X) \geq \Delta_f(v \mid Y). \]
Proof.Submodularity of \(f\) gives:
\[ f(X \cup \{v\}) + f(Y) \geq f(Y \cup \{v\}) + f(X). \]
Rearranging yields:
\[ f(X \cup \{v\}) – f(X) \geq f(Y \cup \{v\}) – f(Y), \]
i.e. \[ \Delta_f(v \mid X) \geq \Delta_f(v \mid Y). \quad \square \]
Definition 11 (Cut Function)Define the cut function:
\[ g : 2^V \longrightarrow \mathbb{R}_{\geq 0},\quad g(X) = \sum_{\substack{e \in E\\ e \cap X \neq \varnothing,\ e \cap (V \setminus X) \neq \varnothing}} w(e),\quad \forall X \subseteq V. \]
Theorem 5 (Symmetry and Submodularity of the Cut)Let \(g\) be the cut function on \((V, E, w)\). Then for all \(X, Y \subseteq V\):
Multiplying by \(w(e) \geq 0\) and summing over \(E\) yields the desired inequality. □
Theorem 6 (Total Coverage and Upper Bound)For any weighted n-SuperHyperGraph \((V, E, w)\) with coverage function \(f\),
\[ f(V) = \sum_{e \in E} w(e)\quad \text{and} \quad f(X) \leq f(V)\quad \forall X \subseteq V. \]
Proof.By definition of \(f\),
\[ f(V) = \sum_{e \in E: e \cap V \neq \varnothing} w(e) = \sum_{e \in E} w(e). \]
Monotonicity of \(f\) then implies \(f(X) \leq f(V)\) for every \(X \subseteq V\). □
A signed graph is a graph whose edges carry a sign + or −, modeling cooperative or adversarial interactions among vertices [19, 20]. A signed hypergraph extends this by assigning each hyperedge a sign, capturing polarity in multi-way group interactions [41–43]. In this section, we review the definition, properties, and potential applications of Signed n-SuperHyperGraphs as outlined below.
Definition 12 (Signed n-SuperHyperGraph [21])Let \(V_0\) be a finite base set and, for \(k \geq 0\), define
\[ \mathcal{P}^0(V_0) = V_0,\quad \mathcal{P}^{k+1}(V_0) = \mathcal{P}(\mathcal{P}^k(V_0)). \]
A signed n–SuperHyperGraph is a triple:
\[ \text{SWSuHyG}^{(n)} = (V, E, \varphi), \]
where
\[ V \subseteq \mathcal{P}^n(V_0),\quad E \subseteq \mathcal{P}^{n+1}(V_0), \]
and
\[ \varphi : V \times E \longrightarrow \{-1, 0, +1\} \]
is the incidence sign function defined by:
\[ \varphi(v, e) = \begin{cases} +1, & \text{if } v \in e \text{ and the incidence is positive}, \\ -1, & \text{if } v \in e \text{ and the incidence is negative}, \\ 0, & \text{if } v \notin e. \end{cases} \]
When \(n = 1\), this recovers a signed hypergraph, and if additionally each \(e \in E\) has exactly two vertices, a signed graph.
Example 12 (Signed 2-SuperHyperGraph)Let \(V_0 = \{A, B, C\}\). Then
\[ \mathcal{P}^1(V_0) = \{\{A\}, \{B\}, \{C\}, \{A, B\}, \{A, C\}, \{B, C\}, \varnothing, V_0\}, \] \[ \mathcal{P}^2(V_0) = \mathcal{P}(\mathcal{P}^1(V_0)),\quad \mathcal{P}^3(V_0) = \mathcal{P}(\mathcal{P}^2(V_0)). \]
Choose \[ v_1 = \{\{A\}, \{B\}\},\quad v_2 = \{\{B\}, \{C\}\},\quad v_3 = \{\{A, B\}, \{C\}\}, \] so \[ V = \{v_1, v_2, v_3\} \subseteq \mathcal{P}^2(V_0). \]
Then define \[ e_1 = \{v_1, v_2\},\quad e_2 = \{v_2, v_3\},\quad e_3 = \{v_1, v_3\}, \] so \[ E = \{e_1, e_2, e_3\} \subseteq \mathcal{P}^3(V_0). \]
The incidence sign function \(\varphi\) may be given by:
| e₁ | e₂ | e₃ | |
|---|---|---|---|
| v₁ | +1 | 0 | −1 |
| v₂ | +1 | +1 | 0 |
| v₃ | 0 | −1 | −1 |
so that \(\varphi(v_i, e_j)\) is +1 for positive incidence, −1 for negative, and 0 otherwise. Thus \(\text{SWSuHyG}^{(2)} = (V, E, \varphi)\) is a signed 2-SuperHyperGraph.
Example 13 (Signed 2-SuperHyperGraph: Corporate Collaboration)Let \(V_0 = \{\text{Manager}, \text{Engineer}, \text{Designer}\}\). Form \(\mathcal{P}^1(V_0)\), \(\mathcal{P}^2(V_0)\), \(\mathcal{P}^3(V_0)\) as above. Pick
\[ v_1 = \{\{\text{Manager}\}, \{\text{Engineer}\}\},\quad v_2 = \{\{\text{Engineer}\}, \{\text{Designer}\}\},\quad v_3 = \{\{\text{Manager}\}, \{\text{Designer}\}\}, \]
so \[ V = \{v_1, v_2, v_3\} \subseteq \mathcal{P}^2(V_0), \] and \[ e_1 = \{v_1, v_2\},\quad e_2 = \{v_1, v_3\},\quad e_3 = \{v_2, v_3\}. \] so \[ E = \{e_1, e_2, e_3\} \subseteq \mathcal{P}^3(V_0). \]
Define \(\varphi\) by:
| e₁ | e₂ | e₃ | |
|---|---|---|---|
| v₁ | +1 | 0 | −1 |
| v₂ | +1 | −1 | 0 |
| v₃ | 0 | +1 | +1 |
Interpreting +1 as collaborative incidence, −1 as competitive, and 0 as no incidence, hence \(\text{SWSuHyG}^{(2)} = (V, E, \varphi)\) models signed relations among hierarchical role-pairs.
Theorem 7 (Signed Degree Sum)Let \(\mathcal{H} = (V, E, \varphi)\) be a signed n-SuperHyperGraph, and define the signed degree of each supervertex \(v \in V\) by:
\[ \deg_\varphi(v) = \sum_{e \in E} \varphi(v, e). \]
Assume that each superedge \(e \in E\) has zero net incidence:
\[ \sum_{v \in V} \varphi(v, e) = 0 \quad \forall\, e \in E. \]
Then the sum of all signed degrees is zero:
\[ \sum_{v \in V} \deg_\varphi(v) = 0. \]
Proof.By definition,
\[ \sum_{v \in V} \deg_\varphi(v) = \sum_{v \in V} \sum_{e \in E} \varphi(v, e) = \sum_{e \in E} \sum_{v \in V} \varphi(v, e) = \sum_{e \in E} 0 = 0, \]
where the interchange of the summation order is justified by finiteness, and each inner sum vanishes by hypothesis. □
Definition 13 (Sign of a Simple Cycle)Let \(\mathcal{H} = (V, E, \varphi)\) be a signed SuperHyperGraph and let
\[ C = v_0, e_1, v_1, e_2, \ldots, e_k, v_k \quad (v_0 = v_k,\ k \geq 2) \]
be a simple cycle in the sense of Definition 3 (vertices \(v_0, \ldots, v_{k-1}\) and hyperedges \(e_1, \ldots, e_k\) all distinct). We define the sign of \(C\) by:
\[ \text{sgn}(C) = \prod_{i=1}^{k} \varphi(v_{i-1}, e_i)\, \varphi(v_i, e_i). \]
We call \(C\) positive if \(\text{sgn}(C) = +1\), and negative if \(\text{sgn}(C) = -1\).
Example 14 (Sign of a Simple Cycle in a Social Trust SuperHyperGraph)Let the base set of individuals be: \[ H = \{\text{Ayano}, \text{Tenma}, \text{Yuya}\}. \]
For \(n = 1\), set \[ V = \{\{\text{Ayano}\}, \{\text{Tenma}\}, \{\text{Yuya}\}\} \subseteq \mathcal{P}^1(H), \] \[ E = \{e_{AB}, e_{BC}, e_{CA}\} \subseteq \mathcal{P}^2(H), \]
where \[ e_{AB} = \{\{\text{Ayano}\}, \{\text{Tenma}\}\},\quad e_{BC} = \{\{\text{Tenma}\}, \{\text{Yuya}\}\},\quad e_{CA} = \{\{\text{Yuya}\}, \{\text{Ayano}\}\}. \]
Define the incidence sign function \(\varphi : V \times E \to \{-1, 0, +1\}\) by:
\[ \varphi(\{X\}, e_{XY}) = \begin{cases} +1, & \text{if X and Y trust each other}, \\ -1, & \text{if X and Y distrust each other}, \\ 0, & \text{otherwise}. \end{cases} \]
Suppose:
Consider the simple cycle \[ C : \{\text{Ayano}\} \xrightarrow{e_{AB}} \{\text{Tenma}\} \xrightarrow{e_{BC}} \{\text{Yuya}\} \xrightarrow{e_{CA}} \{\text{Ayano}\}. \]
By Definition, its sign is:
\[ \text{sgn}(C) = \left(\varphi(\{\text{Ayano}\}, e_{AB}) \cdot \varphi(\{\text{Tenma}\}, e_{AB})\right) \cdot \left(\varphi(\{\text{Tenma}\}, e_{BC}) \cdot \varphi(\{\text{Yuya}\}, e_{BC})\right) \cdot \left(\varphi(\{\text{Yuya}\}, e_{CA}) \cdot \varphi(\{\text{Ayano}\}, e_{CA})\right) \] \[ = (+1 \cdot +1) \cdot (-1 \cdot -1) \cdot (+1 \cdot +1) = +1. \]
Hence \(C\) is a positive simple cycle, indicating that the pattern of trust and distrust among Ayano, Tenma, and Yuya is structurally balanced.
Definition 14 (Switching Equivalence)Let \(\mathcal{H} = (V, E, \varphi)\) be a signed n-SuperHyperGraph. For any function \(\sigma : V \to \{\pm 1\}\), the switch of \(\mathcal{H}\) by \(\sigma\) is the signed n-SuperHyperGraph \(\mathcal{H}^\sigma = (V, E, \varphi^\sigma)\), where:
\[ \varphi^\sigma(v, e) = \sigma(v) \cdot \varphi(v, e) \quad \forall\, v \in V,\ e \in E. \]
Two signed n-SuperHyperGraphs \(\mathcal{H}_1\) and \(\mathcal{H}_2\) on the same \((V, E)\) are switching equivalent if there exists \(\sigma\) such that \(\mathcal{H}_2 = \mathcal{H}_1^\sigma\).
Example 15 (Switching Equivalence in a Signed 1-SuperHyperGraph)Let the base set be: \[ V_0 = \{A, B, C\}. \]
For \(n = 1\), set: \[ V = \{\{A\}, \{B\}, \{C\}\} \subseteq \mathcal{P}^1(V_0),\quad E = \{e_1, e_2, e_3\} \subseteq \mathcal{P}^2(V_0), \]
where \[ e_1 = \{\{A\}, \{B\}\},\quad e_2 = \{\{B\}, \{C\}\},\quad e_3 = \{\{C\}, \{A\}\}. \]
Define the incidence sign function \(\varphi : V \times E \to \{-1, 0, +1\}\) by:
\[ \varphi(v, e) = \begin{cases} +1, & v \in e \text{ and } e = e_1, \\ -1, & v \in e \text{ and } e \in \{e_2, e_3\}, \\ 0, & v \notin e. \end{cases} \]
Thus all incidences of \(e_1\) are positive, while those of \(e_2, e_3\) are negative. This signed 1-SuperHyperGraph \(\mathcal{H} = (V, E, \varphi)\) is balanced, since the unique simple cycle
\[ \{A\} \xrightarrow{e_1} \{B\} \xrightarrow{e_2} \{C\} \xrightarrow{e_3} \{A\} \]
has sign \((+1) \times (-1) \times (-1) = +1\).
Now define a switching function \(\sigma : V \rightarrow \{\pm 1\}\) by:
\[ \sigma(\{A\}) = +1,\quad \sigma(\{B\}) = +1,\quad \sigma(\{C\}) = -1. \]
The switched incidence function \(\varphi^\sigma(v, e) = \sigma(v) \cdot \varphi(v, e)\) then satisfies:
\[ \varphi^\sigma(v, e) = +1 \quad \forall\, v \in e,\ e \in E, \]
so that \(\mathcal{H}^\sigma\) has all positive incidences. Hence \(\mathcal{H}\) and \(\mathcal{H}^\sigma\) are switching equivalent.
Theorem 8 (Balance Characterization)A signed n-SuperHyperGraph \(\mathcal{H} = (V, E, \varphi)\) is balanced— i.e., every simple cycle has sign +1— if and only if it is switching equivalent to one whose incidence function satisfies:
\[ \varphi^\sigma(v, e) = +1 \quad \text{whenever } \varphi(v, e) \neq 0. \]
Proof.Fix a vertex \(v_0\) in each connected component. For any \(v \in V\), choose a simple path \(P\) from \(v_0\) to \(v\). Define:
\[ \sigma(v) = \prod_{(u, e) \in P} \varphi(u, e), \]
the product of the two incidences for each edge along \(P\). Balance (positivity of all cycle signs) guarantees \(\sigma(v)\) is path-independent. One then checks that in the switched graph \(\mathcal{H}^\sigma\), every nonzero incidence is \(+1\).
If \(\mathcal{H}^\sigma\) has \(\varphi^\sigma(v, e) = +1\) for all \(v \in e\), then the sign of any simple cycle—being the product of the switched incidences—equals \(+1\), so \(\mathcal{H}\) is balanced. □
Definition 15 (Signed Incidence Matrix)Order the vertices \(V = \{v_1, \ldots, v_p\}\) and hyperedges \(E = \{e_1, \ldots, e_q\}\). The signed incidence matrix \(B \in \{-1, 0, +1\}^{p \times q}\) is:
\[ B_{i,j} = \varphi(v_i, e_j), \quad 1 \leq i \leq p,\ 1 \leq j \leq q. \]
Example 16 (Signed Incidence Matrix in a Board Committee Network)Consider a board of four directors: \[ V = \{\text{Hiroshi}, \text{Yuki}, \text{Sakura}, \text{Takashi}\}. \]
They serve on three committees:
\[ e_1 = \{\text{Hiroshi}, \text{Yuki}\},\quad e_2 = \{\text{Yuki}, \text{Sakura}, \text{Takashi}\},\quad e_3 = \{\text{Hiroshi}, \text{Takashi}\}. \]
Define the incidence sign function \(\varphi : V \times E \to \{-1, 0, +1\}\) by:
\[ \varphi(v, e) = \begin{cases} +1, & \text{if director } v \text{ supports committee } e, \\ -1, & \text{if director } v \text{ opposes committee } e, \\ 0, & \text{if } v \text{ is not on } e. \end{cases} \]
Suppose their positions are:
Ordering \(V = (\text{Hiroshi}, \text{Yuki}, \text{Sakura}, \text{Takashi})\) and \(E = (e_1, e_2, e_3)\), the signed incidence matrix \(B \in \{-1, 0, +1\}^{4 \times 3}\) is:
\[ B = [\varphi(v_i, e_j)] = \begin{pmatrix} +1 & 0 & -1 \\ -1 & +1 & 0 \\ 0 & +1 & 0 \\ 0 & -1 & +1 \end{pmatrix}. \]
Theorem 9 (Rank of the Incidence Matrix)Let \(\mathcal{H} = (V, E, \varphi)\) be a signed n-SuperHyperGraph with incidence matrix \(B\). If \(\mathcal{H}\) has \(b\) balanced connected components (up to switching), then over \(\mathbb{R}\):
\[ \text{rank}(B) = |V| – b. \]
Proof.Decompose \(\mathcal{H}\) into its connected components. In each balanced component, the all-ones row vector lies in the left nullspace of the corresponding submatrix of \(B\), yielding exactly one linear dependency among its rows. Unbalanced components have full row rank. Summing these contributions gives:
\[ \text{rank}(B) = |V| – b. \quad \square \]
Theorem 10 (Cycle Sign Invariance under Switching)Let \(\mathcal{H} = (V, E, \varphi)\) be a signed n-SuperHyperGraph, and let \(\sigma : V \to \{\pm 1\}\). Define the switched incidence \(\varphi^\sigma(v, e) = \sigma(v)\, \varphi(v, e)\). Then for every simple cycle
\[ C : v_0, e_1, v_1, \ldots, e_k, v_k \quad (v_0 = v_k), \]
we have:
\[ \text{sgn}_{\varphi^\sigma}(C) = \text{sgn}_\varphi(C). \]
Proof.By definition:
\[ \text{sgn}_{\varphi^\sigma}(C) = \prod_{i=1}^{k} \varphi^\sigma(v_{i-1}, e_i)\, \varphi^\sigma(v_i, e_i) = \prod_{i=1}^{k} \left(\sigma(v_{i-1}) \varphi(v_{i-1}, e_i)\right)\left(\sigma(v_i) \varphi(v_i, e_i)\right). \]
Since each \(\sigma(v)\) appears exactly twice in this product (once for each end of each \(e_i\)), all factors of \(\sigma(v)\) cancel in pairs, leaving:
\[ \text{sgn}_{\varphi^\sigma}(C) = \text{sgn}_\varphi(C). \quad \square \]
Theorem 11 (Incidence Matrix under Switching)Let \(\mathcal{H} = (V, E, \varphi)\) have signed incidence matrix \(B\) with rows indexed by \(V\) and columns by \(E\). If \(\sigma : V \to \{\pm 1\}\) is a switching function, let \(D = \text{diag}(\sigma(v_1), \ldots, \sigma(v_{|V|}))\). Then the switched incidence matrix \(B^\sigma\) satisfies:
\[ B^\sigma = D B. \]
In particular, \[ \text{rank}(B^\sigma) = \text{rank}(B). \]
Proof.By definition, \[ (B^\sigma)_{v,e} = \varphi^\sigma(v, e) = \sigma(v) \varphi(v, e) = (D B)_{v,e}. \]
Since \(D\) is invertible over \(\mathbb{R}\), left-multiplication by \(D\) preserves rank. □
Theorem 12 (Two-Coloring Characterization of Balance)A signed n-SuperHyperGraph \(\mathcal{H} = (V, E, \varphi)\) is balanced if and only if there exists a function \(\sigma : V \to \{\pm 1\}\) and signs \(\{\varepsilon_e \in \{\pm 1\} : e \in E\}\) such that:
\[ \varphi(v, e) = \sigma(v)\, \varepsilon_e \quad \text{for all } v \in e. \]
Proof.(⇒) If \(\mathcal{H}\) is balanced, choose \(\sigma\) as in the proof of the Balance Characterization so that \(\varphi^\sigma(v, e) = +1\) for all \(v \in e\). Then \(\varphi(v, e) = \sigma(v) \cdot (+1)\), so \(\varepsilon_e = +1\).
(⇐) If such \(\sigma\) and \(\varepsilon_e\) exist, then for any simple cycle \(C\),
\[ \text{sgn}(C) = \prod_{i=1}^{k} \varphi(v_{i-1}, e_i)\, \varphi(v_i, e_i) = \prod_{i=1}^{k} \left(\sigma(v_{i-1}) \varepsilon_{e_i}\right)\left(\sigma(v_i) \varepsilon_{e_i}\right) = \prod_{i=1}^{k} \left(\sigma(v_{i-1}) \sigma(v_i)\right) \left(\varepsilon_{e_i}^2\right) = +1, \]
since each \(\varepsilon_{e_i}^2 = 1\) and each \(\sigma(v)\) appears twice. Hence all cycles are positive and \(\mathcal{H}\) is balanced. □
In this work, we have explored both the theoretical properties and practical applications of weighted SuperHyperGraphs and signed SuperHyperGraphs [21]. Weighted SuperHyperGraphs enable us to assign and analyze quantitative strengths to multi-level connections, supporting refined community detection, resource allocation, and resilience optimization in complex hierarchical networks.
Signed SuperHyperGraphs, by contrast, also allow us to model positive and negative influences within layered group interactions, facilitating rigorous study of cooperative versus adversarial dynamics, balance analysis, and conflict resolution.
Looking ahead, we plan to extend this framework to other variants of SuperHyperGraphs, develop efficient algorithms for their analysis, and pursue further real-world case studies. We also intend to integrate uncertainty and vagueness through extensions based on Fuzzy Sets [44–46], Intuitionistic Fuzzy Sets [47–49], Lexicographic max product of picture fuzzy graph [50], Neutrosophic Sets [51, 52], HyperFuzzy Sets [53–55], Plithogenic Sets [56–58], and related formalisms.
This work was conducted without any external financial support or sponsorship.
