Brief Primer on Graphs

Throughout these web pages, networks are represented as graphs. Here, I present a brief explantion of graphs and some associated terminology.

While many people may imagine something along the lines of the image on the left below when they hear the word “graph”, mathematicians envision something similar to the image to the right. In mathematics, the word graph has a particular definition.

A graph consist of two elements: nodes and edges.

Nodes are usually represented by circles (or ovals, or some other shape). In a functional network, these nodes would represent the variables we are measuring. Nodes are also known as vertices.Edges are represented by lines, and each edge connects two nodes. In a functional network, these edges would represent functional interactions between the variables. Edges may be directed—in which case they are drawn with an arrowhead—orundirected—in which case they are drawn plain. When all the edges in a graph are directed or all are undirected, the graph is known as a directed graph or undirected graph, respectively. Edges are also known as arcs or links.

If all nodes in a graph are connected to all other nodes, the graph is known as the full graph for those nodes; if there are no edges at all, it is known as the empty graph.

In a directed graph, there is some terminology that is useful to know. Take the graph below as an example. Concentrating on the black and white node, we can identify other nodes based on their relationships to it. The light blue node is its parent, and the two dark green nodes are its children. This familial analogy can be taken further to identify nodes. The orange node is its grandparent, the light green node its sibling, and the yellow node could be called an aunt or uncle. All nodes that be reached by tracing arrows forward from our node of interest are called its descendants (here, the dark green and dark blue nodes), and all nodes that can be reached by tracing arrows backwards are called its ancestors (here, the light blue and orange nodes).