Class GraphCentralityExtensions

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Centrality measures: degree, closeness (Wasserman-Faust scaled, so disconnected graphs need no special casing), betweenness via Brandes' algorithm (breadth-first for hop counts, Dijkstra-based for weights, which requires strictly positive weights), PageRank for directed graphs, and the spectral pair — eigenvector and Katz — by power iteration. On multigraphs, parallel edges count as distinct shortest paths, which is the natural multigraph semantics.

public static class GraphCentralityExtensions

Inheritance

object

GraphCentralityExtensions

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

BetweennessCentrality<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>)

Gets hop-count betweenness centrality (Brandes, breadth-first).

public static IReadOnlyDictionary<TVertex, double> BetweennessCentrality<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to measure.

Returns

IReadOnlyDictionary<TVertex, double>

Raw betweenness per vertex (undirected pair contributions counted once).

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

BetweennessCentrality<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>, CancellationToken)

Gets hop-count betweenness centrality, observing cancellationToken between source vertices.

public static IReadOnlyDictionary<TVertex, double> BetweennessCentrality<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph, CancellationToken cancellationToken) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to measure.

cancellationToken CancellationToken

Cancels the computation cooperatively.

Returns

IReadOnlyDictionary<TVertex, double>

Raw betweenness per vertex.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

OperationCanceledException

The token was cancelled.

BetweennessCentrality<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>, ParallelOptions)

Gets hop-count betweenness centrality with the per-source Brandes passes running in parallel. The token inside parallelOptions cancels cooperatively between sources.

public static IReadOnlyDictionary<TVertex, double> BetweennessCentrality<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph, ParallelOptions parallelOptions) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to measure; only read, never mutated.

parallelOptions ParallelOptions

Degree of parallelism and cancellation.

Returns

IReadOnlyDictionary<TVertex, double>

Raw betweenness per vertex (undirected pair contributions counted once).

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

OperationCanceledException

The token inside the options was cancelled.

BetweennessCentrality<TVertex, TEdge, TWeight>(IReadOnlyGraph<TVertex, TEdge>, Func<TEdge, TWeight>)

Gets weighted betweenness centrality (Brandes over Dijkstra), which requires strictly positive weights.

public static IReadOnlyDictionary<TVertex, double> BetweennessCentrality<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to measure.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight; every weight must be above zero.

Returns

IReadOnlyDictionary<TVertex, double>

Raw betweenness per vertex (undirected pair contributions counted once).

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

NegativeWeightException

A zero or negative edge weight was encountered.

BetweennessCentrality<TVertex, TEdge, TWeight>(IReadOnlyGraph<TVertex, TEdge>, Func<TEdge, TWeight>, CancellationToken)

Gets weighted betweenness centrality (strictly positive weights), observing cancellationToken between source vertices.

public static IReadOnlyDictionary<TVertex, double> BetweennessCentrality<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector, CancellationToken cancellationToken) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to measure.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight; every weight must be above zero.

cancellationToken CancellationToken

Cancels the computation cooperatively.

Returns

IReadOnlyDictionary<TVertex, double>

Raw betweenness per vertex.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

NegativeWeightException

A zero or negative edge weight was encountered.

OperationCanceledException

The token was cancelled.

BetweennessCentrality<TVertex, TEdge, TWeight>(IReadOnlyGraph<TVertex, TEdge>, Func<TEdge, TWeight>, ParallelOptions)

Gets weighted betweenness centrality (strictly positive weights) with the per-source Brandes passes running in parallel. weightSelector is invoked concurrently and must be pure. The token inside parallelOptions cancels cooperatively between sources.

public static IReadOnlyDictionary<TVertex, double> BetweennessCentrality<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector, ParallelOptions parallelOptions) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to measure; only read, never mutated.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight; every weight must be above zero, and it must be safe to call concurrently.

parallelOptions ParallelOptions

Degree of parallelism and cancellation.

Returns

IReadOnlyDictionary<TVertex, double>

Raw betweenness per vertex (undirected pair contributions counted once).

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

AggregateException

A per-source pass failed, e.g. with NegativeWeightException.

OperationCanceledException

The token inside the options was cancelled.

ClosenessCentrality<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>)

Gets hop-count closeness centrality.

public static IReadOnlyDictionary<TVertex, double> ClosenessCentrality<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to measure.

Returns

IReadOnlyDictionary<TVertex, double>

Closeness per vertex.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

ClosenessCentrality<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>, CancellationToken)

Gets hop-count closeness centrality, observing cancellationToken between vertices.

public static IReadOnlyDictionary<TVertex, double> ClosenessCentrality<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph, CancellationToken cancellationToken) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to measure.

cancellationToken CancellationToken

Cancels the computation cooperatively.

Returns

IReadOnlyDictionary<TVertex, double>

Closeness per vertex.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

OperationCanceledException

The token was cancelled.

ClosenessCentrality<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>, ParallelOptions)

Gets hop-count closeness centrality with the per-vertex sweeps running in parallel. The token inside parallelOptions cancels cooperatively between vertices.

public static IReadOnlyDictionary<TVertex, double> ClosenessCentrality<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph, ParallelOptions parallelOptions) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to measure; only read, never mutated.

parallelOptions ParallelOptions

Degree of parallelism and cancellation.

Returns

IReadOnlyDictionary<TVertex, double>

Closeness per vertex, identical to the sequential result.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

OperationCanceledException

The token inside the options was cancelled.

ClosenessCentrality<TVertex, TEdge, TWeight>(IReadOnlyGraph<TVertex, TEdge>, Func<TEdge, TWeight>)

Gets closeness centrality from weighted distances (measured from each vertex outward), Wasserman-Faust scaled by reachable-set size so disconnected graphs yield comparable values; unreachable and isolated vertices score 0.

public static IReadOnlyDictionary<TVertex, double> ClosenessCentrality<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to measure.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight.

Returns

IReadOnlyDictionary<TVertex, double>

Closeness per vertex.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

ClosenessCentrality<TVertex, TEdge, TWeight>(IReadOnlyGraph<TVertex, TEdge>, Func<TEdge, TWeight>, CancellationToken)

Gets weighted closeness centrality, observing cancellationToken between vertices.

public static IReadOnlyDictionary<TVertex, double> ClosenessCentrality<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector, CancellationToken cancellationToken) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to measure.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight.

cancellationToken CancellationToken

Cancels the computation cooperatively.

Returns

IReadOnlyDictionary<TVertex, double>

Closeness per vertex.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

OperationCanceledException

The token was cancelled.

ClosenessCentrality<TVertex, TEdge, TWeight>(IReadOnlyGraph<TVertex, TEdge>, Func<TEdge, TWeight>, ParallelOptions)

Gets weighted closeness centrality with the per-vertex sweeps running in parallel. weightSelector is invoked concurrently and must be pure. Every vertex's score is computed independently, so the result is identical to the sequential one.

public static IReadOnlyDictionary<TVertex, double> ClosenessCentrality<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector, ParallelOptions parallelOptions) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to measure; only read, never mutated.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight; must be safe to call concurrently.

parallelOptions ParallelOptions

Degree of parallelism and cancellation.

Returns

IReadOnlyDictionary<TVertex, double>

Closeness per vertex, identical to the sequential result.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

OperationCanceledException

The token inside the options was cancelled.

DegreeCentrality<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>)

Gets each vertex's degree divided by (V - 1); on directed graphs the total degree (in + out) is used.

public static IReadOnlyDictionary<TVertex, double> DegreeCentrality<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to measure.

Returns

IReadOnlyDictionary<TVertex, double>

Degree centrality per vertex (0 for a single-vertex graph).

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

EigenvectorCentrality<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>, int, double, CancellationToken)

Computes eigenvector centrality by shifted power iteration (x ← (A + I)·x, so bipartite graphs cannot oscillate): each vertex's score is proportional to the sum of its in-neighbors' scores (neighbors, when undirected), L2-normalized. On DAGs the spectrum is degenerate and scores drift toward the sinks without converging — use KatzCentrality<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>, double, double, int, double, CancellationToken) there.

public static IReadOnlyDictionary<TVertex, double> EigenvectorCentrality<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph, int maxIterations = 100, double tolerance = 1E-09, CancellationToken cancellationToken = default) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to measure.

maxIterations int

The iteration cap, at least 1.

tolerance double

The L1 convergence threshold.

cancellationToken CancellationToken

Cancels the computation cooperatively between power iterations.

Returns

IReadOnlyDictionary<TVertex, double>

Eigenvector centrality per vertex, L2-normalized (empty for the empty graph).

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

ArgumentOutOfRangeException

maxIterations is below 1.

OperationCanceledException

The token was cancelled.

KatzCentrality<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>, double, double, int, double, CancellationToken)

Computes Katz centrality by fixed-point iteration: every vertex gets a base score beta plus alpha times its in-neighbors' scores (neighbors, when undirected), L2-normalized. Unlike eigenvector centrality it stays meaningful on DAGs. Convergence requires alpha below the reciprocal of the spectral radius; past the iteration cap the current values are returned as-is.

public static IReadOnlyDictionary<TVertex, double> KatzCentrality<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph, double alpha = 0.1, double beta = 1, int maxIterations = 100, double tolerance = 1E-09, CancellationToken cancellationToken = default) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to measure.

alpha double

The attenuation factor, above 0; 0.1 is the classic choice.

beta double

The base score every vertex starts from.

maxIterations int

The iteration cap, at least 1.

tolerance double

The L1 convergence threshold.

cancellationToken CancellationToken

Cancels the computation cooperatively between iterations.

Returns

IReadOnlyDictionary<TVertex, double>

Katz centrality per vertex, L2-normalized (empty for the empty graph).

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

ArgumentOutOfRangeException

alpha is not positive or maxIterations is below 1.

OperationCanceledException

The token was cancelled.

PageRank<TVertex, TEdge>(IDirectedGraph<TVertex, TEdge>, double, int, double, CancellationToken)

Computes PageRank by power iteration with uniform teleportation; dangling-vertex mass is redistributed uniformly, so ranks always sum to one. Parallel edges each carry their share of the source's rank.

public static IReadOnlyDictionary<TVertex, double> PageRank<TVertex, TEdge>(this IDirectedGraph<TVertex, TEdge> graph, double damping = 0.85, int maxIterations = 100, double tolerance = 1E-09, CancellationToken cancellationToken = default) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IDirectedGraph<TVertex, TEdge>

The directed graph to rank.

damping double

The damping factor in [0, 1]; 0.85 is the classic choice.

maxIterations int

The iteration cap, at least 1.

tolerance double

The L1 convergence threshold.

cancellationToken CancellationToken

Cancels the computation cooperatively between power iterations.

Returns

IReadOnlyDictionary<TVertex, double>

PageRank per vertex, summing to 1 (empty for the empty graph).

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

ArgumentOutOfRangeException

Damping leaves [0, 1] or maxIterations is below 1.

OperationCanceledException

The token was cancelled.