Connected Brains: introduction to graph theory

The Web Connected Brains

Networks and graphs: a connected world

We live in a connected world. All sorts of complex systems we encounter in nature, ranging from interacting molecules, genes to neurons, humans, and social systems can be viewed as networks. Networks are systems of interconnected and interacting elements or components. The mathematical language that describes and quantifies networks is called graph theory. Graph theory is in fact a relatively old branch of mathematics. It started in 1736 when Leonhard Euler solved the problem of the seven bridges of Konigsberg. Since then graph theory has developed enormously, especially after the introduction of random, small-world and scale-free network models. A basic understanding of the concepts, measures and tools of graph theory is necessary to appreciate how it can be applied to the brain. Useful information can be found in several review papers by Bassett and Bullmore (2006), Bassett and Bullmore (2009), Bullmore and Sporns (2009), Reijneveld et al. (2007), Stam (2010), Stam and Reijneveld (2007), van den Heuvel and Hulshoff Pol (2010), Kaiser (2011), Bassett and Gazzaniga (2011). There are also a number of excellent introductory and more advanced books on the topic. Here we provide a brief synopsis of the main concepts of graph theory.

What is a graph?

A graph is a mathematical representation of a network. A graph, usually indicated by the letter G, consists of a set of nodes or vertices (V) and a set of connections, links or edges (E) between these nodes: G(V,E). Two vertices are called neighbors if they are connected by an edge. In an unweighted or binary network edges are absent (0) or present (1); in a weighted network a weight w can be assigned to each edge. The weight can represent the strength of the connection, or some physical distance between the two connected vertices. Edges connecting vertices can be undirected or directed. Directed edges represent the fact that one vertex exerts some influence on its neighbor but not the other way around. A graph can also be represented by a square matrix where the number of rows and columns is equal to the number of vertices. This matrix is called the adjacency matrix of the graph and is often referred to by a capital A. In an undirected graph the matrix A is symmetrical; in a directed graph A does not have to be symmetrical. In an unweighted graph the cells of A have a value of 0 if no edge exists between the two vertices and a value of 1 if two vertices are connected by and edge. In a weighted graph a weight can be assigned to each edge. The size of a graph is equal to the number of vertices of the graph. A graph is connected if any vertex can be reached from any other vertex. In a complete graph all possible edges exist.

Graph measures: simple and complex

A graph G consisting of a set of vertices V and a set of edges E can be characterized by several measures, some relatively simple, others quite complex. Here we describe measures for unweighted networks. For most of these measures weighted versions have now been described as well.

Degree

One of the most important and elementary measures is the degree, often indicated by k. The degree of a vertex is the number of connections or edges it has. The probability that a randomly chosen vertex will have degree k is given by the degree distribution, indicated by P(k). The form of the degree distribution provides important information about the structure of the network. As described below, different types of graphs have their own characteristic degree distribution.

Clustering coefficient

The clustering coefficient of a vertex is the probability that the neighors of this vertex (all other vertices to which it is connected by an edge) are also connected to each other. The clustering coefficient of a vertex ranges between 0 and 1. The average clustering coefficient C of the whole network is the average of the clustering coefficients of all individual vertices. The clustering coefficient is considered to be a measure of the local connectivity or “cliqueness” of a graph. High clustering is associated with robustness of a network, that is resilience against random network damage.

Motifs and modules

The clustering coefficient is a special case of a more general graph property referred to as motifs. The clustering coefficient depends upon the presence of the triangle motif, consisting of three vertices fully connected by edges. Other more complex motifs exists as well, and their presence in graphs can be quantified. Subgraphs that consist of sets of vertices that are more strongly connected to each other than to the rest of the network are called modules. Identification of modules within complex networks is important, since modules often correspond to different functional aspects of the networks, and modules may also be important for the way normal and abnormal activity can spread through the network. It is also possible to define modules within modules. Networks with such a structure are said to have a hierarchical modularity. The concept of a module is a statistical one. Different definitions of modularity exist, the most well known being the modularity as defined by Newman. Alternatively, modularity can also be defined in terms of the eigenvalues and eigenvectors of the graphs matrix. Please note that the clustering coefficient, motifs and modules are descriptions of network structure at increasingly larger scales.

Pathlength and efficiency

Whereas clustering reflects local network structure, the shortest pathlength reflects the level of global integration in the network. A shortest path between two nodes A and B is the path between A and B with the smallest number of edges. The average shortest path L of a network is the average of all shortest paths between all pairs of vertices. The diameter of a graph is the longest of all shortest paths. Related to the idea of the average shortest path is that of global efficiency, which is the inverse of the average shortest path. The local efficiency of a particular vertex is the inverse of the average shortest path connecting all neighbors of that vertex.

Assortativity

Related to the notion of degree is the concept of mixing or assortativity. If vertices with a high degree tend to be connected to other vertices with a high degree, and vertices with a low degree to other low degree vertices, the graph is said to be assortative. An assortative graph has a positive degree correlation. In a disassortative graph, the degree correlation is negative, and high degree vertices tend to connect to low degree vertices and vice versa.

Centrality and hubs

Another important concept related to that of node degree is centrality. Centrality refers to the relative importance of a node or vertex within the network. Node degree is in fact one, relatively simple measure of centrality. A more sophisticated measure of centrality is betweenness. The betweenness centrality of a particular vertex is the fraction of shortest paths in the network that pass through this vertex. In a similar way, betweenness centrality can also be defined for edges (edge centrality). Another concept of centrality is based upon graph spectral analysis. Eigenvector centrality of a vertex is the value of the vector component, where the vector is vector that corresponds to the largest eigenvalue (spectral radius) of the adjacency matrix. If the notion of hub centrality is combined with the definition of modules it becomes possible to classify hubs. Hubs that are mainly connected to other vertices in the same module are referred to as provincial hubs; hubs that are mainly connected to vertices in other modules are called connector hubs. Provincial and connector hubs may play different functional roles within a network.

Graph spectral analysis

Graph spectral analysis is an interesting alternative way to characterize the adjacency matrix of a graph and its related Laplacian matrix. The Laplacian matrix contains the node degree as diagonal elements, and -1 for all cells corresponding to existing edges and 0 for cells corresponding to absent edges. If the adjacency and Laplacian matrix are symmetrical, and eigenvalue / eigenvector analysis can be performed, resulting in a series of eigenvalues and corresponding eigenvectors. It is assumed that the series of eigenvalues and eigenvectors represent all information present in the graph. Some graph spectral measures have special significance. The largest eigenvalue of the adjacency matrix is called the spectral radius and is inversely related to the synchronization threshold of dynamical processes on the graph. In addition, the values of its corresponding vector are a measure of centrality. The spectral gap (the difference between the largest and the second largest eigenvalue) provides information on how rapid the synchronous state is reached. The second smallest eigenvalue of the Laplacian matrix is called the algebraic connectivity. It is a measure of network robustness. If the algebraic connectivity is 0, the network consists of at least two disconnected components. The ratio of the largest and the second smallest eigenvalues of the Laplacian matrix is a measure of the stability of the synchronous state of a dynamical process on the network. The information contained in graph spectral analysis can also be used to identify modules within the network.

Models of complex networks

Models are extremely important in modern network theory. It can be argued that the discovery of models for very large networks with a mixture of randomness and order lies at the heart of the transition from conventional graph theory to the modern science of networks. Here we describe three prototype models that illustrate many of the key principles.

Random graphs

The oldest model of complex networks is that of random graphs as introduced by Rapoport and analyzed in detail by Erdos and Renyi. In a random graph G(V,E) edges between any pair of vertices exist with a probability p. The properties of the random graph have been studies extensively and many important mathematical results have been obtained. For instance, if p is increased from 0 to 1, the size of the largest connected component in the graph will undergo a phase transition at p=0.5. Random graphs have a low clustering coefficient, a small average shortest path length, no assortativity, a narrow degree distribution and not real hubs. While random graphs can explain some properties of real complex networks, notably the short distances between any two nodes, they fail in other respects. In particular, random graphs cannot explain the ubiquitous presence of clustering, modularity and hubs in real networks. Some of these problems were solved by the introduction of more sophisticated models at the end of the nineties in the last century.

Small-world networks

Watts and Strogatz (1998) considered a network on a ring, where each vertex is connected to k neighbors, k/2 in the clockwise direction, and k/2 counter clockwise. This is an ordered, lattice-like network. It has a high clustering coefficient, a long average shortest path length, no modularity or assortativity, a symmetric degree distribution, and no hubs. Next, with a probability p, edges are disconnected and attached to a randomly chosen other vertex. For p = 1 all edges are reconnected, and a random network is obtained, with all corresponding properties such as low clustering and short path lengths. The interesting region is for intermediate values of p. Even for small but non zero values of p, with only a small fraction of rewired edges, the path length already drops to very low values, while the clustering coefficient still maintains its original high values. This type of network, that combines high clustering with short pathlengths, is called a small-world network. Despite its apparent simplicity it is in fact a very powerful model of many real networks that often display the same combination of high clustering and short pathlengths. However, the Watts and Strogatz (WS) model fails to explain other important properties of natural networks such as modularity and broad degree distributions with hub like nodes. This last problem was solved in another model.

Scale-free networks

Barabasi and Albert proposed a model of a growing network. At each iteration, a new vertex is added, and it is connected to existing vertices with a probability that depends upon the degree of that node. As a consequence, nodes with a high degree are more likely to receive more connections, increasing their degree even further. This is an example of positive feedback or preferential attachment. The most interesting feature of the model is the shape of its degree distribution. After a sufficient number of iterations the degree distribution becomes a power law: P(k) = kgamma, where gamma = 3. This power law distribution reflects the presence of large number of highly connected nodes or hubs. Networks with a power law degree distribution are referred to as scale-free (SF). In contrast to WS networks, scale-free networks can explain the presence of hubs in networks, and suggest a growth scenario that gives rise to these hubs. For these reasons SF models have become very important in modern network research. However, even SF models have their limitations: they do not explain clustering very well, they are not assortative, and have no real modules.

Graph theory: a language for networks

In summary, graph theory gives us a language for networks. It allows us to define networks exactly and to quantify network properties at all different levels. This quantification is likely to improve further since new graph measures are described regularly. The real challenge of modern network theory is to come up with models that combine mathematical elegance with explanatory power. The ER, WS and SF models each constitute major steps forward in this respect. However, as we have indicated, none of these models solves all problems. We need new models, that explain how networks can emerge, and how high clustering, short paths, modules and hubs can arise with a minimum number of realistic assumptions. In addition, such models should explain the nature of dynamical processes taking place on the networks, as well as the circular causality between network topology and network dynamics. These are the challenges of modern network theory.

For comments and suggestions: send an e-mail

copyright C.J.Stam
Contact information: Department of Clinical Neurophysiology VU University Medical Center
Postal address: De Boelelaan 1118 Postal code: 1081 HV Amsterdam The Netherlands
P.O Box: 7057 Postal code: 1007 MB Amsterdam The Netherlands
Phone: 020 4440727 Fax: 020 4444816