Multiscale ways to talk about graphs
At the most fundamental level, graphs are just entities and connections between them. Yet, the network topology gives rise to emergent properties. For instance, how information flows through a social network is partly a function who posts the message and how they are connected to the rest of the network, with their immediate connections being likely more important. In this section, I review three levels at which networks operate: local, mesoscale and global. They refer, respectively, to properties of the nodes, properties of parts of the network and properties of the whole network.
In an undirected network, the degree of a vertex \(u\) (\(\deg u\)) refers to the number of edges that are incident on \(u\). In a directed network, this concept is split between indegree ([\(\deg^- u\)], the number of edges that have \(u\) as their destination) and outdegree ([\(\deg^+ u\)], number of edges that have \(u\) as their source). Weighted graphs extend this concept to weighted degree, in which \(\deg u = \sum_{i} w(e_{ui})\).
The (local) clustering coefficient of a vertex measures the probability that its neighbors are connected. It is computed as the ratio between number of triangles involving a vertex, and the number of triplets involving that same vertex.
Often, the clustering coefficient of a directed graph is computed without considering the direction of the edges.
The modularity measures how well a graph can be divided into modules. Given a partition of a graph into \(k\) modules, the modularity \(Q\) is computed as
\[Q = \sum_{i=1}^k (e_{ii} - {a_i^2})\]where \(e_{ii} = \frac {\| \{\{u, v\} \mid u \in V_i, v \in V_i, \{u, v\} \in E \} \|} {\|E\|}\),\(a*i = \frac {\| \{\{u, v\} \mid u \in V_i, \{u, v\} \in E \} \|} {\|E\|}\) and \(V_i\) is the set of vertices in module \(i\). \(e*{ii}\) is the fraction of edges within module \(i\) and \(a_i\) is the fraction of edges incident with one vertex in module \(i\). \(Q\) will be large when the fraction of edges within the module is much larger than expected by chance.
The within-module degree of a vertex is the module version of the degree. It is often normalized as a z-score; the z-score for node \(i\), mapped to module \(k\):
\[Z_i = \frac {\kappa_i - \bar \kappa_k} {\sigma_{\kappa_k}}\]where \(\kappa_i\) is within-module degree (the number of edges between \(i\) and other vertices in module \(k\)); \(\bar \kappa_k\) is the average within-module degree; and \(\sigma_{\kappa_k}\) is the standard deviation of the within module degrees.
The radius and the diameter measure how easy it is to traverse a graph. They both are quantities based on the maximum distance between any two vertices found in the graph. Specifically, the radius is the minimum maximum distance; the diameter is the maximum distance.
The global clustering coefficient of a graph is the ratio between closed and open triplets in that graph. Or, equivalently:
\[C = \frac {3 \times \text{triangles}} {\text{triplets}}\]Often, the clustering coefficient of a directed graph is computed without considering the direction of the edges.
Centrality assigns a score or a ranking to every vertex in the graph, which represents its importance in the network according to some metric. Degree and participation are examples of such metrics, but there are others.
We can clasify graphs into different types by using the global properties of their nodes.
Regular graphs are those in which every node has the same degree. They have a high average clustering coefficient and a large diameter.
Small world graphs have a high average clustering coefficient and a small diameter. They are called small world because, despite their size, the average distance between any two nodes is small. This is often summarized as “six degrees of separation”, the idea that any two people on Earth are connected by at most six social connections. This is because many real-world networks, like social networks, protein interaction networks, and neural networks, exhibit small-world properties.
Milgram et al. conducted experiments that were key to understand the topology of social graphs.
They gave letters to randomly chosen people from Nebraska and Kansas, each of which was to reach a target random person from Massachusetts. To that end, they could only give it to their friend or relative they thought was most likely to know the target. These, in turn, were meant to do the same; and so on, until eventually the letter would reach the target. The majority of letters never reached their target; but those who did, made it in 5 to 6 hops.
This ultimately lead to the postulation of the six degrees of separation, and the realization that social graphs are small world graphs.