Clique expansion of a hypergraph

Projects a net_hypergraph to a standard pairwise netobject (the clique expansion - also called the "downgrade" of a hypergraph to a dyadic graph). Each hyperedge of size k contributes 1 (or its weight) to every pair of its members. The resulting edge weight W[i, j] equals the number of hyperedges containing both i and j (binary incidence) or the sum of incidence products (weighted incidence).

Usage

clique_expansion(hg, weighted = TRUE)

Arguments

hg: A net_hypergraph object as returned by build_hypergraph() or bipartite_groups().
weighted: Logical. If TRUE (default), use the hypergraph's incidence values directly (so weighted hypergraphs from bipartite_groups() produce weighted projections). If FALSE, binarise the incidence first so W[i, j] is just the count of shared hyperedges.

Value

A netobject (also cograph_network) with method = "clique_expansion", undirected, with weighted symmetric adjacency W = incidence %*% t(incidence) and zero diagonal.

Details

The clique expansion is the standard "loss-y but lossless-on-pairwise" projection: it preserves which pairs co-occurred and how often but discards the higher-order grouping. Comparing clique_expansion(hg) to a directly-estimated pairwise network (e.g. via cooccurrence() on the same data) quantifies how much information was carried by the hyperedge structure.

Computed in one BLAS call via tcrossprod(incidence); runs in O(n_nodes^2 * n_hyperedges) time, fast for typical sizes.

Closes the I/O cycle: event data -> bipartite_groups() -> clique_expansion() -> any function that accepts a netobject (centrality, bootstrap, clustering, plotting via cograph).

Note

(experimental) Validated against tcrossprod(incidence) with zero diagonal. No external R package exposes clique expansion as a primitive; the implementation is a direct one-line restatement of the definition.

References

Tian, Y., & Zafarani, R. (2024). Higher-order network analysis methods. SIGKDD Explorations 26(1), Section 5.1.5.

Examples

df <- data.frame(
  player  = c("A", "B", "C", "A", "B", "D", "C", "D", "E"),
  session = c("S1", "S1", "S1", "S2", "S2", "S3", "S3", "S3", "S3")
)
hg  <- bipartite_groups(df, player = "player", group = "session")
net <- clique_expansion(hg)
net$weights
#>   A B C D E
#> A 0 2 1 0 0
#> B 2 0 1 0 0
#> C 1 1 0 1 1
#> D 0 0 1 0 1
#> E 0 0 1 1 0