Module centrality 

Centrality measures, graph centralization and local scan statistics (igraph_centrality.h, igraph_scan.h).

A centrality assigns every vertex (or edge) a score that tells how “important” it is in the network. Different notions of importance lead to different measures: being close to everybody else (closeness, harmonic centrality), lying on many shortest paths (betweenness), being connected to other important vertices (eigenvector centrality, PageRank, hub and authority scores), or bridging structural holes (Burt’s constraint).

A centralization index condenses vertex-level scores into a single number describing how much the whole graph is dominated by a single vertex; it is usually normalized by its value on the most centralized graph of the same size (typically a star), the theoretical maximum.

Local scan statistics count edges (or sum edge weights) within the neighborhoods of vertices, and are used for anomaly detection in (time series of) graphs.

All the functions are methods of Graph, except for the graph-free centralization and the *_tmax free functions that compute theoretical maxima from a number of vertices only.

Example

use igraph::prelude::*;
use igraph::centrality::PageRankOptions;

// A star with 5 leaves: the center is the most central in every sense.
let star = Graph::star(6, StarMode::Undirected, 0).unwrap();

let btw = star.betweenness(None, .., true, false).unwrap();
assert_eq!(btw, vec![10.0, 0.0, 0.0, 0.0, 0.0, 0.0]); // C(5, 2) = 10 pairs of leaves

let clo = star.closeness(.., NeighborMode::All, None, true).unwrap();
assert_eq!(clo[0], 1.0);

let pr = star.pagerank(None, .., &PageRankOptions::default()).unwrap();
assert!((pr.scores.iter().sum::<f64>() - 1.0).abs() < 1e-12);
assert!(pr.scores[0] > pr.scores[1]);

// The star is the most centralized graph: normalized centralization is 1.
let c = star.centralization_degree(NeighborMode::All, Loops::None, true).unwrap();
assert!((c.centralization - 1.0).abs() < 1e-12);

// In Zachary's karate club the instructor (0) and the administrator (33)
// are the two most "between" members.
let karate = Graph::famous("Zachary").unwrap();
let btw = karate.betweenness(None, .., false, false).unwrap();
let mut order: Vec<usize> = (0..34).collect();
order.sort_by(|&a, &b| btw[b].total_cmp(&btw[a]));
assert_eq!(&order[..2], &[0, 33]);

Provided functionality

Measure	Methods	C functions
Closeness	closeness, closeness_cutoff, closeness_reachability	igraph_closeness, igraph_closeness_cutoff
Harmonic centrality	harmonic_centrality, harmonic_centrality_cutoff	igraph_harmonic_centrality[_cutoff]
Vertex betweenness	betweenness, betweenness_cutoff, betweenness_subset	igraph_betweenness[_cutoff/_subset]
Edge betweenness	edge_betweenness, edge_betweenness_cutoff, edge_betweenness_subset	igraph_edge_betweenness[_cutoff/_subset]
PageRank	pagerank, personalized_pagerank, personalized_pagerank_vs	igraph_pagerank, igraph_personalized_pagerank[_vs]
Spectral	eigenvector_centrality, hub_and_authority_scores	igraph_eigenvector_centrality, igraph_hub_and_authority_scores
Structural holes	constraint	igraph_constraint
Edge convergence	convergence_degree	igraph_convergence_degree
Centralization	centralization, centralization_degree, centralization_betweenness, centralization_closeness, centralization_eigenvector_centrality	igraph_centralization*
Theoretical maxima	centralization_degree_tmax, centralization_betweenness_tmax, centralization_closeness_tmax, centralization_eigenvector_centrality_tmax and the homonymous methods of Graph	igraph_centralization_*_tmax
Local scan statistics	local_scan_0, local_scan_1_ecount, local_scan_k_ecount, their _them variants, local_scan_subset_ecount, local_scan_neighborhood_ecount	igraph_local_scan_*

Conventions

• Edge weights are passed as Option<&[f64]>, one weight per edge, None meaning an unweighted computation. The shortest-path based measures (closeness, harmonic centrality, betweenness) and PageRank reject NaN weights; betweenness also requires them to be strictly positive.
• Cutoffs are Option<f64>: None means no limit on the path lengths (the exact measure is computed); Some(c) only considers paths of length at most c (a negative c also means “no limit”, as in C).
• Vertex and edge sets are anything convertible into a VertexSelector/EdgeSelector, e.g. .. (all), a single id, a slice or a range of ids. Results follow the order of the selector.
• ARPACK-based computations (eigenvector centrality, hub and authority scores, PageRankAlgo::Arpack) always run with igraph’s default ARPACK options, which are adequate for virtually every graph.
• igraph reports non-fatal problems (e.g. eigenvector centrality of a disconnected graph) as warnings, not errors: collect them with take_warnings.

See also

• Shortest-path quantities that closeness and betweenness are built on: distances, eccentricity, radius and average_path_length in paths.
• Degree-like measures: degree, strength and maxdegree; k-core decomposition with coreness.
• Community detection by removing high-betweenness edges: community_edge_betweenness.
• The whole spectrum of the adjacency matrix, of which eigenvector centrality is the leading eigenvector: eigen_adjacency.
• Local clustering, the other classic ego-network measure next to Burt’s constraint: transitivity_local_undirected and count_adjacent_triangles.

Structs

Centralization

Vertex-level scores together with the graph-level centralization index.

Closeness

Closeness scores together with reachability information, returned by closeness_reachability.

ConvergenceDegree

Convergence degrees of the edges, see convergence_degree.

EigenScores

Vertex scores that are an eigenvector, with the corresponding eigenvalue.

EigenvectorCentralization

Eigenvector centralities together with the graph-level centralization index, see centralization_eigenvector_centrality.

HubAuthority

Kleinberg’s hub and authority scores, see hub_and_authority_scores.

PageRankOptions

Tuning parameters of the PageRank family of functions (pagerank, personalized_pagerank, personalized_pagerank_vs).

Enums

PageRankAlgo

The algorithm used to compute PageRank (igraph_pagerank_algo_t).

Functions

centralization

Computes the graph-level centralization index from vertex-level scores (igraph_centralization).

centralization_betweenness_tmax

Theoretical maximum of betweenness centralization for a graph with nodes vertices (igraph_centralization_betweenness_tmax with a null graph).

centralization_closeness_tmax

Theoretical maximum of closeness centralization for a graph with nodes vertices (igraph_centralization_closeness_tmax with a null graph).

centralization_degree_tmax

Theoretical maximum of degree centralization for a graph with nodes vertices (igraph_centralization_degree_tmax with a null graph).

centralization_eigenvector_centrality_tmax

Theoretical maximum of eigenvector centralization for a graph with nodes vertices (igraph_centralization_eigenvector_centrality_tmax with a null graph).