GCE: Global Communication Efficiency

In RadicalCommEcol/MultitrophicFun: Different functions for working with multitrophic communities

Global Communication Efficiency

Description

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.

Usage

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

Arguments

g	a network object from igraph.
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.

Details

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})}

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(igraph)
karate <- make_graph("zachary")
GCE(karate, directed = F)

RadicalCommEcol/MultitrophicFun documentation built on Oct. 13, 2023, 1:27 a.m.