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.

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.

Reducing degeneracy in maximum entropy models of networks.

Based on Jaynes's maximum entropy principle, exponential random graphs provide a family of principled models that allow the prediction of network properties as constrained by empirical data (observables). However, their use is often hindered by the degeneracy problem characterized by spontaneous symmetry breaking, where predictions fail. Here we show that degeneracy appears when the corresponding density of states function is not log-concave, which is typically the consequence of nonlinear relationships between the constraining observables. Exploiting these nonlinear relationships here we propose a solution to the degeneracy problem for a large class of systems via transformations that render the density of states function log-concave. The effectiveness of the method is demonstrated on examples.

Pattern formation induced by ion-selective surfaces: models and simulations.

Simple inorganic reactions in gels, such as NaOH + CuCl(2), NaOH + AgNO(3), and CuCl(2) + K(3)[Fe(CN)(6)], can yield to various precipitation patterns. The first compound penetrates in a hydrogel by diffusion, and reacts with the second compound homogenized in the gel. The precipitate patterns formed in these reactions have got two kinds of bordering surfaces. Recent experimental results suggested that one of these surfaces has an ion-selective (semipermeable) character: It restrains the diffusion of the reacting ion contained by the reactant that diffuses into the gel. In this paper, we built the above experimental observation into a reaction-diffusion cellular-automata model of the pattern formation. Computer simulations showed that the model is able to reproduce the basic building elements of the patterns.