Weighted Graph Analysis of Complex Networks

The computation of efficiency and cost can be generalised to weighted graphs. In this case, we require a weighting matrix D (same dimension, N × N, as the corresponding adjacency matrix A of the graph), whose d_ij elements represent additional information about the cost of the edges. Dijkstra's algorithm can be used to search the weighted edge matrix to find the shortest weighted path length l_i,j between each pair of nodes in the graph, i.e., the minimum value of the sum of weights over all possible paths between nodes i and j [13 ]. The efficiency of communication between nodes i and j is then measured by global, regional, and local efficiency of the weighted graph, simply derived from Equations 1–3 by substituting L_i,j with l_i,j. The cost of the weighted graph is defined by the sum of the weights between the connected nodes, K = ∑_i≠j∈Gd_i,j. As for unweighted graph analysis, efficiency and cost parameters can be normalised with respect to the maximum values observed when all the nodes of the graph are connected.
The main concern in modeling weighted networks is the choice of a weighting matrix. For a spatially embedded network like the brain it would generally be appropriate to use some measure of physical distance between nodes as a weighting factor. However, the length of axonal tracts between human brain regions is not yet well-known. An alternative weighting factor, more easily estimated, is a measure of the functional distance between connected regions, e.g., d_i,j = 1 − w_i,j, where w_i,j is the wavelet correlation coefficient for regions i and j. See Figure S2 for an analysis of functionally weighted networks that is directly comparable to the analysis of unweighted networks reported in Figure 4 on the basis of the same experimental data. It can be seen that the pattern of results for unweighted and functionally weighted networks is very similar in these data.