A graph is a data structure consisting of nodes (or vertices) and edges between the nodes, $G = (V, E)$. Each edge in the graph is identified with the pair of nodes it connects, $(V_i, V_j)$. An adjacency matrix is often used to represent a graph, where each element $x_{ij}$ in the matrix represents the edge $(V_i, V_j)$.
1. Types of graphs
There are, of course, different types of graphs. Most simply speaking, graphs can be divided into directed and undirected graphs depending on whether the edges’s directions are defined or not. Sometimes, it may also be useful to know if a graph is acyclic, meaning that the graph does not contain any group of circularly connected nodes.
Alternatively, graphs can also be divided into simple graphs and multigraphs. The former type does not involve more than one edge between any pair of nodes, in contrast to the latter. A simple graph is also complete if every pair of nodes is connected by exactly one edge.
Finally, a graph can be unweighted or weighted depending on whether the edges are binary or have weights. The weights may be proportional to connection strength between the two nodes by the edge.
2. Basic concepts
As one may begin to notice, and not surprisingly, many jargons are used in graph theory. Let’s just cover some basic concepts in this section:
- adjacent nodes are connected by an edge
- degree of a node is the number of nodes connected to the node
- an isolated node has a degree of 0
- a pedant node has a degree of 1
- strength of a node is the sum of weights of its connected edges
- a path is a sequence of connected nodes linking node $i$ to node $j$, $P(i, j) = (v_0, v_1, …, v_n)$
3. Handshaking lemma
For an undirected graph, the degree sum formula states that $\sum_{v \in V} \mathop{deg} v = 2|E|$, i.e., the sum of degrees of all nodes is equal to twice the number of edges. This is simply because each edge is counted for the degree of nodes at both ends. This leads to the handshaking lemma (or theorem), which states that:
In every finite undirected graph, the number of vertices that touch an odd number of edges is even (Wikipedia)
Why? Since the sum of degree is even in an undirected graph, the sum of degree from vertices with odd degrees must be even. This is only possible if the number of vertices with odd degrees is even.
4. Centrality
There are many different centrality measures in graph theory and network analysis. The main idea is to characterise how important (or central) each node is. The definition of importance is, of course, dependent on the application where the graph need to be employed. Here, I will briefly discuss three common centrality measures.
Usually, the centrality values are used to identify a few important nodes or to rank nodes by their importance. However, a limitation of centrality-based ranking is that the centrality measures that are helpful in identifying important nodes may be meaningless for the other not-so-important nodes.
4.1. Degree centrality
The degree centrality is simply the degree of the node, $C_D(v) = \mathop{deg}(v)$. A node with a higher degree may be an information hub of the network, making it potentially more important. For a dense adjacency matrix, computing all nodes’ degree centrality takes $\Theta(V^2)$ time 1.
4.2. Betweenness centrality
The betweenness centrality is the frequency that a node is part of a shortest path, $C_B(v) = \sum_{s \ne v \ne t \in V} \frac{\sigma_{st}(v)}{\sigma_{st}}$. The same measure can be computed for edges. The idea is that shortest paths represent information flow in the actual network, e.g. social networks. This measure requires computing all the shortest paths in the graph, which can be a bottleneck taking $O(V^3)$ time.
It is common to rescale this centrality value with the total number of node pairs, which is $(N-1)(N-2)$ for directed graphs and $\frac{(N-1)(N-2)}{2}$ for undirected graphs. The resultant values can be further normalized to be in $[0, 1]$.
4.3. Eigenvector centrality
The eigenvector centrality is a self-referential measure, where a node become more important if it is connected to other important nodes. Using the adjacency matrix, the eigenvectors and eigenvectors are computed for $Ax = \lambda x$. The eigenvector corresponding to the largest eigenvalue is then used for extracting the centrality score. Essentially, $C_E(v) = A_v$.
4.4. Participation coefficient
The participation coefficient measures the connection diversity of a node, $PC(v) = 1 - \sum_{s}(\frac{K_{vs}}{K_v})^2$, where $K_v$ is the node $v$’s strength and $K_{vs}$ is its strength within the community $s$. This computation requires a community structure to be defined first, with each node belonging to a local community. A node has high participation coefficient if it is evenly connected to different communities.
5. Efficiency
The global efficiency of a network is the average inverse shortest path length, representing teh general ease of information flow in the network. On the other hand, the characteristic path length is the average shortest path length in the network, representing a lack of efficiency. It is also possible to compute local efficiency measures, which is simply the global efficiency in a node’s (immediate) neighbourhood excluding the node itself. The local efficiency can be considered a measure of a local network’s resistance to failure on a small scale, and is related to the clustering coefficient.
5.1. Clustering coefficient
The clustering coefficient measures the degree to which nodes tend to cluster together. It can be computed as the fraction of triangles around a node, or the fraction of the node’s neighbours that are neighbours of each other. For an undirected graph, based on adjacency matrix $A$, the coefficient is:
\[CC = \frac{\sum_{i,j,k} A_{ij} A_{jk} A_{ik}}{\sum_i k_i (k_i - 1)} \quad \text{where } k_i = \sum_j A_{ij}\]If the denominator is 0 (the node’s degree is 0 or 1), then $CC=0$.
-
The Big Theta ($\Theta$) notation means that the function is bound both above and below by the expression asymptotically, in contrast to the Big O ($O$) where the function is only bounded above by the expression. ↩