Nothing.
Or let’s be precise: not much. Both are things (nodes, vertices) connected by other things (links, edges) and any distinction is pretty much nothing but tradition.
My PhD dissertation has a network science part. When I started writing about Erdős-Rényi graphs in this part I realized I had to clear up the relationship between the networks and graphs. After some research I tentatively wrote “Networks are essentially graphs”. Unfortunately, this statement did not resound well with one of my opponents, so I had to dig deeper.
What is a graph?
A graph is the thing math people like to talk about, which makes the question easy, since they like rigorous definitions. Based on Bondy and Murty, 2008, this is it (bear with me):
A graph $G$ is an ordered pair $(V (G), E(G))$ consisting of a set $V (G)$ of vertices and a set $E(G)$, disjoint from $V (G)$, of edges, together with an incidence function $\Psi_G$ that associates with each edge of $G$ an unordered pair of (not necessarily distinct) vertices of $G$.
Source: wikipedia
What we need to remember here, is that nothing is said about the contents of the sets. We can put any entity in them. Anything can be an edge and anything can be a vertex, we just have to put them in the right bag.
What is a network?
A network is the thing non-math people talk about, making the question trickier. You obviously know what a network is. When I say that you and I are friends on Facebook, you understand that we are part of a network and the friendship is a connection, a link between us. The IT guy knows he’s connecting to a network when he plugs in the internet cable. The sociologist knows she’s mapping a network when she checks who talks with whom. The molecular biologist also knows that his proteins have interaction networks. And since everybody knows, but knows from utterly different perspectives, it gets a little murky.
What they all agree on is that you need to define nodes (you and me) and links between the nodes (our Facebook friendship). It sounds familiar, right? Like putting some things in one bag, and putting some other things in some other bag, and saying that the stuff in one bag can connect the stuff in the other bag. Very much like a graph.
Source: ccPixs.com
Sooo, what now?
Now, we call on fellow Hungarian Albert-László Barabási, one of the most famous network scientist and his recent textbook.
In the scientific literature the terms network and graph are used interchangeably:
| Network Science | Graph Theory |
|---|---|
| Network | Graph |
| Node | Vertex |
| Link | Edge |
Yet, there is a subtle distinction between the two terminologies: the {network, node, link} combination often refers to real systems: The WWW is a network of web documents linked by URLs; society is a network of individuals linked by family, friendship or professional ties; the metabolic network is the sum of all chemical reactions that take place in a cell. In contrast, we use the terms {graph, vertex, edge} when we discuss the mathematical representation of these networks: We talk about the web graph, the social graph (a term made popular by Facebook), or the metabolic graph. Yet, this distinction is rarely made, so these two terminologies are often synonyms of each other.
And actually, this sounds okay (he is a main network dude after all!). But I have a question: is this distinction real?
The mathematical graph can hold any object, as long as it’s placed in the appropriate bag. To rephrase Barabási’s argument, the representation (the graph) of the network is when you take the elements of this network and place them in the appropriate bags. But that would mean the links and nodes of a network exist on their own, without human definitions. But they don’t really. Take for example a friendship network. On Facebook, this is very well defined: our profiles are the nodes and confirmed friendships the link. But if we step out of Facebook how is our friendship network defined? When do we become friends? Are you a friend or an acquaintance? In the real world these things are not clear cut. To actually have a network, you must define who or what is a node and what is a link between them. You must put things in bags. You must define a graph. As soon as you can talk about nodes and links of a network you have a graph.
The only distinction I see between the two is social in nature: when we model a real, existing system as a graph, we tend to call it a network, and when we talk about abstract entities - entities that cannot be mapped to existing, real world phenomena - we talk about graphs. So, what’s the difference between a network and a graph?: not much.