Graph

7 min read#networks#foundations

A set of nodes joined by edges — the minimal mathematical object for describing relationships of any kind.

Contents

Graph

A graph is the barest possible model of connection: a set of nodes (also called vertices) and a set of edges, each edge joining a pair of nodes. That is all. A graph carries no geometry, no distance, no embedding in space — only the relation these two are connected. Its power comes precisely from that austerity: anything you can phrase as "things and the links between them" is a graph.

Formally we write G = (V, E), where V is the set of vertices and E \subseteq V \times V the set of edges. The number of edges meeting a node is its degree. Two nodes joined by an edge are neighbors, and a sequence of edges leading from one node to another is a path.

Flavors of graph

The single picture splits into a small family of variants, chosen to match what you are modeling:

  • Undirected vs. directed. A friendship is mutual, so its edge has no arrow — an undirected graph. A hyperlink or a one-way street points one way, giving a directed graph (a digraph), where an edge from a to b need not imply one from b to a.
  • Unweighted vs. weighted. Sometimes an edge simply exists. Other times it carries a number — a distance, a cost, a capacity, a strength. A weighted graph attaches a value to each edge, and most of the interesting optimization problems (Dijkstra's Algorithm, Minimum Spanning Tree) live here.
  • Sparse vs. dense. A graph with n nodes can have up to \binom{n}{2} edges. Real networks are usually sparse — each node connects to only a handful of others — which is what makes algorithms that run in O(V+E) time so valuable.

A graph wants to lay itself out

A graph has no built-in shape, so to draw one we invent positions. A force-directed layout treats the graph as a physical system: every node is a charged particle that pushes all the others away, and every edge is a spring that pulls its two endpoints together. Release the system and it relaxes into a configuration where clusters spread out, connected nodes sit close, and the structure becomes legible. It is the same balance of repulsion and attraction that organizes a hanging mobile.

Drag any node below — the rest of the network will flex and re-settle around it.

A small graph finding its own shape. Nodes repel like charges; edges pull like springs; the whole thing relaxes to equilibrium. Click and drag any node to disturb it.

This same relaxation idea is how diagrams of Complex Systems — protein interactions, social circles, the internet — are drawn so that their hidden community structure becomes visible.

See also