Community detection

The function type community_leading_eigenvector calls after each eigenvector computation.

typedef og_error_t og_community_leading_eigenvector_callback_t(
    const og_vector_int_t *membership,
    og_int_t comm,
    og_real_t eigenvalue,
    const og_vector_t *eigenvector,
    og_arpack_function_t *arpack_multiplier,
    void *arpack_extra,
    void *extra
);

Receives the membership before the split is applied, the id of the community examined, its leading eigenvalue and eigenvector (a view over the community's vertices in increasing id order, valid only during the call), a function that multiplies a vector by that community's generalised modularity matrix, arpack_multiplier(to, from, n, arpack_extra), with its data, and the callback_extra pointer given to community_leading_eigenvector.

Return OG_SUCCESS to go on, OG_STOP to end the run cleanly (this attempt's eigenvalue and eigenvector are still recorded, its split is not made), or any other error code to end the run with that error. The callback must not keep the pointers it receives.

Parameters

• membership The current membership (before this split).
• comm The id of the community being examined.
• eigenvalue Its leading eigenvalue.
• eigenvector Its leading eigenvector, one entry per member vertex in increasing id order.
• arpack_multiplier Multiplies a vector by the community's generalised modularity matrix (arpack_function_t).
• arpack_extra The data to pass to arpack_multiplier.
• extra The callback_extra argument of community_leading_eigenvector.

Returns

OG_SUCCESS to continue, OG_STOP to stop without error, another code to stop with that error.

Complexity

Called once per split attempt.

Checked

Tested for its arguments, OG_STOP and error codes; python-igraph exposes no C callback.

C name

og_community_leading_eigenvector_callback_t

In notebooks

Og.CommunityLeadingEigenvectorCallback

igraph 1.0

igraph_community_leading_eigenvector_callback_t

See also

community_leading_eigenvector

Computes the modularity of a partition of the vertices, with optional weights, resolution and directed form.

og_error_t og_modularity(
    const og_t *graph,
    const og_vector_int_t *membership,
    const og_vector_t *weights,
    const og_real_t resolution,
    const og_bool_t directed,
    og_real_t *modularity
);

Modularity measures how much more edge weight falls inside communities than a random graph with the same degrees would put there. Undirected: Q = W_in / W - gamma * sum_c (K_c / 2W)^2, where W is the total edge weight, W_in the weight of edges with both ends in one community and K_c the summed strength of community c (a self-loop adds its weight twice to its vertex's strength). Directed form (Leicht and Newman 2008), used when directed is true and the graph is directed: Q = W_in / W - gamma * sum_c (Kout_c / W)(Kin_c / W). A resolution of 1 gives the classic Newman-Girvan value; larger values favour smaller communities.

Community ids need not be contiguous: negative ids and ids of |V| or more are accepted and only group the vertices. Multi-edges add up. Without edges, or when all weights are 0, the result is NaN. Each community's share of the total is formed before squaring, so weights near 1e200 or 1e-200 and resolutions up to about 1e308 still give finite values.

Parameters

• graph The graph.
• membership Community id of every vertex (length |V|). Any integers.
• weights Edge weights (length |E|), non-negative; NULL means every edge weighs 1.
• resolution The resolution gamma, at least 0. Use 1 for ordinary modularity.
• directed Use the directed form when the graph is directed. Ignored for undirected graphs.
• modularity Output: the modularity. May be NULL, in which case only the arguments are checked.

Returns

OG_SUCCESS, or an error code. *modularity is NaN when the graph has no edges or a total weight of 0.

Errors

• OG_EINVAL membership does not have |V| entries.
• OG_EINVAL resolution is negative.
• OG_EINVAL weights does not have |E| entries, or holds a negative value.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|); O(|V| log |V|) more when some ids lie outside 0..|V|-1 and must be grouped by sorting.

Checked

Identical to python-igraph 1.0 on 300 random graphs (loops, multi-edges, weights with zeros, odd ids, resolutions 0-2, both forms); 0.15-0.37x python-igraph's time on 100k edges.

C name

og_modularity

In notebooks

Og.Modularity

igraph 1.0

igraph_modularity

See also

modularity_matrix, community_multilevel, community_leiden, reindex_membership

og_t g;
og_vector_int_t memb;
og_real_t q;
/* two triangles joined by the edge 2-3 */
og_small(&g, 6, OG_UNDIRECTED, 0,1, 1,2, 2,0, 3,4, 4,5, 5,3, 2,3, -1);
og_vector_int_init_int(&memb, 6, 0, 0, 0, 1, 1, 1);
og_modularity(&g, &memb, NULL, 1.0, false, &q);   /* q = 5/14 */
og_vector_int_destroy(&memb);
og_destroy(&g);

Builds the modularity matrix: the adjacency matrix minus the null model's expected edge weights.

og_error_t og_modularity_matrix(
    const og_t *graph,
    const og_vector_t *weights,
    const og_real_t resolution,
    og_matrix_t *modmat,
    og_bool_t directed
);

Undirected: B_ij = A_ij - gamma * k_i k_j / 2W, with A the symmetric weighted adjacency matrix (a self-loop of weight w adds 2w to A_ii), k_i the strength of vertex i and W the total edge weight. Directed form, used when directed is true and the graph is directed: B_ij = A_ij - gamma * kout_i kin_j / W, with A_ij the weight from i to j. Multi-edges add up.

Summing B_ij over the pairs inside each community and dividing by 2W (W in the directed form) gives the value of modularity for that partition. The matrix is dense, |V| x |V|. Only the length of weights is checked; with a total weight of 0 the null-model term is undefined and the entries are NaN.

Parameters

• graph The graph.
• weights Edge weights (length |E|); NULL means every edge weighs 1.
• resolution The resolution gamma, at least 0.
• modmat Output: an initialised matrix, resized to |V| x |V|.
• directed Use the directed form when the graph is directed. Ignored for undirected graphs.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL resolution is negative.
• OG_EINVAL weights does not have |E| entries.
• OG_ENOMEM Not enough memory.

Complexity

O(|V|^2 + |E|) time, O(|V|^2) memory.

Checked

Identical to python-igraph 1.0 on 238 random graphs of up to 30 vertices (weights, resolutions, both forms, self-loops).

C name

og_modularity_matrix

In notebooks

Og.ModularityMatrix

igraph 1.0

igraph_modularity_matrix

See also

modularity, community_leading_eigenvector

Finds a partition with the largest possible modularity by exact branch and cut.

og_error_t og_community_optimal_modularity(
    const og_t *graph,
    const og_vector_t *weights,
    const og_real_t resolution,
    og_real_t *modularity,
    og_vector_int_t *membership
);

Searches all partitions and proves the one it returns optimal (Brandes et al. 2008: a 0/1 variable per vertex pair, 'same community or not', with transitivity constraints). Each connected component is solved on its own, since joining parts that no edge links never raises modularity. Open Graph uses its own branch and cut, with no external LP solver: a bounded dual simplex with bound flipping and dual steepest-edge pricing on the LP relaxation, triangle and star inequalities (Groetschel and Wakabayashi) added as cutting planes, reduced-cost fixing, and starting partitions from local search. With integer weights and a rational resolution a branch must promise a whole step of modularity more than the best partition so far.

Directed graphs are optimised for directed modularity. For a directed graph the reported value counts self-loops as python-igraph 1.0 reports them (twice, as in the undirected adjacency matrix); the partition is not affected. The membership is numbered by first appearance. The local search uses its own generator, so the result never depends on the library's random state, and it does not depend on the scale of the weights.

The problem is NP-hard: components of a few dozen vertices take milliseconds to seconds, and components beyond about a hundred vertices can be very slow. Without edges, with a total weight of 0, or with a NaN or infinite resolution every vertex is left alone and the value is NaN; a single vertex with self-loops gives 1 - resolution.

Parameters

• graph The graph, directed or undirected.
• weights Edge weights (length |E|), non-negative, no NaN; NULL means every edge weighs 1.
• resolution The resolution gamma, at least 0.
• modularity Output: the largest modularity. May be NULL.
• membership Output: an optimal partition, ids 0..k-1 by first appearance. May be NULL.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL resolution is negative.
• OG_EINVAL weights does not have |E| entries, or holds a negative value or NaN.
• OG_ENOMEM Not enough memory, or a connected component is too large to solve: more than about 4,470 vertices (1e7 vertex pairs), or a simplex tableau that would exceed 512 MB.

Complexity

Exponential in the worst case. Memory: the pair objective of each component, O(p^2) for p vertices, plus the dense simplex tableau (at most 512 MB).

Checked

Same optimum value as python-igraph 1.0 on 241 graphs (234 random up to about 40 vertices and 7 hard ones); partitions compared by value, since several can be optimal. Median time ratio 0.067 against python-igraph on 240 random graphs.

C name

og_community_optimal_modularity

In notebooks

Og.CommunityOptimalModularity

igraph 1.0

igraph_community_optimal_modularity

See also

modularity, community_multilevel, community_leiden

Cuts a dendrogram after a given number of merges and gives the cluster of every leaf.

og_error_t og_community_to_membership(
    const og_matrix_int_t *merges,
    og_int_t nodes,
    og_int_t steps,
    og_vector_int_t *membership,
    og_vector_int_t *csize
);

merges is a two-column matrix: row i joins two dendrogram nodes into a new node nodes + i, and the leaves are 0..nodes-1. Applying the first steps rows leaves nodes - steps clusters. A row may only name leaves and nodes created by earlier rows, and no node may be merged twice.

Cluster ids: the clusters built by merges come first, numbered while walking the applied rows from the last one backwards (the cluster of the last row applied gets 0); each leaf no applied row touches then gets the next id, in increasing leaf order. csize[c] is the number of leaves in cluster c. This is the numbering python-igraph 1.0 uses.

Parameters

• merges The dendrogram, one merge per row, two columns (as produced by the hierarchical methods).
• nodes The number of leaves, usually |V|.
• steps How many rows to apply, from 0 to the number of rows (and at most nodes).
• membership Output: the cluster of each leaf (length nodes). May be NULL.
• csize Output: the size of each cluster (length nodes - steps). May be NULL.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL nodes or steps is negative, steps exceeds the number of rows or the number of leaves.
• OG_EINVAL merges does not have two columns (when steps > 0).
• OG_EINVAL An applied row names a node that does not exist or is created only by that row or a later one, or a node is merged twice.
• OG_ENOMEM Not enough memory.

Complexity

O(nodes + rows of merges).

Checked

Identical to python-igraph 1.0 on 260 cuts (random merge orders, partial dendrograms, every step count).

C name

og_community_to_membership

In notebooks

Og.CommunityToMembership

igraph 1.0

igraph_community_to_membership

See also

le_community_to_membership, community_walktrap, community_fastgreedy, community_edge_betweenness

Renumbers community ids to 0, 1, 2, ... in order of first appearance.

og_error_t og_reindex_membership(
    og_vector_int_t *membership,
    og_vector_int_t *new_to_old,
    og_int_t *nb_clusters
);

Rewrites membership in place: the community of element 0 becomes 0, the next community not seen yet becomes 1, and so on. The old ids may be any integers, negative ones included. new_to_old, when given, receives for each new id the old id it replaced, and nb_clusters the number of communities.

Ids that all lie in 0..n-1 are mapped through a direct table; other ids are first grouped with a stable sort.

Parameters

• membership Input and output: the ids to renumber.
• new_to_old Output: entry k is the old id of new id k. May be NULL.
• nb_clusters Output: the number of distinct ids. May be NULL.

Returns

OG_SUCCESS, or OG_ENOMEM.

Errors

• OG_ENOMEM Not enough memory.

Complexity

O(n) when every id lies in 0..n-1, O(n log n) otherwise (n = length of membership).

Checked

Same ids, mapping and count as python-igraph 1.0, for ids inside and outside 0..n-1.

C name

og_reindex_membership

In notebooks

Og.ReindexMembership

igraph 1.0

igraph_reindex_membership

See also

compare_communities, community_to_membership

Measures the distance or similarity of two partitions of the same elements.

og_error_t og_compare_communities(
    const og_vector_int_t *comm1,
    const og_vector_int_t *comm2,
    og_real_t *result,
    og_community_comparison_t method
);

Both vectors give a community id per element; ids may be any integers. method chooses the measure:
OG_COMMCMP_VI, variation of information (Meila 2003): H1 + H2 - 2 I, natural logarithms, 0 for identical partitions. OG_COMMCMP_NMI, normalised mutual information (Danon et al. 2005): 2 I / (H1 + H2), 1 for identical partitions and also when both entropies are 0. OG_COMMCMP_SPLIT_JOIN, split-join distance (van Dongen 2000): the sum of the two projection distances of split_join_distance. OG_COMMCMP_RAND, Rand index (Rand 1971): the share of element pairs that both partitions treat alike (together in both or apart in both). OG_COMMCMP_ADJUSTED_RAND, the Rand index corrected for chance (Hubert and Arabie 1985); NaN when its denominator is 0, for example when both partitions put everything in one community.

All five come from one sparse contingency table of the two partitions.

Parameters

• comm1 The first partition.
• comm2 The second partition, same length.
• result Output: the value. May be NULL.
• method One of OG_COMMCMP_VI, OG_COMMCMP_NMI, OG_COMMCMP_SPLIT_JOIN, OG_COMMCMP_RAND, OG_COMMCMP_ADJUSTED_RAND.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL Unknown method.
• OG_EINVAL The two vectors differ in length.
• OG_EINVAL Rand or adjusted Rand index of fewer than two elements.
• OG_ENOMEM Not enough memory.

Complexity

O(n), plus O(n log n) when ids lie outside 0..n-1.

Checked

Identical to python-igraph 1.0 on 260 pairs of partitions for all five measures, NaN where it gives NaN; about 0.2x python-igraph's time.

C name

og_compare_communities

In notebooks

Og.CompareCommunities

igraph 1.0

igraph_compare_communities

See also

split_join_distance, reindex_membership

og_vector_int_t a, b;
og_real_t nmi, vi;
og_vector_int_init_int(&a, 6, 0, 0, 0, 1, 1, 1);
og_vector_int_init_int(&b, 6, 5, 5, 7, 7, 7, 7);
og_compare_communities(&a, &b, &nmi, OG_COMMCMP_NMI);
og_compare_communities(&a, &b, &vi, OG_COMMCMP_VI);
og_vector_int_destroy(&b);
og_vector_int_destroy(&a);

Gives the two projection distances between two partitions; their sum is the split-join distance.

og_error_t og_split_join_distance(
    const og_vector_int_t *comm1,
    const og_vector_int_t *comm2,
    og_int_t *distance12,
    og_int_t *distance21
);

van Dongen (2000). distance12 is n minus the sum, over the communities of comm1, of each one's largest overlap with a community of comm2; distance21 is the same with the roles swapped. distance12 is 0 exactly when every community of comm1 lies inside a single community of comm2 (comm1 refines comm2). The sum of the two is what compare_communities returns for OG_COMMCMP_SPLIT_JOIN. Ids may be any integers.

Parameters

• comm1 The first partition.
• comm2 The second partition, same length.
• distance12 Output: the projection distance of comm1 from comm2. May be NULL.
• distance21 Output: the projection distance of comm2 from comm1. May be NULL.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL The two vectors differ in length.
• OG_ENOMEM Not enough memory.

Complexity

O(n), plus O(n log n) when ids lie outside 0..n-1.

Checked

Both distances identical to python-igraph 1.0 on 260 pairs of partitions.

C name

og_split_join_distance

In notebooks

Og.SplitJoinDistance

igraph 1.0

igraph_split_join_distance

See also

compare_communities

Cuts the leading eigenvector dendrogram, whose leaves are communities rather than vertices.

og_error_t og_le_community_to_membership(
    const og_matrix_int_t *merges,
    og_int_t steps,
    og_vector_int_t *membership,
    og_vector_int_t *csize
);

On input membership holds a community id per vertex, 0..k-1 with k the largest id + 1, usually the membership of community_leading_eigenvector; merges is a dendrogram over these k communities with at most k - 1 rows, usually that function's merges. The first steps rows are applied and membership is rewritten with the resulting cluster ids, numbered as community_to_membership numbers them; csize gets the k - steps cluster sizes.

Parameters

• merges Dendrogram over the starting communities, two columns.
• steps Number of rows to apply, 0..rows.
• membership Input: starting community of each vertex. Output: cluster after the cut.
• csize Output: size of each cluster. May be NULL.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL steps is negative, or larger than the number of rows.
• OG_EINVAL membership holds a negative id.
• OG_EINVAL merges has more rows than k - 1, or a row names a missing, not yet created or already merged node.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| + k).

Checked

python-igraph 1.0 has no wrapper. Checked on hand-computed dendrograms and on every cut of the Zachary leading eigenvector dendrogram.

C name

og_le_community_to_membership

In notebooks

Og.LeCommunityToMembership

igraph 1.0

igraph_le_community_to_membership

See also

community_leading_eigenvector, community_to_membership

Louvain method: raises modularity by local vertex moves, then collapses communities and repeats.

og_error_t og_community_multilevel(
    const og_t *graph,
    const og_vector_t *weights,
    const og_real_t resolution,
    og_vector_int_t *membership,
    og_matrix_int_t *memberships,
    og_vector_t *modularity
);

Blondel, Guillaume, Lambiotte and Lefebvre (2008). At each level the vertices are visited in random order; a vertex moves to the neighbouring community with the largest modularity gain (resolution gamma) when that gain is above 0, ties going to the smallest community label. Sweeps repeat while they raise modularity. Each community then becomes one node of a smaller weighted graph and the next level starts. The run ends when a level no longer raises modularity (or would not stay above -1, which only a resolution above 1 can cause).

Every level is reported: row l of memberships is the partition after level l, modularity[l] its modularity, and membership is the level with the highest modularity. Ids are numbered by first appearance in every level. When no level forms (no edges, total weight 0, one vertex) every vertex stays alone, memberships has no rows and modularity holds one value, the singletons' modularity (NaN without edges). Multi-edges add up; self-loops are kept.

Random: draws from the default generator (rng_default). The order of draws, the tie rules and the stopping rule follow igraph 1.0's observed behaviour, so the same seed gives python-igraph 1.0's levels exactly.

Parameters

• graph An undirected graph.
• weights Edge weights (length |E|), non-negative, no NaN; NULL means every edge weighs 1.
• resolution The resolution gamma, at least 0; 1 is ordinary modularity.
• membership Output: the level with the highest modularity. May be NULL.
• memberships Output: one row per level, |V| columns. May be NULL.
• modularity Output: the modularity of each level. May be NULL.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_UNIMPLEMENTED The graph is directed.
• OG_EINVAL weights does not have |E| entries, or holds a negative value or NaN.
• OG_EINVAL resolution is negative.
• OG_ENOMEM Not enough memory.

Complexity

About O(|E|) per sweep; in practice close to linear in |E|, with a few levels of a few sweeps each.

Checked

With the same seed, python-igraph 1.0's levels and random draws exactly (600 of 600 random graphs, 299 of 299 at resolutions 0.5-10); 0.11-0.24x python-igraph's time on 50,000-edge graphs.

C name

og_community_multilevel

In notebooks

Og.CommunityMultilevel

igraph 1.0

igraph_community_multilevel

See also

community_leiden, modularity, community_fastgreedy

og_t g;
og_vector_int_t membership;
og_vector_t q;
og_famous(&g, "Zachary");
og_vector_int_init(&membership, 0);
og_vector_init(&q, 0);
og_rng_seed(og_rng_default(), 42);
og_community_multilevel(&g, NULL, 1.0, &membership, NULL, &q);
/* OG_VECTOR(q)[og_vector_size(&q) - 1]: modularity of the last level */
og_vector_destroy(&q);
og_vector_int_destroy(&membership);
og_destroy(&g);

Leiden algorithm: optimises a modularity-type quality with explicit vertex weights and guarantees well-connected communities.

og_error_t og_community_leiden(
    const og_t *graph,
    const og_vector_t *edge_weights,
    const og_vector_t *vertex_out_weights,
    const og_vector_t *vertex_in_weights,
    og_real_t resolution,
    og_real_t beta,
    og_bool_t start,
    og_int_t n_iterations,
    og_vector_int_t *membership,
    og_int_t *nb_clusters,
    og_real_t *quality
);

Traag, Waltman and van Eck (2019). Each iteration runs fast local moving (a queue of vertices to revisit), a randomised refinement that splits every community into well-connected parts, and aggregation on the refined partition, level after level. The quality maximised is sum over pairs in the same community of (A_ij - gamma n_i n_j), with n_i the vertex weights. The value reported is (2 W_in - gamma sum_c Nout_c Nin_c) / 2W for an undirected graph and (W_in - gamma sum_c Nout_c Nin_c) / W for a directed one, W being the total edge weight, W_in the weight inside communities and Nout_c, Nin_c the summed out- and in-weights of community c.

With unit vertex weights (vertex_out_weights NULL) this is the constant Potts model (CPM), gamma acting as a density threshold; with the strengths as vertex weights and gamma = resolution / 2W it is modularity. community_leiden_simple sets these up. In-weights are for directed graphs only; NULL in-weights mean the out-weights. Only the lengths of the weight vectors are checked.

beta sets the randomness of the refinement: a vertex joins a part with probability proportional to e^(gain / beta). n_iterations > 0 runs that many iterations; a negative value iterates until an iteration moves no vertex (at most 1000); 0 runs nothing and returns the starting partition as it is, with quality 0. With start true, membership holds the starting partition (renumbered by first appearance when an iteration runs); otherwise every vertex starts alone. Result ids are numbered by first appearance. Random: draws from the default generator as igraph 1.0 does, so the same seed gives python-igraph 1.0's result.

Parameters

• graph The graph, directed or undirected.
• edge_weights Edge weights (length |E|); NULL means every edge weighs 1.
• vertex_out_weights Vertex (out-)weights n_i (length |V|); NULL means 1 for every vertex.
• vertex_in_weights Vertex in-weights for directed graphs (length |V|); NULL means the out-weights.
• resolution The resolution gamma.
• beta Randomness of the refinement; small values (0.01) make it nearly greedy.
• start true: start from the partition in membership; false: from singletons.
• n_iterations Number of iterations; negative: until an iteration moves nothing.
• membership Input (when start is true) and output: the partition. Must not be NULL.
• nb_clusters Output: the number of communities. May be NULL.
• quality Output: the quality defined above (0 when no iteration ran). May be NULL.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL membership is NULL, or start is true and membership does not have |V| entries.
• OG_EINVAL edge_weights does not have |E| entries, or a vertex weight vector does not have |V| entries.
• OG_EINVAL vertex_in_weights is given for an undirected graph.
• OG_ENOMEM Not enough memory.

Complexity

Roughly O(|E|) per iteration: local moving, refinement and aggregation each pass over the edges a few times per level.

Checked

With the same seed, python-igraph 1.0's partition, quality and random draws exactly (200 of 200 fixture graphs); 0.46-0.60x python-igraph's time on repeated runs.

C name

og_community_leiden

In notebooks

Og.CommunityLeiden

igraph 1.0

igraph_community_leiden

See also

community_leiden_simple, community_multilevel, modularity

og_vector_int_t membership;
og_int_t k;
og_real_t quality;
og_vector_int_init(&membership, 0);
og_rng_seed(og_rng_default(), 42);
/* CPM, unit vertex weights: communities denser than 0.05 */
og_community_leiden(&g, NULL, NULL, NULL, 0.05, 0.01, false, -1,
                    &membership, &k, &quality);
og_vector_int_destroy(&membership);

Leiden algorithm with a named objective (modularity, CPM or Erdos-Renyi) instead of explicit vertex weights.

og_error_t og_community_leiden_simple(
    const og_t *graph,
    const og_vector_t *weights,
    og_leiden_objective_t objective,
    og_real_t resolution,
    og_real_t beta,
    og_bool_t start,
    og_int_t n_iterations,
    og_vector_int_t *membership,
    og_int_t *nb_clusters,
    og_real_t *quality
);

A wrapper over community_leiden. OG_LEIDEN_OBJECTIVE_MODULARITY takes the strengths as vertex weights (out- and in-strengths for a directed graph) and divides the resolution by 2W (W for a directed graph), so the quality is modularity with that resolution. OG_LEIDEN_OBJECTIVE_CPM uses unit vertex weights and the resolution as given. OG_LEIDEN_OBJECTIVE_ER uses unit vertex weights and multiplies the resolution by the weighted density p = 2W / (n(n-1)) (W / (n(n-1)) directed; 0 below two vertices), the Erdos-Renyi null model.

Weights must be non-negative for the modularity and ER objectives. The other arguments and the outputs are those of community_leiden.

Parameters

• graph The graph, directed or undirected.
• weights Edge weights (length |E|); NULL means every edge weighs 1.
• objective OG_LEIDEN_OBJECTIVE_MODULARITY, OG_LEIDEN_OBJECTIVE_CPM or OG_LEIDEN_OBJECTIVE_ER.
• resolution The resolution; 1 is ordinary modularity.
• beta Randomness of the refinement (as in community_leiden).
• start true: start from the partition in membership.
• n_iterations Number of iterations; negative: until an iteration moves nothing.
• membership Input (when start is true) and output: the partition.
• nb_clusters Output: the number of communities. May be NULL.
• quality Output: the quality of the result. May be NULL.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL Unknown objective.
• OG_EINVAL weights does not have |E| entries, or holds a negative value (modularity and ER objectives).
• OG_EINVAL start is true and membership does not have |V| entries.
• OG_EINVAL Any error of community_leiden (membership NULL).
• OG_ENOMEM Not enough memory.

Complexity

As community_leiden, plus O(|V| + |E|) to set up the vertex weights.

Checked

Checked to give exactly what community_leiden gives (same seed) with the equivalent vertex weights and resolution; community_leiden itself matches python-igraph 1.0 exactly.

C name

og_community_leiden_simple

In notebooks

Og.CommunityLeidenSimple

igraph 1.0

igraph_community_leiden_simple

See also

community_leiden, community_multilevel

og_vector_int_t membership;
og_int_t k;
og_real_t q;
og_vector_int_init(&membership, 0);
og_rng_seed(og_rng_default(), 42);
og_community_leiden_simple(&g, NULL, OG_LEIDEN_OBJECTIVE_MODULARITY, 1.0, 0.01,
                           false, -1, &membership, &k, &q);

Fluid communities: k communities spread over the graph like competing fluids until they settle.

og_error_t og_community_fluid_communities(
    const og_t *graph,
    og_int_t no_of_communities,
    og_vector_int_t *membership
);

Pares et al. (2017). k distinct random vertices seed the k communities, and each community has density 1/size. In every sweep the vertices are visited in random order; a vertex adds up, per community, the densities of itself and of its neighbours in that community, and joins the community with the largest sum. It stays when its own community is among the largest; other ties are broken at random. Sweeps repeat until one changes nothing. The sums are compared exactly, as integer fractions.

The graph must be simple and connected, and edge directions are ignored (with a warning; a mutual pair then counts as a multi-edge). There are no weights. The result uses ids 0..k-1. With fewer than two vertices every vertex is in community 0 and k is not checked. Random: draws from the default generator.

Parameters

• graph A simple, connected graph.
• no_of_communities k, the number of communities: 1..|V|.
• membership Output: the community of each vertex. May be NULL.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL The graph has self-loops or multi-edges (directions ignored).
• OG_EINVAL no_of_communities is below 1 or above |V| (graphs of two or more vertices).
• OG_EINVAL The graph is not connected.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|) per sweep; the number of sweeps is usually small.

Checked

Randomised: the same partition as python-igraph 1.0 on 18 graphs where its answer does not depend on the seed; modularity mean and spread over 60 seeds on 25 graphs.

C name

og_community_fluid_communities

In notebooks

Og.CommunityFluidCommunities

igraph 1.0

igraph_community_fluid_communities

See also

community_label_propagation, community_multilevel

Label propagation: each vertex repeatedly takes the label that dominates among its neighbours.

og_error_t og_community_label_propagation(
    const og_t *graph,
    og_vector_int_t *membership,
    og_neimode_t mode,
    const og_vector_t *weights,
    const og_vector_int_t *initial,
    const og_vector_bool_t *fixed,
    og_lpa_variant_t lpa_variant
);

Raghavan, Albert and Kumara (2007). Every vertex starts with its own label, or the one given in initial. A vertex's dominant labels are those carried by the largest total edge weight among its neighbours; it takes one of them, at random when several tie. Variants: OG_LPA_DOMINANCE sweeps in random order until every vertex holds a dominant label (tested before the first sweep too, so a labelling that is already stable comes back unchanged); OG_LPA_RETENTION keeps a vertex's label whenever it is among the dominant ones and stops after a sweep without change; OG_LPA_FAST (Traag and Subelj 2023) keeps a queue, starting with every free vertex in id order, and queues again the neighbours of a vertex whose label changed.

In a directed graph mode decides which edges carry labels: OG_OUT along the edge direction (a vertex reads its in-neighbours), OG_IN against it, OG_ALL both ways; undirected graphs always use every edge. In initial a negative value, or the value |V|, means no label; fixed (used only with initial) marks vertices that keep their label. Vertices no label reaches get one new label per connected group of them. Labels are renumbered 0..k-1 by first appearance. An undirected self-loop adds its weight once to its vertex's own label; zero-weight edges still carry labels.

Random: draws from the default generator. The dominance variant draws as igraph 1.0 does, so the same seed gives python-igraph 1.0's labels.

Parameters

• graph The graph.
• membership Output: the label of each vertex, 0..k-1. May be NULL.
• mode OG_OUT, OG_IN or OG_ALL; which edge directions carry labels in a directed graph.
• weights Edge weights (length |E|), non-negative, no NaN; NULL means every edge weighs 1.
• initial Starting labels (length |V|); negative or |V| means unlabelled. NULL: every vertex its own label.
• fixed Vertices whose initial label never changes (length |V|). Ignored without initial. May be NULL.
• lpa_variant OG_LPA_DOMINANCE, OG_LPA_RETENTION or OG_LPA_FAST.

Returns

OG_SUCCESS, or an error code. Warnings when fixed is given without initial, or marks unlabelled vertices (those flags are ignored).

Errors

• OG_EINVAL Unknown variant.
• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL weights does not have |E| entries, or holds a negative value or NaN.
• OG_EINVAL initial or fixed does not have |V| entries, or an initial label is above |V|.
• OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|) per sweep (per pass over the queue for the fast variant); usually a few sweeps.

Checked

Dominance variant: with the same seed, python-igraph 1.0's labels (600 of 600 random graphs). Retention and fast variants: checked on seed-independent cases and by modularity and cluster-count distributions over 40 seeds. 0.46-0.61x python-igraph's time.

C name

og_community_label_propagation

In notebooks

Og.CommunityLabelPropagation

igraph 1.0

igraph_community_label_propagation

See also

community_fluid_communities, community_leiden, community_multilevel

og_vector_int_t labels;
og_vector_int_init(&labels, 0);
og_rng_seed(og_rng_default(), 1);
og_community_label_propagation(&g, &labels, OG_ALL, NULL, NULL, NULL,
                               OG_LPA_DOMINANCE);
og_vector_int_destroy(&labels);

Voronoi communities: picks dense generator vertices and assigns every vertex to its nearest generator.

og_error_t og_community_voronoi(
    const og_t *graph,
    og_vector_int_t *membership,
    og_vector_int_t *generators,
    og_real_t *modularity,
    const og_vector_t *lengths,
    const og_vector_t *weights,
    og_neimode_t mode,
    og_real_t r
);

Deritei et al. (2014); Molnar et al. (2024). Each edge's length is divided by its edge clustering coefficient (z + 1) / (min(d_a, d_b) - 1), z being the number of common neighbours of its endpoints, so edges in dense regions become short; an edge with an endpoint of degree 1 gets length 0. Each vertex gets a local density s * m / (m + k): s its strength, m the edges inside its closed neighbourhood, k the edges leaving it. Vertices are taken by decreasing density, and one that is not within distance r of an earlier generator becomes a generator. Every vertex then joins its nearest generator; distances within 1e-10 relative count as equal and such ties are broken at random.

A negative r asks for the radius with the best modularity: 17 radii evenly spaced between the shortest edge and the radius beyond which the partition no longer changes, then Brent's method around the best of them; the best partition seen is returned. An infinite or NaN r lets each generator claim everything it reaches. generators come in order of decreasing density and membership[v] is the position of v's generator in it. The modularity uses weights with resolution 1.

In a directed graph mode sets the direction of distances from a generator (OG_OUT: generator to vertex), and directed modularity is used unless mode is OG_ALL; undirected graphs ignore mode. The graph must be simple; with directions ignored (undirected, or OG_ALL) two opposite edges count as a multi-edge. Without edges every vertex is its own generator and modularity is NaN.

Parameters

• graph A simple graph.
• membership Output: for each vertex, the index of its generator in generators. May be NULL.
• generators Output: the generator vertices, by decreasing density. May be NULL.
• modularity Output: the modularity of the result. May be NULL.
• lengths Edge lengths (length |E|), non-negative; NULL means 1.
• weights Edge weights (length |E|), positive; NULL means 1. Used for densities and modularity.
• mode OG_OUT, OG_IN or OG_ALL for directed graphs.
• r The radius; negative chooses it automatically.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL lengths or weights does not have |E| entries.
• OG_EINVAL The graph has self-loops or multi-edges (with directions ignored unless mode is OG_OUT or OG_IN).
• OG_EINVAL A length is NaN or negative; a weight is NaN, 0 or negative.
• OG_EINVAL An edge with an endpoint of degree 1 has an infinite length (its scaled length is undefined).
• OG_EINVMODE Invalid mode on a directed graph.
• OG_ENOMEM Not enough memory.

Complexity

O(sum of squared degrees) for the clustering coefficients; per radius one Dijkstra search per generator, pruned by r and by the best distances found, O(g (|V| + |E|) log |V|) at worst for g generators. The automatic radius evaluates 17 radii plus a Brent search.

Checked

Fixed radius: generators, membership and modularity identical to python-igraph 1.0 on 433 cases, with its random tie rule pinned to either end. Automatic radius: quality only, python-igraph's search could not be reproduced; mean modularity 0.401 against its 0.375 on 40 graphs.

C name

og_community_voronoi

In notebooks

Og.CommunityVoronoi

igraph 1.0

igraph_community_voronoi

See also

modularity, community_label_propagation

Walktrap: agglomerative clustering by distances between short random walks.

og_error_t og_community_walktrap(
    const og_t *graph,
    const og_vector_t *weights,
    og_int_t steps,
    og_matrix_int_t *merges,
    og_vector_t *modularity,
    og_vector_int_t *membership
);

Pons and Latapy (2006). Two vertices are close when random walks of steps steps from them reach the graph with similar probabilities. Every vertex gets an extra self-loop (weight: its strength over its number of edge ends; 1 for an isolated vertex). Starting from singletons, the two adjacent communities whose merge least increases the mean squared distance (Ward's criterion) are merged, and the distances to the new community are updated with the Lance-Williams-Jambu formula, until no adjacent pair is left.

Edge directions are ignored and multi-edges add up. Weights may be 0 or infinite, but not negative or NaN, and a vertex whose edges all weigh 0 is refused. merges has one row per merge (|V| minus the number of components), row k joining two communities into community |V| + k. modularity has one entry more than merges has rows: before any merge, then after each one (input self-loops count in the total weight only). membership is the cut with the largest modularity, the first one on ties.

Walk vectors are cached under a 4 GiB budget and recomputed when dropped. The arithmetic and the order among equal distances follow python-igraph 1.0, so results agree exactly when no two candidate distances tie, on Windows and macOS alike.

Parameters

• graph The graph; directions are ignored.
• weights Edge weights (length |E|), non-negative (0 and infinity allowed); NULL means 1.
• steps Length of the random walks, at least 1; 4 or 5 are usual.
• merges Output: the dendrogram, two columns. May be NULL.
• modularity Output: modularity before any merge and after each one. May be NULL.
• membership Output: the cut with the largest modularity. May be NULL.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL steps is 0 or negative.
• OG_EINVAL weights does not have |E| entries, or holds a negative value or NaN.
• OG_EINVAL A vertex has edges whose weights add up to 0.
• OG_EOVERFLOW More than 2^32 - 1 vertices.
• OG_ENOMEM Not enough memory.

Complexity

O(|E| |V|^2) at worst; about O(|V|^2 log |V|) on sparse graphs (Pons and Latapy). Memory up to the 4 GiB vector cache.

Checked

Merges, modularity and membership identical to python-igraph 1.0 whenever no two candidate distances tie (every tie-free fixture and verifier case); with exact ties the merge order can differ, the best modularity is reached in nearly all cases. 0.88x python-igraph's time on 20k vertices / 100k edges.

C name

og_community_walktrap

In notebooks

Og.CommunityWalktrap

igraph 1.0

igraph_community_walktrap

See also

community_to_membership, community_fastgreedy, community_edge_betweenness

og_t g;
og_matrix_int_t merges;
og_vector_t q;
og_vector_int_t membership;
og_famous(&g, "Zachary");
og_matrix_int_init(&merges, 0, 0);
og_vector_init(&q, 0);
og_vector_int_init(&membership, 0);
og_community_walktrap(&g, NULL, 4, &merges, &q, &membership);
/* another cut: og_community_to_membership(&merges, og_vcount(&g), steps, ...) */
og_vector_int_destroy(&membership);
og_vector_destroy(&q);
og_matrix_int_destroy(&merges);
og_destroy(&g);

Girvan-Newman method: removes the edge of highest betweenness again and again and records the dendrogram.

og_error_t og_community_edge_betweenness(
    const og_t *graph,
    og_vector_int_t *removed_edges,
    og_vector_t *edge_betweenness,
    og_matrix_int_t *merges,
    og_vector_int_t *bridges,
    og_vector_t *modularity,
    og_vector_int_t *membership,
    og_bool_t directed,
    const og_vector_t *weights,
    const og_vector_t *lengths
);

Girvan and Newman (2002). The edge with the highest betweenness (the shortest paths through it, Brandes 2001) is removed, the betweenness of the edges in the component it belonged to is recomputed, and this repeats until no edge is left. Ties go to the edge with the lowest id. With weights the score is betweenness divided by weight (Newman 2004), so heavy edges stay longer. lengths, if given, make shortest paths weighted (Dijkstra); path lengths within 1e-10 relative count as equal. directed true follows edge directions in a directed graph; otherwise directions are ignored and betweenness counts each pair once.

removed_edges lists all |E| edges in removal order, and edge_betweenness the betweenness of each at the moment it was removed (not divided by its weight). merges, bridges, modularity and membership come from replaying that order backwards, exactly as community_eb_get_merges does: the dendrogram, the positions in the removal order of the edges whose removal split a component, the modularity of every level (weighted; directed form when directed is set), and the level with the largest modularity. Every output may be NULL.

Parameters

• graph The graph.
• removed_edges Output: edge ids in removal order. May be NULL.
• edge_betweenness Output: betweenness of each removed edge when it was removed. May be NULL.
• merges Output: the dendrogram. May be NULL.
• bridges Output: positions in the removal order of the edges that split a component. May be NULL.
• modularity Output: modularity before any merge and after each one. May be NULL.
• membership Output: the level with the largest modularity. May be NULL.
• directed Follow edge directions in a directed graph.
• weights Edge weights (length |E|), positive (infinity allowed): betweenness is divided by them and modularity uses them. NULL means 1.
• lengths Edge lengths (length |E|), positive (infinity allowed), for the shortest paths. NULL means 1.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL weights or lengths does not have |E| entries, or holds 0, a negative value or NaN.
• OG_ENOMEM Not enough memory.

Complexity

O(|E|^2 |V|) without lengths; with lengths each recomputation is a Dijkstra-based pass, O(|E| (|V| |E| + |V|^2 log |V|)) in all. Practical up to a few thousand edges.

Checked

Removal order, betweenness, merges, bridges, modularity and membership identical to python-igraph 1.0 on 329 fixture and 991 verifier cases. Known differences: extreme or infinite lengths, where the two libraries' weighted betweenness values differ, and 8 of 991 cases where an equally scored cut is chosen.

C name

og_community_edge_betweenness

In notebooks

Og.CommunityEdgeBetweenness

igraph 1.0

igraph_community_edge_betweenness

See also

community_eb_get_merges, community_to_membership

og_vector_int_t removed, membership;
og_vector_t q;
og_matrix_int_t merges;
og_vector_int_init(&removed, 0);
og_vector_int_init(&membership, 0);
og_vector_init(&q, 0);
og_matrix_int_init(&merges, 0, 0);
og_community_edge_betweenness(&g, &removed, NULL, &merges, NULL, &q,
                              &membership, false, NULL, NULL);

Builds the dendrogram, bridges, modularity values and best membership from an edge removal order.

og_error_t og_community_eb_get_merges(
    const og_t *graph,
    const og_bool_t directed,
    const og_vector_int_t *edges,
    const og_vector_t *weights,
    og_matrix_int_t *res,
    og_vector_int_t *bridges,
    og_vector_t *modularity,
    og_vector_int_t *membership
);

Replays a removal order backwards: putting the edges back from the last removed to the first, each edge that joins two different clusters becomes a merge. Row k joins those clusters into cluster |V| + k; its first column holds the cluster of the edge's tail in a directed graph and of its larger endpoint in an undirected one. The order may be partial or repeat edges; at most |V| - 1 merges are made. bridges[k] is the position in edges of the edge behind row k.

modularity has one entry per level, before any merge and after each one, using weights, in the directed form when directed is set and the graph is directed. membership is the level with the largest modularity, the first one on ties. Every output may be NULL.

Parameters

• graph The graph.
• directed Use directed modularity for a directed graph.
• edges Edge ids in removal order (as from community_edge_betweenness).
• weights Edge weights for the modularity (length |E|), non-negative (0 and infinity allowed); NULL means 1.
• res Output: the dendrogram. May be NULL.
• bridges Output: for each merge row, the position in edges of its edge. May be NULL.
• modularity Output: modularity of every level. May be NULL.
• membership Output: the level with the largest modularity. May be NULL.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVEID edges holds an id outside 0..|E|-1.
• OG_EINVAL weights does not have |E| entries, or holds a negative value or NaN (checked only when modularity or membership is asked for).
• OG_ENOMEM Not enough memory.

Complexity

O(L alpha(|V|)) for the merges, L the length of edges, plus O((|V| + |E|) log |V|) for the modularity values.

Checked

Identical to python-igraph 1.0 on the 329 edge betweenness cases; partial and invalid orders checked for their error codes.

C name

og_community_eb_get_merges

In notebooks

Og.CommunityEbGetMerges

igraph 1.0

igraph_community_eb_get_merges

See also

community_edge_betweenness, community_to_membership

Clauset-Newman-Moore greedy modularity optimisation: merges the adjacent pair of communities that raises modularity most, step by step.

og_error_t og_community_fastgreedy(
    const og_t *graph,
    const og_vector_t *weights,
    og_matrix_int_t *merges,
    og_vector_t *modularity,
    og_vector_int_t *membership
);

Clauset, Newman and Moore (2004), with each community's row of modularity gains kept as a sorted list with a link to its largest entry (Wakita and Tsurumi 2007). Starting from singletons, the pair at the top of a heap of rows is merged and the gains of the merged community's neighbours are updated. Merging goes on until no adjacent pair remains, so the dendrogram also holds merges that lower modularity.

The graph must be undirected and free of multi-edges; self-loops are allowed. Weights may be 0 or infinite but not negative or NaN (with a total weight of 0 every gain is NaN). merges has one row per merge, row k creating community |V| + k. modularity has one entry more, starting with the singletons. membership is the cut with the largest modularity: the last one on ties, never the final single community of a connected graph. Without edges modularity is [NaN] and every vertex stays alone.

The modularity arithmetic and the heap's update rules follow python-igraph 1.0's observed behaviour; merges agree on most small graphs, but on large graphs and with many tied gains the order can differ (see parity).

Parameters

• graph An undirected graph without multi-edges.
• weights Edge weights (length |E|), non-negative (0 and infinity allowed); NULL means 1.
• merges Output: the dendrogram. May be NULL.
• modularity Output: modularity before any merge and after each one. May be NULL.
• membership Output: the cut with the largest modularity. May be NULL.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_UNIMPLEMENTED The graph is directed.
• OG_EINVAL The graph has multi-edges.
• OG_EINVAL weights does not have |E| entries, or holds a negative value or NaN.
• OG_ENOMEM Not enough memory.

Complexity

O(|E| d log |V|), d the depth of the dendrogram; about O(|V| log^2 |V|) on sparse graphs with a balanced hierarchy (Clauset, Newman and Moore).

Checked

Coverage status partial. Modularity values bit for bit where the same pairs merge; merges identical to python-igraph 1.0 on most small graphs (3,880 of 4,000 random graphs of 4-12 vertices) but diverging on large ones (planted 20k vertices: best Q 0.522 against 0.560 unweighted) and on some ties. 0.63-1.04x python-igraph's time.

C name

og_community_fastgreedy

In notebooks

Og.CommunityFastgreedy

igraph 1.0

igraph_community_fastgreedy

See also

community_walktrap, community_multilevel, community_to_membership

og_matrix_int_t merges;
og_vector_t q;
og_vector_int_t membership;
og_matrix_int_init(&merges, 0, 0);
og_vector_init(&q, 0);
og_vector_int_init(&membership, 0);
og_community_fastgreedy(&g, NULL, &merges, &q, &membership);

Spin-glass community detection: simulated annealing of a Potts model whose lowest energy is a generalised modularity optimum.

og_error_t og_community_spinglass(
    const og_t *graph,
    const og_vector_t *weights,
    og_real_t *modularity,
    og_real_t *temperature,
    og_vector_int_t *membership,
    og_vector_int_t *csize,
    og_int_t spins,
    og_bool_t parupdate,
    og_real_t starttemp,
    og_real_t stoptemp,
    og_real_t coolfact,
    og_spincomm_update_t update_rule,
    og_real_t gamma,
    og_spinglass_implementation_t implementation,
    og_real_t gamma_minus
);

Reichardt and Bornholdt (2006). Each vertex holds one of spins states; the energy H = -sum_{i<j} (A_ij - gamma p_ij) delta(s_i, s_j) is lowered by simulated annealing with heat-bath single-spin updates: 30 sweeps per temperature, starting at starttemp and multiplying by coolfact until the next temperature would fall below stoptemp or a temperature changes nothing, then zero-temperature sweeps until no spin moves. The null model is OG_SPINCOMM_UPDATE_SIMPLE (p_ij = p, the graph's density) or OG_SPINCOMM_UPDATE_CONFIG (p_ij = k_i k_j / 2W). spins is an upper bound on the number of communities. starttemp = stoptemp = 0 gives a greedy zero-temperature run.

OG_SPINCOMM_IMP_NEG is Traag and Bruggeman's (2009) variant for weights of either sign: positive and negative links each get their own null model, with resolutions gamma and gamma_minus. The original implementation needs non-negative weights. parupdate updates all spins together in each sweep (original implementation only); otherwise a sweep makes |V| updates of randomly chosen vertices.

The graph must be connected; edge directions are ignored and multi-edges add up. membership is numbered by first appearance, csize gives the community sizes, modularity is the generalised modularity of the result under the chosen null model(s) and resolutions (ordinary modularity for the configuration model with gamma 1), and temperature the last temperature reached. A graph without any weight to arrange gives one community. Random: draws from the default generator; a seed reproduces Open Graph's result, not python-igraph's.

Parameters

• graph A connected graph.
• weights Edge weights (length |E|), finite; non-negative for the original implementation. NULL means 1.
• modularity Output: generalised modularity of the result. May be NULL.
• temperature Output: the final temperature. May be NULL.
• membership Output: community of each vertex. May be NULL.
• csize Output: size of each community. May be NULL.
• spins Number of spin states, at least 2 (capped at |V|).
• parupdate Update all spins at once per sweep (original implementation only).
• starttemp Start temperature, positive; 0 together with stoptemp 0 for a greedy run.
• stoptemp Stop temperature, positive and below starttemp; or 0.
• coolfact Cooling factor in [0, 1).
• update_rule OG_SPINCOMM_UPDATE_SIMPLE or OG_SPINCOMM_UPDATE_CONFIG.
• gamma Resolution of the (positive) links, at least 0.
• implementation OG_SPINCOMM_IMP_ORIG or OG_SPINCOMM_IMP_NEG.
• gamma_minus Resolution of the negative links (OG_SPINCOMM_IMP_NEG only).

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL Unknown implementation or update rule; spins below 2; gamma negative or NaN; gamma_minus NaN (signed variant).
• OG_EINVAL weights does not have |E| entries, or holds NaN, an infinite value, or a negative value (original implementation).
• OG_EINVAL coolfact outside [0, 1); a temperature negative or NaN; only one of the two temperatures 0; starttemp not above stoptemp.
• OG_EINVAL The graph is not connected.
• OG_UNIMPLEMENTED parupdate with OG_SPINCOMM_IMP_NEG.
• OG_ENOMEM Not enough memory.

Complexity

Per temperature, 30 sweeps of |V| updates, each O(degree + spins); about log(stoptemp / starttemp) / log(coolfact) temperatures.

Checked

Randomised: mean and best generalised modularity at least python-igraph 1.0's on 14 settings over several seeds (both implementations, both null models, parallel update); python-igraph's partition on 6 deterministic cases; its error codes.

C name

og_community_spinglass

In notebooks

Og.CommunitySpinglass

igraph 1.0

igraph_community_spinglass

See also

community_spinglass_single, modularity

Finds the community of one vertex by greedy growth under the spin-glass model and reports its cohesion and adhesion.

og_error_t og_community_spinglass_single(
    const og_t *graph,
    const og_vector_t *weights,
    og_int_t vertex,
    og_vector_int_t *community,
    og_real_t *cohesion,
    og_real_t *adhesion,
    og_real_t *inner_links,
    og_real_t *outer_links,
    og_int_t spins,
    og_spincomm_update_t update_rule,
    og_real_t gamma
);

Reichardt and Bornholdt (2006), the community around a single node. Starting with the vertex alone, the community repeatedly adds the outside vertex that lowers its adhesion to the rest of the graph the most, among the vertices with positive adhesion to the community (ties to the smaller id), and stops when no addition lowers it.

inner_links is the total weight of edges inside the community and outer_links that of edges between it and the rest. cohesion = inner_links - gamma * (expected inner weight) and adhesion = outer_links - gamma * (expected weight to the rest), the expectations taken under the null model: p n_s (n_s - 1) / 2 and p n_s n_r for OG_SPINCOMM_UPDATE_SIMPLE (p the density, n_s and n_r the vertex counts inside and outside), K_s^2 / 4W and K_s K_r / 2W for OG_SPINCOMM_UPDATE_CONFIG (K the summed strengths). The graph must be connected; directions are ignored. spins is checked (at least 2) but the search does not use it. community lists the vertices in increasing order.

Parameters

• graph A connected graph.
• weights Edge weights (length |E|), non-negative and finite; NULL means 1.
• vertex The vertex whose community is wanted.
• community Output: the vertices of the community, ascending. May be NULL.
• cohesion Output. May be NULL.
• adhesion Output. May be NULL.
• inner_links Output: weight of edges inside the community. May be NULL.
• outer_links Output: weight of edges leaving the community. May be NULL.
• spins At least 2; kept for compatibility, not used by the search.
• update_rule OG_SPINCOMM_UPDATE_SIMPLE or OG_SPINCOMM_UPDATE_CONFIG.
• gamma Resolution, at least 0.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVVID vertex is not a vertex of the graph.
• OG_EINVAL spins below 2, unknown update rule, gamma negative or NaN.
• OG_EINVAL weights does not have |E| entries, or holds NaN, an infinite or a negative value.
• OG_EINVAL The graph is not connected.
• OG_ENOMEM Not enough memory.

Complexity

O(|E|) to build the graph, plus one scan of the community's frontier per added vertex: O(|V|^2 + |E|) at worst.

Checked

python-igraph 1.0 has no wrapper. Checked on hand-computed answers (two joined K4s, every vertex) and on 151 random graphs where the reported link weights are recomputed from the returned community.

C name

og_community_spinglass_single

In notebooks

Og.CommunitySpinglassSingle

igraph 1.0

igraph_community_spinglass_single

See also

community_spinglass

Newman's leading eigenvector method: splits communities in two by the signs of the leading eigenvector of their modularity matrix.

og_error_t og_community_leading_eigenvector(
    const og_t *graph,
    const og_vector_t *weights,
    og_matrix_int_t *merges,
    og_vector_int_t *membership,
    og_int_t steps,
    og_arpack_options_t *options,
    og_real_t *modularity,
    og_bool_t start,
    og_vector_t *eigenvalues,
    og_vector_list_t *eigenvectors,
    og_vector_int_t *history,
    og_community_leading_eigenvector_callback_t *callback,
    void *callback_extra
);

Newman (2006). Starting from the connected components (or a given membership), it takes a community, computes the leading eigenvector of its generalised modularity matrix B(g)_ij = B_ij - delta_ij sum_{k in g} B_ik, and splits the community by the signs of the entries when the eigenvalue is positive and the split raises modularity; otherwise the community stays whole. Communities are taken from a stack, the halves of a split first. In a split the side holding the community's first vertex keeps its id and the other side gets the next free id. Edge directions are ignored (with a warning).

steps limits the split attempts, failed ones included; the count starts at k - 1 for k starting communities, so steps = |V| splits as far as possible. Single vertices are skipped and two-vertex communities are never split. membership receives the final communities and modularity their modularity. merges is a dendrogram whose leaves are those communities, not vertices: the splits undone from the last one, then the starting communities joined; cut it with le_community_to_membership.

eigenvalues and eigenvectors get one entry per attempt, each eigenvector over the community's vertices in increasing id order with its first clearly non-zero entry positive. history records the run as og_levc_history_t codes: OG_LEVC_HIST_START_FULL, or OG_LEVC_HIST_START_GIVEN followed by the number of given communities; then OG_LEVC_HIST_SPLIT or OG_LEVC_HIST_FAILED, each followed by the community id. callback is called after each eigenvector. The eigenproblems are solved by arpack_rssolve (thick-restart Lanczos) from a fixed start vector, so no random numbers are used; options is accepted for compatibility and ignored.

Parameters

• graph The graph; directions are ignored.
• weights Edge weights (length |E|), non-negative and finite; NULL means 1.
• merges Output: dendrogram over the final communities (communities - 1 rows). May be NULL.
• membership Output, and input when start is true: community of each vertex. May be NULL unless start is true.
• steps Maximum number of split attempts, at least 0.
• options Eigensolver options; ignored. May be NULL.
• modularity Output: modularity of the final partition. May be NULL.
• start true: start from the communities in membership (ids 0..|V|-1); false: from the connected components.
• eigenvalues Output: the eigenvalue of each attempt. May be NULL.
• eigenvectors Output: the eigenvector of each attempt. May be NULL.
• history Output: the run as og_levc_history_t codes. May be NULL.
• callback Called after each eigenvector computation. May be NULL.
• callback_extra Passed to callback as its last argument.

Returns

OG_SUCCESS, also when the callback returned OG_STOP; the callback's own code when it returned any other error; otherwise an error code listed below.

Errors

• OG_EINVAL steps is negative.
• OG_EINVAL start is true and membership is NULL, does not have |V| entries, or holds an id outside 0..|V|-1.
• OG_EINVAL weights does not have |E| entries, or holds a negative, NaN or infinite value.
• OG_EARPACK The eigensolver did not converge.
• OG_ENOMEM Not enough memory.

Complexity

One sparse symmetric eigenproblem per attempt, each matrix-vector product linear in the community's vertices and edges; about O(|V|^2 log |V|) for a full run on a sparse graph (Newman 2006).

Checked

Same membership, merges and modularity as python-igraph 1.0 on 497 cases (eigenvectors to solver tolerance). Where the leading eigenvalue is degenerate any vector of its eigenspace is valid and the split may differ; where python-igraph fails with an ARPACK error on zero-weight components, Open Graph leaves that community whole.

C name

og_community_leading_eigenvector

In notebooks

Og.CommunityLeadingEigenvector

igraph 1.0

igraph_community_leading_eigenvector

See also

le_community_to_membership, community_leading_eigenvector_callback_t, modularity_matrix

Infomap: finds the partition that gives the shortest description of a random walk (the map equation).

og_error_t og_community_infomap(
    const og_t *graph,
    const og_vector_t *edge_weights,
    const og_vector_t *vertex_weights,
    og_int_t nb_trials,
    og_bool_t is_regularized,
    og_real_t regularization_strength,
    og_vector_int_t *membership,
    og_real_t *codelength
);

Rosvall and Bergstrom (2008); Rosvall, Axelsson and Bergstrom (2009). A random walk is described with one codebook per module plus an index codebook; the two-level map equation gives the expected code length per step in bits. The search moves vertices greedily between modules, aggregates modules into nodes and repeats, with submodule and single-vertex refinement. nb_trials independent runs are made and the shortest code wins (ties to the lowest trial); the result is never longer than taking the connected components as modules.

The flow is that of the undirected graph: edge directions do not change the code length or the partition, and vertex_weights are checked but do not affect the result, both as python-igraph 1.0 behaves. A self-loop adds its weight once to its vertex. With is_regularized, the prior network of Smiljanic et al. (2021) adds weak links between all vertices (connectivity regularization_strength * ln(n) / n), which keeps sparse, under-sampled networks from being cut into too many small modules.

membership is numbered by first vertex and codelength is in bits. The null graph gives an empty membership and NaN; a graph where nothing flows (no edges, or all weights 0) gives singletons and 0. Random: each trial gets its own seed, drawn from the default generator in trial order before any trial runs; with Open Graph's own logarithm a seed gives the same bits on every platform and at every thread count.

Parameters

• graph The graph; directions are ignored.
• edge_weights Edge weights (length |E|), non-negative and finite; NULL means 1.
• vertex_weights Vertex weights (length |V|), non-negative and finite; checked, not used. May be NULL.
• nb_trials Number of independent runs, at least 1.
• is_regularized Add the Bayesian prior network (Smiljanic et al. 2021).
• regularization_strength Scale of the prior, finite and at least 0 (only with is_regularized).
• membership Output: module of each vertex. May be NULL.
• codelength Output: the code length in bits. May be NULL.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL edge_weights does not have |E| entries or vertex_weights |V|, or either holds a negative, NaN or infinite value.
• OG_EINVAL nb_trials is below 1.
• OG_EINVAL is_regularized with a negative, NaN or infinite regularization_strength.
• OG_ENOMEM Not enough memory.

Complexity

Roughly O(|E|) per sweep of the greedy search, times the aggregation levels and refinement rounds, times nb_trials (shared among threads).

Checked

Randomised. The objective is exact: Open Graph's code length of python-igraph 1.0's partition equals python-igraph's on 200 random graphs; Open Graph's own partitions are as short or shorter in 184 of 200. 0.26x python-igraph's time for one trial, 0.41x for ten (20k vertices / 100k edges).

Threads

The trials run in parallel on Open Graph's thread layer when set_num_threads(n) is above 1 (or a host executor is set), one trial per task with its own generator and state; tasks beyond the first stay within a 1 GiB memory budget. The answer is the same bits at every thread count and schedule.

C name

og_community_infomap

In notebooks

Og.CommunityInfomap

igraph 1.0

igraph_community_infomap

See also

community_walktrap, community_leiden

og_t g;
og_vector_int_t membership;
og_real_t codelength;
og_famous(&g, "Zachary");
og_vector_int_init(&membership, 0);
og_set_num_threads(0);            /* optional: trials on every core, same answer */
og_rng_seed(og_rng_default(), 7);
og_community_infomap(&g, NULL, NULL, 10, false, 0.0, &membership, &codelength);
og_vector_int_destroy(&membership);
og_destroy(&g);