Centrality

Degree and strength, closeness and harmonic centrality, betweenness, eigenvector centrality, hubs and authorities, PageRank, Burt's constraint, local scan statistics and centralization.

37 entries: 36 functions and 1 type. Part of the Open Graph reference; All functions lists every entry on one page, with a filter. The badges say how each entry is checked.

Types

`pagerank_algo_t`type#

Unit tests

Names the PageRank solver; in Open Graph both values give the same scores.

typedef enum og_pagerank_algo_t {
    OG_PAGERANK_ALGO_ARPACK = 1,
    OG_PAGERANK_ALGO_PRPACK = 2
} og_pagerank_algo_t;

OG_PAGERANK_ALGO_ARPACK (1) and OG_PAGERANK_ALGO_PRPACK (2) are kept so that code written for igraph's interface ports by renaming. Open Graph has one solver of its own (see pagerank) and uses it for both values; any other value is OG_EINVAL.

Returns: Not applicable (an enumeration).
Complexity: Not applicable.
Checked: Both values give the same scores; the ARPACK value matches python-igraph 1.0's implementation="arpack" on 1,250 runs.
C name: og_pagerank_algo_t
In notebooks: Og.PagerankAlgo
igraph 1.0: igraph_pagerank_algo_t
See also: pagerank, personalized_pagerank

Degree and strength

`maxdegree`#

Exact

The largest degree among the chosen vertices.

og_error_t og_maxdegree(
    const og_t *graph,
    og_int_t *res,
    og_vs_t vids,
    og_neimode_t mode,
    og_loops_t loops
);

Degrees along mode as degree counts them, with loops saying how a self-loop counts: OG_NO_LOOPS not at all, OG_LOOPS_ONCE once, OG_LOOPS_TWICE twice where both of its ends are seen. An empty selection gives 0.

Parameters

graph The input graph.
res Receives the largest degree.
vids Vertex selector of the vertices whose values are returned, in selector order.
mode Which way edges are followed in a directed graph: OG_OUT, OG_IN or OG_ALL (either way). Ignored for undirected graphs.
loops OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVVID A vertex id is out of range.
OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_EINVAL Unknown loops value.
OG_ENOMEM Not enough memory.

Complexity

At most O(|V| + |E|).

Checked

Identical to python-igraph 1.0 maxdegree() on 240 graphs, every mode and loop policy, vertex subsets (OG_LOOPS_ONCE from the definition).

C name

og_maxdegree

In notebooks

Og.Maxdegree

igraph 1.0

igraph_maxdegree

See also

strength, centralization_degree

`strength`#

Exact

Weighted degree: the total weight of the edges at each chosen vertex.

og_error_t og_strength(
    const og_t *graph,
    og_vector_t *res,
    const og_vs_t vids,
    og_neimode_t mode,
    og_loops_t loops,
    const og_vector_t *weights
);

For each vertex of vids, the total weight of its edges along mode (mode is ignored for undirected graphs). loops: OG_NO_LOOPS leaves self-loops out, OG_LOOPS_ONCE counts each once, OG_LOOPS_TWICE counts a self-loop twice where both of its ends are seen (undirected graphs and OG_ALL). With weights NULL the result is the degree. Any weights are accepted, negative ones included.

Parameters

graph The input graph.
res Real vector; resized to |vids| and filled.
vids Vertex selector of the vertices whose values are returned, in selector order.
mode Which way edges are followed in a directed graph: OG_OUT, OG_IN or OG_ALL (either way). Ignored for undirected graphs.
loops OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE.
weights Edge weights, one per edge in edge-id order; NULL counts every edge as 1.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_EINVAL Unknown loops value, or the weight vector's length differs from the number of edges.
OG_EINVVID A vertex id is out of range.
OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|).

Checked

Tier 1. Identical to python-igraph 1.0 strength() on 240 graphs, every mode and loop policy, signed weights, vertex subsets. Benchmark 0.05x (weighted), 0.23x (unweighted).

C name

og_strength

In notebooks

Og.Strength

igraph 1.0

igraph_strength

Closeness and harmonic centrality

`closeness`#

Exact Threads

Closeness centrality: the inverse of the total distance from each vertex to the vertices it reaches.

og_error_t og_closeness(
    const og_t *graph,
    og_vector_t *res,
    og_vector_int_t *reachable_count,
    og_bool_t *all_reachable,
    const og_vs_t vids,
    og_neimode_t mode,
    const og_vector_t *weights,
    og_bool_t normalized
);

For each vertex v of vids, closeness is 1 / (sum of the shortest-path lengths from v to every vertex it reaches along mode). Vertices v cannot reach are left out of the sum rather than counted at infinity. With normalized the value is multiplied by how many vertices were reached, which turns it into 1 over the mean distance. A vertex that reaches no other vertex scores NaN.

reachable_count[i] receives how many vertices the i-th chosen vertex reaches (itself not included) and all_reachable whether every chosen vertex reaches all others; both may be NULL. Weights are lengths and must be strictly positive; NULL means length 1.

Parameters

graph The input graph.
res Real vector; resized to |vids| and filled.
reachable_count Integer vector or NULL; resized to |vids|.
all_reachable Receives whether every chosen vertex reaches all others, or NULL.
vids Vertex selector of the vertices whose values are returned, in selector order.
mode Which way edges are followed in a directed graph: OG_OUT, OG_IN or OG_ALL (either way). Ignored for undirected graphs.
weights Edge lengths, one per edge, strictly positive (+infinity allowed); NULL means length 1.
normalized Return 1 over the mean distance instead of 1 over the sum.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN, zero or negative.
OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_EINVVID A vertex id is out of range.
OG_ENOMEM Not enough memory.

Complexity

O(s (|V| + |E|)) unweighted, O(s (|V| + |E|) log |V|) weighted, for s chosen vertices.

Checked

Tier 1. Identical to python-igraph 1.0 closeness() on 240 graphs plus 40 with infinite weights, every mode, raw and normalised; reachable_count and all_reachable (not returned by python-igraph) checked against its distance matrix. Benchmark 0.71-0.79x (unweighted) and 0.60-0.76x (weighted) python-igraph's time.

Threads

One source per piece on the thread layer; each value depends on its source alone and is computed exactly as one thread computes it, so results are bit-identical at any thread count.

C name

og_closeness

In notebooks

Og.Closeness

igraph 1.0

igraph_closeness

og_t g;
og_vector_t c;
og_star(&g, 5, OG_STAR_UNDIRECTED, 0);
og_vector_init(&c, 0);
og_closeness(&g, &c, NULL, NULL, og_vss_all(), OG_ALL, NULL, true);
/* normalised: the centre 1, each leaf 4 / (1 + 3 * 2) = 0.571 */
og_vector_destroy(&c);
og_destroy(&g);

`harmonic_centrality`#

Exact Threads

Harmonic centrality: the sum of the inverse distances from each vertex to all others.

og_error_t og_harmonic_centrality(
    const og_t *graph,
    og_vector_t *res,
    const og_vs_t vids,
    og_neimode_t mode,
    const og_vector_t *weights,
    og_bool_t normalized
);

For each vertex v of vids, the sum of 1 / d(v, u) over the vertices u it reaches along mode; vertices it cannot reach add 0 (Marchiori and Latora, 2000; Rochat, 2009). Unlike closeness it stays meaningful on disconnected graphs. With normalized the sum is divided by |V| - 1, giving the mean over all other vertices. Weights are lengths and must be strictly positive; NULL means length 1.

Parameters

graph The input graph.
res Real vector; resized to |vids| and filled.
vids Vertex selector of the vertices whose values are returned, in selector order.
mode Which way edges are followed in a directed graph: OG_OUT, OG_IN or OG_ALL (either way). Ignored for undirected graphs.
weights Edge lengths, one per edge, strictly positive (+infinity allowed); NULL means length 1.
normalized Divide by |V| - 1.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN, zero or negative.
OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_EINVVID A vertex id is out of range.
OG_ENOMEM Not enough memory.

Complexity

O(s (|V| + |E|)) unweighted, O(s (|V| + |E|) log |V|) weighted, for s chosen vertices.

Checked

Tier 1. Identical to python-igraph 1.0 harmonic_centrality() on 240 graphs plus 40 with infinite weights, raw and normalised. Benchmark 0.85x.

Threads

One source per piece on the thread layer; each value depends on its source alone and is computed exactly as one thread computes it, so results are bit-identical at any thread count.

C name

og_harmonic_centrality

In notebooks

Og.HarmonicCentrality

igraph 1.0

igraph_harmonic_centrality

`closeness_cutoff`#

Exact Threads

Closeness that only counts vertices within a given distance.

og_error_t og_closeness_cutoff(
    const og_t *graph,
    og_vector_t *res,
    og_vector_int_t *reachable_count,
    og_bool_t *all_reachable,
    const og_vs_t vids,
    og_neimode_t mode,
    const og_vector_t *weights,
    og_bool_t normalized,
    og_real_t cutoff
);

As closeness, but a vertex farther than cutoff counts as unreachable, also for reachable_count, all_reachable and the normalisation. A negative cutoff means no limit; a NaN cutoff is OG_EINVAL.

Parameters

graph The input graph.
res Real vector; resized to |vids| and filled.
reachable_count Integer vector or NULL; resized to |vids|.
all_reachable Receives whether every chosen vertex reaches all others within the cutoff, or NULL.
vids Vertex selector of the vertices whose values are returned, in selector order.
mode Which way edges are followed in a directed graph: OG_OUT, OG_IN or OG_ALL (either way). Ignored for undirected graphs.
weights Edge lengths, one per edge, strictly positive (+infinity allowed); NULL means length 1.
normalized Return 1 over the mean distance.
cutoff Longest path length that counts; negative means no limit. NaN is OG_EINVAL.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN, zero or negative.
OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_EINVAL The cutoff is NaN.
OG_EINVVID A vertex id is out of range.
OG_ENOMEM Not enough memory.

Complexity

At most that of closeness; each search stops at the cutoff.

Checked

Identical to python-igraph 1.0 closeness(cutoff=...) with cutoffs including exact path lengths (the boundary) and infinite weights. NaN cutoff: OG_EINVAL on purpose (python-igraph 1.0 accepts a NaN cutoff; Open Graph refuses it).

Threads

One source per piece on the thread layer; each value depends on its source alone and is computed exactly as one thread computes it, so results are bit-identical at any thread count.

C name

og_closeness_cutoff

In notebooks

Og.ClosenessCutoff

igraph 1.0

igraph_closeness_cutoff

`harmonic_centrality_cutoff`#

Exact Threads

Harmonic centrality that only counts vertices within a given distance.

og_error_t og_harmonic_centrality_cutoff(
    const og_t *graph,
    og_vector_t *res,
    const og_vs_t vids,
    og_neimode_t mode,
    const og_vector_t *weights,
    og_bool_t normalized,
    og_real_t cutoff
);

As harmonic_centrality, but vertices farther than cutoff add 0. The normalisation still divides by |V| - 1. A negative cutoff means no limit; a NaN cutoff is OG_EINVAL.

Parameters

graph The input graph.
res Real vector; resized to |vids| and filled.
vids Vertex selector of the vertices whose values are returned, in selector order.
mode Which way edges are followed in a directed graph: OG_OUT, OG_IN or OG_ALL (either way). Ignored for undirected graphs.
weights Edge lengths, one per edge, strictly positive (+infinity allowed); NULL means length 1.
normalized Divide by |V| - 1.
cutoff Longest path length that counts; negative means no limit. NaN is OG_EINVAL.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN, zero or negative.
OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_EINVAL The cutoff is NaN.
OG_EINVVID A vertex id is out of range.
OG_ENOMEM Not enough memory.

Complexity

At most that of harmonic_centrality; each search stops at the cutoff.

Checked

Identical to python-igraph 1.0 harmonic_centrality(cutoff=...), as for closeness_cutoff; NaN cutoff OG_EINVAL on purpose.

Threads

One source per piece on the thread layer; each value depends on its source alone and is computed exactly as one thread computes it, so results are bit-identical at any thread count.

C name

og_harmonic_centrality_cutoff

In notebooks

Og.HarmonicCentralityCutoff

igraph 1.0

igraph_harmonic_centrality_cutoff

Betweenness

`betweenness`#

Exact Threads

Vertex betweenness: how many shortest paths between other vertices pass through each vertex.

og_error_t og_betweenness(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_t *res,
    og_vs_t vids,
    og_bool_t directed,
    og_bool_t normalized
);

The betweenness of v is the sum, over pairs (s, t) of vertices other than v, of the fraction of shortest s-t paths that go through v (Brandes' algorithm, 2001). In an undirected graph, or with directed false, each unordered pair counts once. With weights the lengths are weighted sums, weights must be strictly positive, and lengths within a relative 1e-10 of each other count as equal, so equal-length paths survive rounding.

normalized divides by the count of pairs that do not involve v: (|V| - 1)(|V| - 2) with directed paths, half of that otherwise (only when |V| > 2). vids only selects which values are returned; the work is the same for any selection.

Parameters

graph The input graph.
weights Edge lengths, one per edge, strictly positive (+infinity allowed); NULL means length 1.
res Real vector; resized to |vids| and filled.
vids Vertex selector of the vertices whose values are returned, in selector order.
directed Respect edge directions (directed graphs only) when true, ignore them when false; ignored for undirected graphs.
normalized Divide by the count of pairs that can contribute (see the description).

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN, zero or negative.
OG_EINVVID A vertex id is out of range.
OG_ENOMEM Not enough memory.

Complexity

O(|V| |E|) unweighted; O(|V| (|V| + |E|) log |V|) weighted.

Checked

Tier 1. Identical to python-igraph 1.0 betweenness() on 240 graphs, directed paths or not, integer weights with many equal-length paths, 44 graphs with infinite weights; normalisation checked against the definition (python-igraph has no such flag). Benchmark about 0.9x python-igraph's time unweighted, 0.49-0.98x weighted.

Threads

One source (Brandes pass) per piece on the thread layer; each source's contributions go into a slot of their own and are added to the result in source order, so results are bit-identical at any thread count.

C name

og_betweenness

In notebooks

Og.Betweenness

igraph 1.0

igraph_betweenness

og_t g;
og_vector_t btw;
og_small(&g, 5, OG_UNDIRECTED, 0, 1, 1, 2, 2, 3, 3, 4, -1);   /* a path */
og_vector_init(&btw, 0);
og_betweenness(&g, NULL, &btw, og_vss_all(), OG_UNDIRECTED, false);
/* btw = 0 3 4 3 0: vertex 2 lies on (0,3) (0,4) (1,3) (1,4) */
og_vector_destroy(&btw);
og_destroy(&g);

`edge_betweenness`#

Exact Threads

Edge betweenness: how many shortest paths run along each edge.

og_error_t og_edge_betweenness(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_t *res,
    og_es_t eids,
    og_bool_t directed,
    og_bool_t normalized
);

The betweenness of edge e is the sum, over pairs (s, t), of the fraction of shortest s-t paths that use e (Brandes 2001, 2008). Directions, weights and ties as in betweenness: weights strictly positive, lengths within a relative 1e-10 count as equal, and each unordered pair counts once in an undirected graph or with directed false.

normalized divides by |V| (|V| - 1) with directed paths, half of that otherwise (only when |V| > 1). eids only selects which values are returned.

Parameters

graph The input graph.
weights Edge lengths, one per edge, strictly positive (+infinity allowed); NULL means length 1.
res Real vector; resized to |eids| and filled.
eids Edge selector of the edges whose values are returned, in selector order.
directed Respect edge directions (directed graphs only) when true, ignore them when false; ignored for undirected graphs.
normalized Divide by the count of pairs that can contribute (see the description).

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN, zero or negative.
OG_EINVEID An edge id is out of range.
OG_ENOMEM Not enough memory.

Complexity

O(|V| |E|) unweighted; O(|V| (|V| + |E|) log |V|) weighted.

Checked

Tier 1. Same fixture as betweenness against python-igraph 1.0 edge_betweenness(). Benchmark 0.75x (unweighted), 0.63x (weighted).

Threads

C name

og_edge_betweenness

In notebooks

Og.EdgeBetweenness

igraph 1.0

igraph_edge_betweenness

og_t g;
og_vector_t eb;
og_small(&g, 4, OG_UNDIRECTED, 0, 1, 1, 2, 2, 3, -1);   /* a path */
og_vector_init(&eb, 0);
og_edge_betweenness(&g, NULL, &eb, og_ess_all(OG_EDGEORDER_ID), OG_UNDIRECTED, false);
/* eb = 3 4 3: the middle edge carries (0,2) (0,3) (1,2) (1,3) */
og_vector_destroy(&eb);
og_destroy(&g);

`betweenness_cutoff`#

Exact Threads

Vertex betweenness counting only shortest paths no longer than a cutoff.

og_error_t og_betweenness_cutoff(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_t *res,
    og_vs_t vids,
    og_bool_t directed,
    og_bool_t normalized,
    og_real_t cutoff
);

As betweenness, but only pairs whose shortest-path length is at most cutoff contribute (bounded-distance betweenness, Brandes 2008). Each Brandes pass stops at the cutoff, so small cutoffs are much cheaper. Normalisation as in betweenness. A negative cutoff means no limit; a NaN cutoff is OG_EINVAL.

Parameters

graph The input graph.
weights Edge lengths, one per edge, strictly positive (+infinity allowed); NULL means length 1.
res Real vector; resized to |vids| and filled.
vids Vertex selector of the vertices whose values are returned, in selector order.
directed Respect edge directions (directed graphs only) when true, ignore them when false; ignored for undirected graphs.
normalized Divide by the count of pairs that can contribute (see the description).
cutoff Longest path length that counts; negative means no limit. NaN is OG_EINVAL.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN, zero or negative.
OG_EINVAL The cutoff is NaN.
OG_EINVVID A vertex id is out of range.
OG_ENOMEM Not enough memory.

Complexity

At most that of betweenness; each pass only visits what lies within the cutoff.

Checked

Tier 1. Identical to python-igraph 1.0 betweenness(cutoff=...) with small integer cutoffs and exact path lengths, weighted and not. Benchmark (cutoff 3, 5k vertices, 25k edges) 0.32x. NaN cutoff OG_EINVAL on purpose.

Threads

C name

og_betweenness_cutoff

In notebooks

Og.BetweennessCutoff

igraph 1.0

igraph_betweenness_cutoff

`edge_betweenness_cutoff`#

Exact Threads

Edge betweenness counting only shortest paths no longer than a cutoff.

og_error_t og_edge_betweenness_cutoff(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_t *res,
    og_es_t eids,
    og_bool_t directed,
    og_bool_t normalized,
    og_real_t cutoff
);

As edge_betweenness, but only pairs whose shortest-path length is at most cutoff contribute. A negative cutoff means no limit; a NaN cutoff is OG_EINVAL.

Parameters

graph The input graph.
weights Edge lengths, one per edge, strictly positive (+infinity allowed); NULL means length 1.
res Real vector; resized to |eids| and filled.
eids Edge selector of the edges whose values are returned, in selector order.
directed Respect edge directions (directed graphs only) when true, ignore them when false; ignored for undirected graphs.
normalized Divide by the count of pairs that can contribute (see the description).
cutoff Longest path length that counts; negative means no limit. NaN is OG_EINVAL.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN, zero or negative.
OG_EINVAL The cutoff is NaN.
OG_EINVEID An edge id is out of range.
OG_ENOMEM Not enough memory.

Complexity

At most that of edge_betweenness.

Checked

Tier 1. Same fixture as betweenness_cutoff against python-igraph 1.0 edge_betweenness(cutoff=...). Benchmark (cutoff 3) 0.15-0.24x.

Threads

C name

og_edge_betweenness_cutoff

In notebooks

Og.EdgeBetweennessCutoff

igraph 1.0

igraph_edge_betweenness_cutoff

`betweenness_subset`#

Exact Threads

Vertex betweenness counting only shortest paths from chosen sources to chosen targets.

og_error_t og_betweenness_subset(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_t *res,
    og_vs_t sources,
    og_vs_t targets,
    og_vs_t vids,
    og_bool_t directed,
    og_bool_t normalized
);

As betweenness, but only shortest paths that start at a vertex of sources and end at a vertex of targets contribute (Brandes 2008); only the sources are searched, so few sources are cheap. A source listed twice counts twice. Normalisation is not available: normalized true is OG_UNIMPLEMENTED.

Parameters

graph The input graph.
weights Edge lengths, one per edge, strictly positive (+infinity allowed); NULL means length 1.
res Real vector; resized to |vids| and filled.
sources Vertex selector of the path starts.
targets Vertex selector of the path ends.
vids Vertex selector of the vertices whose values are returned, in selector order.
directed Respect edge directions (directed graphs only) when true, ignore them when false; ignored for undirected graphs.
normalized Must be false.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN, zero or negative.
OG_UNIMPLEMENTED normalized is true.
OG_EINVVID A vertex id is out of range.
OG_ENOMEM Not enough memory.

Complexity

O(|S| |E|) unweighted, O(|S| (|V| + |E|) log |V|) weighted, for |S| sources.

Checked

Identical to python-igraph 1.0 betweenness(sources=..., targets=...) on 240 graphs, weighted and not, repeated sources included.

Threads

C name

og_betweenness_subset

In notebooks

Og.BetweennessSubset

igraph 1.0

igraph_betweenness_subset

`edge_betweenness_subset`#

Exact Threads

Edge betweenness counting only shortest paths from chosen sources to chosen targets.

og_error_t og_edge_betweenness_subset(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_t *res,
    og_vs_t sources,
    og_vs_t targets,
    og_es_t eids,
    og_bool_t directed,
    og_bool_t normalized
);

As edge_betweenness, but only shortest paths from a vertex of sources to a vertex of targets contribute. A source listed twice counts twice. normalized true is OG_UNIMPLEMENTED.

Parameters

graph The input graph.
weights Edge lengths, one per edge, strictly positive (+infinity allowed); NULL means length 1.
res Real vector; resized to |eids| and filled.
sources Vertex selector of the path starts.
targets Vertex selector of the path ends.
eids Edge selector of the edges whose values are returned, in selector order.
directed Respect edge directions (directed graphs only) when true, ignore them when false; ignored for undirected graphs.
normalized Must be false.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN, zero or negative.
OG_UNIMPLEMENTED normalized is true.
OG_EINVVID A vertex id is out of range.
OG_EINVEID An edge id is out of range.
OG_ENOMEM Not enough memory.

Complexity

O(|S| |E|) unweighted, O(|S| (|V| + |E|) log |V|) weighted, for |S| sources.

Checked

As betweenness_subset, against python-igraph 1.0 edge_betweenness(sources=..., targets=...).

Threads

C name

og_edge_betweenness_subset

In notebooks

Og.EdgeBetweennessSubset

igraph 1.0

igraph_edge_betweenness_subset

Eigenvector centrality, hubs and authorities, PageRank

`pagerank`#

Within tolerance

PageRank scores of the vertices (Brin and Page), summing to 1.

og_error_t og_pagerank(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_t *vector,
    og_real_t *value,
    og_real_t damping,
    og_bool_t directed,
    og_vs_t vids,
    og_pagerank_algo_t algo,
    og_arpack_options_t *options
);

The scores are the long-run visiting frequencies of a random walker who, at each step, follows an outgoing edge with probability damping (an edge chosen in proportion to its weight) and otherwise jumps to a vertex chosen uniformly at random; at a vertex without outgoing weight the walker always jumps. With directed false, or in an undirected graph, every edge can be walked both ways (an undirected self-loop gives two arcs). Weights must be non-negative; an infinite weight makes every score NaN.

Open Graph solves the linear system (I - d S^T) y = r by Gauss-Seidel sweeps (over-relaxed, SOR, for undirected walks) until a sweep changes y by less than 1e-12 of its 1-norm, then scales y to sum 1. With damping 1 the walker can be trapped in a closed class; the result is then the limit of PageRank as the damping goes to 1, with a warning.

value is set to 1. vids selects which scores are returned; they always come from the whole graph. algo must be an pagerank_algo_t value; options is ignored.

Parameters

graph The input graph.
weights Non-negative edge weights, one per edge; NULL means 1 per edge.
vector Real vector; resized to |vids| and filled with the scores.
value Receives 1, or NULL.
damping Probability of following an edge, in [0, 1]; 0.85 is usual.
directed Respect edge directions (directed graphs only).
vids Vertex selector of the vertices whose values are returned, in selector order.
algo OG_PAGERANK_ALGO_PRPACK or OG_PAGERANK_ALGO_ARPACK (same result).
options Accepted for portability with igraph's interface and ignored; NULL is fine.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL algo is not one of the pagerank_algo_t values.
OG_EINVAL damping is NaN or outside [0, 1].
OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
OG_EINVVID A vertex id is out of range.
OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|) per sweep; typically some tens of sweeps.

Checked

Tier 1. Within 1e-9 absolute or 1e-7 relative of python-igraph 1.0 (the largest deviation seen is 2.4e-12 over 3,000 runs on 240 graphs), damping 0 to 1, both algorithm values, weights with zeros. At damping 1 with a closed class python-igraph answers NaN or an arbitrary vector, or does not finish; Open Graph returns the limit described above. Benchmark 0.80-0.95x directed, 0.34-0.59x undirected.

C name

og_pagerank

In notebooks

Og.Pagerank

igraph 1.0

igraph_pagerank

og_t g;
og_vector_t pr;
og_small(&g, 3, OG_DIRECTED, 0, 1, 1, 2, 2, 0, 0, 2, -1);
og_vector_init(&pr, 0);
og_pagerank(&g, NULL, &pr, NULL, 0.85, OG_DIRECTED, og_vss_all(),
            OG_PAGERANK_ALGO_PRPACK, NULL);
/* pr = 0.388 0.215 0.397: sums to 1; vertex 2 has two links in */
og_vector_destroy(&pr);
og_destroy(&g);

`personalized_pagerank`#

Within tolerance

PageRank in which the random jumps follow a given distribution.

og_error_t og_personalized_pagerank(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_t *vector,
    og_real_t *value,
    const og_vector_t *reset,
    og_real_t damping,
    og_bool_t directed,
    og_vs_t vids,
    og_pagerank_algo_t algo,
    og_arpack_options_t *options
);

As pagerank, except that a jump lands on vertex v with probability proportional to reset[v]; vertices without outgoing weight also jump by this distribution. reset needs one finite, non-negative entry per vertex with a positive sum; it is scaled to sum 1. reset NULL means uniform jumps, which is pagerank. Scores concentrate around the vertices with large reset values, which makes this a measure of closeness to them.

Parameters

graph The input graph.
weights Non-negative edge weights, one per edge; NULL means 1 per edge.
vector Real vector; resized to |vids| and filled with the scores.
value Receives 1, or NULL.
reset Jump weights, one per vertex, or NULL for uniform.
damping Probability of following an edge, in [0, 1].
directed Respect edge directions (directed graphs only).
vids Vertex selector of the vertices whose values are returned, in selector order.
algo OG_PAGERANK_ALGO_PRPACK or OG_PAGERANK_ALGO_ARPACK (same result).
options Accepted for portability with igraph's interface and ignored; NULL is fine.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL algo is not one of the pagerank_algo_t values.
OG_EINVAL damping is NaN or outside [0, 1].
OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
OG_EINVAL reset has the wrong length, a negative, infinite or NaN entry, or sums to zero.
OG_EINVVID A vertex id is out of range.
OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|) per sweep; typically some tens of sweeps.

Checked

Same tolerance and fixture as pagerank, with random reset vectors including zeros; the invalid reset vectors are OG_EINVAL as in python-igraph 1.0.

C name

og_personalized_pagerank

In notebooks

Og.PersonalizedPagerank

igraph 1.0

igraph_personalized_pagerank

See also

pagerank, personalized_pagerank_vs

`personalized_pagerank_vs`#

Within tolerance

PageRank in which the random jumps go to a chosen set of vertices.

og_error_t og_personalized_pagerank_vs(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_t *vector,
    og_real_t *value,
    og_vs_t reset_vids,
    og_real_t damping,
    og_bool_t directed,
    og_vs_t vids,
    og_pagerank_algo_t algo,
    og_arpack_options_t *options
);

As personalized_pagerank with the jumps spread evenly over reset_vids; a vertex listed twice gets twice the weight. An empty set is OG_EINVAL.

Parameters

graph The input graph.
weights Non-negative edge weights, one per edge; NULL means 1 per edge.
vector Real vector; resized to |vids| and filled with the scores.
value Receives 1, or NULL.
reset_vids The vertices the walker jumps to.
damping Probability of following an edge, in [0, 1].
directed Respect edge directions (directed graphs only).
vids Vertex selector of the vertices whose values are returned, in selector order.
algo OG_PAGERANK_ALGO_PRPACK or OG_PAGERANK_ALGO_ARPACK (same result).
options Accepted for portability with igraph's interface and ignored; NULL is fine.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL reset_vids is empty.
OG_EINVAL algo is not one of the pagerank_algo_t values.
OG_EINVAL damping is NaN or outside [0, 1].
OG_EINVAL The weight vector's length differs from the number of edges, or a weight is NaN or negative.
OG_EINVVID A vertex id is out of range.
OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|) per sweep; typically some tens of sweeps.

Checked

Tier 1. Same tolerance and fixture as pagerank, with reset vertex sets including repeats. Benchmark 0.77x.

C name

og_personalized_pagerank_vs

In notebooks

Og.PersonalizedPagerankVs

igraph 1.0

igraph_personalized_pagerank_vs

See also

personalized_pagerank, pagerank

`eigenvector_centrality`#

Within tolerance SIMD

Eigenvector centrality: each score a fixed multiple of the neighbours' summed scores, scaled so the largest is 1.

og_error_t og_eigenvector_centrality(
    const og_t *graph,
    og_vector_t *vector,
    og_real_t *value,
    og_neimode_t mode,
    const og_vector_t *weights,
    og_arpack_options_t *options
);

The scores are the eigenvector of the largest eigenvalue of the weighted adjacency matrix (Bonacich, 1972), scaled so that the entry largest in size is 1; value receives the eigenvalue. In an undirected graph, or with OG_ALL, the matrix is symmetric and a self-loop counts twice on its diagonal. In a directed graph, with OG_OUT a vertex collects the scores of the vertices pointing to it; with OG_IN, of the vertices it points to.

Directed graphs are solved exactly per strongly connected class (Perron-Frobenius theory of reducible matrices), so graphs that are not strongly connected still get the well-defined leading vector. Without edges, or with only zero weights, every score is 1 and value 0. A directed graph without a cycle has no positive eigenvalue: by convention the vertices without outgoing (OG_OUT) or incoming (OG_IN) weight score 1, the others 0. Both cases warn. Without negative weights no score is negative.

Weights must be finite. Negative weights are accepted with a warning; in a directed graph the eigenvalue of largest real part is then used and only real parts are returned. options is ignored.

Parameters

graph The input graph.
vector Real vector or NULL; resized to |V| and filled.
value Receives the eigenvalue, or NULL.
mode For directed graphs OG_OUT, OG_IN or OG_ALL (see the description); undirected graphs disregard it.
weights Edge weights, one per edge, finite; negative values are accepted with a warning. NULL means 1 per edge.
options Accepted for portability with igraph's interface and ignored; NULL is fine.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL mode is not OG_OUT, OG_IN or OG_ALL in a directed graph.
OG_EINVAL The weight vector's length differs from the number of edges, or a weight is infinite or NaN.
OG_ENOMEM Not enough memory.

Complexity

Iterative: O(|V| + |E|) per matrix-vector product; the number of steps depends on the gap between the two largest eigenvalues.

Checked

Within 1e-9 of python-igraph 1.0 where the leading eigenvector is unique (575 runs on 240 graphs, modes OUT/IN/ALL, positive, integer and signed weights); the conventions exactly. Where several leading eigenvectors exist python-igraph's pick depends on its random start, so Open Graph's is only checked to be one. OPEN: signed directed cycles of more than 256 vertices take about 30 s and come out about 1% off, with a warning (python-igraph fails there too).

SIMD

The Lanczos and Arnoldi solvers' dot products and vector updates run on Open Graph's SIMD kernels (AVX-512, AVX2, NEON or plain C, chosen at run time); reductions use one fixed order, so every CPU path gives the same bits. The non-negative directed case mostly runs power and Gauss-Seidel steps outside these kernels.

C name

og_eigenvector_centrality

In notebooks

Og.EigenvectorCentrality

igraph 1.0

igraph_eigenvector_centrality

og_t g;
og_vector_t ev;
og_real_t lambda;
og_star(&g, 5, OG_STAR_UNDIRECTED, 0);
og_vector_init(&ev, 0);
og_eigenvector_centrality(&g, &ev, &lambda, OG_ALL, NULL, NULL);
/* ev = 1 0.5 0.5 0.5 0.5, lambda = 2 (the square root of the 4 leaves) */
og_vector_destroy(&ev);
og_destroy(&g);

`hub_and_authority_scores`#

Within tolerance SIMD

Hub and authority scores (Kleinberg's HITS) of a directed graph.

og_error_t og_hub_and_authority_scores(
    const og_t *graph,
    og_vector_t *hub_vector,
    og_vector_t *authority_vector,
    og_real_t *value,
    const og_vector_t *weights,
    og_arpack_options_t *options
);

Hubs are the leading eigenvector of A A^T and authorities are A^T times the hubs, where A is the weighted adjacency matrix (Kleinberg, 1999): a good hub points to good authorities, a good authority is pointed to by good hubs. Each vector is scaled so its largest entry is 1, and value receives the leading eigenvalue of A A^T.

In an undirected graph both vectors equal the eigenvector centralities and value is that eigenvalue squared (with a warning). Without edges every score is 1. Weights must be finite; negative ones are accepted with a warning. When many scores come out (nearly) zero a warning says that other score vectors fit the graph equally well. options is ignored.

Parameters

graph The input graph.
hub_vector Real vector or NULL; resized to |V|, the hub scores.
authority_vector Real vector or NULL; resized to |V|, the authority scores.
value Receives the eigenvalue, or NULL.
weights Edge weights, one per edge, finite; negative values are accepted with a warning. NULL means 1 per edge.
options Accepted for portability with igraph's interface and ignored; NULL is fine.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL The weight vector's length differs from the number of edges, or a weight is infinite or NaN.
OG_ENOMEM Not enough memory.

Complexity

Iterative: O(|V| + |E|) per product with A A^T.

Checked

Tier 1. Within 1e-9 of python-igraph 1.0 on 421 runs with a unique answer; conventions exact; degenerate cases checked to be eigenvectors. Benchmark 0.54x (Open Graph returns both vectors, python-igraph's hub_score only hubs).

SIMD

C name

og_hub_and_authority_scores

In notebooks

Og.HubAndAuthorityScores

igraph 1.0

igraph_hub_and_authority_scores

See also

eigenvector_centrality, pagerank

Constraint and convergence degree

`constraint`#

Exact

Burt's constraint: how strongly each vertex's contacts are tied to one another.

og_error_t og_constraint(
    const og_t *graph,
    og_vector_t *res,
    og_vs_t vids,
    const og_vector_t *weights
);

For ego i, let T(v) be the total weight of v's edges in either direction, self-loops left out, and p(i, j) = (weight of the edges joining i and j) / T(i). The constraint of i adds up, over its contacts j, the square of the direct share p(i, j) plus the indirect shares through every other contact q, each p(i, q) times p(q, j) (Burt, 1992 and 2004). A high value means the contacts are connected among themselves: few structural holes around i. Edge directions are ignored; weights NULL counts 1 per edge.

A vertex with no edges at all scores NaN; one with only self-loops scores 0. Weights may be zero or negative; where a total weight is zero the divisions give infinities or NaN, as in python-igraph.

Parameters

graph The input graph.
res Real vector; resized to |vids| and filled.
vids Vertex selector of the vertices whose values are returned, in selector order.
weights Edge weights, one per edge in edge-id order; NULL counts every edge as 1.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVVID A vertex id is out of range.
OG_EINVAL The weight vector's length differs from the number of edges.
OG_ENOMEM Not enough memory.

Complexity

O(sum over vertices of their degree squared).

Checked

Identical to python-igraph 1.0 constraint() on 240 graphs, unweighted and weighted with zeros and negative values, vertex subsets.

C name

og_constraint

In notebooks

Og.Constraint

igraph 1.0

igraph_constraint

See also

strength, local_scan_1_ecount

`convergence_degree`#

Exact

Convergence degree of each edge: whether shortest paths funnel into it or fan out from it.

og_error_t og_convergence_degree(
    const og_t *graph,
    og_vector_t *result,
    og_vector_t *ins,
    og_vector_t *outs
);

For an edge e from i to j, let in(e) be the number of vertices s such that e lies on some shortest path starting at s, and out(e) the number of vertices t such that e lies on some shortest path ending at t (unweighted, all shortest paths count). The convergence degree is (in(e) - out(e)) / (in(e) + out(e)), between -1 and 1. In an undirected graph the edge is taken as stored (from -> to) and the absolute value is returned. ins and outs receive in(e) and out(e); each output may be NULL.

Parameters

graph The input graph.
result Real vector or NULL; resized to |E|.
ins Real vector or NULL; resized to |E|, in(e) per edge.
outs Real vector or NULL; resized to |E|, out(e) per edge.

Returns

OG_SUCCESS, or the error code.

Errors

OG_ENOMEM Not enough memory.

Complexity

O(|V| (|V| + |E|)).

Checked

Identical to python-igraph 1.0 convergence_degree() on 240 graphs; ins and outs (not returned by python-igraph) worked out from the definition and checked to reproduce its values.

C name

og_convergence_degree

In notebooks

Og.ConvergenceDegree

igraph 1.0

igraph_convergence_degree

See also

edge_betweenness

Local scan statistics

`local_scan_0`#

Exact

Scan statistic of order 0: the degree of every vertex, or its strength with weights.

og_error_t og_local_scan_0(
    const og_t *graph,
    og_vector_t *res,
    const og_vector_t *weights,
    og_neimode_t mode
);

Scan statistics (Priebe, Conroy, Marchette and Park, 2005) measure how busy the neighbourhood of each vertex is. Order 0 is the convention that the statistic is the vertex's own number of edges along mode, or their total weight. Self-loops count as strength counts them with OG_LOOPS_TWICE.

Parameters

graph The input graph.
res Real vector; resized to |V| and filled.
weights Edge weights, one per edge in edge-id order; NULL counts every edge as 1.
mode Which way the neighbourhoods are built in a directed graph: OG_OUT, OG_IN or OG_ALL. Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_EINVAL The weight vector's length differs from the number of edges.
OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|).

Checked

Identical to R igraph's local_scan(k = 0), used as a black box (python-igraph has no scan statistics), on 240 seeded graphs, every mode, weighted (reals, small integers, signed) and not.

C name

og_local_scan_0

In notebooks

Og.LocalScan0

igraph 1.0

igraph_local_scan_0

`local_scan_1_ecount`#

Exact

Scan statistic of order 1: the edges (or their weight) among each vertex and its neighbours.

og_error_t og_local_scan_1_ecount(
    const og_t *graph,
    og_vector_t *res,
    const og_vector_t *weights,
    og_neimode_t mode
);

For every vertex v, the number of edges, or their total weight, of the subgraph induced by v and the vertices one step away along mode. Edge directions do not matter for the count, and every edge inside the set, loops and parallel edges included, counts once.

Along OG_OUT or OG_IN in a directed graph the count follows the reference's rule exactly: a neighbour joined to v by several parallel edges has its own edges counted once per parallel edge, and a self-loop at v ends the scan, so v's neighbours with larger ids add none of their own edges. Without loops and parallel edges this is the plain induced count.

Parameters

graph The input graph.
res Real vector; resized to |V| and filled.
weights Edge weights, one per edge in edge-id order; NULL counts every edge as 1.
mode Which way the neighbourhoods are built in a directed graph: OG_OUT, OG_IN or OG_ALL. Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_EINVAL The weight vector's length differs from the number of edges.
OG_ENOMEM Not enough memory.

Complexity

O(sum over vertices of their neighbours' degrees), at most O(|V| |E|).

Checked

Identical to R igraph's local_scan(k = 1) (black box) on 240 graphs, every mode, weighted and not, including its counting of parallel edges and the centre's self-loop along OG_OUT / OG_IN.

C name

og_local_scan_1_ecount

In notebooks

Og.LocalScan1Ecount

igraph 1.0

igraph_local_scan_1_ecount

`local_scan_k_ecount`#

Exact

Scan statistic of order k: the edges (or weight) of the subgraph induced by each vertex's k-step neighbourhood.

og_error_t og_local_scan_k_ecount(
    const og_t *graph,
    og_int_t k,
    og_vector_t *res,
    const og_vector_t *weights,
    og_neimode_t mode
);

For every vertex v, the ball of v is v and every vertex reachable in at most k steps along mode; the statistic is the number of edges (total weight) of the subgraph the ball induces, each edge once and directions ignored. k = 0 is local_scan_0 and k = 1 is local_scan_1_ecount, with its directed rules.

Parameters

graph The input graph.
k Radius of the neighbourhoods; 0 or more.
res Real vector; resized to |V| and filled.
weights Edge weights, one per edge in edge-id order; NULL counts every edge as 1.
mode Which way the neighbourhoods are built in a directed graph: OG_OUT, OG_IN or OG_ALL. Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL k is negative.
OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_EINVAL The weight vector's length differs from the number of edges.
OG_ENOMEM Not enough memory.

Complexity

One bounded breadth-first search per vertex plus the edges of its ball: O(|V| (|V| + |E|)) in the worst case.

Checked

Identical to R igraph's local_scan() (black box) for k = 0 to 3, every mode, weighted and not, on 240 graphs.

C name

og_local_scan_k_ecount

In notebooks

Og.LocalScanKEcount

igraph 1.0

igraph_local_scan_k_ecount

`local_scan_0_them`#

Exact

Order-0 scan statistic of the graph them, restricted to the edges the graph us has too.

og_error_t og_local_scan_0_them(
    const og_t *us,
    const og_t *them,
    og_vector_t *res,
    const og_vector_t *weights_them,
    og_neimode_t mode
);

us and them are two graphs on the same vertices (same count, both directed or both undirected), for example the same network at two times. For each vertex, the statistic is its strength in them along mode (weights weights_them, NULL for 1 per edge), counting only those edges of them that us also has, matched one to one: a pair joined k times in us and more often in them keeps k of them's edges, those with the smallest ids. Self-loops count as in strength with OG_LOOPS_TWICE.

Parameters

us The graph whose edges select what is counted.
them The graph in which the edges are counted.
res Real vector; resized to |V| and filled.
weights_them Weights of them's edges, or NULL for 1 per edge.
mode Which way the neighbourhoods are built in a directed graph: OG_OUT, OG_IN or OG_ALL. Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL us and them differ in vertex count or directedness.
OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_EINVAL The weight vector's length differs from the number of edges.
OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E_us| + |E_them|).

Checked

R igraph local_scan() black box on 240 (us, them) pairs. In 262 weighted runs the reference's choice among parallel edges depends on an unstable sort inside it; there the documented rule (smallest ids kept) is the expectation, and every other run agrees with that rule.

C name

og_local_scan_0_them

In notebooks

Og.LocalScan0Them

igraph 1.0

igraph_local_scan_0_them

`local_scan_1_ecount_them`#

Exact

Order-1 scan statistic with the neighbourhoods taken from us and the edges counted in them.

og_error_t og_local_scan_1_ecount_them(
    const og_t *us,
    const og_t *them,
    og_vector_t *res,
    const og_vector_t *weights_them,
    og_neimode_t mode
);

For every vertex v, the neighbourhood is v and its neighbours along mode in us; the statistic is the number of edges of them (or their total weight) with both ends in that set, each edge once and directions ignored. us and them need equal vertex counts and the same directedness.

Parameters

us The graph that defines the neighbourhoods.
them The graph in which the edges are counted.
res Real vector; resized to |V| and filled.
weights_them Weights of them's edges, or NULL for 1 per edge.
mode Which way the neighbourhoods are built in a directed graph: OG_OUT, OG_IN or OG_ALL. Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL us and them differ in vertex count or directedness.
OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_EINVAL The weight vector's length differs from the number of edges.
OG_ENOMEM Not enough memory.

Complexity

O(sum over vertices of their neighbourhoods' degrees in them).

Checked

R igraph local_scan() black box on 240 graph pairs.

C name

og_local_scan_1_ecount_them

In notebooks

Og.LocalScan1EcountThem

igraph 1.0

igraph_local_scan_1_ecount_them

`local_scan_k_ecount_them`#

Exact

Order-k scan statistic with the neighbourhoods taken from us and the edges counted in them.

og_error_t og_local_scan_k_ecount_them(
    const og_t *us,
    const og_t *them,
    og_int_t k,
    og_vector_t *res,
    const og_vector_t *weights_them,
    og_neimode_t mode
);

As local_scan_1_ecount_them with balls of radius k: v and every vertex within k steps along mode in us. k = 0 is local_scan_0_them.

Parameters

us The graph that defines the neighbourhoods.
them The graph in which the edges are counted.
k Radius of the neighbourhoods; 0 or more.
res Real vector; resized to |V| and filled.
weights_them Weights of them's edges, or NULL for 1 per edge.
mode Which way the neighbourhoods are built in a directed graph: OG_OUT, OG_IN or OG_ALL. Ignored for undirected graphs.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL k is negative.
OG_EINVAL us and them differ in vertex count or directedness.
OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_EINVAL The weight vector's length differs from the number of edges.
OG_ENOMEM Not enough memory.

Complexity

One bounded breadth-first search per vertex in us plus the edges of the ball in them.

Checked

R igraph local_scan() black box, k = 0 to 3, on 240 graph pairs.

C name

og_local_scan_k_ecount_them

In notebooks

Og.LocalScanKEcountThem

igraph 1.0

igraph_local_scan_k_ecount_them

`local_scan_neighborhood_ecount`#

Exact

Edges (or their weight) among given vertex lists, one list per vertex.

og_error_t og_local_scan_neighborhood_ecount(
    const og_t *graph,
    og_vector_t *res,
    const og_vector_t *weights,
    const og_vector_int_list_t *neighborhoods
);

neighborhoods holds one vertex list per vertex of the graph, typically computed earlier (for example with neighborhood). res[i] is the number of edges (total weight) among the vertices of list i. The list is used as given: vertex i is not added. Edges are counted entry by entry, as the reference does, so a vertex listed twice counts its edges again; without repeats this is the edge count of the induced subgraph.

Superseded in the reference interface by local_scan_subset_ecount, which takes any number of lists.

Parameters

graph The input graph.
res Real vector; resized to the number of lists and filled.
weights Edge weights, one per edge in edge-id order; NULL counts every edge as 1.
neighborhoods One list of vertex ids per vertex of the graph.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL The number of lists differs from the number of vertices, or the weight vector's length differs from the number of edges.
OG_EINVVID A listed vertex is out of range.
OG_ENOMEM Not enough memory.

Complexity

O(sum over the lists of the degrees of their entries).

Checked

R igraph local_scan(neighborhoods = ...) black box: lists used as given and repeated entries counted again, as there.

C name

og_local_scan_neighborhood_ecount

In notebooks

Og.LocalScanNeighborhoodEcount

igraph 1.0

igraph_local_scan_neighborhood_ecount

`local_scan_subset_ecount`#

Exact

Edges (or their weight) of the subgraph induced by each given vertex subset.

og_error_t og_local_scan_subset_ecount(
    const og_t *graph,
    og_vector_t *res,
    const og_vector_t *weights,
    const og_vector_int_list_t *subsets
);

For each list in subsets (any number of them), the number of edges, or their total weight, with both ends in the list. Counting is entry by entry as in local_scan_neighborhood_ecount, so a repeated entry counts its edges again; without repeats this is the edge count of the induced subgraph.

Parameters

graph The input graph.
res Real vector; resized to the number of subsets and filled.
weights Edge weights, one per edge in edge-id order; NULL counts every edge as 1.
subsets The vertex lists.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL The weight vector's length differs from the number of edges.
OG_EINVVID A listed vertex is out of range.
OG_ENOMEM Not enough memory.

Complexity

O(sum over the subsets of the degrees of their entries).

Checked

R has no direct call: expectations from the definition (edges of the induced subgraph), cross-checked with the reference's neighbourhood answers where the two coincide.

C name

og_local_scan_subset_ecount

In notebooks

Og.LocalScanSubsetEcount

igraph 1.0

igraph_local_scan_subset_ecount

See also

local_scan_neighborhood_ecount

Centralization

`centralization`#

Exact

Freeman centralization of a score vector: the total gap between the top score and every score.

og_real_t og_centralization(
    const og_vector_t *scores,
    og_real_t theoretical_max,
    og_bool_t normalized
);

Returns the sum over all scores of (largest score - score) (Freeman, 1979), divided by theoretical_max when normalized is true. The theoretical maximum is the value the same measure reaches on the most centralized graph of the same size; the og_centralization_*_tmax functions give it. An empty vector, or a NaN score, gives NaN. The function cannot fail and returns the value itself.

Parameters

scores The vertex scores.
theoretical_max The divisor used when normalized is true.
normalized Divide by theoretical_max.

Returns

The centralization (an og_real_t, not an error code).

Complexity

O(n) for n scores.

Checked

Identical to R igraph's centralize() (black box; python-igraph has no centralization functions) on 30 score vectors, NaN and empty ones included.

C name

og_centralization

In notebooks

Og.Centralization

igraph 1.0

igraph_centralization

`centralization_degree`#

Exact

Degree of every vertex and the graph's degree centralization.

og_error_t og_centralization_degree(
    const og_t *graph,
    og_vector_t *res,
    og_neimode_t mode,
    og_loops_t loops,
    og_real_t *centralization,
    og_real_t *theoretical_max,
    og_bool_t normalized
);

Computes the degrees along mode with the loops policy (as strength without weights), then their centralization (centralization) against centralization_degree_tmax for the same graph, mode and loops. res receives the degrees, centralization the result, theoretical_max the maximum; each may be NULL.

Parameters

graph The input graph.
res Real vector or NULL; receives the vertex scores.
mode Which way edges are followed in a directed graph: OG_OUT, OG_IN or OG_ALL (either way). Ignored for undirected graphs.
loops OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE.
centralization Receives the centralization, or NULL.
theoretical_max Receives the theoretical maximum used, or NULL.
normalized Divide the centralization by the theoretical maximum.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_EINVAL Unknown loops value.
OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|).

Checked

Identical to R igraph's centr_degree() (black box) on 240 graphs, every mode, loops counted or not, raw and normalised; OG_LOOPS_ONCE from the definition.

C name

og_centralization_degree

In notebooks

Og.CentralizationDegree

igraph 1.0

igraph_centralization_degree

`centralization_betweenness`#

Exact Threads

Betweenness of every vertex and the graph's betweenness centralization.

og_error_t og_centralization_betweenness(
    const og_t *graph,
    og_vector_t *res,
    og_bool_t directed,
    og_real_t *centralization,
    og_real_t *theoretical_max,
    og_bool_t normalized
);

Computes the unweighted, unnormalised betweenness of every vertex (betweenness, directed as there), then its centralization against centralization_betweenness_tmax for the same graph. Outputs as in centralization_degree; each may be NULL.

Parameters

graph The input graph.
res Real vector or NULL; receives the vertex scores.
directed Respect edge directions (directed graphs only) when true, ignore them when false; ignored for undirected graphs.
centralization Receives the centralization, or NULL.
theoretical_max Receives the theoretical maximum used, or NULL.
normalized Divide the centralization by the theoretical maximum.

Returns

OG_SUCCESS, or the error code.

Errors

OG_ENOMEM Not enough memory.

Complexity

O(|V| |E|).

Checked

Identical to R igraph's centr_betw() (black box) on 240 graphs, directed or not, raw and normalised.

Threads

Through betweenness: One source (Brandes pass) per piece on the thread layer; each source's contributions go into a slot of their own and are added to the result in source order, so results are bit-identical at any thread count.

C name

og_centralization_betweenness

In notebooks

Og.CentralizationBetweenness

igraph 1.0

igraph_centralization_betweenness

`centralization_closeness`#

Exact Threads

Normalised closeness of every vertex and the graph's closeness centralization.

og_error_t og_centralization_closeness(
    const og_t *graph,
    og_vector_t *res,
    og_neimode_t mode,
    og_real_t *centralization,
    og_real_t *theoretical_max,
    og_bool_t normalized
);

Computes the unweighted, normalised closeness of every vertex along mode (closeness, so distances count only the vertices each one reaches), then its centralization against centralization_closeness_tmax for the same graph. Outputs as in centralization_degree; each may be NULL.

Parameters

graph The input graph.
res Real vector or NULL; receives the vertex scores.
mode Which way edges are followed in a directed graph: OG_OUT, OG_IN or OG_ALL (either way). Ignored for undirected graphs.
centralization Receives the centralization, or NULL.
theoretical_max Receives the theoretical maximum used, or NULL.
normalized Divide the centralization by the theoretical maximum.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_ENOMEM Not enough memory.

Complexity

O(|V| (|V| + |E|)).

Checked

Identical to R igraph's centr_clo() (black box) on 240 graphs, every mode, raw and normalised.

Threads

Through closeness: One source per piece on the thread layer; each value depends on its source alone and is computed exactly as one thread computes it, so results are bit-identical at any thread count.

C name

og_centralization_closeness

In notebooks

Og.CentralizationCloseness

igraph 1.0

igraph_centralization_closeness

`centralization_eigenvector_centrality`#

Within tolerance SIMD

Eigenvector centrality of every vertex and the graph's eigenvector centralization.

og_error_t og_centralization_eigenvector_centrality(
    const og_t *graph,
    og_vector_t *vector,
    og_real_t *value,
    og_neimode_t mode,
    og_arpack_options_t *options,
    og_real_t *centralization,
    og_real_t *theoretical_max,
    og_bool_t normalized
);

Computes the unweighted eigenvector centrality along mode (eigenvector_centrality, scaled so the largest score is 1, value its eigenvalue), then its centralization against centralization_eigenvector_centrality_tmax for the same graph. vector, value, centralization and theoretical_max may each be NULL. options is ignored.

Parameters

graph The input graph.
vector Real vector or NULL; receives the scores.
value Receives the eigenvalue, or NULL.
mode For directed graphs OG_OUT, OG_IN or OG_ALL; undirected graphs disregard it.
options Accepted for portability with igraph's interface and ignored; NULL is fine.
centralization Receives the centralization, or NULL.
theoretical_max Receives the theoretical maximum used, or NULL.
normalized Divide the centralization by the theoretical maximum.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL mode is not OG_OUT, OG_IN or OG_ALL where it matters.
OG_ENOMEM Not enough memory.

Complexity

That of eigenvector_centrality, plus O(|V|).

Checked

R igraph's centr_eigen() (black box) on 240 graphs: scores, eigenvalue and centralization within 1e-9 where the leading eigenvector is unique (926 runs), the theoretical maximum always exactly.

SIMD

Through eigenvector_centrality: The Lanczos and Arnoldi solvers' dot products and vector updates run on Open Graph's SIMD kernels (AVX-512, AVX2, NEON or plain C, chosen at run time); reductions use one fixed order, so every CPU path gives the same bits.

C name

og_centralization_eigenvector_centrality

In notebooks

Og.CentralizationEigenvectorCentrality

igraph 1.0

igraph_centralization_eigenvector_centrality

`centralization_degree_tmax`#

Exact

The largest degree centralization a graph of the given size can have.

og_error_t og_centralization_degree_tmax(
    const og_t *graph,
    og_int_t nodes,
    og_neimode_t mode,
    og_loops_t loops,
    og_real_t *res
);

The degree centralization of the most centralized n-vertex graph: a star, with a self-loop at the centre when loops count. With graph given, its vertex count and directedness are used and nodes is ignored; with graph NULL, n = nodes and the graph is taken as undirected when mode is OG_ALL.

Undirected: (n - 1)(n - 2) without loops, (n - 1) n with OG_LOOPS_TWICE, (n - 1)^2 with OG_LOOPS_ONCE. Directed, OG_OUT or OG_IN (out-star or in-star): (n - 1)^2 without loops, (n - 1) n with. Directed, OG_ALL (a star with edges both ways): 2 (n - 1)(n - 2), 2 (n - 1)^2 with OG_LOOPS_TWICE, (n - 1)(2n - 3) with OG_LOOPS_ONCE. Zero vertices give NaN.

Parameters

graph A graph whose vertex count (and directedness) are used, or NULL to use nodes.
nodes Number of vertices when graph is NULL; ignored otherwise.
mode OG_OUT, OG_IN or OG_ALL.
loops OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE.
res Receives the maximum.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL graph is NULL and nodes is negative.
OG_EINVAL Unknown loops value.
OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL where it matters (no graph, or a directed one).

Complexity

O(1).

Checked

Identical to R igraph's centr_degree_tmax() (black box) for 0 to 12 vertices, every mode, loops or not; OG_LOOPS_ONCE from the definition.

C name

og_centralization_degree_tmax

In notebooks

Og.CentralizationDegreeTmax

igraph 1.0

igraph_centralization_degree_tmax

`centralization_betweenness_tmax`#

Exact

The largest betweenness centralization a graph of the given size can have.

og_error_t og_centralization_betweenness_tmax(
    const og_t *graph,
    og_int_t nodes,
    og_bool_t directed,
    og_real_t *res
);

The betweenness centralization of a star with n vertices, whose centre lies on every path between two leaves: (n - 1)^2 (n - 2) with directed paths, half of that otherwise. With graph given, its vertex count is used and paths are directed only when both directed and the graph are; with graph NULL, n = nodes. Zero vertices give NaN.

Parameters

graph A graph whose vertex count (and directedness) are used, or NULL to use nodes.
nodes Number of vertices when graph is NULL; ignored otherwise.
directed Count directed paths.
res Receives the maximum.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL graph is NULL and nodes is negative.

Complexity

O(1).

Checked

Identical to R igraph's centr_betw_tmax() (black box) for 0 to 12 vertices, directed or not.

C name

og_centralization_betweenness_tmax

In notebooks

Og.CentralizationBetweennessTmax

igraph 1.0

igraph_centralization_betweenness_tmax

`centralization_closeness_tmax`#

Exact

The largest closeness centralization a graph of the given size can have.

og_error_t og_centralization_closeness_tmax(
    const og_t *graph,
    og_int_t nodes,
    og_neimode_t mode,
    og_real_t *res
);

The closeness centralization of the most centralized n-vertex graph, using normalised closeness. With OG_ALL (and always for an undirected graph) that is the star: (n - 1)(n - 2) / (2n - 3). With OG_OUT or OG_IN it is the out-star or in-star, with unreachable vertices taken at distance n: (n - 1)(1 - 1/n). With graph given, its vertex count is used; with graph NULL, n = nodes. Zero vertices give NaN.

Parameters

graph A graph whose vertex count (and directedness) are used, or NULL to use nodes.
nodes Number of vertices when graph is NULL; ignored otherwise.
mode OG_OUT, OG_IN or OG_ALL.
res Receives the maximum.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL graph is NULL and nodes is negative.
OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.

Complexity

O(1).

Checked

Identical to R igraph's centr_clo_tmax() (black box) for 0 to 12 vertices, every mode.

C name

og_centralization_closeness_tmax

In notebooks

Og.CentralizationClosenessTmax

igraph 1.0

igraph_centralization_closeness_tmax

`centralization_eigenvector_centrality_tmax`#

Exact

The largest eigenvector centralization a graph of the given size can have.

og_error_t og_centralization_eigenvector_centrality_tmax(
    const og_t *graph,
    og_int_t nodes,
    og_neimode_t mode,
    og_real_t *res
);

With scores scaled so the largest is 1: for an undirected graph (or OG_ALL) the extreme case is a single edge, whose two ends score 1 and everyone else 0, giving n - 2; for a directed graph with OG_OUT (an in-star) or OG_IN (an out-star) the centre scores 1 and the leaves 0, giving n - 1. One vertex gives 0, zero vertices NaN. With graph given, its vertex count and directedness are used; with graph NULL, n = nodes and OG_ALL means undirected.

Parameters

graph A graph whose vertex count (and directedness) are used, or NULL to use nodes.
nodes Number of vertices when graph is NULL; ignored otherwise.
mode OG_OUT, OG_IN or OG_ALL.
res Receives the maximum.

Returns

OG_SUCCESS, or the error code.

Errors

OG_EINVAL graph is NULL and nodes is negative.
OG_EINVAL mode is not OG_OUT, OG_IN or OG_ALL (no graph, or a directed one).

Complexity

O(1).

Checked

Identical to R igraph's centr_eigen_tmax() (black box) for 0 to 12 vertices, directed (OG_OUT) or not; OG_IN by the out-star symmetry.

C name

og_centralization_eigenvector_centrality_tmax

In notebooks

Og.CentralizationEigenvectorCentralityTmax

igraph 1.0

igraph_centralization_eigenvector_centrality_tmax

Last updated 6 November 2026 · Open Graph 0.1.0 · OpenBI Studio 0.3.78

Centrality

Types

pagerank_algo_ttype#

Degree and strength

maxdegree#

strength#

Closeness and harmonic centrality

closeness#

harmonic_centrality#

closeness_cutoff#

harmonic_centrality_cutoff#

Betweenness

betweenness#

edge_betweenness#

betweenness_cutoff#

edge_betweenness_cutoff#

betweenness_subset#

edge_betweenness_subset#

Eigenvector centrality, hubs and authorities, PageRank

pagerank#

personalized_pagerank#

personalized_pagerank_vs#

eigenvector_centrality#

hub_and_authority_scores#

Constraint and convergence degree

constraint#

convergence_degree#

Local scan statistics

local_scan_0#

local_scan_1_ecount#

local_scan_k_ecount#

local_scan_0_them#

local_scan_1_ecount_them#

local_scan_k_ecount_them#

local_scan_neighborhood_ecount#

local_scan_subset_ecount#

Centralization

centralization#

centralization_degree#

centralization_betweenness#

centralization_closeness#

centralization_eigenvector_centrality#

centralization_degree_tmax#

centralization_betweenness_tmax#

centralization_closeness_tmax#

centralization_eigenvector_centrality_tmax#

`pagerank_algo_t`type#

`maxdegree`#

`strength`#

`closeness`#

`harmonic_centrality`#

`closeness_cutoff`#

`harmonic_centrality_cutoff`#

`betweenness`#

`edge_betweenness`#

`betweenness_cutoff`#

`edge_betweenness_cutoff`#

`betweenness_subset`#

`edge_betweenness_subset`#

`pagerank`#

`personalized_pagerank`#

`personalized_pagerank_vs`#

`eigenvector_centrality`#

`hub_and_authority_scores`#

`constraint`#

`convergence_degree`#

`local_scan_0`#

`local_scan_1_ecount`#

`local_scan_k_ecount`#

`local_scan_0_them`#

`local_scan_1_ecount_them`#

`local_scan_k_ecount_them`#

`local_scan_neighborhood_ecount`#

`local_scan_subset_ecount`#

`centralization`#

`centralization_degree`#

`centralization_betweenness`#

`centralization_closeness`#

`centralization_eigenvector_centrality`#

`centralization_degree_tmax`#

`centralization_betweenness_tmax`#

`centralization_closeness_tmax`#

`centralization_eigenvector_centrality_tmax`#