2.6 Order and Size

As graphs are really just representations of real world relationships, they can be as varied as those relationships. As such, language has developed to explain different facets of a graph.

The order of a graph is the number of nodes in the graph. More accurately, keeping in mind that the graph is really a set of a set of nodes and edges, the order is the cardinality of V(N). Cardinality is simply a mathematical term for how many components/elements there are in a set. Thus, the graph in Figure 1.3 has an order of nine, while Figure 1.4 has an order of seven. The variable n represents the number of nodes in the graph.

Likewise, the cardinality of the set E(M) is the number of edges in the graph. The cardinality of the set E(M) in Figure 1.3 is 16, while in Figure 1.4 it is 11. If you say the cardinality of the graph in Figure 1.3 is 16, we can all understand that you are referring to the number of edges, as you would use the term order if you were talking about the number of nodes. Likewise, in future notation, the number of edges in the graph will be represented as variable m. We use order to refer to the cardinality of the set V(N), while just saying cardinality to refer to the cardinality of set E(M).

Finally, the size of the graph is defined as how many edges there could possibly be if everyone had a relationship with everyone else in the network. It is the maximum possible number of ties, and is calculated as [n(n-1)]/2 for an undirected network, and [n(n-1)] for a directed network.