Weighted Graph

A weighted graph is a graph in which each edge carries a numerical value — a weight — representing the strength, cost, capacity, or intensity of the relationship between the connected nodes. The weights transform the graph from a topological structure into a metric space, enabling analyses that depend not merely on whether two nodes are connected but on how strongly or at what cost.

In network analysis, edge weights are typically interpreted as interaction frequency, tie strength, or probability of influence. In game-theoretic networks, weights may represent payoffs or trust levels. In transportation and infrastructure networks, weights are literal costs — distance, time, or energy. The mathematical treatment is uniform: shortest-path algorithms like Dijkstra's operate on weights regardless of their interpretation, and spectral methods like the graph Laplacian generalize naturally to the weighted case.

The conceptual risk is that weights are not always comparable across edges. A weight of 5 in one relationship may not mean the same thing as a weight of 5 in another, yet most weighted-graph algorithms assume additive comparability. This is a genuine limitation: the mathematics of weighted graphs assumes a single numerical type, while real relational systems often involve qualitatively distinct dimensions of strength that cannot be reduced to a scalar without loss of structure.

The weighted graph is network theory's most useful and most abused formalism: useful because it adds expressive power, abused because every weighted edge looks the same to the algorithm even when the weights mean different things to the system.

Multi-Dimensional Weights and the Comparability Problem

The limitation the article identifies — that weights may not be comparable across edges — is not merely a measurement problem. It is a structural problem that emerges whenever a network carries multiple qualitatively distinct relationships. A social network may simultaneously encode trust, frequency of interaction, emotional intensity, and information flow. Each dimension has its own scale, dynamics, and semantics. Reducing them to a single scalar weight discards the very structure that makes the network interesting.

Multi-dimensional weighted graphs — sometimes called multiplex or multi-layer networks — address this by assigning a vector of weights to each edge rather than a scalar. But this introduces its own difficulties. Shortest-path algorithms assume a total ordering on edge costs; vectors do not provide one unless an artificial aggregation function is imposed. The choice of aggregation — weighted sum, max-min, Pareto dominance — is not mathematically neutral. It encodes assumptions about how the dimensions trade off, and those assumptions are often exactly what the network analysis is supposed to discover rather than presuppose.

The deeper issue is that multi-dimensional weights reveal a mismatch between the formalism of graph theory and the phenomenology of real relationships. Graph theory treats edges as atomic; real relationships are composite. A friendship is not a single variable but a dynamic equilibrium of reciprocity, disclosure, obligation, and affect. When we represent it as a single weight, we are not simplifying for tractability. We are making a theoretical commitment — often an unconscious one — that the relationship has a single underlying magnitude. There is no reason to believe this is true.

The weighted graph is a seductive formalism because it appears to add realism to network analysis. But realism is not the same as validity. A model that includes more variables is not necessarily a better model; it may simply encode more assumptions. The multi-dimensional weight problem reveals that network theory's greatest weakness is not mathematical but ontological: it does not know what an edge is. Until we develop a theory of relational structure that can distinguish between 'connected' and 'connected in what way, under what conditions, with what history,' weighted graphs will remain elegant fictions — powerful for computation, impoverished for understanding.