qbiocode.evaluation.graph_evaluation module

Graph complexity evaluation for QBioCode.

This module is the graph-network analogue of qbiocode.evaluation.dataset_evaluation. Where dataset_evaluation.evaluate(df, y, file) summarizes a tabular (samples x features) dataset, graph_evaluation.evaluate_graph(G, name) summarizes a networkx.Graph with spectral, topological, and structural complexity metrics and returns a one-row transposed pandas.DataFrame.

The metric implementations below are ported from the QuVINE complexity modules (graph.py + graph_enhanced.py) and are self-contained here so that QBioCode owns the graph-complexity math directly (no quvine.complexity dependency). The heavy embedding machinery lives separately under qbiocode.apps.quvine.

Optional dependencies: - ripser -> persistent Betti / persistence-entropy metrics - python-louvain (community) -> modularity / community metrics Both are guarded; missing them degrades gracefully to defaults.

Summary

Classes:

ComplexityConfig

Runtime and approximation settings for scalable metrics.

Functions:

compare_graph_complexities	Compare complexity metrics across multiple graphs.
compute_adjacency_spectral_metrics	Compute IPR of band-edge eigenvectors of the unsigned adjacency matrix A.
compute_algebraic_connectivity	Compute algebraic connectivity (Fiedler value).
compute_approx_path_length_metric	Approximate average shortest-path length using sampled BFS sources.
compute_betti_numbers	Compute persistent Betti numbers β₀, β₁, β₂ using Ripser.
compute_centrality_concentration_metrics	Approximate betweenness Gini and PageRank Gini.
compute_community_metrics	Compute modularity and approximate conductance from detected communities.
compute_complexity_table	Compute a pandas DataFrame of complexity metrics for many graphs.
compute_core_metrics	k-core concentration as a scalable core-periphery proxy.
compute_cycle_metrics	Compute transitivity, normalized cycle density, and nonbacktracking spectral radius.
compute_cyclomatic_number	Compute cyclomatic number (circuit rank / first Betti number of 1-skeleton).
compute_degree_metrics	Degree heterogeneity, hub dominance, and assortativity.
compute_effective_resistance	Compute effective resistance between two nodes.
compute_enhanced_complexity_metrics	Compute the enhanced QuVINE complexity metrics for a single graph.
compute_estrada_index	Compute the Laplacian Estrada index.
compute_feature_dirichlet_energy	Compute normalized feature Dirichlet energy Tr(X^T L X) / Tr(X^T X).
compute_graph_complexity_metrics	Compute comprehensive complexity metrics for a graph.
compute_heat_kernel_traces	Compute normalized heat kernel traces tr(exp(-t L)) / n via the Hutchinson estimator with Rademacher probe vectors and scipy.sparse.linalg.expm_multiply.
compute_inverse_participation_ratio	Compute the mean Inverse Participation Ratio (IPR) over all Laplacian eigenmodes.
compute_kirchhoff_index	Compute Kirchhoff index (total effective resistance).
compute_kirchhoff_stats	Compute Kirchhoff index and normalized variants.
compute_label_homophily	Fraction of edges connecting nodes with identical labels.
compute_laplacian_centrality_complexity	Compute centrality-based complexity metrics from the Laplacian.
compute_laplacian_spectrum	Compute the eigenvalues of the graph Laplacian.
compute_nonbacktracking_spectral_radius	Approximate spectral radius of the Hashimoto/non-backtracking matrix.
compute_odd_girth_metric	Compute log(1 + shortest_odd_cycle_length).
compute_orc_per_edge	Compute Ollivier-Ricci curvature approximations for every edge.
compute_orc_proxy_metrics	Compute scalable ORC-inspired edge bottleneck proxies.
compute_orc_stats	Aggregate ORC statistics over all edges.
compute_participation_ratio	Compute the mean Participation Ratio (PR) over all Laplacian eigenmodes.
compute_persistence_entropy	Compute persistence entropy for each homological dimension.
compute_quantum_advantage_metrics	Compute metrics that predict quantum advantage in graph algorithms.
compute_quantum_complexity	Compute quantum complexity metric inspired by QBioCode.
compute_size_density_metrics	Compute scale and density controls.
compute_sparse_spectral_metrics	Compute scalable spectral descriptors using sparse Lanczos on the normalized Laplacian.
compute_spectral_concentration	Compute spectral concentration from the Laplacian eigenvalue distribution.
compute_spectral_entropy	Compute spectral entropy based on Laplacian eigenvalues.
compute_spectral_gap	Compute the spectral gap (difference between first and second eigenvalues).
compute_topological_metrics	Compute all topological/geometric complexity metrics.
compute_von_neumann_entropy	Compute von Neumann entropy of the graph.
compute_wl_compression_ratio	WL color compression ratio after a few 1-WL refinement iterations.
evaluate_graph	Summarize a graph's complexity as a one-row DataFrame.
fiedler_eigenvalue_sparse	Compute Fiedler eigenvalue and eigenvector using sparse matrix methods.
get_nodelist
get_sparse_adjacency	Sparse adjacency with explicit nodelist for reproducibility.
get_sparse_laplacian	Sparse Laplacian with explicit nodelist for reproducibility.
gini_coefficient	Compute Gini coefficient for a nonnegative vector.
rank_graphs_by_complexity	Rank graphs by a specific complexity metric.
safe_eigsh	Robust wrapper around scipy.sparse.linalg.eigsh.
safe_float	Coerce x to a finite float, returning default if it is not one.
sanitize_graph	Return a simple NetworkX graph suitable for undirected complexity metrics.

Reference

compute_laplacian_spectrum(G, normalized=True)

Compute the eigenvalues of the graph Laplacian.

Parameters:

• G (nx.Graph) – Input graph

• normalized (bool, default=True) – If True, use normalized Laplacian; otherwise use unnormalized

Returns:

eigenvalues – Sorted eigenvalues of the Laplacian (ascending order)

Return type:

np.ndarray

compute_spectral_gap(G, normalized=True)

Compute the spectral gap (difference between first and second eigenvalues).

The spectral gap is related to graph connectivity and mixing time. Larger gaps indicate better connectivity and faster mixing.

Parameters:

• G (nx.Graph) – Input graph

• normalized (bool, default=True) – If True, use normalized Laplacian

Returns:

Spectral gap (lambda_2 - lambda_1)

Return type:

float

fiedler_eigenvalue_sparse(G, normalized=False)

Compute Fiedler eigenvalue and eigenvector using sparse matrix methods.

This is more efficient for large graphs than computing the full spectrum. The Fiedler eigenvalue is the second smallest eigenvalue of the Laplacian, and its eigenvector (Fiedler vector) is useful for graph partitioning.

Parameters:

• G (nx.Graph) – Input graph

• normalized (bool, default=False) – If True, use normalized Laplacian; otherwise use unnormalized

Return type:

Tuple[float, ndarray]

Returns:

• lambda2 (float) – Fiedler eigenvalue (second smallest eigenvalue)

• fiedler_vec (np.ndarray) – Fiedler eigenvector

compute_algebraic_connectivity(G)

Compute algebraic connectivity (Fiedler value).

This is the second smallest eigenvalue of the unnormalized Laplacian matrix. Higher values indicate better connectivity and robustness to node removal.

Parameters:

G (nx.Graph) – Input graph

Returns:

Algebraic connectivity (lambda_2)

Return type:

float

compute_spectral_entropy(G, normalized=True)

Compute spectral entropy based on Laplacian eigenvalues.

Spectral entropy measures the complexity/randomness of the graph structure by treating the normalized positive eigenvalues as a probability distribution. Higher entropy indicates more complex or random structure.

Parameters:

• G (nx.Graph) – Input graph

• normalized (bool, default=True) – If True, use normalized Laplacian

Returns:

Spectral entropy H = -sum(p_i * log(p_i)) where p_i = lambda_i / sum(lambda)

Return type:

float

compute_von_neumann_entropy(G)

Compute von Neumann entropy of the graph.

Implements the Passerini-Severini (2008) definition: the graph is associated with a density matrix rho = L / Tr(L), where L is the combinatorial (unnormalized) Laplacian and Tr(L) = sum of (weighted) degrees. The von Neumann entropy is then:

S = -Tr(rho log2 rho) = -sum_i (lambda_i / Tr(L)) * log2(lambda_i / Tr(L))

where the sum is over non-zero eigenvalues of L.

Parameters:

G (nx.Graph) – Input graph

Returns:

Von Neumann entropy S in bits (log base 2)

Return type:

float

compute_estrada_index(G)

Compute the Laplacian Estrada index.

The Laplacian Estrada Index (LEE) is defined as:

LEE = sum_i exp(lambda_i)

where lambda_i are the eigenvalues of the unnormalized Laplacian. It is related to the number of closed walks in the graph and captures the overall “folding” or connectivity complexity.

Note: For large dense graphs the exponentials can be very large. This implementation uses log-space accumulation when any eigenvalue exceeds 500 to avoid float64 overflow.

Parameters:

G (nx.Graph) – Input graph

Returns:

Laplacian Estrada index LEE = sum exp(lambda_i)

Return type:

float

compute_quantum_complexity(G)

Compute quantum complexity metric inspired by QBioCode.

This combines spectral properties to measure how “quantum” or complex the graph structure is. Higher values indicate more complex structures that may benefit from quantum walks.

The metric is a weighted combination (weights: 0.3, 0.3, 0.4) of: - Spectral gap ratio (gap / spectral radius) - Spectral participation ratio (fraction of active modes) - Normalised von Neumann entropy

Parameters:

G (nx.Graph) – Input graph

Returns:

Quantum complexity score in [0, 1]

Return type:

float

compute_spectral_concentration(G, normalized=True)

Compute spectral concentration from the Laplacian eigenvalue distribution.

Measures how concentrated the spectral energy is among the eigenvalues:

SC = sum(lambda_i^4) / (sum(lambda_i^2))^2

This is analogous to an inverse participation ratio applied to the eigenvalue spectrum (not eigenvectors). Values near 1/k (where k is the number of non-zero eigenvalues) indicate uniform spectral spread; values near 1 indicate extreme spectral concentration in a few modes.

Note: this metric operates on eigenvalues and measures the shape of the spectrum. For eigenvector-based localization, see compute_inverse_participation_ratio().

Parameters:

• G (nx.Graph) – Input graph

• normalized (bool, default=True) – If True, use normalized Laplacian eigenvalues

Returns:

Spectral concentration in [1/k, 1] where k = number of non-zero eigenvalues

Return type:

float

compute_inverse_participation_ratio(G, normalized=True)

Compute the mean Inverse Participation Ratio (IPR) over all Laplacian eigenmodes.

For each normalised eigenvector v of the Laplacian, the IPR is defined as:

IPR(v) = sum_j v_j^4

Because the eigenvectors are L2-normalised (sum v_j^2 = 1), IPR(v) lies in [1/n, 1]. A value of 1/n corresponds to a perfectly delocalised mode (uniform over all n nodes), while IPR = 1 means the mode is entirely concentrated on a single node (Anderson localisation limit).

This function returns the mean IPR averaged over all n eigenmodes.

Parameters:

• G (nx.Graph) – Input graph

• normalized (bool, default=True) – If True, use the normalised Laplacian; otherwise use the combinatorial (unnormalised) Laplacian

Returns:

Mean IPR in [1/n, 1]

Return type:

float

compute_participation_ratio(G, normalized=True)

Compute the mean Participation Ratio (PR) over all Laplacian eigenmodes.

The Participation Ratio is the inverse of the IPR for each eigenmode:

PR(v) = 1 / IPR(v) = 1 / sum_j v_j^4

PR(v) estimates the effective number of nodes over which eigenmode v is spread. It ranges from 1 (fully localised on one node) to n (perfectly delocalised across all nodes). The mean over all modes is returned.

Parameters:

• G (nx.Graph) – Input graph

• normalized (bool, default=True) – If True, use the normalised Laplacian; otherwise use the combinatorial Laplacian

Returns:

Mean participation ratio in [1, n]

Return type:

float

compute_effective_resistance(G, source, target)

Compute effective resistance between two nodes.

Effective resistance is related to random walk commute time and provides a distance metric on the graph.

R(i, j) = L^+_ii + L^+_jj - 2 L^+_ij

where L^+ is the Moore-Penrose pseudoinverse of the Laplacian.

Parameters:

• G (nx.Graph) – Input graph

• source (int) – Source node

• target (int) – Target node

Returns:

Effective resistance (non-negative)

Return type:

float

compute_laplacian_centrality_complexity(G, normalized=True)

Compute centrality-based complexity metrics from the Laplacian.

Uses the Fiedler vector (eigenvector of the second-smallest eigenvalue) as a node-centrality proxy and characterises its distribution via entropy, variance, Gini coefficient, and range.

Parameters:

• G (nx.Graph) – Input graph

• normalized (bool, default=True) – If True, use normalized Laplacian

Returns:

Dictionary of centrality complexity metrics including: - centrality_entropy: Shannon entropy of the Fiedler-vector distribution - centrality_variance: Variance of absolute Fiedler-vector entries - centrality_gini: Gini coefficient of absolute Fiedler-vector entries - centrality_range: Range (max - min) of absolute entries - dominant_eigenvector_centrality: Max entry of the largest-eigenvalue eigenvector

Return type:

dict

compute_graph_complexity_metrics(G)

Compute comprehensive complexity metrics for a graph.

Parameters:

G (nx.Graph) – Input graph

Returns:

Dictionary of complexity metrics

Return type:

dict

compare_graph_complexities(graphs)

Compare complexity metrics across multiple graphs.

Parameters:

graphs (dict) – Dictionary mapping graph names to NetworkX graphs

Returns:

Dictionary mapping graph names to their complexity metrics

Return type:

dict

compute_quantum_advantage_metrics(G)

Compute metrics that predict quantum advantage in graph algorithms.

These metrics help identify when quantum walks are likely to outperform classical random walks based on graph structure.

Parameters:

G (nx.Graph) – Input graph

Returns:

Dictionary including: - spectral_dimension: Effective number of active eigenvalues - modularity: Community structure strength (Louvain greedy) - path_length_ratio: avg_path_length / diameter - clustering_mean/std: Local clustering statistics - degree_heterogeneity: Coefficient of variation of degree sequence - quantum_advantage_score: Weighted composite prediction score

Return type:

dict

rank_graphs_by_complexity(graphs, metric='quantum_complexity')

Rank graphs by a specific complexity metric.

Parameters:

• graphs (dict) – Dictionary mapping graph names to NetworkX graphs

• metric (str, default='quantum_complexity') – Metric to use for ranking

Returns:

List of (name, score) tuples sorted by complexity (descending)

Return type:

list

compute_orc_per_edge(G)

Compute Ollivier-Ricci curvature approximations for every edge.

Two approximations are computed:

1. Generalized Jaccard (gJC): Fast O(d) proxy gJC(u, v) = |N(u) ∩ N(v)| / |N(u) ∪ N(v)|

2. Jost-Liu lower bound (κ_LB): Tighter spectral bound κ_LB(u, v) = Δ / max(dᵤ, d_v) + 1/dᵤ + 1/d_v − 1

Parameters:

G (nx.Graph) – Input graph

Returns:

Mapping (u, v) → {‘gJC’: float, ‘kappa_LB’: float, ‘triangles’: int}

Return type:

dict

compute_orc_stats(G)

Aggregate ORC statistics over all edges.

Returns mean, min, max, std for both gJC and κ_LB, plus the fraction of edges with negative κ_LB (bottleneck indicator).

Parameters:

G (nx.Graph) – Input graph

Returns:

ORC statistics with keys: - orc_gJC_mean, orc_gJC_min, orc_gJC_max, orc_gJC_std - orc_kLB_mean, orc_kLB_min, orc_kLB_max, orc_kLB_std - orc_negative_fraction (fraction of edges with κ_LB < 0) - orc_num_edges

Return type:

dict

compute_cyclomatic_number(G)

Compute cyclomatic number (circuit rank / first Betti number of 1-skeleton).

μ(G) = m − n + c

where m = |E|, n = |V|, c = number of connected components.

Interpretation: - μ = 0 iff G is a forest (no cycles) - μ counts minimum edges to remove to make G acyclic - Dimension of cycle space H₁(G; ℤ₂) - For quantum walks: counts interference-generating loops

Parameters:

G (nx.Graph) – Input graph

Returns:

Non-negative cyclomatic number

Return type:

int

compute_kirchhoff_index(G, tol=1e-10)

Compute Kirchhoff index (total effective resistance).

R_K = n · Σᵢ 1/λᵢ

summing over all positive eigenvalues λᵢ of the Laplacian.

Interpretation: - For disconnected graphs: R_K = ∞ - Classical random-walk mixing time ∝ R_K - Large R_K indicates bottlenecked topology → potential quantum speedup - Complete graph K_n: R_K = n−1 - Path graph P_n: R_K = n(n²−1)/6

Parameters:

• G (nx.Graph) – Input graph

• tol (float) – Eigenvalue threshold for filtering zero mode

Returns:

Kirchhoff index, or np.inf for disconnected graphs

Return type:

float

compute_kirchhoff_stats(G, tol=1e-10)

Compute Kirchhoff index and normalized variants.

Parameters:

• G (nx.Graph) – Input graph

• tol (float) – Eigenvalue threshold

Returns:

• kirchhoff_index: Raw R_K

• kirchhoff_per_pair: R_K / C(n, 2) (mean effective resistance)

• kirchhoff_normalised: R_K / R_K(P_n) (fraction of path-graph value)

Return type:

dict

compute_betti_numbers(G, maxdim=2, filtration_scale=1.0)

Compute persistent Betti numbers β₀, β₁, β₂ using Ripser.

Uses hop-count shortest-path distance matrix for Vietoris-Rips filtration.

At filtration scale ε = 1 (one hop = one edge): - β₀ = number of connected components - β₁ = number of independent cycles in clique complex - β₂ = voids (unfilled tetrahedra) in clique complex

Relationship to cyclomatic number μ: - μ counts all cycles in 1-skeleton (graph edges only) - β₁ counts cycles not filled by triangles - β₁ ≤ μ (triangles reduce cycle count) - β₁ = μ iff G is triangle-free

Parameters:

• G (nx.Graph) – Input graph

• maxdim (int, default=2) – Maximum homological dimension

• filtration_scale (float, default=1.0) – ε at which Betti numbers are evaluated

Returns:

• betti_0, betti_1, betti_2: Betti numbers at filtration_scale

• persistence_diagrams: list of numpy arrays

• betti_sum: β₀ + β₁ + β₂

• euler_characteristic: β₀ − β₁ + β₂

Return type:

dict

compute_persistence_entropy(G, maxdim=2, filtration_scale=1.0)

Compute persistence entropy for each homological dimension.

For persistence diagram D_k = {(bᵢ, dᵢ)}, persistence entropy is:

H_k = −Σᵢ (lᵢ / L) · log(lᵢ / L)

where lᵢ = dᵢ − bᵢ is persistence lifetime and L = Σᵢ lᵢ.

Measures complexity of multi-scale topological structure: - High H_k: many cycles with diverse lifetimes - Low H_k: one dominant topological feature

Parameters:

• G (nx.Graph) – Input graph

• maxdim (int, default=2) – Maximum dimension

• filtration_scale (float) – Unused (entropy computed over all features)

Returns:

persistence_entropy_H0, persistence_entropy_H1, persistence_entropy_H2

Return type:

dict

compute_topological_metrics(G, include_betti=True, include_persistence_entropy=True, maxdim=2, filtration_scale=1.0)

Compute all topological/geometric complexity metrics.

Metrics computed: - ORC (Ollivier-Ricci curvature): gJC and κ_LB approximations - Cyclomatic number: Circuit rank μ - Kirchhoff index: Total effective resistance R_K - Betti numbers: β₀, β₁, β₂ (if include_betti=True) - Persistence entropy: H₀, H₁, H₂ (if include_persistence_entropy=True)

Parameters:

• G (nx.Graph) – Input graph

• include_betti (bool, default=True) – Compute Betti numbers (expensive for large graphs)

• include_persistence_entropy (bool, default=True) – Compute persistence entropy (requires include_betti=True)

• maxdim (int, default=2) – Maximum homological dimension

• filtration_scale (float, default=1.0) – ε at which Betti numbers are evaluated

Returns:

All topological metrics

Return type:

dict

class ComplexityConfig(spectral_k=64, eig_tol=1e-05, path_num_sources=64, betweenness_k=256, wl_iterations=3, nonbacktracking_max_directed_edges=1000000, random_state=0, use_largest_cc_for_path=True, pagerank_alpha=0.85, pagerank_max_iter=200, pagerank_tol=1e-06, heat_kernel_t_values=(1.0, 10.0), heat_kernel_n_probes=20, odd_girth_max_sources=32, odd_girth_min_cycle_break=5)

Bases: object

Runtime and approximation settings for scalable metrics.

spectral_k: int = 64

eig_tol: float = 1e-05

path_num_sources: int = 64

betweenness_k: int = 256

wl_iterations: int = 3

nonbacktracking_max_directed_edges: int = 1000000

random_state: int = 0

use_largest_cc_for_path: bool = True

pagerank_alpha: float = 0.85

pagerank_max_iter: int = 200

pagerank_tol: float = 1e-06

heat_kernel_t_values: Tuple[float, ...] = (1.0, 10.0)

heat_kernel_n_probes: int = 20

odd_girth_max_sources: int = 32

odd_girth_min_cycle_break: int = 5

sanitize_graph(G, make_undirected=True, remove_selfloops=True)

Return a simple NetworkX graph suitable for undirected complexity metrics.

Return type:

Graph

safe_float(x, default=nan)

Coerce x to a finite float, returning default if it is not one.

Deliberately broad on the coercion: this is called on values from many metric backends, and float() raises TypeError for a None or a sequence, ValueError for an unparsable string, and OverflowError for an out-of-range value. Not logged – it runs once per metric value, and the caller decides what a missing metric means.

Return type:

float

gini_coefficient(values)

Compute Gini coefficient for a nonnegative vector.

Return type:

float

get_nodelist(G)

Return type:

List[Hashable]

get_sparse_laplacian(G, normalized=True)

Sparse Laplacian with explicit nodelist for reproducibility.

Return type:

Tuple[csr_matrix, List[Hashable]]

get_sparse_adjacency(G)

Sparse adjacency with explicit nodelist for reproducibility.

Return type:

Tuple[csr_matrix, List[Hashable]]

safe_eigsh(L, k, which, tol=1e-05, return_eigenvectors=True)

Robust wrapper around scipy.sparse.linalg.eigsh.

Return type:

Tuple[ndarray, Optional[ndarray]]

compute_size_density_metrics(G)

Compute scale and density controls.

Return type:

Dict[str, float]

compute_sparse_spectral_metrics(G, config=ComplexityConfig(spectral_k=64, eig_tol=1e-05, path_num_sources=64, betweenness_k=256, wl_iterations=3, nonbacktracking_max_directed_edges=1000000, random_state=0, use_largest_cc_for_path=True, pagerank_alpha=0.85, pagerank_max_iter=200, pagerank_tol=1e-06, heat_kernel_t_values=(1.0, 10.0), heat_kernel_n_probes=20, odd_girth_max_sources=32, odd_girth_min_cycle_break=5))

Compute scalable spectral descriptors using sparse Lanczos on the normalized Laplacian.

Return type:

Dict[str, float]

Existing keys (unchanged semantics):

• normalized_spectral_gap

• laplacian_effective_rank_partial

• ipr_low_mean

• ipr_high_mean

• spectral_degeneracy_fraction (BUG-FIXED: within-block gaps only)

New keys:

• bipartite_proximitymax(0, 2 - lambda_n^(L_norm)).

  Equals 0 iff a bipartite component exists.

• algebraic_connectivity_ratio : lambda_2 / lambda_n^(L_norm).

• spectral_entropy_partialShannon entropy of normalized partial spectrum,

  normalized to [0,1].

compute_adjacency_spectral_metrics(G, config=ComplexityConfig(spectral_k=64, eig_tol=1e-05, path_num_sources=64, betweenness_k=256, wl_iterations=3, nonbacktracking_max_directed_edges=1000000, random_state=0, use_largest_cc_for_path=True, pagerank_alpha=0.85, pagerank_max_iter=200, pagerank_tol=1e-06, heat_kernel_t_values=(1.0, 10.0), heat_kernel_n_probes=20, odd_girth_max_sources=32, odd_girth_min_cycle_break=5))

Compute IPR of band-edge eigenvectors of the unsigned adjacency matrix A.

Theoretically motivated for QW pathways that use H = A (rather than H = L), and complementary to Laplacian-IPR because adjacency eigenvectors are not degree-normalized; localization signals on hubs survive.

Return type:

Dict[str, float]

compute_heat_kernel_traces(G, config=ComplexityConfig(spectral_k=64, eig_tol=1e-05, path_num_sources=64, betweenness_k=256, wl_iterations=3, nonbacktracking_max_directed_edges=1000000, random_state=0, use_largest_cc_for_path=True, pagerank_alpha=0.85, pagerank_max_iter=200, pagerank_tol=1e-06, heat_kernel_t_values=(1.0, 10.0), heat_kernel_n_probes=20, odd_girth_max_sources=32, odd_girth_min_cycle_break=5))

Compute normalized heat kernel traces tr(exp(-t L)) / n via the Hutchinson estimator with Rademacher probe vectors and scipy.sparse.linalg.expm_multiply.

Theoretically motivated: tr(exp(-t L)) = sum_i exp(-t lambda_i) is the smooth spectral observable that integrates the diffusion behavior the relevant QW vs classical mixing bounds depend on. At small t it is dominated by the bulk spectrum; at large t it is dominated by the spectral gap.

Each call is ~O(n_probes * matvec * scipy_internal_steps). For n=5000 with sparse L, this is at most a few seconds.

Return type:

Dict[str, float]

compute_odd_girth_metric(G, config=ComplexityConfig(spectral_k=64, eig_tol=1e-05, path_num_sources=64, betweenness_k=256, wl_iterations=3, nonbacktracking_max_directed_edges=1000000, random_state=0, use_largest_cc_for_path=True, pagerank_alpha=0.85, pagerank_max_iter=200, pagerank_tol=1e-06, heat_kernel_t_values=(1.0, 10.0), heat_kernel_n_probes=20, odd_girth_max_sources=32, odd_girth_min_cycle_break=5))

Compute log(1 + shortest_odd_cycle_length).

Return type:

Dict[str, float]

Procedure:

1. If G is bipartite, return NaN (no odd cycle exists).

2. Fast triangle existence check via shared-neighbor scan; if any triangle exists, return log(1 + 3).

3. Otherwise, BFS from up to odd_girth_max_sources sampled sources; for each source s, scan all edges and identify same-level closures (level u == level v), giving an odd cycle of length 2 * level + 1 passing through s. Track the minimum.

Returns NaN if no odd cycle is found within the source budget.

compute_approx_path_length_metric(G, config=ComplexityConfig(spectral_k=64, eig_tol=1e-05, path_num_sources=64, betweenness_k=256, wl_iterations=3, nonbacktracking_max_directed_edges=1000000, random_state=0, use_largest_cc_for_path=True, pagerank_alpha=0.85, pagerank_max_iter=200, pagerank_tol=1e-06, heat_kernel_t_values=(1.0, 10.0), heat_kernel_n_probes=20, odd_girth_max_sources=32, odd_girth_min_cycle_break=5))

Approximate average shortest-path length using sampled BFS sources.

Return type:

Dict[str, float]

Also returns:

• largest_cc_fraction

• closeness_gini_approx (NEW; free byproduct of same BFS calls).

For disconnected graphs, the metric is computed on the largest connected component when use_largest_cc_for_path is True.

compute_community_metrics(G, config=ComplexityConfig(spectral_k=64, eig_tol=1e-05, path_num_sources=64, betweenness_k=256, wl_iterations=3, nonbacktracking_max_directed_edges=1000000, random_state=0, use_largest_cc_for_path=True, pagerank_alpha=0.85, pagerank_max_iter=200, pagerank_tol=1e-06, heat_kernel_t_values=(1.0, 10.0), heat_kernel_n_probes=20, odd_girth_max_sources=32, odd_girth_min_cycle_break=5))

Compute modularity and approximate conductance from detected communities.

Return type:

Dict[str, float]

compute_degree_metrics(G)

Degree heterogeneity, hub dominance, and assortativity.

Return type:

Dict[str, float]

compute_centrality_concentration_metrics(G, config=ComplexityConfig(spectral_k=64, eig_tol=1e-05, path_num_sources=64, betweenness_k=256, wl_iterations=3, nonbacktracking_max_directed_edges=1000000, random_state=0, use_largest_cc_for_path=True, pagerank_alpha=0.85, pagerank_max_iter=200, pagerank_tol=1e-06, heat_kernel_t_values=(1.0, 10.0), heat_kernel_n_probes=20, odd_girth_max_sources=32, odd_girth_min_cycle_break=5))

Approximate betweenness Gini and PageRank Gini.

Return type:

Dict[str, float]

compute_cycle_metrics(G, config=ComplexityConfig(spectral_k=64, eig_tol=1e-05, path_num_sources=64, betweenness_k=256, wl_iterations=3, nonbacktracking_max_directed_edges=1000000, random_state=0, use_largest_cc_for_path=True, pagerank_alpha=0.85, pagerank_max_iter=200, pagerank_tol=1e-06, heat_kernel_t_values=(1.0, 10.0), heat_kernel_n_probes=20, odd_girth_max_sources=32, odd_girth_min_cycle_break=5))

Compute transitivity, normalized cycle density, and nonbacktracking spectral radius.

Return type:

Dict[str, float]

compute_nonbacktracking_spectral_radius(G, config=ComplexityConfig(spectral_k=64, eig_tol=1e-05, path_num_sources=64, betweenness_k=256, wl_iterations=3, nonbacktracking_max_directed_edges=1000000, random_state=0, use_largest_cc_for_path=True, pagerank_alpha=0.85, pagerank_max_iter=200, pagerank_tol=1e-06, heat_kernel_t_values=(1.0, 10.0), heat_kernel_n_probes=20, odd_girth_max_sources=32, odd_girth_min_cycle_break=5))

Approximate spectral radius of the Hashimoto/non-backtracking matrix.

Return type:

float

compute_orc_proxy_metrics(G)

Compute scalable ORC-inspired edge bottleneck proxies.

Return type:

Dict[str, float]

Uses the Jost-Liu style lower-bound proxy:

kappa_LB(u,v) = Delta/max(d_u,d_v) + 1/d_u + 1/d_v - 1

compute_wl_compression_ratio(G, config=ComplexityConfig(spectral_k=64, eig_tol=1e-05, path_num_sources=64, betweenness_k=256, wl_iterations=3, nonbacktracking_max_directed_edges=1000000, random_state=0, use_largest_cc_for_path=True, pagerank_alpha=0.85, pagerank_max_iter=200, pagerank_tol=1e-06, heat_kernel_t_values=(1.0, 10.0), heat_kernel_n_probes=20, odd_girth_max_sources=32, odd_girth_min_cycle_break=5))

WL color compression ratio after a few 1-WL refinement iterations.

Return type:

Dict[str, float]

compute_core_metrics(G)

k-core concentration as a scalable core-periphery proxy.

Return type:

Dict[str, float]

compute_label_homophily(G, labels)

Fraction of edges connecting nodes with identical labels.

Return type:

Dict[str, float]

compute_feature_dirichlet_energy(G, features, normalized_laplacian=True)

Compute normalized feature Dirichlet energy Tr(X^T L X) / Tr(X^T X).

Return type:

Dict[str, float]

compute_enhanced_complexity_metrics(G, labels=None, features=None, config=ComplexityConfig(spectral_k=64, eig_tol=1e-05, path_num_sources=64, betweenness_k=256, wl_iterations=3, nonbacktracking_max_directed_edges=1000000, random_state=0, use_largest_cc_for_path=True, pagerank_alpha=0.85, pagerank_max_iter=200, pagerank_tol=1e-06, heat_kernel_t_values=(1.0, 10.0), heat_kernel_n_probes=20, odd_girth_max_sources=32, odd_girth_min_cycle_break=5), sanitize=True)

Compute the enhanced QuVINE complexity metrics for a single graph.

This function computes 36 comprehensive metrics (27 original + 9 new theory-grade metrics) that characterize graph structure and predict quantum advantage.

Parameters:

• G (nx.Graph) – Input graph

• labels (optional) – Node labels for computing label homophily

• features (optional) – Node features for computing feature Dirichlet energy

• config (ComplexityConfig) – Configuration for approximation parameters

• sanitize (bool, default=True) – If True, convert to simple undirected graph and remove self-loops

Returns:

Dictionary containing all 36 complexity metrics

Return type:

dict

compute_complexity_table(graphs, labels=None, features=None, config=ComplexityConfig(spectral_k=64, eig_tol=1e-05, path_num_sources=64, betweenness_k=256, wl_iterations=3, nonbacktracking_max_directed_edges=1000000, random_state=0, use_largest_cc_for_path=True, pagerank_alpha=0.85, pagerank_max_iter=200, pagerank_tol=1e-06, heat_kernel_t_values=(1.0, 10.0), heat_kernel_n_probes=20, odd_girth_max_sources=32, odd_girth_min_cycle_break=5))

Compute a pandas DataFrame of complexity metrics for many graphs.

Parameters:

• graphs (dict) – Dictionary mapping graph names to NetworkX graphs

• labels (optional) – Dictionary mapping graph names to node labels

• features (optional) – Dictionary mapping graph names to node features

• config (ComplexityConfig) – Configuration for approximation parameters

Returns:

DataFrame with one row per graph and columns for each metric

Return type:

pd.DataFrame

evaluate_graph(G, name='')

Summarize a graph’s complexity as a one-row DataFrame.

Mirrors qbiocode.evaluation.dataset_evaluation.evaluate(): it runs the core spectral/topological metrics (compute_graph_complexity_metrics()) and the enhanced structural metrics (compute_enhanced_complexity_metrics()), merges them, and returns a transposed one-row summary keyed by name.

Parameters:

• G (networkx.Graph) – Graph to evaluate. Any networkx graph class is accepted; metrics undefined for the given class are omitted rather than raised (see Notes).

• name (str) – Identifier stored in the Graph column of the summary.

Returns:

One-row summary of graph complexity metrics.

Return type:

pandas.DataFrame

Raises:

TypeError – if G is not a networkx graph, or name is not a string.

Notes

An empty graph is a legitimate input and yields a size-only summary (Graph/num_nodes/num_edges) with a UserWarning. None is not: it is a caller error and raises, because the size-only summary previously returned for it reported “0 nodes” for a graph that was in fact missing.

Individual metric groups degrade independently: if either the core or the enhanced block fails, its columns are absent from the returned frame and a UserWarning names the failure. The frame is never partially populated with fabricated values, so check for a column before reading it rather than assuming a fixed width.