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—or undirected—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).
A directed graph is considered to have a cycle if you can trace a path from a node and return to that same node. One often hears of a DAG (directed acyclic graph), which indicates that the graph has no cycles. In a DAG, ancestors and descendents are well defined, meaning they are specific non-overlapping sets of nodes—for a node in a cycle, it is its own ancestor and descendant! (This is because it can be reached both by tracing the edges forward and backward.)
Finally, one last piece of terminology that will be usefull is the concept of degree of a node. A node's degree is the number of edges connecting to it. In a direct graph, we can also talk of in-degree, the number of edges terminating on a node, and out-degree, the number of edges starting at that node. For example, in the undirected graph to the left below, the black and white node has degree 4. In the directed graph to the right, the black and white node has an in-degree of 1 and an out-degree of 2.
