Global Communication Efficiency — GCE • intsegration

The average inverse shortest path length is a measure known as the global efficiency (see Latora and Marchiori, 2001). We implement the global communication efficiency (GCE) for weighted networks and propose a new normalisation method for the GCE. The global efficiency may be meaningfully computed on disconnected networks, as paths between disconnected nodes are defined to have infinite length and correspondingly zero efficiency. Assumption: Edge weights are non-negative and represent the appeal of links, hence we want shortest paths with heavy links.

Non-normalised GCE: $$E(g) = \frac{1}{N} \sum_{i \in V} \frac{\sum_{j \in V,i \neq j} d_{ij}}{N - 1},$$ where $N$ is the number of vertices of graph $g$ and $d_{ij}$ is the shortest-path distance between $i$ and $j$, computed by the Floyd-Warshall's algorithm with inverse edge weights as edge costs. See https://en.wikipedia.org/wiki/Floyd-Warshall_algorithm. Normalisation: the previous efficiency should be divided by the efficency of an ideal graph. $$E(g_{ideal}) = \frac{1}{N} \sum_{i \in V} \frac{\sum_{j \in V,i \neq j} l_{ij}}{N - 1}.$$ The normalised communication efficiency is then given by $$GCE(g)=\frac{E(g)}{E(g_{ideal})}$$

GCE(
  g,
  directed = FALSE,
  normalised = TRUE,
  weights = NULL,
  lengths = NULL,
  verbose = TRUE
)

Arguments

g	a network.
directed	logical, if the directed network has to be considered. If FALSE (default) the network is taken as undirected.
normalised	logical, default TRUE.
weights	edge weights, representing the appeal of each link. if weights is NULL (the default) and g has a weight edge attribute that will be passed to the igraph `distances` function, as $w_{ij}^{-1}$. If this is NA then no weights are used (even if the graph has a weight attribute). The normalisation of the GCE relises on the comparison with the efficiency of a $G_{ideal}$, characterised by the weighted adjacency matrix $G_{ideal} = \frac{W + \Phi}{2}$. See [2] for more details.
lengths	Euclidean length of the edge, i.e., Euclidean distance between its two end-points, which are assumed to be non-negative reals. If this is NULL (the default) and `g` has an edge attribute `length` that will be used. If this is NA then no lengths are used (even if the graph edges have a length attribute).
verbose	logical, default TRUE.

Value

A list

non_normalised - communication efficiency $E(G)$,
normalised - normalised communication efficiency, $GCE(G)$, or NULL if normalised is FALSE. If the network is topological (i.e. no flows) or if weights = NA then the normalised topological efficiency is equal to the non-normalised topological efficiency.
normalised_lengths - normalised communication efficiency w.r.t. edge lengths, i.e. $GCE^{Eucl}(G)$: shortest-paths are computed using the flows (as in the usual normalied version), but now the path total cost and total strength are, respectively, the sum of Euclidean distances (lengths) and the sum of the reciprocals of the lengths of edges over the paths. NULL if there are non lengths. If normalised = FALSE but lengths are provided, then the $GCE^{Eucl}(G)$ (that is normalised_lengths) will be computed anyway.

References

[1]: Latora, V. & Marchiori, M. (2001). Efficient Behavior of Small-World Networks. https://doi.org/10.1103/PhysRevLett.87.198701
[2]: Bertagnolli, G., Gallotti R. & De Domenico, M. (2020) Quantifying efficient information exchange in real flow networks. arxiv

Examples

library(intsegration)
library(igraph)
#> 
#> Attaching package: ‘igraph’
#> The following objects are masked from ‘package:stats’:
#> 
#>     decompose, spectrum
#> The following object is masked from ‘package:base’:
#> 
#>     union
karate <- make_graph("zachary")
GCE(karate, directed = F)
#> Unweighted graph, topological case.No Euclidean lengths/distances provided.Start computation of shortest-paths
#> Error in rcpp_floyd_flow(x): vector is too large