Similarity, transitivity and mixing

Chooses how get_laplacian() scales D - A.

typedef enum og_laplacian_normalization_t {
    OG_LAPLACIAN_UNNORMALIZED = 0, /* D - A */
    OG_LAPLACIAN_SYMMETRIC = 1,    /* I - D^(-1/2) A D^(-1/2) */
    OG_LAPLACIAN_LEFT = 2,         /* I - D^(-1) A   (rows scaled) */
    OG_LAPLACIAN_RIGHT = 3         /* I - A D^(-1)   (columns scaled) */
} og_laplacian_normalization_t;

OG_LAPLACIAN_UNNORMALIZED (0): L = D - A. OG_LAPLACIAN_SYMMETRIC (1): I - D^(-1/2) A D^(-1/2), symmetric for undirected graphs, eigenvalues in [0, 2]. OG_LAPLACIAN_LEFT (2): I - D^(-1) A, the random-walk form with rows scaled. OG_LAPLACIAN_RIGHT (3): I - A D^(-1), columns scaled. D holds the degrees or strengths chosen by the mode argument.

Checked

Same four values as igraph 1.0.

C name

og_laplacian_normalization_t

In notebooks

Og.LaplacianNormalization

igraph 1.0

igraph_laplacian_normalization_t

See also

get_laplacian, get_laplacian_sparse

Counts, for pairs of vertices, how many vertices both of them point to.

og_error_t og_bibcoupling(
    const og_t *graph,
    og_matrix_t *res,
    const og_vs_t vids
);

Row i of res belongs to the i-th vertex u of vids and has one column per vertex of the graph: res[i][v] is the number of vertices w with edges u -> w and v -> w, the bibliographic coupling of two papers that cite the same works (Kessler, 1963).

Multi-edges count with their multiplicity and self-loops are allowed: an entry counts the ways to pick two different edges at the shared vertex, one leading to each of the two vertices, so for a simple graph the diagonal is zero. Undirected graphs use all neighbours.

When a vertex appears several times in vids only its last row is filled; the earlier ones stay zero (the reference's behaviour).

Parameters

• graph The input graph; it is not changed.
• res An initialized matrix; receives |vids| rows and |V| columns.
• vids The vertices whose rows are computed.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVVID The selector names a vertex that does not exist.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|vids| |V| + sum over the selected u of the degrees of u's neighbours).

Checked

Identical to igraph 1.0 on 220 random graphs (loops, multi-edges, both directions).

C name

og_bibcoupling

In notebooks

Og.Bibcoupling

igraph 1.0

igraph_bibcoupling

See also

cocitation, similarity_jaccard, similarity_inverse_log_weighted

Counts, for pairs of vertices, how many vertices point to both of them.

og_error_t og_cocitation(
    const og_t *graph,
    og_matrix_t *res,
    const og_vs_t vids
);

Row i of res belongs to the i-th vertex u of vids: res[i][v] is the number of vertices w with edges w -> u and w -> v, the cocitation of two papers cited together (Small, 1973).

Multi-edges count with their multiplicity and self-loops are allowed: an entry counts the ways to pick two different edges at the shared vertex, one leading to each of the two vertices, so for a simple graph the diagonal is zero. Undirected graphs use all neighbours.

When a vertex appears several times in vids only its last row is filled; the earlier ones stay zero (the reference's behaviour).

Parameters

• graph The input graph; it is not changed.
• res An initialized matrix; receives |vids| rows and |V| columns.
• vids The vertices whose rows are computed.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVVID The selector names a vertex that does not exist.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|vids| |V| + sum over the selected u of the degrees of u's neighbours).

Checked

Identical to igraph 1.0 on 220 random graphs.

C name

og_cocitation

In notebooks

Og.Cocitation

igraph 1.0

igraph_cocitation

See also

bibcoupling, similarity_inverse_log_weighted

Computes the Jaccard similarity of the neighbourhoods of two sets of vertices.

og_error_t og_similarity_jaccard(
    const og_t *graph,
    og_matrix_t *res,
    const og_vs_t from,
    const og_vs_t to,
    og_neimode_t mode,
    og_bool_t loops
);

res[i][j] = |N(a) ∩ N(b)| / |N(a) ∪ N(b)| for a the i-th vertex of from and b the j-th vertex of to: the number of shared neighbours over the number of distinct neighbours of the two (Jaccard, 1901). Neighbour sets follow mode in directed graphs (OG_OUT successors, OG_IN predecessors, OG_ALL both) and use all neighbours in undirected ones; multi-edges count once. With loops true every vertex is counted as its own neighbour; with loops false self-loops are ignored.

Two empty sets give 0, except on the diagonal positions (same row and column index naming the same vertex), which are always 1. The row vertex's set is marked once and each cell counts the column vertex's marked neighbours; when the sets are dense, the sets become bit rows and a cell is one AND plus a bit count. Both give the same exact counts.

Parameters

• graph The input graph; it is not changed.
• res An initialized matrix; receives |from| rows and |to| columns.
• from The row vertices.
• to The column vertices.
• mode OG_OUT, OG_IN or OG_ALL.
• loops Whether each vertex counts as its own neighbour.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVVID A selector names a vertex that does not exist.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|) for the neighbour sets, then for each cell the size of the column vertex's set (or |V|/64 words on the dense path).

Checked

Identical to igraph 1.0 on 220 random graphs, all modes, loops on and off.

Threads

Uses Open Graph's thread layer when set_num_threads() allows more than one thread and the work is large enough: rows are split into chunks over the tasks, each task with its own scratch marks. Every value is computed exactly as one thread computes it, so the result is identical for any number of threads.

SIMD

The dense path counts shared neighbours with the and_popcount kernel (VPOPCNTDQ, POPCNT or NEON CNT); it is chosen when the sets average at least two elements per 64-bit word (eight on the scalar path).

C name

og_similarity_jaccard

In notebooks

Og.SimilarityJaccard

igraph 1.0

igraph_similarity_jaccard

See also

similarity_jaccard_pairs, similarity_jaccard_es, similarity_dice, cocitation

og_t g;
og_matrix_t sim;
og_small(&g, 4, OG_UNDIRECTED, 0,1, 0,2, 1,2, 2,3, -1);
og_matrix_init(&sim, 0, 0);
og_similarity_jaccard(&g, &sim, og_vss_all(), og_vss_all(), OG_ALL, false);
/* sim[0][1] = 1/3: N(0) = {1,2}, N(1) = {0,2} share one of three vertices */
og_matrix_destroy(&sim);
og_destroy(&g);

Computes the Jaccard similarity for a list of vertex pairs.

og_error_t og_similarity_jaccard_pairs(
    const og_t *graph,
    og_vector_t *res,
    const og_vector_int_t *pairs,
    og_neimode_t mode,
    og_bool_t loops
);

pairs holds 2k vertex ids (a0, b0, a1, b1, ...); res[i] is the Jaccard similarity of the neighbour sets of ai and bi, defined as in similarity_jaccard(). Neighbour sets follow mode in directed graphs (OG_OUT successors, OG_IN predecessors, OG_ALL both) and use all neighbours in undirected ones; multi-edges count once. With loops true every vertex is counted as its own neighbour; with loops false self-loops are ignored. A pair (v, v) gives 1; two empty sets give 0. Only the sets of vertices named in pairs are built.

Parameters

• graph The input graph; it is not changed.
• res Receives one value per pair.
• pairs The vertex pairs, flattened; an even number of ids.
• mode OG_OUT, OG_IN or OG_ALL.
• loops Whether each vertex counts as its own neighbour.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL pairs has an odd number of entries.
• OG_EINVVID pairs holds an id that is not a vertex.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E| + sum over the pairs of the two set sizes).

Checked

Identical to igraph 1.0 on 220 random graphs.

Threads

Uses Open Graph's thread layer when set_num_threads() allows more than one thread and the work is large enough: pairs are split into chunks over the tasks, each task with its own scratch marks. Every value is computed exactly as one thread computes it, so the result is identical for any number of threads.

C name

og_similarity_jaccard_pairs

In notebooks

Og.SimilarityJaccardPairs

igraph 1.0

igraph_similarity_jaccard_pairs

See also

similarity_jaccard, similarity_jaccard_es, similarity_dice_pairs

Computes the Jaccard similarity of the two endpoints of each selected edge.

og_error_t og_similarity_jaccard_es(
    const og_t *graph,
    og_vector_t *res,
    const og_es_t es,
    og_neimode_t mode,
    og_bool_t loops
);

For every edge of es, in selector order, the Jaccard similarity of the neighbour sets of its two endpoints, as similarity_jaccard_pairs() computes it for the pair (from, to). Neighbour sets follow mode in directed graphs (OG_OUT successors, OG_IN predecessors, OG_ALL both) and use all neighbours in undirected ones; multi-edges count once. With loops true every vertex is counted as its own neighbour; with loops false self-loops are ignored. A self-loop's endpoints are the same vertex and give 1.

Parameters

• graph The input graph; it is not changed.
• res Receives one value per selected edge.
• es The edges whose endpoints are compared.
• mode OG_OUT, OG_IN or OG_ALL.
• loops Whether each vertex counts as its own neighbour.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVEID The selector names an edge that does not exist.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E| + sum over the selected edges of the two set sizes).

Checked

Equal to igraph 1.0's pair form on the edge endpoints, 220 graphs.

Threads

Uses Open Graph's thread layer when set_num_threads() allows more than one thread and the work is large enough: pairs are split into chunks over the tasks, each task with its own scratch marks. Every value is computed exactly as one thread computes it, so the result is identical for any number of threads.

C name

og_similarity_jaccard_es

In notebooks

Og.SimilarityJaccardEs

igraph 1.0

igraph_similarity_jaccard_es

See also

similarity_jaccard_pairs, similarity_dice_es

Computes the Dice similarity of the neighbourhoods of two sets of vertices.

og_error_t og_similarity_dice(
    const og_t *graph,
    og_matrix_t *res,
    const og_vs_t vit_from,
    const og_vs_t vit_to,
    og_neimode_t mode,
    og_bool_t loops
);

res[i][j] = 2 |N(a) ∩ N(b)| / (|N(a)| + |N(b)|) for a the i-th vertex of vit_from and b the j-th vertex of vit_to (Dice, 1945). For one pair it equals 2J / (1 + J), J the Jaccard similarity. Neighbour sets follow mode in directed graphs (OG_OUT successors, OG_IN predecessors, OG_ALL both) and use all neighbours in undirected ones; multi-edges count once. With loops true every vertex is counted as its own neighbour; with loops false self-loops are ignored.

Two empty sets give 0, except on the diagonal positions (same row and column index naming the same vertex), which are 1. Same machinery as similarity_jaccard().

Parameters

• graph The input graph; it is not changed.
• res An initialized matrix; receives |vit_from| rows and |vit_to| columns.
• vit_from The row vertices.
• vit_to The column vertices.
• mode OG_OUT, OG_IN or OG_ALL.
• loops Whether each vertex counts as its own neighbour.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVVID A selector names a vertex that does not exist.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

As similarity_jaccard().

Checked

Identical to igraph 1.0 on 220 random graphs.

Threads

Uses Open Graph's thread layer when set_num_threads() allows more than one thread and the work is large enough: rows are split into chunks over the tasks, each task with its own scratch marks. Every value is computed exactly as one thread computes it, so the result is identical for any number of threads.

SIMD

As similarity_jaccard(): the dense path uses the and_popcount kernel.

C name

og_similarity_dice

In notebooks

Og.SimilarityDice

igraph 1.0

igraph_similarity_dice

See also

similarity_dice_pairs, similarity_dice_es, similarity_jaccard

Computes the Dice similarity for a list of vertex pairs.

og_error_t og_similarity_dice_pairs(
    const og_t *graph,
    og_vector_t *res,
    const og_vector_int_t *pairs,
    og_neimode_t mode,
    og_bool_t loops
);

pairs holds 2k vertex ids (a0, b0, a1, b1, ...); res[i] is the Dice similarity 2 |N(ai) ∩ N(bi)| / (|N(ai)| + |N(bi)|). Neighbour sets follow mode in directed graphs (OG_OUT successors, OG_IN predecessors, OG_ALL both) and use all neighbours in undirected ones; multi-edges count once. With loops true every vertex is counted as its own neighbour; with loops false self-loops are ignored. A pair (v, v) gives 1; two empty sets give 0.

Parameters

• graph The input graph; it is not changed.
• res Receives one value per pair.
• pairs The vertex pairs, flattened; an even number of ids.
• mode OG_OUT, OG_IN or OG_ALL.
• loops Whether each vertex counts as its own neighbour.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL pairs has an odd number of entries.
• OG_EINVVID pairs holds an id that is not a vertex.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E| + sum over the pairs of the two set sizes).

Checked

Identical to igraph 1.0 on 220 random graphs.

Threads

Uses Open Graph's thread layer when set_num_threads() allows more than one thread and the work is large enough: pairs are split into chunks over the tasks, each task with its own scratch marks. Every value is computed exactly as one thread computes it, so the result is identical for any number of threads.

C name

og_similarity_dice_pairs

In notebooks

Og.SimilarityDicePairs

igraph 1.0

igraph_similarity_dice_pairs

See also

similarity_dice, similarity_jaccard_pairs

Computes the Dice similarity of the two endpoints of each selected edge.

og_error_t og_similarity_dice_es(
    const og_t *graph,
    og_vector_t *res,
    const og_es_t es,
    og_neimode_t mode,
    og_bool_t loops
);

For every edge of es, in selector order, the Dice similarity of the neighbour sets of its two endpoints. Neighbour sets follow mode in directed graphs (OG_OUT successors, OG_IN predecessors, OG_ALL both) and use all neighbours in undirected ones; multi-edges count once. With loops true every vertex is counted as its own neighbour; with loops false self-loops are ignored. A self-loop gives 1.

Parameters

• graph The input graph; it is not changed.
• res Receives one value per selected edge.
• es The edges whose endpoints are compared.
• mode OG_OUT, OG_IN or OG_ALL.
• loops Whether each vertex counts as its own neighbour.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVEID The selector names an edge that does not exist.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E| + sum over the selected edges of the two set sizes).

Checked

Equal to igraph 1.0's pair form on the edge endpoints, 220 graphs.

Threads

Uses Open Graph's thread layer when set_num_threads() allows more than one thread and the work is large enough: pairs are split into chunks over the tasks, each task with its own scratch marks. Every value is computed exactly as one thread computes it, so the result is identical for any number of threads.

C name

og_similarity_dice_es

In notebooks

Og.SimilarityDiceEs

igraph 1.0

igraph_similarity_dice_es

See also

similarity_dice_pairs, similarity_jaccard_es

Adamic-Adar similarity: shared neighbours, each weighted by one over the log of its degree.

og_error_t og_similarity_inverse_log_weighted(
    const og_t *graph,
    og_matrix_t *res,
    const og_vs_t vids,
    og_neimode_t mode
);

res[i][v] sums 1 / log(k(w)) over the neighbours w that the i-th vertex u of vids shares with v (Adamic and Adar, 2003), so rare shared neighbours weigh more than hubs. mode chooses the neighbours in directed graphs and with them the degree k(w): OG_OUT compares successors and weights each by its in-degree, OG_IN compares predecessors and uses the out-degree, OG_ALL uses both and the total degree. Undirected graphs use all neighbours and degrees.

Shared neighbours are counted as in cocitation(), once per pair of different edges, so multi-edges count with their multiplicity and the diagonal of a simple graph is zero. A vertex of degree 1 can never be shared and adds nothing.

Parameters

• graph The input graph; it is not changed.
• res An initialized matrix; receives |vids| rows and |V| columns.
• vids The vertices whose rows are computed.
• mode OG_OUT, OG_IN or OG_ALL.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVVID The selector names a vertex that does not exist.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|vids| |V| + sum over the selected u of the degrees of u's neighbours).

Checked

Identical to igraph 1.0 on 220 random graphs, all modes.

C name

og_similarity_inverse_log_weighted

In notebooks

Og.SimilarityInverseLogWeighted

igraph 1.0

igraph_similarity_inverse_log_weighted

See also

cocitation, bibcoupling, similarity_jaccard

Computes the global clustering coefficient: the share of connected triples that are closed.

og_error_t og_transitivity_undirected(
    const og_t *graph,
    og_real_t *res,
    og_transitivity_mode_t mode
);

res = 3T / P, T the number of triangles and P the number of connected triples (paths of two edges, counted at their middle vertex as d(d - 1)/2) (Wasserman and Faust, 1994). The graph is read as simple and undirected: directions, multi-edges and self-loops are ignored. A graph without connected triples gives NaN with OG_TRANSITIVITY_NAN and 0 with OG_TRANSITIVITY_ZERO.

Triangles are listed once each by orienting every edge towards its end of higher (degree, id) rank (Chiba-Nishizeki, Schank-Wagner).

Parameters

• graph The input graph; it is not changed.
• res Receives the coefficient.
• mode OG_TRANSITIVITY_NAN (0) or OG_TRANSITIVITY_ZERO (1): the value when it is undefined.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVAL mode is neither OG_TRANSITIVITY_NAN nor OG_TRANSITIVITY_ZERO.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

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

Checked

Identical to igraph 1.0 on 220 random graphs, both modes.

C name

og_transitivity_undirected

In notebooks

Og.TransitivityUndirected

igraph 1.0

igraph_transitivity_undirected

See also

transitivity_local_undirected, transitivity_avglocal_undirected, count_triangles

og_t g;
og_real_t t;
/* a triangle 0-1-2 with a pendant vertex 3 on 2 */
og_small(&g, 4, OG_UNDIRECTED, 0,1, 1,2, 2,0, 2,3, -1);
og_transitivity_undirected(&g, &t, OG_TRANSITIVITY_NAN);   /* 3 / 5 = 0.6 */
og_destroy(&g);

Computes the local clustering coefficient of selected vertices.

og_error_t og_transitivity_local_undirected(
    const og_t *graph,
    og_vector_t *res,
    const og_vs_t vids,
    og_transitivity_mode_t mode
);

For a vertex with d distinct neighbours (other than itself) and t triangles through it, the coefficient is t / (d(d - 1)/2): the share of its neighbour pairs that are joined (Watts and Strogatz, 1998). Directions, repeated edges and self-loops play no part, so the graph counts as simple and undirected. Where a vertex has zero or one neighbour the value is NaN or 0, as mode says.

With all vertices selected, every triangle is listed once (O(|E|^1.5)); for a vertex list (repeats allowed) each vertex counts the edges among its own neighbours.

Parameters

• graph The input graph; it is not changed.
• res Receives one value per selected vertex.
• vids The vertices to compute.
• mode OG_TRANSITIVITY_NAN or OG_TRANSITIVITY_ZERO.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVAL mode is neither OG_TRANSITIVITY_NAN nor OG_TRANSITIVITY_ZERO.
• OG_EINVVID The selector names a vertex that does not exist.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

All vertices: O(|V| + |E|^1.5). A list: the sum, over the selected vertices, of their neighbours' degrees.

Checked

Identical to igraph 1.0 on 220 random graphs, all vertices and vertex lists.

C name

og_transitivity_local_undirected

In notebooks

Og.TransitivityLocalUndirected

igraph 1.0

igraph_transitivity_local_undirected

See also

transitivity_undirected, transitivity_avglocal_undirected, transitivity_barrat

og_t g;
og_vector_t loc;
og_small(&g, 4, OG_UNDIRECTED, 0,1, 1,2, 2,0, 2,3, -1);
og_vector_init(&loc, 0);
og_transitivity_local_undirected(&g, &loc, og_vss_all(), OG_TRANSITIVITY_ZERO);
/* loc = 1 1 0.333 0 */
og_vector_destroy(&loc);
og_destroy(&g);

Computes the average of the local clustering coefficients.

og_error_t og_transitivity_avglocal_undirected(
    const og_t *graph,
    og_real_t *res,
    og_transitivity_mode_t mode
);

The mean of transitivity_local_undirected() over the vertices. The graph is read as simple and undirected: directions, multi-edges and self-loops are ignored. With OG_TRANSITIVITY_NAN the vertices with fewer than two neighbours are left out of the mean (NaN when no vertex qualifies); with OG_TRANSITIVITY_ZERO they count as 0 and the mean is over all vertices (0 for the null graph).

Parameters

• graph The input graph; it is not changed.
• res Receives the average.
• mode OG_TRANSITIVITY_NAN or OG_TRANSITIVITY_ZERO.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVAL mode is neither OG_TRANSITIVITY_NAN nor OG_TRANSITIVITY_ZERO.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

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

Checked

Identical to igraph 1.0 on 220 random graphs, both modes.

C name

og_transitivity_avglocal_undirected

In notebooks

Og.TransitivityAvglocalUndirected

igraph 1.0

igraph_transitivity_avglocal_undirected

See also

transitivity_local_undirected, transitivity_undirected

Computes the weighted local clustering coefficient of Barrat et al.

og_error_t og_transitivity_barrat(
    const og_t *graph,
    og_vector_t *res,
    const og_vs_t vids,
    const og_vector_t *weights,
    og_transitivity_mode_t mode
);

For a vertex i with strength s_i and degree k_i, the coefficient is 1 / (s_i (k_i - 1)) times the sum, over ordered pairs of neighbours j, h that are joined, of (w_ij + w_ih) / 2 (Barrat, Barthelemy, Pastor-Satorras and Vespignani, 2004, eq. 5). With equal weights it equals the unweighted local coefficient. Edge directions are ignored; the degree counts a self-loop twice.

The graph must have no multi-edges once directions are ignored. With weights NULL the function warns and returns transitivity_local_undirected(). A zero denominator gives NaN with OG_TRANSITIVITY_NAN and 0 with OG_TRANSITIVITY_ZERO. With self-loops the values follow the reference, which counts triangles differently for 'all vertices' and for a vertex list; both ways are reproduced. The null graph gives an empty result.

Parameters

• graph The input graph; it is not changed.
• res Receives one value per selected vertex.
• vids The vertices to compute.
• weights Edge weights, or NULL for the unweighted coefficient (with a warning).
• mode OG_TRANSITIVITY_NAN or OG_TRANSITIVITY_ZERO.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVAL mode is invalid, weights has the wrong length, or the graph has multi-edges (directions ignored).
• OG_EINVVID The selector names a vertex that does not exist.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

All vertices: O(|E|^1.5) for simple graphs. A list: the sum, over the selected vertices, of their neighbours' degrees.

Checked

Identical to igraph 1.0 on 220 graphs with several weight kinds, both counting paths.

C name

og_transitivity_barrat

In notebooks

Og.TransitivityBarrat

igraph 1.0

igraph_transitivity_barrat

See also

transitivity_local_undirected, strength

Computes the edge clustering coefficient of selected edges.

og_error_t og_ecc(
    const og_t *graph,
    og_vector_t *res,
    const og_es_t eids,
    og_int_t k,
    og_bool_t offset,
    og_bool_t normalize
);

For an edge {i, j}, z is the number of cycles of length k through it in the simple undirected graph: triangles for k = 3, squares for k = 4 (Radicchi et al., 2004). With offset true, 1 is added to z. With normalize true, z is divided by the largest number of such cycles the degrees allow: min(d_i - 1, d_j - 1) for k = 3 and (d_i - 1)(d_j - 1) for k = 4, with degrees counting multi-edges and self-loops (twice). A bound of zero gives an infinite or NaN value.

Directed graphs are treated as undirected. A self-loop lies on no cycle and gets z = 0. Results follow the selector's order.

Parameters

• graph The input graph; it is not changed.
• res Receives one value per selected edge.
• eids The edges to compute.
• k The cycle length: 3 or 4.
• offset Whether to add 1 to the cycle count.
• normalize Whether to divide by the largest possible count.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVAL k is below 3.
• OG_UNIMPLEMENTED k is above 4.
• OG_EINVEID The selector names an edge that does not exist.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

k = 3: O(d_i + d_j) per edge. k = 4: the sum of the degrees of j's neighbours per edge. Plus O(|V| + |E|) for the neighbour sets.

Checked

Not exposed by python-igraph: checked against cycle counts from its simple_cycles() and degrees on 220 graphs.

C name

og_ecc

In notebooks

Og.Ecc

igraph 1.0

igraph_ecc

See also

transitivity_local_undirected, community_edge_betweenness

Builds the Laplacian matrix of a graph, plain or normalized.

og_error_t og_get_laplacian(
    const og_t *graph,
    og_matrix_t *res,
    og_neimode_t mode,
    og_laplacian_normalization_t normalization,
    const og_vector_t *weights
);

With A the weighted adjacency matrix and D the diagonal matrix of degrees (strengths), normalization selects L = D - A (OG_LAPLACIAN_UNNORMALIZED), I - D^(-1/2) A D^(-1/2) (OG_LAPLACIAN_SYMMETRIC), I - D^(-1) A (OG_LAPLACIAN_LEFT, rows scaled) or I - A D^(-1) (OG_LAPLACIAN_RIGHT, columns scaled). In directed graphs mode chooses D: OG_OUT the out-degrees (row sums of A), OG_IN the in-degrees (column sums), OG_ALL ignores directions. An undirected self-loop adds twice its weight to both A and D.

In the normalized forms an isolated vertex gets 0 on the diagonal. For directed graphs a normalized form is refused when a vertex has zero degree on the side used for scaling but edges on the other side (for example OG_OUT with SYMMETRIC or RIGHT and a vertex that only receives edges); an infinite degree is refused for every normalized form. The symmetric scale is computed from two square roots, so strengths beyond 1e154 do not overflow.

Parameters

• graph The input graph; it is not changed.
• res An initialized matrix; receives the |V| x |V| Laplacian.
• mode OG_OUT, OG_IN or OG_ALL (directed graphs).
• normalization An laplacian_normalization_t value.
• weights Edge weights (non-negative, not NaN), or NULL.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL Unknown normalization; weights has the wrong length or a negative or NaN value; a normalized form meets an infinite degree or a zero degree it would divide by.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

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

Checked

Identical to igraph 1.0 for every normalization and mode on 910 graphs, extreme weights included.

C name

og_get_laplacian

In notebooks

Og.GetLaplacian

igraph 1.0

igraph_get_laplacian

See also

get_laplacian_sparse, laplacian_normalization_t, get_adjacency, get_stochastic

og_t g;
og_matrix_t L;
og_small(&g, 3, OG_UNDIRECTED, 0,1, 1,2, -1);   /* a path */
og_matrix_init(&L, 0, 0);
og_get_laplacian(&g, &L, OG_ALL, OG_LAPLACIAN_UNNORMALIZED, NULL);
/* L = [1 -1 0; -1 2 -1; 0 -1 1] */
og_matrix_destroy(&L);
og_destroy(&g);

Builds the Laplacian matrix in sparse form.

og_error_t og_get_laplacian_sparse(
    const og_t *graph,
    og_sparsemat_t *sparseres,
    og_neimode_t mode,
    og_laplacian_normalization_t normalization,
    const og_vector_t *weights
);

The same matrix as get_laplacian(), written into an sparsemat_t in triplet form: one entry per vertex with a non-zero diagonal and one per edge direction with a non-zero weight. Entries for the same position (parallel edges, self-loops) add up, as triplet entries do. The matrix is resized to |V| x |V| first.

Parameters

• graph The input graph; it is not changed.
• sparseres An initialized sparse matrix; receives the Laplacian.
• mode OG_OUT, OG_IN or OG_ALL (directed graphs).
• normalization An laplacian_normalization_t value.
• weights Edge weights (non-negative, not NaN), or NULL.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL As get_laplacian().
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|).

Checked

Same entries as the dense form on the same fixtures.

C name

og_get_laplacian_sparse

In notebooks

Og.GetLaplacianSparse

igraph 1.0

igraph_get_laplacian_sparse

See also

get_laplacian, get_adjacency_sparse

Measures whether edges tend to join vertices of the same category.

og_error_t og_assortativity_nominal(
    const og_t *graph,
    const og_vector_t *weights,
    const og_vector_int_t *types,
    og_real_t *res,
    og_bool_t directed,
    og_bool_t normalized
);

types gives every vertex a category (a non-negative integer). With e_ij the share of edge ends going from category i to category j, a_i and b_i its row and column sums, the unnormalized value is sum_i e_ii - sum_i a_i b_i (the modularity of the categories), and the normalized one divides it by 1 - sum_i a_i b_i (Newman, 2003, eq. 2): 1 when edges only join equal categories, negative when they avoid them.

With directed true and a directed graph, edges are counted from tail to head; otherwise each edge counts in both directions. Weights are not supported yet. A graph without edges gives NaN.

Parameters

• graph The input graph; it is not changed.
• weights Must be NULL.
• types One non-negative category per vertex.
• res Receives the coefficient.
• directed Whether to use edge directions (directed graphs only).
• normalized Whether to divide by 1 - sum a_i b_i.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_UNIMPLEMENTED weights is not NULL.
• OG_EINVAL types does not have one entry per vertex or holds a negative value.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 on 220 random graphs.

C name

og_assortativity_nominal

In notebooks

Og.AssortativityNominal

igraph 1.0

igraph_assortativity_nominal

See also

assortativity, assortativity_degree, joint_type_distribution, modularity

Measures the correlation of a vertex value across the ends of the edges.

og_error_t og_assortativity(
    const og_t *graph,
    const og_vector_t *weights,
    const og_vector_t *values,
    const og_vector_t *values_in,
    og_real_t *res,
    og_bool_t directed,
    og_bool_t normalized
);

The Pearson correlation of values[u] and values[v] over the edges (u, v), each edge weighted by its weight (an edge of weight 2 counts like two edges). Undirected (or with directed false), each edge counts in both directions (Newman, 2002, eq. 4). Directed, the tail contributes values and the head values_in, or values again when values_in is NULL (Newman, 2003, eq. 21).

With normalized false the result is the covariance alone. When a variance is zero the coefficient is undefined (0/0) and the result is NaN or rounding noise, as in the reference. values_in is ignored, with a warning, when the computation is undirected.

Parameters

• graph The input graph; it is not changed.
• weights Edge weights, or NULL.
• values One value per vertex (the out-value in the directed case).
• values_in One in-value per vertex for the directed case, or NULL to use values.
• res Receives the coefficient.
• directed Whether to use edge directions (directed graphs only).
• normalized true: the correlation; false: the covariance.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVAL values or values_in does not have one entry per vertex, or weights does not have one entry per edge.

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 on 220 random graphs, weighted and not; zero-variance cases only required to succeed.

C name

og_assortativity

In notebooks

Og.Assortativity

igraph 1.0

igraph_assortativity

See also

assortativity_degree, assortativity_nominal

Measures whether vertices connect to vertices of similar degree.

og_error_t og_assortativity_degree(
    const og_t *graph,
    og_real_t *res,
    og_bool_t directed
);

assortativity() with degrees as the values, always normalized: positive when high-degree vertices link to each other, negative when hubs link to low-degree vertices. Undirected (or directed false), the degree with self-loops counted twice; directed, the out-degree of the tail against the in-degree of the head. Regular graphs give NaN (zero variance).

Parameters

• graph The input graph; it is not changed.
• res Receives the coefficient.
• directed Whether to use edge directions (directed graphs only).

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 on 220 random graphs.

C name

og_assortativity_degree

In notebooks

Og.AssortativityDegree

igraph 1.0

igraph_assortativity_degree

See also

assortativity, avg_nearest_neighbor_degree, joint_degree_distribution

og_t g;
og_real_t r;
/* two hubs, 3 and 4, linked to each other and to three leaves each */
og_small(&g, 8, OG_UNDIRECTED, 3,4, 3,0, 3,1, 3,2, 4,5, 4,6, 4,7, -1);
og_assortativity_degree(&g, &r, false);   /* r = -0.75: the hubs link mostly to leaves */
og_destroy(&g);

Computes the average degree of each vertex's neighbours, and its average per degree.

og_error_t og_avg_nearest_neighbor_degree(
    const og_t *graph,
    og_vs_t vids,
    og_neimode_t mode,
    og_neimode_t neighbor_degree_mode,
    og_vector_t *knn,
    og_vector_t *knnk,
    const og_vector_t *weights
);

knn[i] is the mean degree of the neighbours of the i-th selected vertex v. mode chooses which neighbours (and v's own degree), neighbor_degree_mode which degree of theirs is averaged; undirected graphs use all neighbours and degrees. Multi-edges count with their multiplicity and a self-loop makes v its own neighbour. With weights, the weighted form of Barrat et al. (2004, eq. 6): sum of w_vj k_j over the strength of v. A vertex without neighbours (or with zero strength) gets NaN.

knnk[k - 1] is the average of the neighbour degrees over the selected vertices of degree k (weighted: the sum of their numerators over the sum of their strengths), for k from 1 to the largest degree in the graph; NaN where no selected vertex has degree k. knn and knnk may be NULL.

Parameters

• graph The input graph; it is not changed.
• vids The vertices to compute.
• mode Which neighbours: OG_OUT, OG_IN or OG_ALL.
• neighbor_degree_mode Which degree of the neighbours: OG_OUT, OG_IN or OG_ALL.
• knn Receives one value per selected vertex; may be NULL.
• knnk Receives the average per degree; may be NULL.
• weights Edge weights, or NULL.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVMODE mode or neighbor_degree_mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL weights does not have one entry per edge.
• OG_EINVVID The selector names a vertex that does not exist.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 for mode ALL/ALL (all python-igraph exposes); the other mode pairs checked against a reference written from the definitions.

C name

og_avg_nearest_neighbor_degree

In notebooks

Og.AvgNearestNeighborDegree

igraph 1.0

igraph_avg_nearest_neighbor_degree

See also

degree_correlation_vector, assortativity_degree, strength

Computes the mean neighbour degree as a function of a vertex's degree, over all edges.

og_error_t og_degree_correlation_vector(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_t *knnk,
    og_neimode_t from_mode,
    og_neimode_t to_mode,
    og_bool_t directed_neighbors
);

knnk[k] is the mean to_mode degree of the vertices reached from vertices whose from_mode degree is k, taken over all connections and weighted by the edge weights; k runs from 0 to the largest from_mode degree, and NaN marks degrees without connections. With directed_neighbors true each directed edge is followed from tail to head only; with false, in both directions. Undirected graphs use total degrees and both directions.

This is k_nn(k) of Pastor-Satorras, Vazquez and Vespignani (2001), computed from the edges rather than from per-vertex averages.

Parameters

• graph The input graph; it is not changed.
• weights Edge weights, or NULL.
• knnk Receives the vector, indexed by degree.
• from_mode The degree of the source vertex: OG_OUT, OG_IN or OG_ALL.
• to_mode The degree of the reached vertex: OG_OUT, OG_IN or OG_ALL.
• directed_neighbors true: follow edges tail to head only; false: both ways.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVMODE from_mode or to_mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL weights does not have one entry per edge.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|).

Checked

Not exposed by python-igraph: a reference written from the definition, cross-checked against python-igraph's knn().

C name

og_degree_correlation_vector

In notebooks

Og.DegreeCorrelationVector

igraph 1.0

igraph_degree_correlation_vector

See also

avg_nearest_neighbor_degree, joint_degree_distribution

Builds the mixing matrix of vertex categories across the edges.

og_error_t og_joint_type_distribution(
    const og_t *graph,
    const og_vector_t *weights,
    og_matrix_t *p,
    const og_vector_int_t *from_types,
    const og_vector_int_t *to_types,
    og_bool_t directed,
    og_bool_t normalized
);

p[i][j] is the number (or total weight) of connections from a vertex of category i to a vertex of category j; from_types gives the category at the source and to_types at the target (to_types NULL: from_types for both). With directed true and a directed graph each edge counts once, tail to head; otherwise in both directions. With normalized true the matrix is divided by its sum, giving the joint distribution e_ij of Newman (2003). The matrix has (largest from category + 1) rows and (largest to category + 1) columns.

Parameters

• graph The input graph; it is not changed.
• weights Edge weights, or NULL.
• p An initialized matrix; receives the mixing matrix.
• from_types One non-negative category per vertex, used at the source.
• to_types One non-negative category per vertex, used at the target, or NULL.
• directed Whether to use edge directions (directed graphs only).
• normalized Whether to divide by the sum.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVAL A type vector does not have one entry per vertex or holds a negative value, or weights has the wrong length.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E| + rows x columns).

Checked

Not exposed by python-igraph: a reference written from the definition, cross-checked against python-igraph's modularity().

C name

og_joint_type_distribution

In notebooks

Og.JointTypeDistribution

igraph 1.0

igraph_joint_type_distribution

See also

assortativity_nominal, joint_degree_distribution

Builds the joint distribution of the degrees at the two ends of the edges.

og_error_t og_joint_degree_distribution(
    const og_t *graph,
    const og_vector_t *weights,
    og_matrix_t *p,
    og_neimode_t from_mode,
    og_neimode_t to_mode,
    og_bool_t directed_neighbors,
    og_bool_t normalized,
    og_int_t max_from_degree,
    og_int_t max_to_degree
);

p[i][j] is the number (or total weight) of connections from a vertex whose from_mode degree is i to a vertex whose to_mode degree is j. With directed_neighbors true each directed edge counts once, tail to head; with false, both ways. Undirected graphs use total degrees and both ways. The matrix has max_from_degree + 1 rows and max_to_degree + 1 columns; a negative maximum means the largest degree present, and connections beyond the limits are left out. normalized divides by the sum.

Parameters

• graph The input graph; it is not changed.
• weights Edge weights, or NULL.
• p An initialized matrix; receives the distribution.
• from_mode The degree at the source: OG_OUT, OG_IN or OG_ALL.
• to_mode The degree at the target: OG_OUT, OG_IN or OG_ALL.
• directed_neighbors true: tail to head only; false: both ways.
• normalized Whether to divide by the sum.
• max_from_degree The largest source degree kept, or negative for all.
• max_to_degree The largest target degree kept, or negative for all.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVMODE from_mode or to_mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL weights does not have one entry per edge.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E| + rows x columns).

Checked

Not exposed by python-igraph: a reference written from the definition, cross-checked against degree assortativity.

C name

og_joint_degree_distribution

In notebooks

Og.JointDegreeDistribution

igraph 1.0

igraph_joint_degree_distribution

See also

joint_degree_matrix, joint_type_distribution, degree_correlation_vector

Builds the joint degree matrix: edge counts by the degrees of their two ends.

og_error_t og_joint_degree_matrix(
    const og_t *graph,
    const og_vector_t *weights,
    og_matrix_t *jdm,
    og_int_t max_out_degree,
    og_int_t max_in_degree
);

jdm[i - 1][j - 1] is the number (or total weight) of edges between a vertex of degree i and one of degree j (Stanton and Pinar, 2012). Directed graphs use the out-degree of the tail and the in-degree of the head. In undirected graphs the matrix is symmetric: an edge between degrees i != j is counted in both (i, j) and (j, i), an edge between equal degrees once in (i, i). The matrix has max_out_degree rows and max_in_degree columns (negative: the largest degree present); edges beyond the limits are left out.

Parameters

• graph The input graph; it is not changed.
• weights Edge weights, or NULL to count edges.
• jdm An initialized matrix; receives the joint degree matrix.
• max_out_degree Rows: the largest (out-)degree kept, or negative for all.
• max_in_degree Columns: the largest (in-)degree kept, or negative for all.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVAL weights does not have one entry per edge.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E| + rows x columns).

Checked

Not exposed by python-igraph: cross-checked against the joint degree distribution.

C name

og_joint_degree_matrix

In notebooks

Og.JointDegreeMatrix

igraph 1.0

igraph_joint_degree_matrix

See also

joint_degree_distribution

Gives the edge count or density of what is left as vertices are removed one by one.

og_error_t og_rich_club_sequence(
    const og_t *graph,
    const og_vector_t *weights,
    og_vector_t *res,
    const og_vector_int_t *vertex_order,
    og_bool_t normalized,
    og_bool_t loops,
    og_bool_t directed
);

Removes the vertices in vertex_order one at a time. res[i] describes the subgraph induced by the vertices not yet removed after i removals, vertex_order[i .. n - 1]: its number of edges (or total weight, self-loops included) or, with normalized true, that divided by the number of possible edges among its n - i vertices. That count follows density(): directed (directed true on a directed graph) k(k - 1), or k^2 with loops; undirected k(k - 1)/2, or k(k + 1)/2 with loops.

Ordering the vertices by increasing degree gives the rich-club curve of Zhou and Mondragon (2004) and Colizza et al. (2006). The sequence is built from the back, adding vertices, in one pass.

Parameters

• graph The input graph; it is not changed.
• weights Edge weights, or NULL to count edges.
• res Receives |V| values.
• vertex_order A permutation of the vertices: the removal order.
• normalized Whether to divide by the number of possible edges.
• loops Whether self-loops count as possible edges in that number.
• directed Whether to count possible edges as directed (directed graphs only).

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVAL vertex_order does not have one entry per vertex or repeats a vertex, or weights has the wrong length.
• OG_EINVVID vertex_order holds an id that is not a vertex.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

O(|V| + |E|).

Checked

Not exposed by python-igraph: checked against its induced_subgraph() edge counts and density() on 220 graphs.

C name

og_rich_club_sequence

In notebooks

Og.RichClubSequence

igraph 1.0

igraph_rich_club_sequence

See also

density, induced_subgraph

Tells whether a vector describes a valid matching of the graph.

og_error_t og_is_matching(
    const og_t *graph,
    const og_vector_bool_t *types,
    const og_vector_int_t *matching,
    og_bool_t *result
);

matching[v] is the vertex matched to v, or -1. It is a matching when it is symmetric (matching[matching[v]] = v), every matched pair is joined by an edge (either direction), and, when types is given, the two ends of every pair have different types. A vertex matched to itself is valid only along a self-loop and without types. A vector of the wrong length is simply not a matching (false, no error).

Parameters

• graph The input graph; it is not changed.
• types One boolean per vertex for a bipartite check, or NULL.
• matching The partner of every vertex, or -1.
• result Receives the answer.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVAL types has fewer entries than the graph has vertices (python-igraph does not check this).

Complexity

O(|V| log d).

Checked

Identical to igraph 1.0 on 220 graphs x about 10 candidate vectors.

C name

og_is_matching

In notebooks

Og.IsMatching

igraph 1.0

igraph_is_matching

See also

is_maximal_matching, maximum_bipartite_matching

Tells whether a matching is maximal: no edge could be added to it.

og_error_t og_is_maximal_matching(
    const og_t *graph,
    const og_vector_bool_t *types,
    const og_vector_int_t *matching,
    og_bool_t *result
);

True when is_matching() accepts the vector and no edge joins two unmatched vertices (of different types, when types is given). A maximal matching need not be maximum.

Parameters

• graph The input graph; it is not changed.
• types One boolean per vertex for a bipartite check, or NULL.
• matching The partner of every vertex, or -1.
• result Receives the answer.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVAL types has fewer entries than the graph has vertices.

Complexity

O(|V| + |E|).

Checked

Identical to igraph 1.0 on the same candidates.

C name

og_is_maximal_matching

In notebooks

Og.IsMaximalMatching

igraph 1.0

igraph_is_maximal_matching

See also

is_matching, maximum_bipartite_matching

Finds a maximum matching, or a maximum-weight matching, of a bipartite graph.

og_error_t og_maximum_bipartite_matching(
    const og_t *graph,
    const og_vector_bool_t *types,
    og_int_t *matching_size,
    og_real_t *matching_weight,
    og_vector_int_t *matching,
    const og_vector_t *weights,
    og_real_t eps
);

types splits the vertices into two sides (false and true); every edge must join the two sides. Edge directions are ignored. Without weights the result has the most pairs possible: Hopcroft-Karp after a greedy start. With weights it has the largest total weight, whatever its size: successive shortest augmenting paths with vertex potentials (the Hungarian method), each search a Dijkstra on a binary heap (or a Fibonacci heap when |E| > 4|V|). The search stops when the best augmenting path would lower the total by more than eps; a negative eps means automatic, an absolute 1000 machine epsilons (about 2.2e-13), as python-igraph uses.

matching[v] receives the partner of v or -1, matching_size the number of pairs and matching_weight their total weight (the number of pairs without weights); each may be NULL. Maximum matchings are seldom unique, so the vector may differ from python-igraph's while the size and weight agree. Among maximum-weight matchings ours has the most pairs.

Parameters

• graph The input graph; it is not changed.
• types One boolean per vertex: the side it is on.
• matching_size Receives the number of matched pairs; may be NULL.
• matching_weight Receives the total weight; may be NULL.
• matching Receives the partner of every vertex, or -1; may be NULL.
• weights Edge weights (finite), or NULL for a maximum cardinality matching.
• eps Tolerance for the weighted search; negative for automatic.

Returns

OG_SUCCESS, or the error code of the failure.

Errors

• OG_EINVAL types has fewer entries than vertices; an edge (or self-loop) joins two vertices of the same type; weights has fewer entries than edges or a NaN or infinite value.
• OG_ENOMEM Not enough memory for the work arrays or the result.

Complexity

Unweighted: O(sqrt(|V|) |E|). Weighted: O(|V| |E| + |V|^2 log |V|).

Checked

Size equal to igraph 1.0's; weighted total equal within 1e-9 relative; the matching itself may differ, and on weight ties ours has the most pairs.

C name

og_maximum_bipartite_matching

In notebooks

Og.MaximumBipartiteMatching

igraph 1.0

igraph_maximum_bipartite_matching

See also

is_matching, is_maximal_matching, is_bipartite

og_t g;
og_vector_bool_t types;
og_vector_int_t match;
og_int_t size;
og_real_t weight;
/* left side 0, 1, 2; right side 3, 4 */
og_small(&g, 5, OG_UNDIRECTED, 0,3, 0,4, 1,3, 2,4, -1);
og_vector_bool_init(&types, 5);
OG_VECTOR(types)[3] = true;
OG_VECTOR(types)[4] = true;
og_vector_int_init(&match, 0);
og_maximum_bipartite_matching(&g, &types, &size, &weight, &match, NULL, -1);
/* size = 2 */
og_vector_int_destroy(&match);
og_vector_bool_destroy(&types);
og_destroy(&g);