Abstract
Many natural, technological, and social systems incorporate multiway interactions, yet are characterized and measured on the basis of weighted pairwise interactions. In this article, I propose a family of models in which pairwise interactions originate from multiway interactions, by starting from ensembles of hypergraphs and applying projections that generate ensembles of weighted projected networks. I calculate analytically the statistical properties of weighted projected networks, and suggest ways these could be used beyond theoretical studies. Weighted projected networks typically exhibit weight disorder along links even for very simple generating hypergraph ensembles.
Abstract
Also, as the size of a hypergraph changes, a signature of multiway interaction emerges on the link weights of weighted projected networks that distinguishes them from fundamentally weighted pairwise networks. This signature could be used to search for hidden multiway interactions in weighted network data. I find the percolation threshold and size of the largest component for hypergraphs of arbitrary uniform rank, translate the results into projected networks, and show that the transition is second order. This general approach to network formation has the potential to shed new light on our understanding of weighted networks.
I. INTRODUCTION
Recent years have seen the growth of complex networks theory, a research area concerned with the general theory of systems of interacting elements [1] . Its relevance has been illustrated in a number of problems, such as infectious disease propagation [2] , the strength of social ties [3] , data routing in technological networks [4] , and motifs in biological networks [5] .
I. INTRODUCTION
An underlying driver for the growth of this field has been the increased availability of digitized information, which can be efficiently analyzed to uncover relations between system elements.
I. INTRODUCTION
A simplifying assumption that is made in networks theory is to characterize interactions as being exclusively pairwise (each interaction represented by a link between two nodes), often with an associated interaction intensity or weight, generating so-called weighted networks (also known as weighted graphs in Mathematics). The reason for this approach is that usually the information available for real systems is relatively limited. Despite these limitations, weighted networks have proven very useful, as a number of measurable network quantities have shown their relevance in application. Examples of these quantities are the distribution of node degree [6, 7] (number of links connecting to a node), optimal path lengths between network nodes [8] , and node clustering [9] (a measure of loops of length three). Other properties that depend on specific groups of links (e.g., network communities) have also proven quite useful [10, 11] .
I. INTRODUCTION
There are situations, however, where it is known that interactions extend to groups larger than two (multiway interactions), and one can use such information to create more accurate models, avoiding the possibility of oversimplified or misleading results. Examples of these situations are, for instance, networks of affiliations [12] [13] [14] , where nodes representing individuals connect to each other by virtue of their membership to a group such as their family or workplace colleagues; another example are folksonomies [15] , systems that encode information of triplets of the following three ingredients: objects, descriptors of the objects, and the individuals making the descriptions. Characterizing these examples by avoiding the pairwise simplification should lead to more informative and reliable results.
I. INTRODUCTION
Through various independent approaches, researchers focusing on problems of multiway interactions have proposed mechanisms by which pairwise network weights are generated as a consequence of these interactions (see, e.g. [12] and [16] ). For instance, in affiliation networks, when two nodes belong simultaneously to multiple groups, a feature called comembership, it is assumed that their relationship intensity is equal to the number of groups they both belong to. Perhaps the most appealing feature of these ideas is that they provide a unifying principle to the structure of some interacting systems: the presence of a group generates links, and being part of multiple groups generates weights. Surprisingly, these unifying ideas have received limited attention, perhaps because some of the mathematical models that are required are less straightforward than typical networks. Here, I focus on a systematic approach grounded in statistical mechanics to relate multiway interactions to weighted networks.
I. INTRODUCTION
To model multiway interactions, it is appropriate to use hypergraphs, which are generalizations of networks [17] . They are composed of a set of nodes and a set of hyperedges.
I. INTRODUCTION
Each hyperedge is a group of interconnected nodes (a clique), and the hypergraph is the collection of all the hyperedges and isolated nodes; networks are the specialization of hypergraphs in which all hyperedges are cliques each with only two nodes, i.e., links. The size of a hyperedge is called rank. In a statistical mechanics formulation (random) hypergraphs are called homogeneous when all hyperedges are equally likely to be present, or heterogeneous when each hyperedge has its own (possibly unique) probability to appear. For the examples mentioned above: in a folksonomy, for instance, hyperedges are all of rank three, whereas in affiliation networks, in principle, hyperedges can have different ranks; both examples are likely to be heterogeneous hypergraphs.
I. INTRODUCTION
The notion of hypergraphs generating weights is equivalent to constructing networks that represent a projection of a hypergraph. In other words, starting from a hypergraph, one can create an associated set of links that form a weighted projected network, where each link weight is given by the structure of the hypergraph and a projection rule. This construction suggests some intriguing possibilities: some data that is typically studied as a network may in fact emerge from underlying hypergraphs. If that is the case, it should be possible in principle to construct hypergraph models and accompanying projections that can fit observed data and narrow down its origins.
I. INTRODUCTION
In this article, I study homogeneous and heterogeneous entropy maximizing hypergraph ensembles of arbitrary uniform rank r and define general projections of hypergraphs that lead to ensembles of weighted projected networks. Some specific projection examples that have been used in the literature are explored [12, 16] , the properties of their respective projected networks calculated, and their interpretations briefly discussed. The percolation threshold and size of the largest connected component of hypergraphs of arbitrary uniform rank are also derived by use of the mapping between the Potts model and percolation theory [18] , and the results are then translated into the percolation properties of the projected networks.
I. INTRODUCTION
These results show that the transition is of second order. I find that, as a function of size, the link weights on weighted projected networks can display a signature of the presence of hidden multiway relations: when faced with a weighted network, this signature could provide indications that there is an associated hypergraph hidden in the data.
I. INTRODUCTION
The article is structured in the following way: Sec. II focuses on the general definitions of projections of hypergraphs onto networks, and on models of entropy maximizing ensembles of hypergraphs. With these results, in Sec. III I study in greater detail the statistical properties of general projected networks, as well as some concrete examples. These results suggest how to explore network data for possible signatures of multiway relations. Completing the results, Sec. IV focuses on the percolation properties of hypergraphs and their projected networks, and explores the general notion of sparsity. I finalize the article in Sec. V with some discussion and conclusions.
II. MAXIMUM ENTROPY HYPERGRAPHS AND THE NETWORK PROJEC-

TION
Consider a hypergraph, represented by σ, consisting of a set of nodes 1, . . . , N, and for each possible hyperedge of r nodes i 1 , . . . , i r , an indicator σ i 1 ,...,ir equal to 1 if the hyperedge is present and 0 if it is absent; all subindices i 1 , . . . , i r take non-repeated values from the set {1, . . . , N}. In general, a hypergraph does not require r to be the same for all hyperedges.
TION
However, for the sake of simplicity, I focus on single rank (all hyperedges have the same r) undirected hypergraphs, with the indicator σ i 1 ,...,ir symmetric under permutations of i 1 , . . . , i r (if one is interested in studying combinations of rank, one merely requires the introduction of the proper parameters for this, but the qualitative nature of the problem is the same as that studied here). Unweighted undirected networks correspond to r = 2.
TION
The general hypergraph projection onto a network is defined as a function P applied over hyperedges of σ that produces the adjacency matrix w ij for the weighted projected network G. Network G is formed by the same node set as σ, and its adjacency matrix is w ij . If a node does not belong to any hyperedge, it is isolated in both σ and G. For given σ, one can define the subset O ij (σ) := {(i 1 , . . . , i r )|(i 1 , . . . , i r ) ∈ σ ∧i ∈ {i 1 , . . . , i r }∧j ∈ {i 1 , . . . , i r }} of its hyperedges that include simultaneously nodes i and j. The kinds of projections studied here are of the type
TION
where o ij ≡ |O ij (σ)| is the size (cardinality) of O ij (σ). Thus, the weight of link ij in G only depends on the number of hyperedges that contain i and j, an intuitive choice, although certainly not the only possible model (in the literature, all examples I have found are limited to this kind of projection [12, 16, 19] ).
TION
On a concrete empirical case, the projection P should reflect the understanding of the relation between σ and G. Here, I present results for some reasonable sample choices of
TION
, where θ is the Heaviside step function (= 0 if the argument is 0 or less, and 1 otherwise). In addition, I show some features satisfied by the projected networks generated by a large class of projections with the general form of Eq. (1). To perform calculations, note that the additive projection can be written in terms of σ i 1 ,...,ir as
TION
whereas the nominal projection is represented by
TION
An illustration of P a for the case of r = 3 is shown in Fig. 1 .
TION
In the literature, both hypergraphs and projections have been used to study interaction data qualitatively embedded in complex networks theory, but without a sense of unification.
TION
For instance, the choice P n (O ij ) is implicit in work such as [19] ; there, if σ i 1 ,...,ir is interpreted as a specific motif (structural pattern), the model generates unweighted networks guaranteed to posses those motifs. In another approach, found in Refs. [20, 21] , each hypergraph (containing r = 2 and 3 only) treats each rank separately in that the interactions of nodes by way of pairs is counted independently to the triplet interactions, with no notion of projection onto a simple network. Refs. [12, 15] do consider projections in some form, but are limited by rank r of hypergraph and by the nature of the projection. Projection P a is in fact common [12] , and it is often used as a way to characterize the one-mode networks that emerge from bipartite graphs [16] (recent work also uses the notion of projection in the context of time evolving networks [22] ). Eq. (1) offers a unified way to relate networks and hypergraphs, which can be applied to the models cited above to develop additional understanding of the problems.
TION
To build unbiased statistical models, I adapt to hypergraphs the canonical ensemble approach developed in Ref. [23] . The set of all possible hypergraphs σ is given by {σ} conf (the ensemble), or in other words, {σ} conf is the union of all possible unique hypergraphs σ. To analytically formulate the ensemble problem, consider the entropy S, defined as
TION
where P (σ) represents the probability of a given configuration within the hypergraph ensemble, and the sum over configurations is equivalent to summing over all hyperedge combi-
TION
. The canonical ensemble approach finds the distribution P (σ) that maximizes S while satisfying conditions that define the ensemble of interest. Such conditions, say { X α }, with α an enumeration index, are taken to be of the form
TION
Finally, since P (σ) are probabilities, one must guarantee normalization, which translates into {σ} conf
TION
The solution to this problem (P (σ) satisfying the conditions above) is obtained via Lagrange multipliers. Each condition is related to a multiplier, and one solves the equations
TION
for P (σ), with η, β 1 , . . . the Lagrange multipliers. The solution to the problem can be expressed as
TION
The partition function Z, and H(σ) (defined as the Hamiltonian), are respectively given by
TION
and
TION
Among the simplest non-trivial problems one can address is that of the fully random hypergraph with equal probability for any hyperedge to exist. The constraint associated with this example is the requirement that there is a given average number of hyperedges, L r , over the hypergraph ensemble. Since L r for a given configuration σ is given by L r (σ) = (i 1 ,...,ir)∈σ σ i 1 ,...,ir , the set of constraints reduces to two Lagrange multipliers, one for the normalization, and another parameter, labelled β, for L r . Introducing this in Eq. (7) generates the Hamiltonian
TION
and the partition function 
TION
and p ≡ (1 + e β ) −1 is the probability for a hyperedge to be present, which is evident from writing L r / N r = (1 + e β ) −1 = p; p also corresponds to the expectation value of any hyperedge σ i 1 ,...,ir = {σ} conf σ i 1 ,...,ir P (σ) = (1 + e β ) −1 = p, i.e., the probability for any hyperedge to exist. The fact that all hyperedges are equally likely suggests referring to this case as the homogeneous hypergraph ensemble. The probability of a specific hypergraph configuration to be observed is given by Eq. (8), which in this case yields
TION
where the relations 1+e −β = (1−p) −1 and e −β = p(1−p) −1 have been used. The application of the P a and P n to the homogeneous ensemble is tackled below in a more general ensemble.
TION
The solution to the simple homogeneous problem above, helps to identify some basic features of the canonical approach, including quantities such as the probability of a hyperedge, and of a specific hypergraph σ. Building on this, one can construct the more general heterogeneous case, where each hyperedge has its own expectation σ i 1 ,...,ir . Thus, the Hamiltonian of Eq. (10) becomes
TION
In analogy with the homogeneous case, one defines
TION
The partition function becomes
TION
where p represents the hyperedge expectations {p 1,...,r , . . . , p N −r+1,...,N }. The probability of a hypergraph configuration σ is then
TION
which is the joint probability that hyperedges with σ i 1 ,...,ir = 1 are present, and those with 
III. APPLICATION OF THE HYPERGRAPH PROJECTION
Since only projections of the form P(O ij ) = P(o ij ) are considered here, the statistical properties of the projected networks depend on the statistical properties of o ij . It is most useful to focus on the distribution of o ij in the heterogeneous ensemble, φ ij (o ij , p), and determine how this translates into the homogeneous case (Table I summarizes 
III. APPLICATION OF THE HYPERGRAPH PROJECTION
where δ(x, y, . . . , z) is the Kronecker delta which can have two or more arguments, and is equal to 1 if all the arguments are equal, and 0 otherwise. In the sum above, only those configurations for which delta is 1 contribute to φ ij (o ij , p), and this occurs only when there are exactly o ij hyperedges in σ that include ij.
III. APPLICATION OF THE HYPERGRAPH PROJECTION
To perform the calculation, note the independence of each component of p in Eq. (17).
III. APPLICATION OF THE HYPERGRAPH PROJECTION
This allows factoring the sum over configurations in Eq. (18) into a product of i) the configurations of hyperedges T ij (N, r), which cannot affect the delta, and ii) the configurations of hyperedges T ij (N, r), which can. The hyperedges (i 1 , . . . , i r ) ∈ T ij (N, r) each contribute a factor
III. APPLICATION OF THE HYPERGRAPH PROJECTION
..,ir = 1. Therefore, the remaining factors of Eq. (18) lead to
III. APPLICATION OF THE HYPERGRAPH PROJECTION
where V ij and O ij are the unions of all possible sets V ij (σ) and O ij (σ), respectively, and
III. APPLICATION OF THE HYPERGRAPH PROJECTION
Equation (19) has been expressed in a way that makes it straightforward to explain and convert into an algorithm for calculation, as I attempt to explain now. The expression can be described in the following terms: i) separate the hyperedges from T(N, r) into two groups, one that can influence ij over all possible configurations, namely T ij (N, r), and another that cannot (T ij (N, r)), ii) identify out of T ij (N, r) the hyperedges of σ visiting i and j, The average of o ij can be determined from Eq.
III. APPLICATION OF THE HYPERGRAPH PROJECTION
which fits intuition, stating that the expectation of the number of hyperedges visiting the pair ij, is the sum of expectations of each hyperedge that can visit ij to be present over the ensemble.
III. APPLICATION OF THE HYPERGRAPH PROJECTION
In the homogeneous case, where
III. APPLICATION OF THE HYPERGRAPH PROJECTION
a binomial distribution with o ij = N −2 r−2 p ( Fig. 2(a) ). Both this average, and more generally Eq. (20), have an interesting interpretation explained below regarding signatures of multiway interactions in observational studies. Another noteworthy fact exhibited by Eq. (21), even in this very simple case of homogeneous p, is that o ij does not have a fixed value but instead follows a probability distribution consequence of the projection process.
III. APPLICATION OF THE HYPERGRAPH PROJECTION
Some general features of P can now be described if one conditions it to be a monotonic smooth projection, satisfying the inverse function theorem. This condition offers a way to formally write the distribution of w ij from the distribution of o ij because there is a one-toone relation between the two quantities. Furthermore, one can make use of the monotonicity in both the discrete and continuous variable cases. For the discrete case, defining the distribution µ ij (w ij , p) of weights, it is simple to see that µ ij (w ij , p) = φ ij (P(o ij ), p) and the set of possible w ij is obtained by applying Eq. (1) to the domain of o ij . In the continuous case, introducing the densities
III. APPLICATION OF THE HYPERGRAPH PROJECTION
the change of variables theorem for probability distributions implies
III. APPLICATION OF THE HYPERGRAPH PROJECTION
where P ′ is the derivative of P. The additive projection P a satisfies monotonicity in a trivial way because it is just the identity function. However, a large class of functions also satisfy monotonicity, including all power law and logarithmic growth functions. The nominal projection, on the other hand, does not satisfy the condition because any value of o ij ≥ 1 leads to the same weight w ij = 1, and thus the inverse of P n is not uniquely defined.
III. APPLICATION OF THE HYPERGRAPH PROJECTION
Regarding the influence ofφ ij , if this distribution is sufficiently narrow in comparison to the shape of P, asymptotic estimates ofμ ij (w ij , p) and it properties (e.g., moments) can be straightforwardly obtained. Certainly, one could argue that for there to be a weighted network with the behavior described here, it is also necessary to impose conditions on the type of projection that applies. This is indeed true, but the conditions necessary to obtain correlation between w ij and N are relatively modest and well justified in numerous circumstances. For instance, here I focus on a monotonically increasing P, which proves sufficient. Furthermore, it is even acceptable to have a p ij that decreases with N, just as long as the decrease is slower than
III. APPLICATION OF THE HYPERGRAPH PROJECTION
. The level of detail known about P and p ij goes hand in hand with the detail that can be learned about the multiway interactions. For instance, if p ij = p (homogeneous) and P = P a , then ln w ij vs. ln N would yield the value of r. If, on the other hand, all one knows is that P is monotonically increasing, the ln w ij vs. ln N would offer an estimate of the combined effects of P and p ij . Overall, the present discussion suggest that in the case of evolving networks with correlations between N and the set of w ij , it is reasonable to suspect multiway interactions active in the background, and further exploration for evidence of such interactions is well justified. These results are general, and do not need to be specialized into a particular example. However, if one is interested in using the results of this article as a method to attempt to determine quantitative details of the multiway interactions that may be present, additional work is needed to extend the results to more detailed and perhaps slightly different situations.
III. APPLICATION OF THE HYPERGRAPH PROJECTION
The two projections P a and P n can now be explained further. For P a , the properties of w ij are those of o ij , and thus already calculated. The other property to describe is the so-called strength s i of node i, equal to j o ij . It is intuitively helpful to calculate the distribution of strengths ξ i (s i , p) by making use of the relation between s i and ℓ i , the number of hyperedges visiting i. These two quantities relate via s i = (r − 1)ℓ i , and one can determine the distribution ζ i (ℓ i , p) of ℓ i and from it compute ξ i (s i , p). Note that while s i is a property of the graph, ℓ i is a property of the hypergraph. Once again, the independence of the components of p simplifies the sum over configurations {σ} conf (notation in Table II ). The hyperedges that could affect ℓ i belong to T i (N, r), the collection of all hyperedges visiting i in T(N, r), and
III. APPLICATION OF THE HYPERGRAPH PROJECTION
..,ir )P (σ, p), one can quickly conclude that
III. APPLICATION OF THE HYPERGRAPH PROJECTION
where Λ i is the ensemble of configurations λ i (σ), and
III. APPLICATION OF THE HYPERGRAPH PROJECTION
where s i takes values 0, r − 1, 2(r − 1), . . . , (r − 1)
III. APPLICATION OF THE HYPERGRAPH PROJECTION
. Once again, an equivalence between hyperedge sets and combinatorics can be drawn: 
III. APPLICATION OF THE HYPERGRAPH PROJECTION
and
III. APPLICATION OF THE HYPERGRAPH PROJECTION
For the homogeneous case, ζ i (ℓ i , p) = (
III. APPLICATION OF THE HYPERGRAPH PROJECTION
Therefore,
III. APPLICATION OF THE HYPERGRAPH PROJECTION
and s i = (r − 1)
III. APPLICATION OF THE HYPERGRAPH PROJECTION
p (see Fig. 2(b) ).
III. APPLICATION OF THE HYPERGRAPH PROJECTION
The nominal interaction P n needs a different treatment. Note that under this projection, w ij can be either 0 or 1. To determine the probability for w ij , π ij (w ij , p), one merely needs to determine the probabilities that o ij is either 0 or
III. APPLICATION OF THE HYPERGRAPH PROJECTION
In the homogeneous case,
III. APPLICATION OF THE HYPERGRAPH PROJECTION
Both Eqs. (28) and (29) are closely related to the average number of connections for each node of a projected network, as explained next.
III. APPLICATION OF THE HYPERGRAPH PROJECTION
For any weighted projected network generated from a P satisfying o ij > 0 ⇒ w ij > 0 and o ij = 0 ⇒ w ij = 0, such as P a and P n , the number of connections k i visiting node i are characterized by ψ i (k i , p), the distribution of k i (an expanded and pedagogical exposition of the calculation and its consequences can be found in [26] ). The degree can be either 0 or take any value from r − 1 Table III), one can proceed in a similar way as before: in configuration σ, the set of hyperedges visiting i and producing degree k i is K i (σ). This means that hyperedges in K i (σ) visit exactly k i nodes and node i. It is interesting to note that another configuration σ ′ , associated with
III. APPLICATION OF THE HYPERGRAPH PROJECTION
, with a different set and/or number of hyperedges can lead to the same k i , because these hyperedges still visit the same number of nodes k i (see Fig. 3 for an illustration). With this definition, one can write
III. APPLICATION OF THE HYPERGRAPH PROJECTION
where K i is the union of all possible sets K i (σ), and the complement set K i (σ) satisfies
III. APPLICATION OF THE HYPERGRAPH PROJECTION
Since the number of hyperedges is not fixed across members of i (σ) and K i (ℓ i ) to represent, respectively, the sets K i (σ) involving exactly ℓ i hyperedges and their unions, one can write
III. APPLICATION OF THE HYPERGRAPH PROJECTION
The sets K i (ℓ i ) are only subsets of Λ i in which the ℓ i hyperedges involve exactly i and k i other nodes. Finally, it is possible to exploit one more symmetry that facilitates an algorithmic understanding of ψ i (k i , p): the sets that make up K i (ℓ i ) involve several possible distinct node sets. However, one can further segregate these sets by the specific nodes in them.
III. APPLICATION OF THE HYPERGRAPH PROJECTION
Hence, if one takes a set, ρ(k i ), of k i specific nodes and i, there are several configurations in which their associated K (ℓ i ) i (σ) contain ℓ i hyperedges visiting only those nodes. Thus, a configuration with specific ρ(k i ) nodes connected to i, using ℓ i hyperedges is labelled
III. APPLICATION OF THE HYPERGRAPH PROJECTION
(σ), and the union of configurations is labelled I i (ρ(k i ), ℓ i ) . The union of all sets I i (ρ(k i ), ℓ i ) (which are non-intersecting) is equal to K i (ℓ i ). This leads to the final expression (32) where , and
III. APPLICATION OF THE HYPERGRAPH PROJECTION
; the later is the result of a combinatorial problem that can be defined in terms of general graph theory. Specifically, Q r−1 (k i , ℓ i ) corresponds to the number of distinct hypergraphs that can be constructed with k i nodes and ℓ i hyperedges of rank r − 1, and each node belongs to at least one of the hyperedges [26] . In fact, each I
III. APPLICATION OF THE HYPERGRAPH PROJECTION
can be mapped to each one of these hypergraphs. To determine k i (p) , it is convenient to use the relation
III. APPLICATION OF THE HYPERGRAPH PROJECTION
By first summing over a single j, one notices that only hyperedges in T ij (N, r) must be considered in detail. Given that
III. APPLICATION OF THE HYPERGRAPH PROJECTION
one riley01@example.org. APPLICATION OF THE HYPERGRAPH PROJECTION
When compared with Eq. (28), it becomes evident that each link ij contributes to k i independently.
III. APPLICATION OF THE HYPERGRAPH PROJECTION
In the homogeneous case, making use of the combinatorial results presented, one obtains ( Fig. 2(c) )
III. APPLICATION OF THE HYPERGRAPH PROJECTION
Without diving into too much detail, Q r−1 (k i , ℓ i ) can be calculated via the inclusionexclusion principle of combinatorics [26, 29] , which produces
III. APPLICATION OF THE HYPERGRAPH PROJECTION
Among the identities satisfied by Q r−1 (k, ℓ) [26] , one finds that (
III. APPLICATION OF THE HYPERGRAPH PROJECTION
, which is used to show normalization of ψ i (k i , p). Another identity,
III. APPLICATION OF THE HYPERGRAPH PROJECTION
where the brackets are equal to π ij (w ij = 1, p) from Eq. (29) (see Fig. 2(d) ). This average can also be calculated directly from Eq. (35) [26] .
III. APPLICATION OF THE HYPERGRAPH PROJECTION
To conclude this section, it is useful to point out how the previous results can be connected with concrete problems. The logic is similar to that found in [23, 27] , in which the ensemble is chosen to fit observations. In the framework presented here, it is possible to choose the hypergraph ensemble to fit hypergraph properties (such as Eqs. (20) or (25)), projected network properties (Eqs. (26) or (35)), or a combination of both (as long as it is well defined); the choice comes down to practical considerations such as the available data one intends to fit, or the belief that certain mechanisms may be at play and therefore must be part of the model. Once an ensemble is defined (satisfying the assumptions of hyperedges which are non-interacting, undirected, and with uniform rank), the expressions derived above for the heterogeneous ensemble apply, but an additional set of constraints emerges for the p i 1 ,...,ir guaranteeing that the entropy is maximized, distinguishing the situation from that of the fully heterogeneous ensemble, where each p i 1 ,...,ir is free to have any value between 0 and 1.
III. APPLICATION OF THE HYPERGRAPH PROJECTION
As an example, consider the ensemble that specifies strengths s i on the projected net-works with projection P a . This can be constructed from the Hamiltonian
III. APPLICATION OF THE HYPERGRAPH PROJECTION
This ensemble is completely specified by calculating the relation between σ i 1 ,...,ir , by definition equal to p i 1 ,...,ir , and the set of parameters {β 1 , . . . , β N }. After determining P (σ), one can compute σ i 1 ,...,ir = {σ} conf σ i 1 ,...,ir P (σ) to find
III. APPLICATION OF THE HYPERGRAPH PROJECTION
where the parameters satisfy Eq. (26), and therefore
III. APPLICATION OF THE HYPERGRAPH PROJECTION
One way to understand this result is from the relation dp i 1 ,...,ir = −(r − 1)
III. APPLICATION OF THE HYPERGRAPH PROJECTION
If only β ig changes (by, say, dβ ig ), hyperedges without node i g are unaffected, and those with i g all increase in probability proportionally to dβ ig . As in Ref. [23] , the β i can be taken from a distribution, leading in turn to a distribution of s i . This can be used to obtain a desired distribution of s i as dictated by the problem.
IV. PERCOLATION PROPERTIES AND SPARSE CASES
Another important aspect of the hypergraph ensemble and its projected networks is their percolation properties. To calculate these, one can use the equivalence, first pointed out by Fortuin and Kasteleyn [18] , between percolation and the mean-field q-states Potts model at q → 1. The solution to the later model consists of determining the state of the nodes, and whether there is a phase transition. The solution and its properties can be obtained by studying the model's Helmholtz free energy. A detailed development of equivalence of the models can be found in Refs. [27, 28] ; here, I set up the calculation starting at the free energy and develop the percolation properties from there. I consider the homogeneous case only, although it is possible to solve some forms of heterogeneous models. In order to find the Helmholtz free energy of the system, one must first determine the partition function Z q . In this model, it can be written on the basis of all configurations of state values u i , or in terms of the set of numbers {N u } u=1,...,q . Using the later set of variables, and taking into account the multiplicity in the choices for each node state, one riley01@example.org. PERCOLATION PROPERTIES AND SPARSE CASES
where the inverse temperature parameter β is absorbed into J. In the canonical ensemble, the free energy is given by F q = − ln Z q . When the interaction J is too weak to keep the nodes ordered collectively in groups of common states, the solution to the problem is expected to be symmetric, i.e. c u = 1/q (all states are equally occupied). However, as the interaction strengthens, one would expect that symmetry is broken and one state (say u = 1) becomes dominant. By these arguments, F q can be sought by introducing the ansatz
IV. PERCOLATION PROPERTIES AND SPARSE CASES
wheref q is the fractional size of the system in state u = 1, and the condition u c u = 1 is automatically satisfied. This leads to
IV. PERCOLATION PROPERTIES AND SPARSE CASES
(1+(q−1)fq ) ln
IV. PERCOLATION PROPERTIES AND SPARSE CASES
In the thermodynamic limit (N → ∞), the Laplace method of integration can be applied to Z q [30] . Once applied, F q = − ln Z q yields to leading order
IV. PERCOLATION PROPERTIES AND SPARSE CASES
where f q is the value off q for which the exponent of the argument of the Z q integral is maximized. Explicitly, f q is obtained by equating to 0 the first derivative with respect tof q of the exponent in Eq. (45), and using c 1 (f q ) and c u (f q ) to refer to the the fractions c u from
IV. PERCOLATION PROPERTIES AND SPARSE CASES
Eq. (44) evaluated at u = 1 and u = 1, respectively. Thus, f q must satisfy
IV. PERCOLATION PROPERTIES AND SPARSE CASES
This is the self-consistency equation for the fractional size of the component of broken symmetry. For q = 1, f ≡ f q=1 is the fractional size of the percolating spanning cluster.
IV. PERCOLATION PROPERTIES AND SPARSE CASES
Note that f q = 0 is also a solution to Eq. (47), but its stability breaks down when the second derivative of the exponent of the integrand of Z q changes sign. The value of J for which the sign change occurs is given by the relation
IV. PERCOLATION PROPERTIES AND SPARSE CASES
where q = 1 has already been introduced (otherwise the solution would be the same but with N/q in place of N everywhere).
IV. PERCOLATION PROPERTIES AND SPARSE CASES
In the thermodynamic limit, one can derive a compact equation for f and arbitrary (
IV. PERCOLATION PROPERTIES AND SPARSE CASES
Close to percolation, it is justified to write J = λJ c , with λ ≥ 1 and J c from Eq. (48). By L'Hopital's rule, for the dominant term in N, the size of the largest component emerges as
IV. PERCOLATION PROPERTIES AND SPARSE CASES
which generalizes expressions for f for r = 2 and 3 in Refs. [20, 21] (these authors tackle the percolation question to illustrate ideas different than those explored here). To test this expression, it is customary to define the percolation problem with respect to a network (or hypergraph) that is not complete, but instead is already diluted. By defining the rescaling z = p/p max where typically p max ≪ 1, the original undiluted hypergraph is z = 1, and percolation occurs at z c = p c /p max , or if using λ max , z c = 1/λ max (see Fig 4(a) ).
IV. PERCOLATION PROPERTIES AND SPARSE CASES
The percolation transition can be shown to be second order by expanding both sides of Eq. (50), which leads to
IV. PERCOLATION PROPERTIES AND SPARSE CASES
For small f , close to the percolation transition, only the first few terms on both sides of the equality are relevant. Retaining up to second order
IV. PERCOLATION PROPERTIES AND SPARSE CASES
which produces
IV. PERCOLATION PROPERTIES AND SPARSE CASES
clearly indicating a continuous transition, in the same universality class of regular network percolation, which diverges at the transition with exponent 1. This result is known in the literature [20] .
IV. PERCOLATION PROPERTIES AND SPARSE CASES
The previous results focus on hypergraphs, but their relevance to projected networks is not explicitly clear. To clarify this, it is sufficient to explore the properties of φ ij (o ij , p).
IV. PERCOLATION PROPERTIES AND SPARSE CASES
For this, it is useful to have in mind the asymptotic relations N . Inserting p = λp c in Eq. (21), and taking the limit N ≫ o ij , the re-
IV. PERCOLATION PROPERTIES AND SPARSE CASES
with average λ/N (Fig. 4(b) ). Therefore, as N increases, the weights on the links vanish, signalling the fact that in this dilute regime, the hypergraph and projected networks are virtually the same, and hyperedges are non-overlapping asymptotically. Thus, one only needs to calculate the hypergraph percolation properties to be able to write down the projected network percolation properties. In this sparse regime, the other distributions discussed above have particular forms: for the hypergraph, the distribution of hyperedges visiting a node becomes ζ (Fig. 4(c) ). From these results, the meaning of λ emerges as the parameter that measures the average node strength of the projected network. Finally, the degree distribution can be calculated if one keeps in mind that in the sparse limit, the probability that hyperedges overlap is minimal, and therefore, one expects that only the minimum number of hyperedges ℓ i → ⌈k i /(r − 1)⌉ contribute to the distribution. There are subtleties present in explicitly calculating
IV. PERCOLATION PROPERTIES AND SPARSE CASES
is not a multiple of r − 1 because hyperedges are forced to overlap in this case, and thus to avoid further details, I only write the unevaluated result (Fig. 4(d) ). However, the calculations are not prohibitive, and are derived in detail in [26] .
IV. PERCOLATION PROPERTIES AND SPARSE CASES
The sparse regime close to percolation is not the only possible sparse regime. To be concrete, note that for p close to p c , the average node strength is constant, but the average overlap on projected links scales as N −1 , so the larger the network, the less interaction present along the links. However, one can consider a regime in which o ij ∼ λ/N is constant, and in this regime node strength increases with N. Both of these regimes are "sparse" in the sense that p vanishes asymptotically, but each regime has specific properties.
IV. PERCOLATION PROPERTIES AND SPARSE CASES
Generally, these sparse regimes can be defined based on any sensible property, and lead to interesting behavior. Finally, for the dense regime (p constant), the interesting effect of growth of o ij vs. N emerges, which is a unique feature of this model, and the signature that multiway interactions are potentially present.
V. CONCLUSIONS
In conclusion, in this article I present a model of hypergraphs and associated weighted projected networks that offers a concise and intuitive picture of hypergraphs, networks, and weights. By using statistical mechanics concepts, together with combinatorial tools, I have been able to determine some basic features of homogeneous and heterogeneous projected networks that offer concrete tests to determine whether a network that has been empirically measured may bear the signature of multiway (group) interactions. The general idea of using the projection of a hypergraph onto a network, which has not been studied systematically to the author's knowledge until this article, deserves a close look to determine further properties 

{'paper_id': '28113979', 'title': 'Weighted projected networks: mapping hypergraphs to networks', 's2_url': 'https://api.semanticscholar.org/CorpusID:28113979', 'source': 'S2ORC'}