Higher-order hypergraph from a network's clique structure
Source:R/hypergraph.R
build_hypergraph.Rdbuild_hypergraph() turns a network into a hypergraph by promoting its
cliques to hyperedges: every set of 3 to max_size nodes that are all
tied to each other becomes a hyperedge, kept with probability p, and
the pairwise edges can be kept as hyperedges of size 2. It takes a
netobject, a bare cograph_network, a simplicial_complex or an
adjacency or weight matrix, and returns a net_hypergraph, the input of
the hypergraph verbs such as hypergraph_measures(),
hypergraph_centrality() and clique_expansion().
A hyperedge built this way records that every pair of its nodes is tied
in the thresholded network; a pairwise network cannot show whether those
nodes also act together as a group. When group memberships are observed
directly, bipartite_groups() builds the hypergraph from them instead.
Each clique also contributes its smaller cliques: with max_size = 4, a
4-clique gives one hyperedge of size 4 and four of size 3.
Arguments
- net
The network: a
netobject, barecograph_network,simplicial_complex(its edges are read as ties of weight 1 and the cliques are found again up tomax_size), or a numeric or logical adjacency or weight matrix (nodes are namedV1,V2, ... when it has no row names). A tie counts in either direction, so a directed network is symmetrised, and self-loops are ignored.- p
The probability that each clique of 3 or more nodes becomes a hyperedge, a number in
[0, 1]; each clique is kept or dropped independently. Default1(every clique is kept). Pairwise edges are not sampled.- method
How hyperedges are found.
"clique"(default) promotes the cliques of the thresholded network."vr"and"rips"(a metric Vietoris-Rips construction) are not implemented and raise an error instead of falling back to"clique".- include_pairwise
Whether the pairwise edges of the thresholded network become hyperedges of size 2.
FALSEgives a hypergraph of hyperedges of size 3 or more only. DefaultTRUE.- max_size
The largest hyperedge size, at least 2. Default
3(triangles);4adds the 4-cliques, and so on. With2, only the pairwise edges remain (none, withinclude_pairwise = FALSE).- threshold
The cut-off that turns weights into ties: an edge is kept when its absolute weight is non-zero and at least
threshold, so negative weights count by their size. A negative value raises an error. Default0(every non-zero weight is a tie).- seed
An integer that makes the sampling reproducible when
0 < p < 1. The session's own random stream is left as it was. DefaultNULL.- x
For the
print()method: anet_hypergraph.- ...
Not used.
- object
For the
summary()method: anet_hypergraph.
Value
A net_hypergraph object. print() shows the numbers of nodes
and hyperedges, the size distribution and the settings, and returns
its input invisibly. summary() prints the counts with the mean and
largest hyperedge size, and returns a data frame with one row per node:
node and degree, the number of hyperedges that contain it. The
object holds:
hyperedgesA list of integer vectors, one per hyperedge, each the sorted indices of the nodes it spans; pairwise edges, when kept, come first.
incidenceAn integer matrix of nodes by hyperedges, 1 where a node belongs to a hyperedge and 0 elsewhere. Its row names are the node names and its column names
h1,h2, ...nodesThe node names.
n_nodes,n_hyperedgesThe numbers of nodes and hyperedges.
size_distributionA named integer vector with the number of hyperedges of each size, named
size_2,size_3, ...paramsThe settings used:
method,p,include_pairwise,max_size,thresholdandseed.
Details
The construction follows Burgio, Matamalas, Gomez and Arenas (2020) on
cooperation in networks and hypergraphs. The cliques are found with
build_simplicial(), and each clique of 3 or more nodes then goes
through an independent Bernoulli(p) trial that decides whether it
becomes a hyperedge. The pairwise edges are not sampled: with
include_pairwise = TRUE all of them are kept, so the hypergraph holds
the pairwise structure and the sampled higher-order interactions
together.
At the limits:
p = 0withinclude_pairwise = TRUEgives the thresholded pairwise network as a hypergraph of size-2 edges.p = 1withinclude_pairwise = FALSEgives only the hyperedges of size 3 or more, every clique of the network's clique complex up tomax_size.
References
Burgio, G., Matamalas, J. T., Gomez, S., & Arenas, A. (2020). Evolution of cooperation in the presence of higher-order interactions: from networks to hypergraphs. Entropy 22(7), 744. doi:10.3390/e22070744
See also
build_simplicial() (the clique enumeration),
bipartite_groups(), build_network().
Examples
set.seed(1)
n <- 8
adj <- matrix(stats::rbinom(n * n, 1, 0.5), n, n)
diag(adj) <- 0
adj <- (adj + t(adj)) > 0
rownames(adj) <- colnames(adj) <- LETTERS[seq_len(n)]
hg <- build_hypergraph(adj, p = 1, max_size = 3L)
print(hg)
#> Hypergraph: 8 nodes, 51 hyperedges
#> Size distribution:
#> size_2 : 23
#> size_3 : 28
#> Method: clique, p = 1.00, include_pairwise = TRUE, max_size = 3
summary(hg)
#> Hypergraph summary
#> Nodes: 8
#> Hyperedges: 51
#> Mean size: 2.55
#> Max size: 3
#> node degree
#> 1 A 17
#> 2 B 17
#> 3 C 23
#> 4 D 17
#> 5 E 17
#> 6 F 13
#> 7 G 13
#> 8 H 13