Graphs are, in a reductive sense, nothing more than a collection of nodes and edges. This is, however, like saying that a symphony is just a collection of notes. Networks formed from identical numbers of edges and nodes can have starkly differing properties depending upon the patterning of edges in the network (as we will see shortly), and a cardinal virtue of graph theoretic approaches to networks is that they can not only describe network structures, but they can also interpret these structures to reveal properties of networks and their nodes. We have already encountered one such measure, the “modularity” of a graph, which indicated the extent of community structure in a network. We now consider another fundamental property of graphs, which is how efficiently their structures facilitate local and global communication (by communication, we simply mean the passing of something, like a packet of information, from node to node over the network). Numerous methods have been proposed to capture this property in graphs (e.g. the “efficiency” and “cost-efficiency” measures (Achard et al., 2006; Latora and Marchiori, 2001)), and we focus on some of the most well-known, the “small-world” measures (Watts and Strogatz, 1998).
