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.
