Jacobian

An extension of Open Graph's own: how sensitive a centrality is to each edge weight, as derivatives, for PageRank, eigenvector centrality, strength, betweenness, closeness and harmonic centrality.

14 entries: 10 functions and 4 types. 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

`jacobian_measure_t`type#

Exact Extension

The centrality measures whose sensitivity to edge weights og_jacobian_* compute.

typedef enum og_jacobian_measure_t {
    OG_JACOBIAN_PAGERANK = 0,
    OG_JACOBIAN_EIGENVECTOR = 1,
    OG_JACOBIAN_STRENGTH = 2,
    OG_JACOBIAN_BETWEENNESS = 3,
    OG_JACOBIAN_CLOSENESS = 4,
    OG_JACOBIAN_HARMONIC = 5
} og_jacobian_measure_t;

Each measure is differentiated through Open Graph's own centrality function with fixed options: OG_JACOBIAN_PAGERANK (0) pagerank with the given damping and directedness; OG_JACOBIAN_EIGENVECTOR (1) eigenvector_centrality (mode OUT when directed, else ALL, scores scaled so the largest is 1); OG_JACOBIAN_STRENGTH (2) strength with the given mode, self-loops counted twice; OG_JACOBIAN_BETWEENNESS (3) betweenness, not normalised; OG_JACOBIAN_CLOSENESS (4) closeness, normalised; OG_JACOBIAN_HARMONIC (5) harmonic_centrality, normalised. Any other value is OG_EINVAL in every operation.

Checked: Open Graph extension, no igraph counterpart: a port of Norway Analytics' own C# Jacobian tool, extended. Values 0 to 5 as the tool's measures.
C name: og_jacobian_measure_t
In notebooks: Og.JacobianMeasure
igraph 1.0: None: Open Graph's own.
See also: jacobian_options_t, jacobian_measure_name, jacobian_smoothness

`jacobian_smoothness_t`type#

Exact Extension

How smoothly a measure depends on the edge weights.

typedef enum og_jacobian_smoothness_t {
    OG_JACOBIAN_SMOOTH = 0,
    OG_JACOBIAN_PIECEWISE_LINEAR = 1,
    OG_JACOBIAN_PIECEWISE_CONSTANT = 2
} og_jacobian_smoothness_t;

OG_JACOBIAN_SMOOTH (0): PageRank, eigenvector and strength have ordinary derivatives (the eigenvector scores have a kink where two vertices share the top score). OG_JACOBIAN_PIECEWISE_LINEAR (1): closeness and harmonic centrality are built from shortest distances, which are linear in the weights between shortest-path ties and have kinks at ties. OG_JACOBIAN_PIECEWISE_CONSTANT (2): betweenness only changes when the set of shortest paths changes, so its derivative is 0 almost everywhere.

Checked: Open Graph extension, no igraph counterpart: a port of Norway Analytics' own C# Jacobian tool, extended.
C name: og_jacobian_smoothness_t
In notebooks: Og.JacobianSmoothnessType
igraph 1.0: None: Open Graph's own.
See also: jacobian_smoothness, jacobian_warning

`jacobian_method_t`type#

Exact Extension

How the derivatives are computed: exactly, or by finite differences.

typedef enum og_jacobian_method_t {
    OG_JACOBIAN_EXACT = 0,
    OG_JACOBIAN_FINITE_DIFF = 1,
    OG_JACOBIAN_FINITE_DIFF_RICHARDSON = 2
} og_jacobian_method_t;

OG_JACOBIAN_EXACT (0, the default) differentiates the measure's own equations: strength by definition; PageRank through its stationary equation (one linear solve with I - d P^T per column, one transposed solve per row); the eigenvector by first-order perturbation of the leading eigenpair; closeness and harmonic as one-sided derivatives from the shortest-path structure; betweenness as 0, with tie flags.

OG_JACOBIAN_FINITE_DIFF (1) is the central difference of Norway Analytics' earlier Jacobian tool (in C#), for parity: h = eps max(1, |w_e|), w+ = w_e + h, w- = max(w_e - h, 1e-12), derivative (c(w+) - c(w-)) / (w+ - w-). OG_JACOBIAN_FINITE_DIFF_RICHARDSON (2) combines steps h and h/2 as (4 D(h/2) - D(h)) / 3, error O(h^4) on smooth measures; where w_e - h would leave the weights a measure accepts the steps shrink to h = w_e / 2, and a zero PageRank weight uses forward differences (2 F(h/2) - F(h), error O(h^2)).

Checked: Open Graph extension, no igraph counterpart: a port of Norway Analytics' own C# Jacobian tool, extended. FINITE_DIFF reproduces the tool's formula bit for bit.
C name: og_jacobian_method_t
In notebooks: Og.JacobianMethod
igraph 1.0: None: Open Graph's own.
See also: jacobian_options_t, jacobian_column

`jacobian_options_t`type#

Exact Extension

The options of every Jacobian operation: measure, method, step and the measure's own settings.

typedef struct og_jacobian_options_t {
    og_jacobian_measure_t measure;  /* default OG_JACOBIAN_PAGERANK */
    og_jacobian_method_t method;    /* default OG_JACOBIAN_EXACT */
    og_real_t eps;                  /* relative step of the finite differences, 1e-4;
        * must be positive and finite in every method */
    og_real_t damping;              /* PageRank, 0.85 */
    og_bool_t directed;             /* PageRank, eigenvector, betweenness: true */
    og_neimode_t mode;              /* strength, closeness, harmonic: OG_ALL */
} og_jacobian_options_t;

Fill it with jacobian_options_init and change what you need. Passing NULL options to an operation means the defaults. Each measure reads only its own settings: damping for PageRank, directed for PageRank, eigenvector and betweenness, mode for strength, closeness and harmonic. eps is checked in every method (it must be positive and finite) even though only the finite-difference methods use it.

Parameters

measure jacobian_measure_t; default OG_JACOBIAN_PAGERANK.
method jacobian_method_t; default OG_JACOBIAN_EXACT.
eps Relative step of the finite differences; default 1e-4; positive and finite.
damping PageRank's damping factor; default 0.85.
directed PageRank, eigenvector, betweenness: follow edge directions; default true.
mode Strength, closeness, harmonic: OG_OUT, OG_IN or OG_ALL; default OG_ALL.

Checked

Open Graph extension, no igraph counterpart: a port of Norway Analytics' own C# Jacobian tool, extended. Parameters and defaults as the tool's.

C name

og_jacobian_options_t

In notebooks

Og.JacobianOptions

igraph 1.0

None: Open Graph's own.

See also

jacobian_options_init

Options and measures

`jacobian_options_init`#

Exact Extension

Fills an options structure with the defaults.

og_error_t og_jacobian_options_init(og_jacobian_options_t *opts);

measure OG_JACOBIAN_PAGERANK, method OG_JACOBIAN_EXACT, eps 1e-4, damping 0.85, directed true, mode OG_ALL.

Parameters

opts The structure to fill.

Returns

OG_SUCCESS.

Errors

OG_EINVAL opts is NULL.

Complexity

O(1).

Checked

Open Graph extension, no igraph counterpart: a port of Norway Analytics' own C# Jacobian tool, extended. Defaults as the tool's.

C name

og_jacobian_options_init

In notebooks

Og.JacobianOptionsInit

igraph 1.0

None: Open Graph's own.

See also

jacobian_options_t

`jacobian_smoothness`#

Exact Extension

Returns the smoothness class of a measure.

og_jacobian_smoothness_t og_jacobian_smoothness(
    og_jacobian_measure_t measure
);

OG_JACOBIAN_PIECEWISE_CONSTANT for betweenness, OG_JACOBIAN_PIECEWISE_LINEAR for closeness and harmonic, OG_JACOBIAN_SMOOTH for the others, including an unknown value.

Parameters

measure The measure.

Returns

The smoothness class.

Complexity

O(1).

Checked

Open Graph extension, no igraph counterpart: a port of Norway Analytics' own C# Jacobian tool, extended.

C name

og_jacobian_smoothness

In notebooks

Og.JacobianSmoothness

igraph 1.0

None: Open Graph's own.

`jacobian_warning`#

Exact Extension

Returns a short warning text for the measures that are not smooth.

const char *og_jacobian_warning(og_jacobian_measure_t measure);

For betweenness, a text saying it is piecewise constant (finite differences are 0 almost everywhere and jump at shortest-path ties); for closeness and harmonic, that they are piecewise linear (valid local slopes away from ties, one-sided at ties). NULL for the smooth measures. These are the texts of Norway Analytics' earlier Jacobian tool (in C#). The string is static: do not free it.

Parameters

measure The measure.

Returns

A static text, or NULL.

Complexity

O(1).

Checked

Open Graph extension, no igraph counterpart: a port of Norway Analytics' own C# Jacobian tool, extended. The tool's own warning texts.

C name

og_jacobian_warning

In notebooks

Og.JacobianWarning

igraph 1.0

None: Open Graph's own.

See also

jacobian_smoothness

`jacobian_measure_name`#

Exact Extension

Returns the name of a measure.

const char *og_jacobian_measure_name(og_jacobian_measure_t measure);

"pagerank", "eigenvector", "strength", "betweenness", "closeness" or "harmonic"; NULL for an unknown value. The string is static.

Parameters

measure The measure.

Returns

A static name, or NULL.

Complexity

O(1).

Checked

Open Graph extension, no igraph counterpart: a port of Norway Analytics' own C# Jacobian tool, extended. The tool's measure names.

C name

og_jacobian_measure_name

In notebooks

Og.JacobianMeasureName

igraph 1.0

None: Open Graph's own.

See also

jacobian_measure_from_name

`jacobian_measure_from_name`#

Exact Extension

Parses a measure name, ignoring case.

og_error_t og_jacobian_measure_from_name(
    const char *name,
    og_jacobian_measure_t *measure
);

Accepts the six names jacobian_measure_name gives, in any mix of upper and lower case, and stores the measure. Anything else is refused, as Norway Analytics' earlier Jacobian tool refuses an unknown measure.

Parameters

name The name to parse.
measure Output: the measure.

Returns

OG_SUCCESS.

Errors

OG_EINVAL name is NULL or not one of the six names.

Complexity

O(length of the name).

Checked

Open Graph extension, no igraph counterpart: a port of Norway Analytics' own C# Jacobian tool, extended.

C name

og_jacobian_measure_from_name

In notebooks

Og.JacobianMeasureFromName

igraph 1.0

None: Open Graph's own.

See also

jacobian_measure_name

Derivatives

`jacobian_column`#

Within tolerance Threads Extension

Returns how every vertex's centrality responds to the weight of one edge.

og_error_t og_jacobian_column(
    const og_t *graph,
    const og_vector_t *weights,
    og_int_t edge,
    const og_jacobian_options_t *opts,
    og_vector_t *res,
    og_real_t *colsum,
    og_vector_t *left,
    og_vector_t *right,
    og_vector_bool_t *tie
);

J[i][e] = d c_i / d w_e: how the centrality c_i of vertex i responds to the weight w_e of edge e, around the given weights (all 1 when weights is NULL). res[i] = d c_i / d w_edge for every vertex i. colsum, when given, is the sum of res: about 0 for PageRank, whose scores always sum to 1 (a built-in check).

left and right (optional) are the one-sided derivatives as w_e decreases towards, and increases from, its value; tie marks the entries where they differ; res holds their mean, what a central difference measures across a kink. In EXACT mode they differ only at an eigenvector's shared top score and at closeness or harmonic shortest-path ties; for betweenness both are 0 and tie marks the entries that may jump under an arbitrarily small move of w_e. In the finite-difference methods left = right = res and tie is all false.

Undefined points give NaN: closeness of a vertex that reaches no other vertex, PageRank columns of an edge whose tail has no positive out-weight, and eigenvector entries where the scores are not unique (several classes share the leading eigenvalue, with a warning) or the sign of a shared top score flips.

Parameters

graph The graph (at least one edge).
weights Edge weights, or NULL for all 1.
edge The edge whose weight moves.
opts Options, or NULL for the defaults.
res Output: one derivative per vertex (resized to |V|).
colsum Output, may be NULL: the sum of res.
left Output, may be NULL: left derivatives.
right Output, may be NULL: right derivatives.
tie Output, may be NULL: true where left and right differ.

Returns

OG_SUCCESS.

Errors

OG_EINVEID edge is not an edge of the graph.
OG_EINVAL The graph has no edges; eps is not positive or not finite; weights does not have |E| entries.
OG_EINVAL An unknown measure or method.
OG_EINVAL Weights the measure refuses: PageRank negative or NaN; eigenvector NaN; betweenness, closeness and harmonic not above zero; exact strength NaN.
OG_EINVAL PageRank's exact method at damping 1 on a walk with a closed class.
OG_UNIMPLEMENTED Exact eigenvector: a directed walk with a cycle and a negative weight (the leading eigenpair can be complex).
OG_DIVERGED Exact eigenvector: a linear solve fails (the leading eigenvalue is not simple).
OG_ENOMEM Not enough memory.

Complexity

Finite differences: 2 evaluations of the measure (Richardson 4). Exact: one linear solve (PageRank, eigenvector), one shortest-path pass per vertex (closeness, harmonic), O(|V|) (strength).

Checked

FINITE_DIFF against Norway Analytics' earlier Jacobian tool (in C#) (black box, karate club and a weighted directed graph, every measure): within 4.8e-11 of the column's largest entry; against the C# formula over python-igraph on 216 cases: within 7.1e-9. EXACT within 3.3e-10 of Richardson differences (PageRank, eigenvector, strength); PageRank column sums 0 within 1e-12; closeness and harmonic sides checked against a brute-force path oracle.

Threads

Exact closeness and harmonic: the shortest-path pass of each source vertex is a task. Finite differences call the og_ centrality functions, which use the thread layer themselves (betweenness, closeness, harmonic). Results are bit-identical for any thread count.

C name

og_jacobian_column

In notebooks

Og.JacobianColumn

igraph 1.0

None: Open Graph's own.

#include "og.h"
#include <stdio.h>

int main(void) {
    og_t g;
    og_jacobian_options_t opts;
    og_vector_t d;
    og_real_t colsum;
    og_famous(&g, "Zachary");
    og_jacobian_options_init(&opts);            /* PageRank, exact, damping 0.85 */
    opts.directed = false;
    og_vector_init(&d, 0);
    og_jacobian_column(&g, NULL, 0, &opts, &d, &colsum, NULL, NULL, NULL);
    printf("dPR(0)/dw0 = %g, dPR(1)/dw0 = %g, column sum %.1e\n",
           OG_VECTOR(d)[0], OG_VECTOR(d)[1], colsum);   /* sum about 0 */
    og_vector_destroy(&d);
    og_destroy(&g);
    return 0;
}

`jacobian_row`#

Within tolerance Threads Extension

Returns how one vertex's centrality responds to the weight of every edge.

og_error_t og_jacobian_row(
    const og_t *graph,
    const og_vector_t *weights,
    og_int_t vertex,
    const og_jacobian_options_t *opts,
    og_vector_t *res,
    og_vector_t *left,
    og_vector_t *right,
    og_vector_bool_t *tie
);

J[i][e] = d c_i / d w_e: how the centrality c_i of vertex i responds to the weight w_e of edge e, around the given weights (all 1 when weights is NULL). res[e] = d c_vertex / d w_e for every edge e.

Exact PageRank and eigenvector rows take one transposed (adjoint) solve for all edges at once instead of a solve per edge; exact closeness and harmonic rows take one shortest-path pass plus a bit-parallel reachability table. Finite differences compute each column once (2 evaluations per edge).

Parameters

graph The graph (at least one edge).
weights Edge weights, or NULL for all 1.
vertex The vertex whose centrality is followed.
opts Options, or NULL for the defaults.
res Output: one derivative per edge (resized to |E|).
left Output, may be NULL: left derivatives.
right Output, may be NULL: right derivatives.
tie Output, may be NULL: true where left and right differ.

Returns

OG_SUCCESS.

Errors

OG_EINVVID vertex is not a vertex of the graph.
OG_EINVAL The graph has no edges; eps is not positive or not finite; weights does not have |E| entries.
OG_EINVAL An unknown measure or method.
OG_EINVAL Weights the measure refuses: PageRank negative or NaN; eigenvector NaN; betweenness, closeness and harmonic not above zero; exact strength NaN.
OG_EINVAL PageRank's exact method at damping 1 on a walk with a closed class.
OG_UNIMPLEMENTED Exact eigenvector: a directed walk with a cycle and a negative weight (the leading eigenpair can be complex).
OG_DIVERGED Exact eigenvector: a linear solve fails (the leading eigenvalue is not simple).
OG_ENOMEM Not enough memory.

Complexity

Finite differences: 2|E| evaluations. Exact: one adjoint solve (PageRank; the eigenvector 1 + the number of tied top scores), one shortest-path pass plus an O(|E| |V| / 64) reachability table (closeness, harmonic), O(|E|) (strength).

Checked

As jacobian_column (the earlier Jacobian tool's row on the weighted graph: within 7.8e-12 of the largest entry). EXACT is 128-1200x faster than finite differences at 1,000 edges and 1,600-10,000x at 10,000 edges (PageRank, eigenvector).

Threads

Finite differences: the edges (columns) are split over tasks, each evaluating the measure on its own thread; the first failing edge's error is the one reported. Exact rows run on the calling thread. Results are bit-identical for any thread count.

C name

og_jacobian_row

In notebooks

Og.JacobianRow

igraph 1.0

None: Open Graph's own.

`jacobian_top_k`#

Within tolerance Threads Extension

Returns the k edges whose weights move one vertex's centrality the most.

og_error_t og_jacobian_top_k(
    const og_t *graph,
    const og_vector_t *weights,
    og_int_t vertex,
    og_int_t k,
    const og_jacobian_options_t *opts,
    og_vector_int_t *edges,
    og_vector_t *values,
    og_vector_int_t *endpoints
);

Computes the row of vertex (as jacobian_row, the mean of the two sides) and ranks the edges by |derivative|, largest first; equal sizes go by ascending edge id (the stable order of Norway Analytics' earlier Jacobian tool) and NaN counts as the smallest. When the graph has fewer than k edges, all are returned. edges and values get the chosen edges and their derivatives; endpoints, when given, two vertex ids per edge (from and to, as edge reports them).

Parameters

graph The graph (at least one edge).
weights Edge weights, or NULL for all 1.
vertex The vertex whose centrality is followed.
k How many edges to return, >= 1.
opts Options, or NULL for the defaults.
edges Output, may be NULL: the edge ids, most influential first.
values Output, may be NULL: their derivatives (signed).
endpoints Output, may be NULL: from and to of each edge.

Returns

OG_SUCCESS.

Errors

OG_EINVVID vertex is not a vertex of the graph.
OG_EINVAL k is below 1.
OG_EINVAL The graph has no edges; eps is not positive or not finite; weights does not have |E| entries.
OG_EINVAL An unknown measure or method.
OG_EINVAL Weights the measure refuses: PageRank negative or NaN; eigenvector NaN; betweenness, closeness and harmonic not above zero; exact strength NaN.
OG_EINVAL PageRank's exact method at damping 1 on a walk with a closed class.
OG_UNIMPLEMENTED Exact eigenvector: a directed walk with a cycle and a negative weight (the leading eigenpair can be complex).
OG_DIVERGED Exact eigenvector: a linear solve fails (the leading eigenvalue is not simple).
OG_ENOMEM Not enough memory.

Complexity

As jacobian_row, plus O(|E| log |E|) for the ranking.

Checked

The earlier Jacobian tool's edges, endpoints and values on the karate club (PageRank, eigenvector, closeness) and on a weighted graph (harmonic); random cases compare the order wherever sizes differ beyond the tolerance.

Threads

As jacobian_row.

C name

og_jacobian_top_k

In notebooks

Og.JacobianTopK

igraph 1.0

None: Open Graph's own.

See also

jacobian_row

#include "og.h"
#include <stdio.h>

int main(void) {
    og_t g;
    og_jacobian_options_t opts;
    og_vector_int_t edges, ends;
    og_vector_t vals;
    og_int_t i;
    og_famous(&g, "Zachary");
    og_jacobian_options_init(&opts);
    opts.measure = OG_JACOBIAN_CLOSENESS;       /* piecewise linear: see the warning */
    og_vector_int_init(&edges, 0);
    og_vector_int_init(&ends, 0);
    og_vector_init(&vals, 0);
    og_jacobian_top_k(&g, NULL, 0, 5, &opts, &edges, &vals, &ends);
    for (i = 0; i < og_vector_int_size(&edges); i++) {
        printf("edge %" OG_PRId " (%" OG_PRId "-%" OG_PRId "): %g\n", OG_VECTOR(edges)[i],
               OG_VECTOR(ends)[2 * i], OG_VECTOR(ends)[2 * i + 1], OG_VECTOR(vals)[i]);
    }
    og_vector_destroy(&vals);
    og_vector_int_destroy(&ends);
    og_vector_int_destroy(&edges);
    og_destroy(&g);
    return 0;
}

`jacobian_full`#

Within tolerance Threads Extension

Returns the whole Jacobian: every vertex's response to every edge weight.

og_error_t og_jacobian_full(
    const og_t *graph,
    const og_vector_t *weights,
    const og_jacobian_options_t *opts,
    og_matrix_t *res,
    og_vector_t *colsums,
    og_matrix_t *left,
    og_matrix_t *right,
    og_matrix_bool_t *tie
);

J[i][e] = d c_i / d w_e: how the centrality c_i of vertex i responds to the weight w_e of edge e, around the given weights (all 1 when weights is NULL). res is the |V| x |E| matrix (rows vertices, columns edges) and colsums, when given, its |E| column sums. left, right and tie are optional matrices of the same size (see jacobian_column).

Exact PageRank and eigenvector use one dense LU factorisation of the |V| x |V| system, reused for every row, when |V| <= |E| and the system is small against the arcs (|V|^2 at most 200 times the arcs of the walk for PageRank, 400 times the edges for the eigenvector); otherwise min(|V|, |E|) iterative solves. Closeness and harmonic take |V| shortest-path passes; finite differences 2|E| evaluations. The library sets no size limit: the matrix alone takes |V| x |E| reals, so callers should cap the size.

Parameters

graph The graph (at least one edge).
weights Edge weights, or NULL for all 1.
opts Options, or NULL for the defaults.
res Output, may be NULL: the |V| x |E| matrix.
colsums Output, may be NULL: the |E| column sums.
left Output, may be NULL: left derivatives, |V| x |E|.
right Output, may be NULL: right derivatives, |V| x |E|.
tie Output, may be NULL: true where left and right differ, |V| x |E|.

Returns

OG_SUCCESS.

Errors

OG_ENOMEM |V| x |E| does not fit in an og_int_t, or memory runs out.
OG_EINVAL The graph has no edges; eps is not positive or not finite; weights does not have |E| entries.
OG_EINVAL An unknown measure or method.
OG_EINVAL Weights the measure refuses: PageRank negative or NaN; eigenvector NaN; betweenness, closeness and harmonic not above zero; exact strength NaN.
OG_EINVAL PageRank's exact method at damping 1 on a walk with a closed class.
OG_UNIMPLEMENTED Exact eigenvector: a directed walk with a cycle and a negative weight (the leading eigenpair can be complex).
OG_DIVERGED Exact eigenvector: a linear solve fails (the leading eigenvalue is not simple).

Complexity

Finite differences: 2|E| evaluations and |V| |E| memory. Exact PageRank and eigenvector: O(|V|^3) with the dense route, else min(|V|, |E|) iterative solves; closeness and harmonic: |V| shortest-path passes.

Checked

Every route checked against jacobian_column and jacobian_row; at 1,000 edges the exact matrix takes 10-12 ms against 190-1,230 ms by finite differences.

Threads

Finite differences: columns split over tasks. Exact PageRank and eigenvector: the iterative solves (and the eigenvector's dense-LU solves, with factors built once on the calling thread and only read by the tasks) split over tasks; exact closeness and harmonic: one task per source. Bit-identical for any thread count.

C name

og_jacobian_full

In notebooks

Og.JacobianFull

igraph 1.0

None: Open Graph's own.

See also

jacobian_column, jacobian_row

`jacobian_betweenness_margins`#

Unit tests Threads Extension

Tells how far each edge weight can move before any betweenness can change.

og_error_t og_jacobian_betweenness_margins(
    const og_t *graph,
    const og_vector_t *weights,
    og_bool_t directed,
    og_vector_t *up,
    og_vector_t *down,
    og_vector_bool_t *vertex_tie
);

Betweenness is constant in the weights until the set of shortest paths of some pair changes. For every edge e, up[e] is how far w_e can grow before that happens (+inf: never; 0: at once) and down[e] how far it can shrink (+inf: never; a value at or beyond w_e means no change while the weight stays positive). Strictly inside these margins every shortest-path set, hence every vertex and edge betweenness, stays the same; at the margin one changes. Self-loops are never on a shortest path: +inf both ways.

vertex_tie[v] is true when v lies on some but not all shortest paths between some pair of other vertices, so an arbitrarily small change of some weight can move its betweenness; when false, no small change of any single weight moves it. Path lengths count as equal as in betweenness (relative tolerance 1e-10). The margins come from the shortest-path DAG of every source and its dominator tree (Cooper, Harvey and Kennedy, 2001).

Parameters

graph The graph.
weights Edge weights (positive), or NULL for all 1.
directed Follow edge directions, as betweenness's directed.
up Output, may be NULL: margin upwards per edge.
down Output, may be NULL: margin downwards per edge.
vertex_tie Output, may be NULL: per vertex, whether it sits at a tie.

Returns

OG_SUCCESS.

Errors

OG_EINVAL As betweenness: weights of the wrong length, or not above zero.
OG_ENOMEM Not enough memory.

Complexity

One shortest-path pass per vertex plus sorting: O(|V| |E| log |E|).

Checked

No oracle has this. Checked through betweenness itself on seeded random graphs: nothing changes just inside a margin, the edge's own betweenness changes just outside; independently verified against shortest-path DAGs recomputed after each move (dyadic weights, exact sums); vertex_tie equals the brute-force 'on some but not all shortest paths of a pair'.

Threads

One task per source vertex; the margins are minima and the ties an 'or' over sources, exact in any order.

C name

og_jacobian_betweenness_margins

In notebooks

Og.JacobianBetweennessMargins

igraph 1.0

None: Open Graph's own.

See also

betweenness, jacobian_column

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

Jacobian

Types

jacobian_measure_ttype#

jacobian_smoothness_ttype#

jacobian_method_ttype#

jacobian_options_ttype#

Options and measures

jacobian_options_init#

jacobian_smoothness#

jacobian_warning#

jacobian_measure_name#

jacobian_measure_from_name#

Derivatives

jacobian_column#

jacobian_row#

jacobian_top_k#

jacobian_full#

jacobian_betweenness_margins#

`jacobian_measure_t`type#

`jacobian_smoothness_t`type#

`jacobian_method_t`type#

`jacobian_options_t`type#

`jacobian_options_init`#

`jacobian_smoothness`#

`jacobian_warning`#

`jacobian_measure_name`#

`jacobian_measure_from_name`#

`jacobian_column`#

`jacobian_row`#

`jacobian_top_k`#

`jacobian_full`#

`jacobian_betweenness_margins`#