hypergraph_centrality() scores how central each node of a hypergraph
is, with up to three eigenvector centralities from Benson (2019):
clique-motif (CEC, "clique"), Z-eigenvector (ZEC, "Z") and
H-eigenvector (HEC, "H"). CEC flattens the groups into pairs by clique
expansion and takes the eigenvector centrality of that pairwise graph.
ZEC and HEC work on the hyperedges directly: a node's score grows with
the product of the scores of the other members of each hyperedge it
belongs to. It reads a net_hypergraph from build_hypergraph() or
bipartite_groups().
The variants can rank the nodes differently, since CEC counts shared
memberships pair by pair while ZEC and HEC weigh each group as a whole.
ZEC and HEC are defined for uniform hypergraphs only, where every
hyperedge of two or more members has the same size. On a disconnected
hypergraph, compare scores within one component: CEC gives zero to every
component whose leading eigenvalue is below the largest, and the
Z-eigenvector is not unique.
hypergraph_measures() describes the structure the scores come from.
Arguments
- hg
The hypergraph: a
net_hypergraphfrombuild_hypergraph()orbipartite_groups().- type
The centralities to compute, any of
"clique","Z"and"H", returned in the order given. Default"clique"."Z"and"H"need a uniform hypergraph (every hyperedge with two or more members has the same size); on any other they raise an error of classnestimate_nonuniform_hypergraph.- max_iter
The largest number of power-iteration steps for
"Z"and"H". Default1000."clique"is solved directly and ignores it.- tol
The convergence tolerance for
"Z"and"H": the iteration stops once the L1 change between successive iterates is below it. Default1e-8. An iteration that does not get there withinmax_itersteps, or that stops without solving the eigen-equation, warns with classnestimate_no_converge.- normalize
How each vector is scaled.
TRUE(default) gives it unit Euclidean (L2) norm;FALSEdivides it by its largest absolute entry, so the top node scores 1, the scale ofigraph::eigen_centrality().
Value
A named list with one numeric vector per requested type, in the
order given, each with one value per node of hg, named by the nodes.
A hypergraph with no hyperedges, or with only one-member hyperedges,
gives all-zero vectors, and one without nodes empty vectors.
Details
Clique-motif eigenvector centrality (CEC) is the leading eigenvector
of the clique-expanded pairwise graph \(W\) with
\(W_{ij} = |\{e : i, j \in e\}|\), the number of hyperedges two
nodes share. It reads membership only, so incidence weights are ignored:
it equals igraph::eigen_centrality() on
clique_expansion(hg, weighted = FALSE), and on clique_expansion()'s
default output only for an unweighted hypergraph. The vector is solved
directly from a symmetric eigendecomposition of each connected component
(Perron-Frobenius makes the leading eigenvalue of a connected component
simple), not by power iteration, which oscillates when the clique
expansion is bipartite (for example a star of pairs). When several
components share the largest eigenvalue, the result is the projection of
the uniform vector onto their joint leading eigenspace; components with a
smaller leading eigenvalue score zero.
Z-eigenvector centrality (ZEC) solves the eigen-equation on the
hyperedge tensor,
$$\lambda\, x_i \;=\; \sum_{e \ni i}\; \prod_{j \in e,\; j \neq i} x_j,$$
by a shifted power iteration (a variant of SS-HOPM, Kolda & Mayo, 2011,
that normalises the tensor step before adding the shift). Tensor products
and normalisation are evaluated in log space, so the centralities stay
finite and normalised for large hyperedges. Besides the step tolerance,
the iteration checks that the eigen-equation residual is small (relative
residual at most max(sqrt(tol), 1e-6)); otherwise it warns.
H-eigenvector centrality (HEC) solves, by the same iteration, $$\lambda\, x_i^{k-1} \;=\; \sum_{e \ni i}\; \prod_{j \in e,\; j \neq i} x_j.$$
Uniform hypergraphs only. Benson (2019) defines ZEC and HEC for
\(k\)-uniform hypergraphs. With mixed sizes the right-hand side mixes
polynomial degrees, so the equation has no scale-free solution: the
vector satisfies it only at the normalisation chosen inside the
iteration. Hyperedges with one member contribute nothing and are ignored
by the uniformity check. For mixed sizes use "clique", or keep one
size with build_hypergraph() (include_pairwise = FALSE).
Disconnected hypergraphs. The Z-eigenvector is not unique when the
hypergraph has several components: different iterations can solve the
equation with different vectors, so compare "Z" values within one
connected hypergraph only.
Note
The "clique" (CEC) variant is validated against
igraph::eigen_centrality() (cosine ~ 1). The "Z" and "H" variants
are experimental: they are validated only against a clean-room
list-based tensor power iteration (the same operator with a different
loop structure), as no R package exposes tensor eigenvectors for an
independent comparison.
References
Benson, A. R. (2019). Three hypergraph eigenvector centralities. SIAM Journal on Mathematics of Data Science 1(2), 293-312. arXiv:1807.09644.
Kolda, T. G., & Mayo, J. R. (2011). Shifted power method for computing tensor eigenpairs. SIAM Journal on Matrix Analysis and Applications 32(4), 1095-1124. doi:10.1137/100801482
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", "session")
hypergraph_centrality(hg)
#> $clique
#> A B C D E
#> 0.5345225 0.5345225 0.5345225 0.2672612 0.2672612
#>
# Z and H need a uniform hypergraph: here every session has three players
df3 <- data.frame(
player = c("A", "B", "C", "A", "B", "D", "C", "D", "E"),
session = c("S1", "S1", "S1", "S2", "S2", "S2", "S3", "S3", "S3")
)
hypergraph_centrality(bipartite_groups(df3, "player", "session"),
type = c("clique", "Z", "H"))
#> $clique
#> A B C D E
#> 0.5127870 0.5127870 0.4559848 0.4559848 0.2413603
#>
#> $Z
#> A B C D E
#> 0.5345225 0.5345225 0.4364358 0.4364358 0.2182179
#>
#> $H
#> A B C D E
#> 0.4867656 0.4867656 0.4556438 0.4556438 0.3330103
#>