Community detection in directed weighted networks using Voronoi partitioning.

Community detection is a ubiquitous problem in applied network analysis, however efficient techniques do not yet exist for all types of network data. Directed and weighted networks are an example, where the different information encoded by link weights and the possibly high graph density can cause difficulties for some approaches. Here we present an algorithm based on Voronoi partitioning generalized to deal with directed weighted networks. As an added benefit, this method can directly employ edge weights that represent lengths, in contrast to algorithms that operate with connection strengths, requiring ad-hoc transformations of length data. We demonstrate the method on inter-areal brain connectivity, air transportation networks, and several social networks. We compare the performance with several other well-known algorithms, applying them on a set of randomly generated benchmark networks. The algorithm can handle dense graphs where weights are the main factor determining communities. The hierarchical structure of networks can also be detected, as shown for the brain. Its time efficiency is comparable or even outperforms some of the state-of-the-art algorithms, the part with the highest time-complexity being Dijkstra's shortest paths algorithm ( O ( | E | + | V | log | V | ) ).

Predictability of cortico-cortical connections in the mammalian brain.

Despite a five order of magnitude range in size, the brains of mammals share many anatomical and functional characteristics that translate into cortical network commonalities. Here we develop a machine learning framework to quantify the degree of predictability of the weighted interareal cortical matrix. Partial network connectivity data were obtained with retrograde tract-tracing experiments generated with a consistent methodology, supplemented by projection length measurements in a nonhuman primate (macaque) and a rodent (mouse). We show that there is a significant level of predictability embedded in the interareal cortical networks of both species. At the binary level, links are predictable with an area under the ROC curve of at least 0.8 for the macaque. Weighted medium and strong links are predictable with an 85%-90% accuracy (mouse) and 70%-80% (macaque), whereas weak links are not predictable in either species. These observations reinforce earlier observations that the formation and evolution of the cortical network at the mesoscale is, to a large extent, rule based. Using the methodology presented here, we performed imputations on all area pairs, generating samples for the complete interareal network in both species. These are necessary for comparative studies of the connectome with minimal bias, both within and across species.

The fractal brain: scale-invariance in structure and dynamics.

The past 40 years have witnessed extensive research on fractal structure and scale-free dynamics in the brain. Although considerable progress has been made, a comprehensive picture has yet to emerge, and needs further linking to a mechanistic account of brain function. Here, we review these concepts, connecting observations across different levels of organization, from both a structural and functional perspective. We argue that, paradoxically, the level of cortical circuits is the least understood from a structural point of view and perhaps the best studied from a dynamical one. We further link observations about scale-freeness and fractality with evidence that the environment provides constraints that may explain the usefulness of fractal structure and scale-free dynamics in the brain. Moreover, we discuss evidence that behavior exhibits scale-free properties, likely emerging from similarly organized brain dynamics, enabling an organism to thrive in an environment that shares the same organizational principles. Finally, we review the sparse evidence for and try to speculate on the functional consequences of fractality and scale-freeness for brain computation. These properties may endow the brain with computational capabilities that transcend current models of neural computation and could hold the key to unraveling how the brain constructs percepts and generates behavior.

Alcohol and sweet reward are encoded by distinct meta-ensembles.

Cue-reward associations form distinct memories that can drive appetitive behaviors and cravings for both drugs and natural rewards. It is still unclear how such memories are encoded in the brain's reward system. We trained rats to concurrently self-administer either alcohol or a sweet saccharin solution as drug or natural rewards, respectively. Memory recall due to cue exposure reactivated reward-associated functional ensembles in reward-related brain regions, marked by a neural cFos response. While the local ensembles activated by cue presentation for either reward consisted of similar numbers of neurons, using advanced statistical network theory, we found robust reward-specific co-activation patterns across brain regions. Interestingly, the resulting meta-ensemble networks differed by the most influential regions, which in case of saccharin comprised the prefrontal cortex, while for alcohol seeking control shifted to insular cortex with strong involvement of the amygdala. Our results support the view of memory representation as a differential co-activation of local neuronal ensembles. This article is part of the special issue on 'Neurocircuitry Modulating Drug and Alcohol Abuse'.

A Novel Measure Inspired by Lyapunov Exponents for the Characterization of Dynamics in State-Transition Networks.

The combination of network sciences, nonlinear dynamics and time series analysis provides novel insights and analogies between the different approaches to complex systems. By combining the considerations behind the Lyapunov exponent of dynamical systems and the average entropy of transition probabilities for Markov chains, we introduce a network measure for characterizing the dynamics on state-transition networks with special focus on differentiating between chaotic and cyclic modes. One important property of this Lyapunov measure consists of its non-monotonous dependence on the cylicity of the dynamics. Motivated by providing proper use cases for studying the new measure, we also lay out a method for mapping time series to state transition networks by phase space coarse graining. Using both discrete time and continuous time dynamical systems the Lyapunov measure extracted from the corresponding state-transition networks exhibits similar behavior to that of the Lyapunov exponent. In addition, it demonstrates a strong sensitivity to boundary crisis suggesting applicability in predicting the collapse of chaos.

Cell Surface Protein mRNAs Show Differential Transcription in Pyramidal and Fast-Spiking Cells as Revealed by Single-Cell Sequencing.

The prefrontal cortex (PFC) plays a key role in higher order cognitive functions and psychiatric disorders such as autism, schizophrenia, and depression. In the PFC, the two major classes of neurons are the glutamatergic pyramidal (Pyr) cells and the GABAergic interneurons such as fast-spiking (FS) cells. Despite extensive electrophysiological, morphological, and pharmacological studies of the PFC, the therapeutically utilized drug targets are restricted to dopaminergic, glutamatergic, and GABAergic receptors. To expand the pharmacological possibilities as well as to better understand the cellular and network effects of clinically used drugs, it is important to identify cell-type-selective, druggable cell surface proteins and to link developed drug candidates to Pyr or FS cell targets. To identify the mRNAs of such cell-specific/enriched proteins, we performed ultra-deep single-cell mRNA sequencing (19 685 transcripts in total) on electrophysiologically characterized intact PFC neurons harvested from acute brain slices of mice. Several selectively expressed transcripts were identified with some of the genes that have already been associated with cellular mechanisms of psychiatric diseases, which we can now assign to Pyr (e.g., Kcnn2, Gria3) or FS (e.g., Kcnk2, Kcnmb1) cells. The earlier classification of PFC neurons was also confirmed at mRNA level, and additional markers have been provided.

A continuous-time MaxSAT solver with high analog performance.

Many real-life optimization problems can be formulated in Boolean logic as MaxSAT, a class of problems where the task is finding Boolean assignments to variables satisfying the maximum number of logical constraints. Since MaxSAT is NP-hard, no algorithm is known to efficiently solve these problems. Here we present a continuous-time analog solver for MaxSAT and show that the scaling of the escape rate, an invariant of the solver's dynamics, can predict the maximum number of satisfiable constraints, often well before finding the optimal assignment. Simulating the solver, we illustrate its performance on MaxSAT competition problems, then apply it to two-color Ramsey number R(m, m) problems. Although it finds colorings without monochromatic 5-cliques of complete graphs on N ≤ 42 vertices, the best coloring for N = 43 has two monochromatic 5-cliques, supporting the conjecture that R(5, 5) = 43. This approach shows the potential of continuous-time analog dynamical systems as algorithms for discrete optimization.

The Mouse Cortical Connectome, Characterized by an Ultra-Dense Cortical Graph, Maintains Specificity by Distinct Connectivity Profiles.

The inter-areal wiring pattern of the mouse cerebral cortex was analyzed in relation to a refined parcellation of cortical areas. Twenty-seven retrograde tracer injections were made in 19 areas of a 47-area parcellation of the mouse neocortex. Flat mounts of the cortex and multiple histological markers enabled detailed counts of labeled neurons in individual areas. The observed log-normal distribution of connection weights to each cortical area spans 5 orders of magnitude and reveals a distinct connectivity profile for each area, analogous to that observed in macaques. The cortical network has a density of 97%, considerably higher than the 66% density reported in macaques. A weighted graph analysis reveals a similar global efficiency but weaker spatial clustering compared with that reported in macaques. The consistency, precision of the connectivity profile, density, and weighted graph analysis of the present data differ significantly from those obtained in earlier studies in the mouse.

A multiscale cerebral neurochemical connectome of the rat brain.

Understanding the rat neurochemical connectome is fundamental for exploring neuronal information processing. By using advanced data mining, supervised machine learning, and network analysis, this study integrates over 5 decades of neuroanatomical investigations into a multiscale, multilayer neurochemical connectome of the rat brain. This neurochemical connectivity database (ChemNetDB) is supported by comprehensive systematically-determined receptor distribution maps. The rat connectome has an onion-type structural organization and shares a number of structural features with mesoscale connectomes of mouse and macaque. Furthermore, we demonstrate that extremal values of graph theoretical measures (e.g., degree and betweenness) are associated with evolutionary-conserved deep brain structures such as amygdala, bed nucleus of the stria terminalis, dorsal raphe, and lateral hypothalamus, which regulate primitive, yet fundamental functions, such as circadian rhythms, reward, aggression, anxiety, and fear. The ChemNetDB is a freely available resource for systems analysis of motor, sensory, emotional, and cognitive information processing.

Stochastic graph Voronoi tessellation reveals community structure.

Given a network, the statistical ensemble of its graph-Voronoi diagrams with randomly chosen cell centers exhibits properties convertible into information on the network's large scale structures. We define a node-pair level measure called Voronoi cohesion which describes the probability for sharing the same Voronoi cell, when randomly choosing g centers in the network. This measure provides information based on the global context (the network in its entirety), a type of information that is not carried by other similarity measures. We explore the mathematical background of this phenomenon and several of its potential applications. A special focus is laid on the possibilities and limitations pertaining to the exploitation of the phenomenon for community detection purposes.

Spatial Embedding and Wiring Cost Constrain the Functional Layout of the Cortical Network of Rodents and Primates.

Mammals show a wide range of brain sizes, reflecting adaptation to diverse habitats. Comparing interareal cortical networks across brains of different sizes and mammalian orders provides robust information on evolutionarily preserved features and species-specific processing modalities. However, these networks are spatially embedded, directed, and weighted, making comparisons challenging. Using tract tracing data from macaque and mouse, we show the existence of a general organizational principle based on an exponential distance rule (EDR) and cortical geometry, enabling network comparisons within the same model framework. These comparisons reveal the existence of network invariants between mouse and macaque, exemplified in graph motif profiles and connection similarity indices, but also significant differences, such as fractionally smaller and much weaker long-distance connections in the macaque than in mouse. The latter lends credence to the prediction that long-distance cortico-cortical connections could be very weak in the much-expanded human cortex, implying an increased susceptibility to disconnection syndromes such as Alzheimer disease and schizophrenia. Finally, our data from tracer experiments involving only gray matter connections in the primary visual areas of both species show that an EDR holds at local scales as well (within 1.5 mm), supporting the hypothesis that it is a universally valid property across all scales and, possibly, across the mammalian class.

Order-to-chaos transition in the hardness of random Boolean satisfiability problems.

Transient chaos is a ubiquitous phenomenon characterizing the dynamics of phase-space trajectories evolving towards a steady-state attractor in physical systems as diverse as fluids, chemical reactions, and condensed matter systems. Here we show that transient chaos also appears in the dynamics of certain efficient algorithms searching for solutions of constraint satisfaction problems that include scheduling, circuit design, routing, database problems, and even Sudoku. In particular, we present a study of the emergence of hardness in Boolean satisfiability (k-SAT), a canonical class of constraint satisfaction problems, by using an analog deterministic algorithm based on a system of ordinary differential equations. Problem hardness is defined through the escape rate κ, an invariant measure of transient chaos of the dynamical system corresponding to the analog algorithm, and it expresses the rate at which the trajectory approaches a solution. We show that for a given density of constraints and fixed number of Boolean variables N, the hardness of formulas in random k-SAT ensembles has a wide variation, approximable by a lognormal distribution. We also show that when increasing the density of constraints α, hardness appears through a second-order phase transition at α_{χ} in the random 3-SAT ensemble where dynamical trajectories become transiently chaotic. A similar behavior is found in 4-SAT as well, however, such a transition does not occur for 2-SAT. This behavior also implies a novel type of transient chaos in which the escape rate has an exponential-algebraic dependence on the critical parameter κ∼N^{B|α-α_{χ}|^{1-γ}} with 0<γ<1. We demonstrate that the transition is generated by the appearance of metastable basins in the solution space as the density of constraints α is increased.

Principles of dynamical modularity in biological regulatory networks.

Intractable diseases such as cancer are associated with breakdown in multiple individual functions, which conspire to create unhealthy phenotype-combinations. An important challenge is to decipher how these functions are coordinated in health and disease. We approach this by drawing on dynamical systems theory. We posit that distinct phenotype-combinations are generated by interactions among robust regulatory switches, each in control of a discrete set of phenotypic outcomes. First, we demonstrate the advantage of characterizing multi-switch regulatory systems in terms of their constituent switches by building a multiswitch cell cycle model which points to novel, testable interactions critical for early G2/M commitment to division. Second, we define quantitative measures of dynamical modularity, namely that global cell states are discrete combinations of switch-level phenotypes. Finally, we formulate three general principles that govern the way coupled switches coordinate their function.

Predicting commuter flows in spatial networks using a radiation model based on temporal ranges.

Understanding network flows such as commuter traffic in large transportation networks is an ongoing challenge due to the complex nature of the transportation infrastructure and human mobility. Here we show a first-principles based method for traffic prediction using a cost-based generalization of the radiation model for human mobility, coupled with a cost-minimizing algorithm for efficient distribution of the mobility fluxes through the network. Using US census and highway traffic data, we show that traffic can efficiently and accurately be computed from a range-limited, network betweenness type calculation. The model based on travel time costs captures the log-normal distribution of the traffic and attains a high Pearson correlation coefficient (0.75) when compared with real traffic. Because of its principled nature, this method can inform many applications related to human mobility driven flows in spatial networks, ranging from transportation, through urban planning to mitigation of the effects of catastrophic events.

Cortical high-density counterstream architectures.

Small-world networks provide an appealing description of cortical architecture owing to their capacity for integration and segregation combined with an economy of connectivity. Previous reports of low-density interareal graphs and apparent small-world properties are challenged by data that reveal high-density cortical graphs in which economy of connections is achieved by weight heterogeneity and distance-weight correlations. These properties define a model that predicts many binary and weighted features of the cortical network including a core-periphery, a typical feature of self-organizing information processing systems. Feedback and feedforward pathways between areas exhibit a dual counterstream organization, and their integration into local circuits constrains cortical computation. Here, we propose a bow-tie representation of interareal architecture derived from the hierarchical laminar weights of pathways between the high-efficiency dense core and periphery.

A predictive network model of cerebral cortical connectivity based on a distance rule.

Recent advances in neuroscience have engendered interest in large-scale brain networks. Using a consistent database of cortico-cortical connectivity, generated from hemisphere-wide, retrograde tracing experiments in the macaque, we analyzed interareal weights and distances to reveal an important organizational principle of brain connectivity. Using appropriate graph theoretical measures, we show that although very dense (66%), the interareal network has strong structural specificity. Connection weights exhibit a heavy-tailed lognormal distribution spanning five orders of magnitude and conform to a distance rule reflecting exponential decay with interareal separation. A single-parameter random graph model based on this rule predicts numerous features of the cortical network: (1) the existence of a network core and the distribution of cliques, (2) global and local binary properties, (3) global and local weight-based communication efficiencies modeled as network conductance, and (4) overall wire-length minimization. These findings underscore the importance of distance and weight-based heterogeneity in cortical architecture and processing.

Asymmetric continuous-time neural networks without local traps for solving constraint satisfaction problems.

There has been a long history of using neural networks for combinatorial optimization and constraint satisfaction problems. Symmetric Hopfield networks and similar approaches use steepest descent dynamics, and they always converge to the closest local minimum of the energy landscape. For finding global minima additional parameter-sensitive techniques are used, such as classical simulated annealing or the so-called chaotic simulated annealing, which induces chaotic dynamics by addition of extra terms to the energy landscape. Here we show that asymmetric continuous-time neural networks can solve constraint satisfaction problems without getting trapped in non-solution attractors. We concentrate on a model solving Boolean satisfiability (k-SAT), which is a quintessential NP-complete problem. There is a one-to-one correspondence between the stable fixed points of the neural network and the k-SAT solutions and we present numerical evidence that limit cycles may also be avoided by appropriately choosing the parameters of the model. This optimal parameter region is fairly independent of the size and hardness of instances, this way parameters can be chosen independently of the properties of problems and no tuning is required during the dynamical process. The model is similar to cellular neural networks already used in CNN computers. On an analog device solving a SAT problem would take a single operation: the connection weights are determined by the k-SAT instance and starting from any initial condition the system searches until finding a solution. In this new approach transient chaotic behavior appears as a natural consequence of optimization hardness and not as an externally induced effect.

The role of long-range connections on the specificity of the macaque interareal cortical network.

We investigated the influence of interareal distance on connectivity patterns in a database obtained from the injection of retrograde tracers in 29 areas distributed over six regions (occipital, temporal, parietal, frontal, prefrontal, and limbic). One-third of the 1,615 pathways projecting to the 29 target areas were reported only recently and deemed new-found projections (NFPs). NFPs are predominantly long-range, low-weight connections. A minimum dominating set analysis (a graph theoretic measure) shows that NFPs play a major role in globalizing input to small groups of areas. Randomization tests show that (i) NFPs make important contributions to the specificity of the connectivity profile of individual cortical areas, and (ii) NFPs share key properties with known connections at the same distance. We developed a similarity index, which shows that intraregion similarity is high, whereas the interregion similarity declines with distance. For area pairs, there is a steep decline with distance in the similarity and probability of being connected. Nevertheless, the present findings reveal an unexpected binary specificity despite the high density (66%) of the cortical graph. This specificity is made possible because connections are largely concentrated over short distances. These findings emphasize the importance of long-distance connections in the connectivity profile of an area. We demonstrate that long-distance connections are particularly prevalent for prefrontal areas, where they may play a prominent role in large-scale communication and information integration.

The chaos within Sudoku.

The mathematical structure of Sudoku puzzles is akin to hard constraint satisfaction problems lying at the basis of many applications, including protein folding and the ground-state problem of glassy spin systems. Via an exact mapping of Sudoku into a deterministic, continuous-time dynamical system, here we show that the difficulty of Sudoku translates into transient chaotic behavior exhibited by this system. We also show that the escape rate κ, an invariant of transient chaos, provides a scalar measure of the puzzle's hardness that correlates well with human difficulty ratings. Accordingly, η = -log10κ can be used to define a "Richter"-type scale for puzzle hardness, with easy puzzles having 0 < η ≤ 1, medium ones 1 < η ≤ 2, hard with 2 < η ≤ 3 and ultra-hard with η > 3. To our best knowledge, there are no known puzzles with η > 4.

Range-limited centrality measures in complex networks.

Here we present a range-limited approach to centrality measures in both nonweighted and weighted directed complex networks. We introduce an efficient method that generates for every node and every edge its betweenness centrality based on shortest paths of lengths not longer than ℓ=1,...,L in the case of nonweighted networks, and for weighted networks the corresponding quantities based on minimum weight paths with path weights not larger than w(ℓ)=ℓΔ, ℓ=1,2...,L=R/Δ. These measures provide a systematic description on the positioning importance of a node (edge) with respect to its network neighborhoods one step out, two steps out, etc., up to and including the whole network. They are more informative than traditional centrality measures, as network transport typically happens on all length scales, from transport to nearest neighbors to the farthest reaches of the network. We show that range-limited centralities obey universal scaling laws for large nonweighted networks. As the computation of traditional centrality measures is costly, this scaling behavior can be exploited to efficiently estimate centralities of nodes and edges for all ranges, including the traditional ones. The scaling behavior can also be exploited to show that the ranking top list of nodes (edges) based on their range-limited centralities quickly freezes as a function of the range, and hence the diameter-range top list can be efficiently predicted. We also show how to estimate the typical largest node-to-node distance for a network of N nodes, exploiting the afore-mentioned scaling behavior. These observations were made on model networks and on a large social network inferred from cell-phone trace logs (∼5.5×10(6) nodes and ∼2.7×10(7) edges). Finally, we apply these concepts to efficiently detect the vulnerability backbone of a network (defined as the smallest percolating cluster of the highest betweenness nodes and edges) and illustrate the importance of weight-based centrality measures in weighted networks in detecting such backbones.