easygraph.functions.centrality.katz_centrality module

easygraph.functions.centrality.katz_centrality.katz_centrality(G, alpha=0.1, beta=1.0, max_iter=1000, tol=1e-06, normalized=True)

Compute the Katz centrality for nodes in a graph.

Katz centrality computes the influence of a node based on the total number of walks between nodes, attenuated by a factor of their length. It is defined as the solution to the linear system:

\[x = \alpha A x + \beta\]

where:

• ( A ) is the adjacency matrix of the graph,

• ( alpha ) is a scalar attenuation factor,

• ( beta ) is the bias vector (typically all ones),

• and ( x ) is the resulting centrality vector.

The algorithm runs an iterative fixed-point method until convergence.

Parameters:

• G (easygraph.Graph) – An EasyGraph graph instance. Must be simple (non-multigraph).

• alpha (float, optional (default=0.1)) – Attenuation factor, must be smaller than the reciprocal of the largest eigenvalue of the adjacency matrix to ensure convergence.

• beta (float or dict, optional (default=1.0)) – Bias term. Can be a constant scalar applied to all nodes, or a dictionary mapping node IDs to values.

• max_iter (int, optional (default=1000)) – Maximum number of iterations before the algorithm terminates.

• tol (float, optional (default=1e-6)) – Convergence tolerance. Iteration stops when the L1 norm of the difference between successive iterations is below this threshold.

• normalized (bool, optional (default=True)) – If True, the result vector will be normalized to unit norm (L2).

Returns:

A dictionary mapping node IDs to Katz centrality scores.

Return type:

dict

Raises:

RuntimeError – If the algorithm fails to converge within max_iter iterations.

Examples

>>> import easygraph as eg
>>> from easygraph import katz_centrality
>>> G = eg.Graph()
>>> G.add_edges_from([(0, 1), (1, 2), (2, 3)])
>>> katz_centrality(G, alpha=0.05)
{0: 0.370..., 1: 0.447..., 2: 0.447..., 3: 0.370...}