Directed network motifs in Alzheimer's disease and mild cognitive impairment.

Directed network motifs are the building blocks of complex networks, such as human brain networks, and capture deep connectivity information that is not contained in standard network measures. In this paper we present the first application of directed network motifs in vivo to human brain networks, utilizing recently developed directed progression networks which are built upon rates of cortical thickness changes between brain regions. This is in contrast to previous studies which have relied on simulations and in vitro analysis of non-human brains. We show that frequencies of specific directed network motifs can be used to distinguish between patients with Alzheimer's disease (AD) and normal control (NC) subjects. Especially interesting from a clinical standpoint, these motif frequencies can also distinguish between subjects with mild cognitive impairment who remained stable over three years (MCI) and those who converted to AD (CONV). Furthermore, we find that the entropy of the distribution of directed network motifs increased from MCI to CONV to AD, implying that the distribution of pathology is more structured in MCI but becomes less so as it progresses to CONV and further to AD. Thus, directed network motifs frequencies and distributional properties provide new insights into the progression of Alzheimer's disease as well as new imaging markers for distinguishing between normal controls, stable mild cognitive impairment, MCI converters and Alzheimer's disease.

Stochastic geometric network models for groups of functional and structural connectomes.

Structural and functional connectomes are emerging as important instruments in the study of normal brain function and in the development of new biomarkers for a variety of brain disorders. In contrast to single-network studies that presently dominate the (non-connectome) network literature, connectome analyses typically examine groups of empirical networks and then compare these against standard (stochastic) network models. The current practice in connectome studies is to employ stochastic network models derived from social science and engineering contexts as the basis for the comparison. However, these are not necessarily best suited for the analysis of connectomes, which often contain groups of very closely related networks, such as occurs with a set of controls or a set of patients with a specific disorder. This paper studies important extensions of standard stochastic models that make them better adapted for analysis of connectomes, and develops new statistical fitting methodologies that account for inter-subject variations. The extensions explicitly incorporate geometric information about a network based on distances and inter/intra hemispherical asymmetries (to supplement ordinary degree-distribution information), and utilize a stochastic choice of network density levels (for fixed threshold networks) to better capture the variance in average connectivity among subjects. The new statistical tools introduced here allow one to compare groups of networks by matching both their average characteristics and the variations among them. A notable finding is that connectomes have high "smallworldness" beyond that arising from geometric and degree considerations alone.

Directed progression brain networks in Alzheimer's disease: properties and classification.

This article introduces a new approach in brain connectomics aimed at characterizing the temporal spread in the brain of pathologies like Alzheimer's disease (AD). The main instrument is the development of "directed progression networks" (DPNets), wherein one constructs directed edges between nodes based on (weakly) inferred directions of the temporal spreading of the pathology. This stands in contrast to many previously studied brain networks where edges represent correlations, physical connections, or functional progressions. In addition, this is one of a few studies showing the value of using directed networks in the study of AD. This article focuses on the construction of DPNets for AD using longitudinal cortical thickness measurements from magnetic resonance imaging data. The network properties are then characterized, providing new insights into AD progression, as well as novel markers for differentiating normal cognition (NC) and AD at the group level. It also demonstrates the important role of nodal variations for network classification (i.e., the significance of standard deviations, not just mean values of nodal properties). Finally, the DPNets are utilized to classify subjects based on their global network measures using a variety of data-mining methodologies. In contrast to most brain networks, these DPNets do not show high clustering and small-world properties.

Hierarchical networks, power laws, and neuronal avalanches.

We show that in networks with a hierarchical architecture, critical dynamical behaviors can emerge even when the underlying dynamical processes are not critical. This finding provides explicit insight into current studies of the brain's neuronal network showing power-law avalanches in neural recordings, and provides a theoretical justification of recent numerical findings. Our analysis shows how the hierarchical organization of a network can itself lead to power-law distributions of avalanche sizes and durations, scaling laws between anomalous exponents, and universal functions-even in the absence of self-organized criticality or critical points. This hierarchy-induced phenomenon is independent of, though can potentially operate in conjunction with, standard dynamical mechanisms for generating power laws.

Combinatorial games with a pass: a dynamical systems approach.

By treating combinatorial games as dynamical systems, we are able to address a longstanding open question in combinatorial game theory, namely, how the introduction of a "pass" move into a game affects its behavior. We consider two well known combinatorial games, 3-pile Nim and 3-row Chomp. In the case of Nim, we observe that the introduction of the pass dramatically alters the game's underlying structure, rendering it considerably more complex, while for Chomp, the pass move is found to have relatively minimal impact. We show how these results can be understood by recasting these games as dynamical systems describable by dynamical recursion relations. From these recursion relations, we are able to identify underlying structural connections between these "games with passes" and a recently introduced class of "generic (perturbed) games." This connection, together with a (non-rigorous) numerical stability analysis, allows one to understand and predict the effect of a pass on a game.

Construction and analysis of random networks with explosive percolation.

The existence of explosive phase transitions in random (Erdös Rényi-type) networks has been recently documented by Achlioptas, D'Souza, and Spencer [Science 323, 1453 (2009)] via simulations. In this Letter we describe the underlying mechanism behind these first-order phase transitions and develop tools that allow us to identify (and predict) when a random network will exhibit an explosive transition. Several interesting new models displaying explosive transitions are also presented.