Hello Complex Networks!!!

This began as an excuse to knock the rust off my JavaScript while working through a graph-theory assignment, but it quickly turned into a small tour of why the networks we actually care about — the web, social graphs, the brain, the power grid — look almost nothing like the random graphs we tend to reach for first.

The plan was simple: grow a network one node at a time in the browser, draw it live, and watch its degree distribution — the histogram of how many connections each node has. That single curve turns out to say almost everything about a network’s character.

Drawing a living graph with vis.js

For the visualization I reached for vis.js, which makes an interactive, force-directed network almost embarrassingly easy: a DataSet of nodes, a DataSet of edges, and a Network bound to a container.

const nodes = new vis.DataSet();
const edges = new vis.DataSet();
const container = document.getElementById('mynetwork');
const network = new vis.Network(container, { nodes, edges }, {});

Because the DataSets are live, the picture re-renders on its own every time I add a node or an edge. So the only real question is the growth rule: when a new node joins, who does it connect to?

The naive rule: connect at random

The first instinct is to wire each new node to an existing one chosen uniformly at random.

let lastId = 0;
function addRandomNode() {
  const id = ++lastId;
  nodes.add({ id, label: String(id) });
  if (id > 1) {
    const target = 1 + Math.floor(Math.random() * (id - 1)); // any existing node
    edges.add({ from: id, to: target });
  }
}

This is essentially the Erdős–Rényi mental model: every node is equally likely to receive a connection. Grow it for a while and the degree distribution is sharply peaked around the mean — a bell-shaped (Poisson) curve. Every node is more or less average; there are no celebrities. It is tidy, and it is almost nothing like reality.

Why real networks aren’t random

Map the actual web, or who-follows-whom, or which airports connect to which, and you do not get a bell curve. You get a power law: the overwhelming majority of nodes have very few links, while a tiny handful — the hubs — carry an enormous number. Google, a superconnector airport, a celebrity account. These are scale-free networks, and the mechanism behind them is wonderfully intuitive.

Preferential attachment: the rich get richer

The insight of the Barabási–Albert model is that new nodes don’t choose uniformly — they prefer what is already popular. A new website links to sites that are already well-linked; a newcomer follows accounts that already have followers. Make the probability of connecting to a node proportional to its current degree, and hubs emerge on their own.

function addPreferentialNode() {
  const id = ++lastId;
  nodes.add({ id, label: String(id) });
  if (id === 1) return;

  // Each existing node appears in `stubs` once per edge it already has, so
  // drawing uniformly from stubs selects a target with probability
  // proportional to its degree -- the essence of preferential attachment.
  const stubs = [];
  edges.get().forEach(e => stubs.push(e.from, e.to));
  const target = stubs.length
    ? stubs[Math.floor(Math.random() * stubs.length)]
    : 1; // the very first edge has nothing to bias toward yet
  edges.add({ from: id, to: target });
}

That stubs array is the whole trick. A node that already owns ten edges appears ten times in it, so it is ten times as likely to win the next connection. Run this and the graph visibly sprouts a few dominant hubs while most nodes stay sparse — the signature of a scale-free network, falling straight out of one biased coin flip.

Reading the degree distribution

To see the structure rather than just admire it, I tally the degree of every node. Extracting that from the edge list is a two-step frequency count: first each node’s degree, then how many nodes share each degree.

function degreeDistribution() {
  const degree = {};
  edges.get().forEach(e => {
    degree[e.from] = (degree[e.from] || 0) + 1;
    degree[e.to]   = (degree[e.to]   || 0) + 1;
  });
  const counts = {};                       // degree k -> number of nodes with degree k
  Object.values(degree).forEach(k => { counts[k] = (counts[k] || 0) + 1; });
  return Object.entries(counts).map(([k, n]) => [Number(k), n]);
}

I plotted that with Flot, and here is the part worth internalizing: on ordinary linear axes a power law just looks like a cliff hugging both walls, and it tells you very little. Plot it on log–log axes and a genuine power law straightens into a line whose slope is the exponent γ. That straight line is the fingerprint of scale-free structure — the single most useful thing to check about any network you meet.

$.plot('#histogram', [degreeDistribution()], {
  xaxis: { transform: v => Math.log(v || 1) },  // log-log turns a power law
  yaxis: { transform: v => Math.log(v || 1) },  // into a straight line
});

Why the shape matters

The degree distribution is not merely aesthetic — it predicts how a network lives and dies. Scale-free networks are remarkably robust to random failure: knock out a random node and you almost certainly hit one of the many low-degree ones, and nothing much notices. But they are fragile to targeted attack: remove a few hubs and the whole thing shatters into disconnected islands. Erdős–Rényi graphs, having no hubs, degrade gracefully under either. The same curve that tells you a network has celebrities also tells you exactly where it is vulnerable — which is why “what does the degree distribution look like?” is the first question worth asking about any complex system.

The interactive sketch below is where all of this started — a network growing live in the browser. Add a few nodes and watch the structure assemble itself.

Full Screen Version