Trees: the simplest way to branch out
A network is a tree when it is connected and has no cycle, no path \(a\to b\to\cdots\to a\). Then it always has exactly \(L = N-1\) links for \(N\) nodes, and deleting any one link splits it into two pieces. Any node can serve as the root. Every other node sits in a layer, and the layer number is its shortest distance to the root; nodes with no children are the leaves.
In NetworkX: nx.is_tree(G) is True for paths and stars and False for cycles and complete networks.
Finding shortest paths: breadth-first search
NetworkX will find shortest paths for you, but what happens behind the scenes is breadth-first search. Starting from a source, visit all of its neighbors (distance 1), then all of their unvisited neighbors (distance 2), and so on, like a snowball rolling outward. Each layer is finished before the next one starts, so the first time a node is reached is along a shortest path. The links used to reach new nodes form a shortest-path tree rooted at the source.
The algorithm
- Put the source in the frontier (a first-in, first-out queue) with \(\ell(s,s) = 0\); every other distance is unknown.
- Take the next node \(i\) out of the frontier.
- For each neighbor \(j\) of \(i\) without a distance yet: set \(\ell_{sj} = \ell_{si} + 1\), add the link \(i\to j\) to the tree, and put \(j\) in the frontier.
- Repeat until the frontier is empty. Nodes still without a distance cannot be reached.
Frontier, next out first
Distance and the average path length
The distance \(\ell(i\to j)\) is the length of a shortest path from \(i\) to \(j\). In a directed network it need not equal \(\ell(j\to i)\), and some targets may not be reachable at all. Averaging over every ordered pair gives the average path length,
\[ \langle \ell\rangle = \frac{\sum_{i\neq j} \ell(i\to j)}{N(N-1)} , \]
which is finite only if every node can reach every other. In the example from the slides, \(\ell(1\to 2) = 1\), \(\ell(1\to 7) = 2\) and \(\ell(1\to 6) = 4\), but nobody can reach node 4.
\(\ell(i\to j)\), row \(i\) to column \(j\)
Large worlds and small worlds
On a 2D square lattice, distance is the Manhattan distance: you can only walk along the streets. Within distance \(\ell\) there are about \(\ell^2\) nodes, so \(N\propto\langle\ell\rangle^2\) and \(\langle\ell\rangle\propto N^{1/2}\). Any algebraic growth \(\langle\ell\rangle\propto N^\alpha\) with \(\alpha>0\) makes a large world. In a small world the average path length grows only like \(\log N\), a very, very slowly increasing function of \(N\). Grow each network below and watch.
How slow is “very, very slowly”?
Any power of \(N\), however small, eventually beats \(\log N\). The crossover can lie unimaginably far out, which is why a logarithm behaves like a constant for every network we will ever see.
Where the logarithm comes from
A very crude estimate: if each node has about \(\langle k\rangle\) neighbors, there are about \(\langle k\rangle^n\) nodes in layer \(n\) around any source, ignoring loops, overlapping neighbors and variations in degree. Adding up the layers out to the farthest one,
\[ N \sim \sum_{n=0}^{\ell_\text{max}} \langle k\rangle^n = \frac{\langle k\rangle^{\ell_\text{max}+1}-1}{\langle k\rangle-1} \sim \langle k\rangle^{\ell_\text{max}} \quad\Longrightarrow\quad \langle\ell\rangle \sim \ell_\text{max} \sim \log_{\langle k\rangle} N \propto \log N . \]
In a Cayley tree (Bethe lattice), where every node has exactly \(k\) neighbors, this is exact: layer \(n\) has \(k(k-1)^{n-1}\) nodes. Random links come close, because loops are rare. In the 2D lattice the loops cannot be ignored: your neighbors’ neighbors are mostly each other’s neighbors too, so layers grow only like \(4n\). The key to small-worldness is relatively rare loops and a lack of regularity, in other words randomness.
Nodes in each layer
Watts and Strogatz: a little randomness goes a long way
Start from a ring where each node links to its nearest neighbors: lots of local loops, long distances. Now rewire each link, with probability \(p\), to a random node. At \(p = 1\) the network is random: short distances, few loops. Watts and Strogatz (Nature, 1998) found that a tiny \(p\) is enough to collapse the path length while barely touching the clustering, the share of your friends who are friends with each other (defined in the next section). Real networks live in that window: both clustered and small.
Clustering: are my friends friends with each other?
The clustering coefficient of a node is the fraction of pairs of its neighbors that are linked to each other. With \(\tau(i)\) the number of triangles through \(i\), and at most \(\binom{k_i}{2}\) of them,
\[ C(i) = \frac{\tau(i)}{\tau_\text{max}(i)} = \frac{\tau(i)}{\binom{k_i}{2}} = \frac{2\,\tau(i)}{k_i(k_i-1)} , \]
defined only when \(k_i > 1\). Click the dashed lines to link or unlink pairs of \(i\)’s friends.
One number for a whole network: two different answers
The clustering coefficient of a network averages \(C(i)\) over the \(N_{k>1}\) nodes that have at least two neighbors. A related but different quantity, the transitivity, counts triangles against triads, the connected triples centered on a node:
\[ C = \frac{\sum_{i:\,k_i>1} C(i)}{N_{k>1}}, \qquad T = 3\,\frac{\text{number of triangles}}{\text{number of triads}}, \qquad \text{triads} = \sum_i \frac{k_i(k_i-1)}{2} = \frac{1}{2}\Big(\sum_i k_i^2 - \sum_i k_i\Big) . \]
\(C\) weights every node equally; \(T\) weights them by their number of triads, so hubs with sparsely linked friends pull it down. NetworkX’s average_clustering also counts nodes with \(k < 2\) as zero, which underestimates \(C\) as defined in the textbook. Real networks have \(C\) and \(T\) far above what random links would give, about \(\langle k\rangle/(N-1)\).