Network Structure and What the Measures Mean

A network is a set of nodes and the connections between them. That definition is almost empty, which is why it applies to so much. The substance is in the structure, and structure is described through a small set of measures, each answering a different question.

Degree distribution

The degree of a node is its number of connections; the distribution of degrees across all nodes is the first thing to look at. If it is concentrated around a mean, the network is roughly homogeneous and most nodes are interchangeable. If it is heavily skewed, a small number of nodes carry a disproportionate share of the connections, and almost every process on the network will be dominated by them.

The frequent mistake is jumping from "the distribution is skewed" to "the distribution is a power law" to "therefore preferential attachment generated it". None of those steps is automatic. Log-normal distributions look very similar over the ranges typically observed, several mechanisms produce heavy tails, and the shape of a distribution is weak evidence about its origin - the same identification problem described in validation and calibration.

Path length and the small-world property

Average shortest path length measures how many steps separate a typical pair of nodes. Social networks consistently show short paths - the small-world result - and short paths mean nothing in the network is structurally far away.

The important qualification is that short paths do not imply easy reach. A path exists mathematically; traversing it requires each intermediary to actually pass the thing along. Short paths mean information can cross the network quickly, not that it does.

Clustering

The clustering coefficient measures how often a node's contacts are connected to each other. Social networks cluster heavily, because people meet through shared contexts. High clustering means redundant paths: your contacts mostly know each other, so information reaching you arrives through several routes.

This redundancy has opposite effects depending on what is spreading. For simple contagion, redundancy is wasted - one exposure was enough. For complex contagion, where several independent confirmations are needed before adoption, redundancy is exactly what makes adoption possible. This is why clustering helps behaviour spread and does nothing for news, and it is developed in how opinions spread.

Centrality: four different questions

"Central" is not one concept, and the measures disagree with each other by design:

• Degree centrality counts connections. Answers: who has the most direct contacts?
• Betweenness centrality counts how often a node lies on shortest paths between others. Answers: who is a bottleneck? A node with few connections can have very high betweenness if it is the only bridge between two groups.
• Closeness centrality measures average distance to everyone else. Answers: who can reach the whole network fastest?
• Eigenvector centrality weights connections by the importance of who they connect to. Answers: who is connected to well-connected nodes?

Choosing among them requires knowing what flows through the network and how. Betweenness assumes things travel along shortest paths, which is true for a package and false for a rumour. Applying a measure whose flow assumption does not match the process is the most common error in applied network analysis.

Community structure

Most real networks divide into groups with dense internal connection and sparser links between them. Community detection algorithms find these groups, and they will find them whether or not they exist: run a detection algorithm on a random graph and it returns communities. Any partition needs to be tested against a null model before it is interpreted.

Communities also depend on resolution. The same network can be partitioned into a few large groups or many small ones, and neither is the correct answer. The right scale depends on the question, which should be settled before the algorithm runs rather than after.

What networks leave out

A static network is a snapshot of something that changes. Ties form and dissolve, and for fast processes the sequence of contacts matters more than the aggregate structure: a path that exists in the aggregated network may not exist in time order, because the second contact happened before the first. Aggregating a temporal network into a static one systematically overstates reachability. Similarly, treating all edges as equivalent discards weight and type, and a network of "who someone has ever messaged" describes something very different from a network of "who someone trusts". These limits matter most when the network is reconstructed from platform logs, which is the subject of digital traces and privacy.