The application of graph theoretical analysis to complex networks in the brain

Introduction

Traditionally, neuroscientists correlate ‘focal’ brain lesions, for instance brain tumors, with ‘focal’ clinical deficits. This approach gave important insights into the localization of brain functions; a classical example is the identification of the motor speech center in the lower left frontal cortex by the French neurologist Paul Broca at the end of the 19th century. Particularly during the last decades of the 20th century, this essentially reductionistic program led to significant progress in neuroscience in terms of molecular and genetic mechanisms . Despite the impressive increase of knowledge in neuroscience, however, progress in true understanding of higher level brain processes has been disappointing. Evidence has accumulated that functional networks throughout the brain are necessary, particularly for higher cognitive functions such as memory, planning, and abstract reasoning. It is more and more acknowledged that the brain should be conceived as a complex network of dynamical systems, consisting of numerous functional interactions between closely related as well as more remote brain areas (Varela et al., 2001).

Evaluation of the strength and temporal and spatial patterns of interactions in the brain and the characteristics of the underlying functional and anatomical networks may contribute substantially to the understanding of brain function and dysfunction. A major advantage of this approach is that a lot can be learned from other fields of science, particularly the social sciences, that are also devoted to the study of complex systems. In the last decade of the 20th century, considerable progress has been made in the study of complex systems consisting of large numbers of weakly interacting elements. The modern theory of networks, which is derived from graph theory, has proven to be particularly valuable for this purpose (Amaral and Ottino, 2004; Boccaletti et al., 2006).

Historical background

The modern theory of networks has its roots both in mathematics and sociology. In 1736 the mathematician Leonard Euler solved the problem of ‘the bridges of Konigsberg’. This problem involved the question whether it was possible to make a walk crossing exactly one time each of the seven bridges connecting the two islands in the river Pregel and its shores. Euler proved that this is not possible by representing the problem as an abstract network: a ‘graph’. This is often considered as the first proof in graph theory. Since then, graph theory has become an important field within mathematics, and the only available tool to handle network properties theoretically.

An important step forward occurred when ‘random’ graphs were discovered (Solomonov and Rapoport, 1951; Erdos and Renyi, 1960). In random graphs, connections between the network nodes are present with a fixed and equal likelihood. Many important theories have been proven for random graphs. In particular it has been shown that properties of the graphs often undergo a sudden transition (‘phase transition’) as a function of increasing likelihood that edges are present. However, despite the success of random graph theory, most real-world networks, particularly those found in social or biological systems, have properties that cannot be explained very well by classic random graphs. These properties include the high clustering and power law degree distributions. One empirically observed phenomenon in many real networks is the fact that the ‘distances’ in sparsely and mainly locally connected networks are often much smaller than expected theoretically. This phenomenon was probably first observed by the Hungarian writer Frigyes Karinthy in a short story called ‘Chains’. In this story he speculates that in the modern world the distance between any two persons is unlikely to be more than five persons, a phenomenon later studied and described in more detail by Stanley Milgram, and referred to as the ‘small world phenomenon’, or ‘six degrees of separation’ (Milgram, 1967).

Recent advances

The publication of a landmark paper in 1998 by Watts and Strogatz (Watts and Strogatz, 1998) provided a simple and elegant way of modeling small world networks. These authors proposed a very simple model of a one-dimensional network. Initially each node (‘vertex’) in the network is only connected to its ‘k’ nearest neighbors (k is called the degree of the network), representing a so-called ‘regular’ network. Next, with likelihood ‘p’, connections (‘edges’) are chosen at random and connected to another vertex, also chosen randomly. With increasing p, more and more edges become randomly re-connected and finally, for p = 1, the network is completely random (Fig. 1). Thus, this simple model allows the investigation of the whole range from regular to random networks, including an intermediate range.

The intermediate range proved to be crucial to the solution of the small world phenomenon. In order to show this, the authors introduced two measures: the clustering coeffi- cient ‘C’, which is the likelihood that neighbors of a vertex will also be connected, and the path length ‘L’ which is the average of the shortest distance between pairs of vertices counted in number of edges. Watts and Strogatz showed that regular networks have a high C but also a very high L. In contrast, random networks have a low C and a low L. So, neither regular nor random networks explain the small world phenomenon. However, when p is only slightly higher than 0 (with very few edges randomly rewired) the path length L drops sharply, while C hardly changes (Fig. 2). Thus networks with a small fraction of randomly rewired connections combine both high clustering and a small path length, and this is exactly the small world phenomenon to be explained. The authors demonstrated the existence of such small world networks in the nervous system of Caenorhabditis elegans, a social network of actors, and the network of power plants in the United States. Furthermore, they showed that a small world architecture might facilitate the spread of infection or information in networks (Watts and Strogatz, 1998).

A second major discovery was presented in 1999 by Baraba´si and Albert (Barabasi and Albert, 1999). They proposed a model for the growth of a network where the likelihood that newly added edges connect to a vertex depends upon the degree of this vertex. Thus, vertices that have a high degree (large number of edges) are more likely

to get even more edges. This is the network equivalent of ‘the rich getting richer’. Networks generated in this way are characterized by a degree distribution which can be described by a power law:

 Networks with a power law degree distribution are called ‘scale free’. It has been shown that many social and technological networks, such as for instance collaborative networks of scientists, the World Wide Web, and networks of airports, are likely to be scale free (Newman, 2003).

Basics of modern network theory

The discovery of small world networks and scale free networks set off a large body of theoretical and experimental research, which has led to increasing knowledge on various aspects of network properties in the last decade. Before we move on to the application of network theories to experimental neural networks, and healthy and diseased brain, we will provide some basic knowledge on several aspects of network properties. As mentioned before, more detailed mathematical descriptions can be found in Albert and Baraba´si (Albert and Baraba´si, 2002) and Stam and Reijneveld (Stam and Reijneveld, 2007).

Core measures

The degree distribution, clustering coefficient, and path length are the core measures of graphs. The degree distribution can be described as the likelihood p(k) that a randomly chosen vertex will have degree k. The clustering coefficient C is an index of local structure. It is the likelihood that neighbors of a vertex will also be connected to each other, and have been interpreted as a measure of resilience to random error (if a vertex is lost, its neighbours remain connected). The path length L is a global characteristic; it indicates how well integrated a graph is, and how easy it is to transport information or other entities in the network (Fig. 3). On the basis of the abovementioned three measures, four different types of graphs can be distinguished: (i) regular or ordered; (ii) small world; (iii) random (see Fig. 1); (iv) scale free. We should stress that neither regular, small  world, nor random networks are scale free. Scale free networks can have very small path lengths of the order of lnln(N), but the clustering coefficient may also be smaller than that of small world networks (Cohen and Havlin, 2003).

References

1.Achard S, Bullmore E. Efficiency and cost of economical brain functional networks. PLoS Comput Biol 2007;3:e17.

2.Achard S, Salvador R, Whitcher B, Suckling J, Bullmore E. A resilient, low-frequency, small-world human brain functional network with highly connected association cortical hubs. J Neurosci 2006;26:63–72.

3.Aertsen AM, Gerstein GL, Habib MK, Palm G. Dynamics of neuronal firing correlation: modulation of ‘‘effective connectivity. J Neurophysiol 1989;61:900–17.

4.Albert R, Baraba´si AL. Statistical mechanics of complex networks. Rev Mod Phys 2002;74:47–97.

5.Amaral LAN, Ottino JM. Complex networks; augmenting the framework for the study of complex systems. Eur Phys J B 2004;38:147–62.

6.Artzy-Randrup Y, Fleishman SJ, Ben Tal N, Stone L. Comment on Network motifs: simple building blocks of complex networks’’ and  Superfamilies of evolved and designed networks. Science 2004;305:1107.

7.Astolfi L, De Vico Fallani F, Cincotti F, Mattia D, Marciani MG, Bufalari S, et al. Imaging functional brain connectivity patterns from high-resolution EEG and fMRI via graph theory. Psychophysiology 2007;44:10.1111.