Complexity Summary#

This page summarizes the asymptotic complexity classes used in API docstrings.

Notation: n = number of nodes, m = number of edges, n_a = agents, n_f = artifacts, e_b = bipartite edges, I = iterations, T = trials.

Statistical#

Function	Time	Space	Notes
`disparity`	`O(n + m)`	`O(n + m)`	Alias for disparity_filter.
`disparity_filter`	`O(n + m)`	`O(n + m)`	n=V, m=E.
`ecm_filter`	`O(I * n^2 + m)`	`O(n + m)`	I=max_iter, n=V, m=E.
`lans`	`O(m log n)`	`O(n + m)`	Alias for lans_filter.
`lans_filter`	`O(m log n)`	`O(n + m)`	Worst-case over node-local sorted edge-weight lookups.
`marginal_likelihood_filter`	`O(n + m)`	`O(n + m)`	n=V, m=E.
`mlf`	`O(n + m)`	`O(n + m)`	Alias for marginal_likelihood_filter.
`multiple_linkage_analysis`	`O(m log n)`	`O(n + m)`	Dominated by lans_filter.
`noise_corrected_filter`	`O(n + m)`	`O(n + m)`	n=V, m=E.

Structural#

Function	Time	Space	Notes
`doubly_stochastic_filter`	`O(I * n^2 + m)`	`O(n^2 + m)`	I=max_iter for Sinkhorn-Knopp normalization.
`edge_betweenness_filter`	`O(nm + n^2 log n)`	`O(n + m)`	Dominated by weighted Brandes edge-betweenness.
`global_sparsification`	`O(m log m)`	`O(n + m)`
`global_threshold_filter`	`O(m)`	`O(n + m)`	n=V, m=E.
`h_backbone`	`O(nm + n^2 log n + m log m)`	`O(n + m)`	Dominated by edge-betweenness on residual graph.
`high_salience_skeleton`	`O(nm + n^2 log n)`	`O(n + m)`	Runs a shortest-path tree from each root.
`maximum_spanning_tree_backbone`	`O(m log n)`	`O(n + m)`
`metric_backbone`	`O(nm + n^2 log n)`	`O(n^2 + m)`	All-pairs weighted shortest paths.
`modularity_backbone`	`O(nm)`	`O(n + m)`	Practical/heuristic bound due to repeated Louvain runs.
`node_degree_filter`	`O(n + m)`	`O(n + m)`
`planar_maximally_filtered_graph`	`O(mn + m log m)`	`O(n + m)`
`primary_linkage_analysis`	`O(m)`	`O(n + m)`
`strongest_n_ties`	`O(m log n)`	`O(n + m)`	Worst-case across per-node strongest-edge selection.
`ultrametric_backbone`	`O(mn + m log n)`	`O(n + m)`	MST plus per-edge minimax path checks.

Proximity#

Function	Time	Space	Notes
`adamic_adar_index`	`O(mn)`	`O(n + m)`
`cosine_backbone`	`O(mn)`	`O(n + m)`
`dice_backbone`	`O(mn)`	`O(n + m)`
`graph_distance_proximity`	`O(n(n + m))`	`O(n^2 + m)`	Computes all-pairs shortest paths before edge annotation.
`hub_depressed_index`	`O(mn)`	`O(n + m)`
`hub_promoted_index`	`O(mn)`	`O(n + m)`
`jaccard_backbone`	`O(mn)`	`O(n + m)`
`lhn_local_index`	`O(mn)`	`O(n + m)`
`local_path_index`	`O(n^3)`	`O(n^2)`	Dense adjacency matrix multiplication.
`neighborhood_overlap`	`O(mn)`	`O(n + m)`	Worst-case over per-edge neighbor-set intersections.
`preferential_attachment_score`	`O(n + m)`	`O(n + m)`
`resource_allocation_index`	`O(mn)`	`O(n + m)`

Hybrid#

Function	Time	Space	Notes
`glab_filter`	`O(nm + n^2 log n)`	`O(n + m)`	Dominated by weighted edge-betweenness centrality.

Bipartite#

Function	Time	Space	Notes
`backbone`	`O(n + m) dispatch checks + selected method cost`	`O(1) additional beyond selected method`
`backbone_from_projection`	`O(T n_a^2 n_f + e_b)`	`O(n_a n_f + n_a^2)`	Worst-case over {sdsm, fdsm, fixedfill, fixedrow, fixedcol}.
`backbone_from_unweighted`	`O(mn)`	`O(n + m)`	Worst-case over {sparsify, lspar, local_degree}.
`backbone_from_weighted`	`O(m log n)`	`O(n + m)`	Worst-case over {disparity, mlf, lans, global_threshold}.
`bicm`	`O(n_a n_f + e_b)`	`O(n_a n_f)`
`bipartite_projection`	`O(n_a^2 n_f + I n_a^2 + e_b)`	`O(n_a n_f + n_a^2)`	Worst-case over supported projection methods.
`fastball`	`O(r c + S c)`	`O(r c)`	r=rows, c=cols, S=n_swaps.
`fdsm`	`O(T n_a^2 n_f + e_b)`	`O(n_a n_f + n_a^2)`	T=trials for Monte Carlo fixed-degree randomization.
`fixedcol`	`O(n_a^2 n_f + e_b)`	`O(n_a n_f + n_a^2)`
`fixedfill`	`O(n_a^2 n_f + e_b)`	`O(n_a n_f + n_a^2)`
`fixedrow`	`O(n_a^2 n_f + e_b)`	`O(n_a n_f + n_a^2)`
`hyper_projection`	`O(n_a^2 n_f + e_b)`	`O(n_a n_f + n_a^2)`
`probs_projection`	`O(n_a^2 n_f + e_b)`	`O(n_a n_f + n_a^2)`
`sdsm`	`O(n_a^2 n_f + e_b)`	`O(n_a n_f + n_a^2)`	Includes projection-weight annotation.
`simple_projection`	`O(n_a^2 n_f + e_b)`	`O(n_a n_f + n_a^2)`	n_a=agents, n_f=artifacts, e_b=bipartite edges.
`ycn_projection`	`O(n_a^2 n_f + I n_a^2 + e_b)`	`O(n_a n_f + n_a^2)`	I=max_iter for stationary-flow convergence.

Unweighted#

Function	Time	Space	Notes
`local_degree`	`O(m + n)`	`O(n + m)`	Wrapper over sparsify with degree scoring.
`lspar`	`O(mn)`	`O(n + m)`	Wrapper over sparsify with Jaccard scoring.
`sparsify`	`O(mn)`	`O(n + m)`	Worst-case; depends on escore/filter choices.

Filters#

Function	Time	Space	Notes
`boolean_filter`	`O(n + m)`	`O(n + m)`
`consensus_backbone`	`O(km)`	`O(m)`	k=number of input backbones, m=edges per backbone.
`fraction_filter`	`O(m log m)`	`O(n + m)`	Edge mode; node mode is O(n log n).
`multigraph_to_weighted`	`O(m)`	`O(n + m)`	m counts input edge instances for multigraphs.
`threshold_filter`	`O(n + m)`	`O(n + m)`

Measures#

Function	Time	Space	Notes
`compare_backbones`	`O(b * C)`	`O(b * q)`	b=backbones, q=measures, C=cost per measure evaluation.
`edge_fraction`	`O(1)`	`O(1)`
`ks_degree`	`O(n)`	`O(n)`
`ks_weight`	`O(m)`	`O(m)`
`node_fraction`	`O(n)`	`O(n)`
`reachability`	`O(n + m)`	`O(n)`
`weight_fraction`	`O(m)`	`O(1)`

Visualization#

Function	Time	Space	Notes
`compare_graphs`	`O(n + m) without layout; plus layout cost if pos is None`	`O(n + m)`	Spring layout adds iterative graph-drawing overhead.
`graph_difference`	`O(n + m)`	`O(n + m)`
`save_graph_comparison`	`O(n + m) without layout; plus rendering/write cost`	`O(n + m)`