xgi.algorithms.centrality

Algorithms for computing the centralities of nodes (and edges) in a hypergraph.

Functions

xgi.algorithms.centrality.clique_eigenvector_centrality(H, tol=1e-06)[source]

Compute the clique motif eigenvector centrality of a hypergraph.

Parameters:

H (Hypergraph) – The hypergraph of interest.
tol (float, optional) – The tolerance when computing the eigenvector. By default, 1e-6.

Returns:

Centrality, where keys are node IDs and values are centralities. The centralities are 1-normalized.

Return type:

dict

See also

clique_eigenvector_centrality

References

Three Hypergraph Eigenvector Centralities, Austin R. Benson, https://doi.org/10.1137/18M1203031

xgi.algorithms.centrality.node_edge_centrality(H, f=<function <lambda>>, g=<function <lambda>>, phi=<function <lambda>>, psi=<function <lambda>>, max_iter=100, tol=1e-06)[source]

Computes the node and edge centralities

Parameters:

H (Hypergraph) – The hypergraph of interest
f (lambda function, optional) – The function f as described in Tudisco and Higham. Must accept a numpy array. By default, \(f(x) = x^2\).
g (lambda function, optional) – The function g as described in Tudisco and Higham. Must accept a numpy array. By default, :math`g(x) = sqrt{x}`.
phi (lambda function, optional) – The function phi as described in Tudisco and Higham. Must accept a numpy array. By default \(\phi(x) = x^2\).
psi (lambda function, optional) – The function psi as described in Tudisco and Higham. Must accept a numpy array. By default: \(\psi(x) = \sqrt{x}\).
max_iter (int, optional) – Number of iterations at which the algorithm terminates if convergence is not reached. By default, 100.
tol (float > 0, optional) – The total allowable error in the node and edge centralities. By default, 1e-6.

Returns:

The node centrality where keys are node IDs and values are associated centralities and the edge centrality where keys are the edge IDs and values are associated centralities. The centralities of both the nodes and edges are 1-normalized.

Return type:

dict, dict

Notes

In the paper from which this was taken, it is more general in that it includes general functions for both nodes and edges, nodes and edges may be weighted, and one can choose different norms for normalization.

References

Node and edge nonlinear eigenvector centrality for hypergraphs, Francesco Tudisco & Desmond J. Higham, https://doi.org/10.1038/s42005-021-00704-2

xgi.algorithms.centrality.line_vector_centrality(H)[source]

The vector centrality of nodes in the line graph of the hypergraph.

Parameters:: H (Hypergraph) – The hypergraph of interest
Returns:: Centrality, where keys are node IDs and values are lists of centralities.
Return type:: dict

References

“Vector centrality in hypergraphs”, K. Kovalenko, M. Romance, E. Vasilyeva, D. Aleja, R. Criado, D. Musatov, A.M. Raigorodskii, J. Flores, I. Samoylenko, K. Alfaro-Bittner, M. Perc, S. Boccaletti, https://doi.org/10.1016/j.chaos.2022.112397

xgi.algorithms.centrality.katz_centrality(H, index=False, cutoff=100)[source]

Returns the Katz-centrality vector of a non-empty hypergraph H.

The Katz-centrality measures the relative importance of a node by counting how many distinct walks start from it. The longer the walk is the smaller its contribution will be (attenuation factor \(\alpha\)). Initially defined for graphs, the Katz-centrality is here generalized to hypergraphs using the most basic definition of neighbors: two nodes that share an hyperedge.

Parameters:

H (xgi.Hypergraph) – Hypergraph on which to compute the Katz-centralities.
index (bool) – If set to True, will return a dictionary mapping each vector index to a node. Default value is False.
cutoff (int) – Power at which to stop the series \(A + \alpha A^2 + \alpha^2 A^3 + \dots\) Default value is 100.

Returns:

c (np.ndarray) – Vector of the node centralities, sorted by the node indexes.
nodedict (dict) – If index is set to True, nodedict will contain the nodes ids, keyed by their indice in vector c. Thus, c[key] will be the centrality of node nodedict[key].

Raises:

XGIError – If the hypergraph is empty.

Notes

[1] The Katz-centrality is defined as

\[c = [(I - \alpha A^{t})^{-1} - I]{\bf 1},\]

where \(A\) is the adjency matrix of the the (hyper)graph. Since \(A^{t} = A\) for undirected graphs (our case), we have:

\[ \begin{align}\begin{aligned}&[I + A + \alpha A^2 + \alpha^2 A^3 + \dots](I - \alpha A^{t})\\& = [I + A + \alpha A^2 + \alpha^2 A^3 + \dots](I - \alpha A)\\& = (I + A + \alpha A^2 + \alpha^2 A^3 + \dots) - A - \alpha A^2\\& - \alpha^2 A^3 - \alpha^3 A^4 - \dots\\& = I\end{aligned}\end{align} \]

And \((I - \alpha A^{t})^{-1} = I + A + \alpha A^2 + \alpha^2 A^3 + \dots\) Thus we can use the power serie to compute the Katz-centrality. [2] The Katz-centrality of isolated nodes (no hyperedges contains them) is zero. The Katz-centrality of an empty hypergraph is not defined.

References

See https://en.wikipedia.org/wiki/Katz_centrality#Alpha_centrality (visited May 20 2023) for a clear definition of Katz centrality.