Acknowledgements
Mrs Alexandra Linger is thanked for secretarial assistance. Two anonymous reviewers are thanked for comments on an earlier version of this paper.
EEG and MEG (magnetoencephalography) are widely used to study functional connectivity between different brain regions. We address the question whether such connectivity patterns display an optimal organization for information processing. MEG recordings of five healthy human subjects were converted to sparsely connected graphs (N=126; k=15) by applying a suitable threshold to the N∗N matrix of synchronization strengths. For intermediate frequencies (8–30 Hz) the synchronization patterns were similar to those of an ordered graph with a consistent drop of synchronization strength as a function of distance. For low (<8 Hz) and high (>30 Hz) frequency bands the synchronization patterns displayed the features of a so-called ‘small-world’ network. This might reflect an optimal organization pattern for information processing, connecting any two brain area by only a small number of intermediate steps.
Patterns of statistical interdependencies between EEG, MEG and more recently also fMRI are widely studied to gain information about what is called ‘functional connectivity’ in the brain. Functional connectivity depends upon, but is not the same as the actual anatomical connections of the underlying neuronal networks. One question in relation to functional connectivity is whether it reflects specific spatial and temporal features related to an optimal state for information processing. In this context Tononi and Edelman introduced the neural complexity measure Cn to quantify a balance between local independence and global integration in functional connectivity patterns [17]. However some of the predictions of Tononi's model could not be confirmed in experimental studies [5] and [18]. In this paper we use a different approach and examine functional connectivity patterns from the point of view of graph theory. We address the question whether these connectivity patterns display the features of an optimal, ‘small-world’ like network.
The small-world phenomenon (also popularly called ‘six degrees of separation’) originally stems from sociology. It refers to the surprising property of large, sparsely connected social networks that any two people are connected by at most a few (no more than six) intermediate acquaintances. In a seminal paper Watts and Strogatz proposed a simple model to explain this property of networks [19]. They consider a one-dimensional graph with N nodes (called vertices in graph theory), each vertex being connected to its k nearest neighbours (where N≫k≫ln[N]). The connections between vertices are called edges; the number k of edges per vertex is also called the degree of the graph. Next, with a probability P, a random edge is chosen and rewired to connect to a randomly chosen vertex. By varying P between 0 and 1 graphs can be created which span the whole range from regular (P=0) to random (P=1).
Two measures were introduced to characterize such graphs: the characteristic path length Lp is the mean of the shortest path (expressed in number of edges) connecting any two vertices on the graph. The cluster coefficient Cp is the likelihood (between 0 and 1) that the kv neighbors of vertex v are also connected to each other, averaged over all vertices. Regular networks or graphs have a high Cp (Cp≈3/4) but a long characteristic path length (Lp≈N/2k); random graphs have a low Cp (k/N) but the shortest possible path length (Lp≈ln(N)/ln(k)). The discovery of Watts and Strogatz was that networks with 0<P≪1, thus regular networks with only a very small number of random edges, have a path length that is much smaller than that of a regular network, while the Cp is still close to that of a regular network. This dramatic drop in Lp for P only slightly higher than 0 implies that any vertex on the graph can be reached from any other vertex in only a small number of steps. This is equivalent to the small-world phenomenon and this type of graph (Cp close to regular network; Lp close to random network) was called a small-world graph by Watts and Strogatz. They showed that many real world networks such as networks of actors playing in the same movies, the power grid of North America and the neuronal network of Caenorhabditis elegans have small-world features. Furthermore, they suggested that such networks may be optimal for information processing in complex systems.
Since then it has been shown that many real networks display small world features and that these may reflect an optimal architecture for information processing (for a review see ref. [16]). Lago-Fernandez et al. showed that neural network models with small-world structure facilitate fast system response and the emergence of coherent oscillations [9]. A similar relationship between small-world architecture and synchronous oscillations was shown in model networks by Barahona and Pecora [2]. Sporns and Tononi used a genetic algorithm to select artificial neural networks with maximal entropy, integration or complexity [12]. The most interesting category was the group of networks with the highest complexity. The complexity measure Cn(x) obtains it highest values for networks with an optimal combination of segregation and integration; for application to EEG and MEG see refs. [5] and [18]. Networks with the highest complexity and thus optimal information processing properties showed typical small-world properties [12].
A slightly different model which also explains the small-world phenomenon is constituted by scale-free networks. In such networks the likelihood that a vertex will have k edges is inversely proportional to k [1]. It has been shown that the networks studied by Watts and Strogatz as well as the world wide web and metabolic pathways in 43 different types of organisms are of this type [1] and [8]. The characteristic path length of scale-free networks may be even smaller (of the order of ln(In(N)) than that of the model proposed by Watts and Strogatz (where it is of the order of ln(N)); such graphs have been called ‘ultra small’ [6].
If small-world or scale free properties of neuronal networks are really important for optimal information processing, it is important to know whether the typical features such as a high Cp, a low Lp and a scale-free degree distribution can be discovered in patterns of functional connectivity as well. To address this question we studied no-task, eyes-closed MEG recordings of five healthy human subjects (two females; mean age 30.5 year, range 25–38 year; all right-handed). MEG was recorded with a whole-head MEG system (CTF, Canada). Epochs of 4096 samples (sample frequency: 625 Hz) and 126 artefact free channels recorded during a no-task, eyes-closed condition were selected for analysis. The pattern of functional connectivity was determined by computing the synchronization likelihood between all pair wise combinations of channels, resulting in a 126 by 126 connectivity matrix (synchronization likelihood analysis of this data set was reported in ref. [14]). The synchronization likelihood (SL) is a general measure of the degree of linear and non-linear coupling between two channels [15]. Briefly, from two discrete time series xi and yi vectors are reconstructed with the method of time-delay embedding. The synchronization likelihood SL at time i is then defined as the likelihood (between 0 and 1), averaged over all j, that the distance between Yi and Yj is smaller than a cutoff distance rcutoff, given the distance between Xi and Xj is smaller than rcutoff. SL close to 0 indicates no coupling, whereas a SL=1 indicates complete coupling.
To convert the full connectivity matrix to a sparsely connected graph, we choose a threshold such that only pairs of channels with a SL above this threshold were considered to be connected by an edge; otherwise they were not considered to be connected. By varying the threshold the average number k of edges per vertex (vertex corresponds to MEG channel) could be varied.
Because there is strong evidence that synchronization in different frequency bands may be related to different functions in the brain, we applied the analysis to MEG data filtered in several frequency bands: delta (0.5–4 Hz); theta (4–8 Hz); alpha (8–13 Hz); beta (13–30 Hz) and gamma (30–48 Hz). For most analyses the threshold was chosen such that k=15; in all cases N=126. For the resulting graphs the cluster coefficient Cp and the characteristic path length Lp were determined. These were compared to the same measures of a regular/ordered graph (here the strength of the coupling was inversely proportional to the physical distance between the MEG sensors) with the same N and k and to the mean of 50 random graphs with the same N and k.
The results for the cluster coefficient Cp are shown in Fig. 1a. As expected, the Cp of the ordered network was the highest and the Cp of the random network was the lowest. Cp of MEG data is equal to that of an ordered graph in the alpha and beta band (95% confidence intervals overlap) and slightly lower (but still much higher than that of random graphs) in the other bands (non-overlapping 95% confidence intervals). Pathlengths for different types of graphs are shown in Fig. 1b. Here the path length of the ordered graph is the longest and the path length of the random graphs is the shortest. For the MEG data path lengths were comparable to those of an ordered graph in the alpha (8–13 Hz) and beta (13–30 Hz) band (overlapping confidence intervals); in the other frequency bands the path length of the MEG data was intermediate between that of an ordered and that of a random graph (non-overlapping confidence intervals).
(A) Cluster coefficient Cp in different frequency bands for ordered graph (Cp-o), mean (error bars indicate 95% confidence interval [mean±2×SEM]) of MEG recordings of five subjects (Cp) and mean of 50 random graphs (Cp-r). In all cases number of vertices=126 and number of edges per vertex=15. Cp of ordered graph is much higher than that of random graph. (B) Characteristic path length in different frequency bands for ordered graph (Lp-o), mean (error bars indicate 95% confidence interval [mean±2×SEM]) of MEG recordings of five subjects (Lp) and mean of 50 random graphs (Lp-r). In all cases number of vertices=126 and number of edges per vertex=15. Lp of ordered graph is much higher than that of random graph.
To study the possible influence of the choice of k on these results, gamma band (30–48 Hz) filtered data of one subject were analyzed for different values of k from k=10 to k=20 ( Fig. 2). Fig. 2a shows the Cp for the ordered network, the MEG data and 50 random networks as a function of k. For the range of k investigated (which covers the range N≫k≫ln(N)) Cp of the ordered and the MEG data were always much higher than the Cp of the random graphs. Only for a relatively high k the Cp for ordered and MEG graphs diverges and the difference with the random graph Cp diminishes. Fig. 2b shows the Lp for the ordered network, the MEG data and 50 random networks as a function of k. Lp of the ordered graph decreases slightly with higher k; a similar trend is seen for the MEG Lp but hardly for the random graph Lp. For all values of k, Lp is intermediate between Lp-o (ordered graph) and Lp-r (random graph). Finally we investigated the degree distribution of the gamma band data of this subject for k=15; no evidence was found for a scale free distribution.
(A) Influence of different choices of the mean number k of edges per vertex (the degree of the graph) on the cluster coefficient of an ordered graph (Cp-o), of MEG data filtered in the gamma band (Cp) and the mean of 50 random graphs (Cp-r). (B) Influence of different choices of the mean number k of edges per vertex (the degree of the graph) on the characteristic path length of an ordered graph (Lp-o), of MEG data filtered in the gamma band (Lp) and the mean of 50 random graphs (Lp-r).
The results of this study show that the functional connectivity matrix of MEG recordings can be converted into a sparsely connected graph by applying a suitable threshold. The resulting graphs can be readily characterized with tools from graph theory such as the clustering coefficient Cp, the characteristic path length Lp and the degree distribution, despite the fact that the size N of this graph is quite small for this type of analysis. In this study we specifically addressed the question whether sparsely connected graphs derived from MEG recordings of healthy human subjects show the typical characteristics of a small-world network. Such a network should have a relatively small path length combined with a relatively high clustering coefficient.
We found that the answer to this question depends upon the frequency band studied. In the alpha (8–13 Hz) and the beta band (13–30 Hz) the MEG graphs closely resembled ordered graphs, that is they had both a high Cp as well as a high Lp. So in the alpha and beta band MEG functional connectivity patterns are not of the small-world type. Instead, the strength of the synchronization between any two MEG channels seems to decay systematically with distance. (Please note that this indicates the results are not simply reflecting power in the different frequency bands, because the alpha band has very high and the beta band very low power.) Findings in the delta, theta and gamma band were different: here the clustering coefficient was still much higher than that of random networks, while the path length was intermediate between that of ordered and random graphs. This suggests that functional connectivity patterns in low (below 8 Hz) and high (above 30 Hz) frequency bands do display the characteristics of a small-world network.
The different graph types of intermediate frequency bands (8–30 Hz) on the one hand and low/high frequency bands (<8 Hz/>30 Hz) on the other hand might be related to different functions of synchronization in these bands. In particular the theta and gamma bands have been most directly related to information processing: the theta band in relation to working memory [10] and [13] and the gamma band in relation to perception, attention, conscious awareness, etc. [3]. Also, interactions between theta and gamma band processes have been described [4] and [11]. It may be that the small-world features of the low/high bands are related to the optimal information processing in these bands. However we should indicate that the present results relate to time series recorded at the sensor level, and not to actual sources in the brain. In further studies is would be worthwhile to see whether similar ‘small-world’ like features can be detected in activity patterns from reconstructed sources, for instance using synthetic aperture magnetography or dynamic imaging of coherent sources [7].
Mrs Alexandra Linger is thanked for secretarial assistance. Two anonymous reviewers are thanked for comments on an earlier version of this paper.
Emergence of scaling in random networks
Science, 286 (1999), pp. 509–512
Synchronization in small-world systems
Phys. Rev. Lett., 89 (2002), p. art 054191
Gamma, alpha, delta, and theta oscillations govern cognitive processes
Int. J. Psychophysiol., 39 (2001), pp. 241–248
Functional connectivity of gamma EEG activity is modulated at low frequency during conscious recollection
Int. J. Psychophysiol., 46 (2002), pp. 91–100
A neural complexity measure applied to MEG data in Alzheimer's disease
Clin. Neurophysiol., 114 (2003), pp. 1034–1040
Scale-free networks are ultra small
Phys. Rev. Lett., 90 (2003), p. art 058701
Dynamic imaging of coherent sources: studying neural interactions in the human brain
Proc. Natl. Acad. Sci. USA, 98 (2001), pp. 694–699
The large-scale organization of metabolic networks
Nature, 407 (2000), pp. 651–654
Fast response and temporal coherent oscillations in small-world networks
Phys. Rev. Lett., 84 (2000), pp. 2758–2761
Synchronization between prefrontal and posterior association cortex during human working memory
Proc. Natl. Acad. Sci. USA, 95 (1998), pp. 7092–7096
Phase-coupling of theta-gamma EEG rhythms during short-term memory processing
Int. J. Psychophysiol., 44 (2002), pp. 1443–1463
Connectivity and complexity: the relationship between neuroanatomy and brain dynamics
Neural Netw., 13 (2000), pp. 909–922
Brain dynamics in theta and alpha frequency bands and working memory performance in humans
Neurosci. Lett., 286 (2000), pp. 115–118
Non-linear synchronization in EEG and whole-head MEG recordings of healthy subjects
Hum. Brain Mapp., 19 (2003), pp. 63–78
Synchronization likelihood: an unbiased measure of generalized synchronization in multivariate data sets
Physica D, 163 (2002), pp. 236–241
Exploring complex networks
Nature, 410 (2001), pp. 268–276
Complexity and coherency: integrating information in the brain
Trends Cogn. Sci., 2 (1998), pp. 474–484
Application of a neural complexity measure to multichannel EEG
Phys. Lett. A, 281 (2001), pp. 131–141
Collective dynamics of ‘small-world’ networks
Nature, 393 (1998), pp. 440–442
Copyright © 2004 Elsevier Ireland Ltd. All rights reserved.