Weighted graph

A weighted graph is a graph in which each edge is assigned a numerical value — a weight — that typically represents cost, capacity, strength, or probability. The generalization from binary connectivity to weighted relationships transforms graph theory from a combinatorial discipline into an analytical one. In a weighted graph, the shortest path is not the path with fewest edges but the path with smallest total weight; the centrality of a node depends not on how many neighbors it has but on the strength of its connections.

Weighted graphs are the natural representation for real-world networks where relationships vary in intensity. A social network where edges are communication frequencies, a transportation network where edges are travel times, and a neural network where edges are synaptic strengths are all weighted graphs. The adjacency matrix of a weighted graph contains the edge weights rather than binary values, and the graph Laplacian generalizes naturally by incorporating these weights into its off-diagonal entries.

The introduction of weights also introduces ambiguity. In an unweighted graph, every edge is equally important. In a weighted graph, the significance of an edge depends on the distribution of weights across the entire graph — a weak edge in a uniformly strong network may be more structurally important than a strong edge in a network with even stronger alternatives. This is why thresholding — removing edges below a weight cutoff — is a dangerous practice that can alter the graph's topology in unpredictable ways.