Cost in a Graph

Cost in a Graph

Represents the total length of the network measured in real transport distances where aij is the presence (1) or absence (0) of a link between i and j and lij the length of the link. This measure can also be calculated based on two other dimensions of the network: the Minimum Spanning Tree (MST) and the Greedy Triangulation (GT). The MST represents the shortest and/or lowest cost subtree of the network; it can be obtained by applying, among other shortest path algorithms, the Kruskal algorithm, which allows finding the lowest cost route connecting all nodes in the network. The GT refers to the maximal connected planar graph keeping the same number of nodes than in the original network but adding all possible links without breaking its planarity. Such operations take into account both the topology and the geography of the network, while comparing the latter with its optimal configurations. More efficient networks have relative costs near to 1, while less efficient networks are closer to 0.

The Kruskal algorithm extracts the optimal cost route (B) from the original network (A). It is defined by one single line joining all nodes at minimum cost (Minimum Spanning Tree). The Greedy Triangulation (GT) adds missing links between all nodes so as to make it complete (maximal) without breaking its planarity (C). Values of 10 at each newly created link were attributed artificially due to the absence of unit but distance would in reality be less evenly distributed, for instance kilometers or hours/days. In its current form, the network (A) is more efficient in terms of weight (CostRel = 0.642) than in terms of links (CostRel = 0.389) with reference to the optimal situations B and C.