Graph algorithms and result interpretation

#From a question to a tool call

Graph analysis usually proceeds through data inspection, entity resolution, computation, and presentation. Confirm version, direction, and properties with get_graph_info, resolve inputs by exact name or search, execute the algorithm, and then pass its results to visualization or reporting. The model organizes the analysis; Graph Engine supplies computed values.

Independent algorithms in one model response may run concurrently, but a step needing actual output must wait. Do not guess a node ID for shortest_path before search_node returns. Before clearing, replacing, or saving a subgraph, check whether the tool changes the active graph.

#Shortest paths and path enumeration

shortest_path with use_weight=true minimizes total edge weight; false minimizes hop count. These are different objectives. Weighted paths use NetworkX shortest-path routines, and all-target single-source requests use Dijkstra. Unweighted paths traverse by hops. A missing path is a valid query outcome represented by found=false, not necessarily a service failure.

A -> B : 2
A -> C : 5
B -> C : 1
B -> D : 4
C -> D : 1

Weighted minimum: A -> B -> C -> D, cost = 4, hops = 3
Minimum hops:     A -> B -> D or A -> C -> D, hops = 2

algorithm=yen_k_shortest returns several simple paths ordered by cost, possibly with different costs. all_shortest_paths returns paths tied at the optimal cost. path_analysis(method=all_simple_paths) enumerates simple paths within cutoff, potentially including many nonoptimal routes. Simple paths do not revisit nodes, unlike general walks.

target="all" computes single-source reachability and paths, showing the nearest 10 by default alongside reachable_count and distance statistics. all_shortest_paths also displays up to 10 by default. Display counts are not total reachable nodes or total shortest paths; inspect truncated and count_returned.

Property-graph parallel edges use minimum-weight projection and paths are distinguished by node sequence. Multiple equivalent relationships along one node sequence do not automatically create different returned paths. Some NebulaGraph tools load a bounded hop neighborhood, where a missing path only describes that scope.

#Centrality: different notions of importance

Centralities do not share one definition of importance. Degree counts direct connectivity, betweenness emphasizes mediation along shortest paths, and PageRank considers links from other important nodes. State the question and edge direction before interpreting rankings; scores from different centralities do not share a common scale.

node_centrality returns top_nodes, bottom_nodes, value_stats, and total_nodes, generally rounded to six decimals. top_nodes defaults to 20, while bottom_nodes avoids overlap with the leading entries. total_nodes counts scored nodes, which need not establish the graph size for methods such as VoteRank.

• NetworkX: closeness and directed distances↗
• NetworkX: betweenness definition↗

#Community detection and modularity

Community detection groups densely connected nodes. Graph Engine constructs the algorithm’s undirected analysis graph and computes communities and modularity. Modularity compares within-group connectivity with a random baseline. It compares partitions under the same graph and weight semantics, not predictive accuracy.

By default, show the five largest communities with ten node previews each. num_communities, communities_shown, communities_truncated, and nodes_truncated distinguish total groups, displayed groups, and both truncation levels. community_id belongs to this computation and is not a stable business identifier across graph versions.

Record graph version, weight usage, undirected projection, and covered nodes when comparing algorithms. Leiden has fallback and weight-transfer limitations, while asyn_fluidc can omit other connected components. These conditions change what the result means.

focus_nodes accepts up to 200 actual node names to associate them with the same community partition rather than IDs from another run. Identical algorithm names do not imply identical implementations across ordinary and large-graph paths: large-graph community analysis currently maps all seven names to scalable weighted synchronous label propagation, with max_iterations=5 by default. Inspect capabilities and consider strict_semantics=true to reject approximate mappings when the named algorithm’s semantics are required.

#Flows, cuts, and spanning trees

Maximum flow treats edge weights as capacities and maximizes flow from source to sink under capacity and conservation constraints. minimum_cut with source/sink finds the minimum-capacity separating cut. Under identical network and capacity conventions, maximum flow and minimum cut have equal values, providing an input-consistency check.

s -> a : 3
s -> b : 2
a -> b : 1
a -> t : 2
b -> t : 3

Feasible flow: s-a-t = 2, s-a-b-t = 1, s-b-t = 2
Maximum flow = 5; a minimum cut is {s} | {a,b,t}, capacity = 5

This illustrative network is calculated by hand. maximum_flow returns max_flow_value and nonzero-edge previews; minimum_cut returns min_cut_value, partition sizes, and cut-edge previews. Flow assignments and minimizing partitions may not be unique, so one returned edge set is not necessarily the only bottleneck solution.

global_minimum_cut has no fixed terminals and currently uses undirected Stoer–Wagner. Directed input requires treat_as_undirected=true; pair weights are combined and self-loops do not participate. Disconnected graphs have a cut value of zero. This asks for the easiest global separation rather than a cut between two chosen terminals.

minimum_spanning_tree minimizes total edge weight while connecting nodes without cycles. Disconnected input returns a minimum spanning forest summary. It minimizes total network connection cost, not every source-to-node path; use shortest_path for routing.

Minimum spanning trees use an undirected analysis graph. Constructed attributed graphs select the minimum-weight relationship per unordered endpoint pair. Ordinary directed graphs are converted directly by NetworkX, which does not guarantee choosing the smaller weight between opposite directions. Record the input representation and projection rule when comparing results.

#Structure, subgraphs, and candidate links

Strongly connected components require mutual directed reachability; weak components ignore direction. graph_connectivity reports both. topological_sort requires a directed acyclic graph. When business dependencies contain cycles, inspect find_cycles before deciding how to change relationships.

With a finite display limit, find_cycles streams one more cycle than the limit to detect truncation. Requesting all results enumerates and stores all simple cycles. maximum_cycle searches at most max_cycles candidates for the longest or greatest-weight simple cycle, defaulting to 10,000. search_exhausted=false means the result is only the best candidate examined, not a proven global optimum.

subgraph_extraction defaults to create_version=true and makes the extracted graph active. Pass false explicitly for explanatory previews. Later centrality, community, and training calls read the active graph, so saving a subgraph changes their input; record the new graph_version.

Structural link prediction needs no trained model. Jaccard measures shared neighbors relative to their union; Adamic–Adar and resource allocation discount high-degree common neighbors; preferential attachment multiplies endpoint degrees. Without two endpoints, the tool scores non-edge pairs and retains the best candidates. top_k bounds retained results, not total scoring work.

• NetworkX: definitions of k-core, k-truss, and k-corona↗

These five groups currently reject multigraphs. Ordinary list previews default to 20 and positive integer limits are capped at 200; the meaning of all depends on the method. All topological orders, antichains, colliders and v-structures retain a hard limit of 200. Read truncated, hard_limit and count_is_exact rather than treating preview length as a total count. The large-graph path has separate capability, budget and artifact constraints. This page documents source contracts, not execution of every algorithm and parameter combination on the current deployment.

#Metrics and output scope

Finite diameter and radius do not establish connectivity of the original directed graph; they may describe only its largest undirected component. Some metrics are undefined on empty graphs or graphs with no degree variation. global_metrics represents nonfinite results with defined=false and value=null. Degree assortativity also includes undefined_reason_code and undefined_reason for no edges or zero endpoint-degree variance. Undefined is neither zero nor evidence that the engine lacks the metric; other input or structural errors can still return success=false.

summary, preview, top_nodes, and truncated describe different levels of output. Global metrics may use the full input graph while lists display only part of it; bounded remote queries can restrict the input itself. Reports should distinguish computation scope from display scope.

The visualize_subgraph catalog defaults are max_nodes=800 and include_community=true. Engine fallback and edge limits are configurable with VISUALIZE_MAX_NODES and VISUALIZE_MAX_EDGES, defaulting to 800 and 2,000. Oversized inputs use deterministic overview selection combining highlights, node types, community representatives, high-degree nodes and connecting paths. Even requested highlights can be truncated; inspect overview.required_nodes_truncated. total_nodes/total_edges describe the original requested scope, while num_nodes/num_edges describe the displayed view. A view cannot establish absence of paths outside it; reports likewise require actual source_results and explicit computation and display scopes.