Hierarchical Modular Structure of the Drosophila Connectome.

The structure of neural circuitry plays a crucial role in brain function. Previous studies of brain organization generally had to trade off between coarse descriptions at a large scale and fine descriptions on a small scale. Researchers have now reconstructed tens to hundreds of thousands of neurons at synaptic resolution, enabling investigations into the interplay between global, modular organization, and cell type-specific wiring. Analyzing data of this scale, however, presents unique challenges. To address this problem, we applied novel community detection methods to analyze the synapse-level reconstruction of an adult female Drosophila melanogaster brain containing >20,000 neurons and 10 million synapses. Using a machine-learning algorithm, we find the most densely connected communities of neurons by maximizing a generalized modularity density measure. We resolve the community structure at a range of scales, from large (on the order of thousands of neurons) to small (on the order of tens of neurons). We find that the network is organized hierarchically, and larger-scale communities are composed of smaller-scale structures. Our methods identify well-known features of the fly brain, including its sensory pathways. Moreover, focusing on specific brain regions, we are able to identify subnetworks with distinct connectivity types. For example, manual efforts have identified layered structures in the fan-shaped body. Our methods not only automatically recover this layered structure, but also resolve finer connectivity patterns to downstream and upstream areas. We also find a novel modular organization of the superior neuropil, with distinct clusters of upstream and downstream brain regions dividing the neuropil into several pathways. These methods show that the fine-scale, local network reconstruction made possible by modern experimental methods are sufficiently detailed to identify the organization of the brain across scales, and enable novel predictions about the structure and function of its parts.Significance Statement The Hemibrain is a partial connectome of an adult female Drosophila melanogaster brain containing >20,000 neurons and 10 million synapses. Analyzing the structure of a network of this size requires novel and efficient computational tools. We applied a new community detection method to automatically uncover the modular structure in the Hemibrain dataset by maximizing a generalized modularity measure. This allowed us to resolve the community structure of the fly hemibrain at a range of spatial scales revealing a hierarchical organization of the network, where larger-scale modules are composed of smaller-scale structures. The method also allowed us to identify subnetworks with distinct cell and connectivity structures, such as the layered structures in the fan-shaped body, and the modular organization of the superior neuropil. Thus, network analysis methods can be adopted to the connectomes being reconstructed using modern experimental methods to reveal the organization of the brain across scales. This supports the view that such connectomes will allow us to uncover the organizational structure of the brain, which can ultimately lead to a better understanding of its function.

How High-Risk Comorbidities Co-Occur in Readmitted Patients With Hip Fracture: Big Data Visual Analytical Approach.

BACKGROUND: When older adult patients with hip fracture (HFx) have unplanned hospital readmissions within 30 days of discharge, it doubles their 1-year mortality, resulting in substantial personal and financial burdens. Although such unplanned readmissions are predominantly caused by reasons not related to HFx surgery, few studies have focused on how pre-existing high-risk comorbidities co-occur within and across subgroups of patients with HFx. OBJECTIVE: This study aims to use a combination of supervised and unsupervised visual analytical methods to (1) obtain an integrated understanding of comorbidity risk, comorbidity co-occurrence, and patient subgroups, and (2) enable a team of clinical and methodological stakeholders to infer the processes that precipitate unplanned hospital readmission, with the goal of designing targeted interventions. METHODS: We extracted a training data set consisting of 16,886 patients (8443 readmitted patients with HFx and 8443 matched controls) and a replication data set consisting of 16,222 patients (8111 readmitted patients with HFx and 8111 matched controls) from the 2010 and 2009 Medicare database, respectively. The analyses consisted of a supervised combinatorial analysis to identify and replicate combinations of comorbidities that conferred significant risk for readmission, an unsupervised bipartite network analysis to identify and replicate how high-risk comorbidity combinations co-occur across readmitted patients with HFx, and an integrated visualization and analysis of comorbidity risk, comorbidity co-occurrence, and patient subgroups to enable clinician stakeholders to infer the processes that precipitate readmission in patient subgroups and to propose targeted interventions. RESULTS: The analyses helped to identify (1) 11 comorbidity combinations that conferred significantly higher risk (ranging from P<.001 to P=.01) for a 30-day readmission, (2) 7 biclusters of patients and comorbidities with a significant bicluster modularity (P<.001; Medicare=0.440; random mean 0.383 [0.002]), indicating strong heterogeneity in the comorbidity profiles of readmitted patients, and (3) inter- and intracluster risk associations, which enabled clinician stakeholders to infer the processes involved in the exacerbation of specific combinations of comorbidities leading to readmission in patient subgroups. CONCLUSIONS: The integrated analysis of risk, co-occurrence, and patient subgroups enabled the inference of processes that precipitate readmission, leading to a comorbidity exacerbation risk model for readmission after HFx. These results have direct implications for (1) the management of comorbidities targeted at high-risk subgroups of patients with the goal of pre-emptively reducing their risk of readmission and (2) the development of more accurate risk prediction models that incorporate information about patient subgroups.

Reduced network extremal ensemble learning (RenEEL) scheme for community detection in complex networks.

We introduce an ensemble learning scheme for community detection in complex networks. The scheme uses a Machine Learning algorithmic paradigm we call Extremal Ensemble Learning. It uses iterative extremal updating of an ensemble of network partitions, which can be found by a conventional base algorithm, to find a node partition that maximizes modularity. At each iteration, core groups of nodes that are in the same community in every ensemble partition are identified and used to form a reduced network. Partitions of the reduced network are then found and used to update the ensemble. The smaller size of the reduced network makes the scheme efficient. We use the scheme to analyze the community structure in a set of commonly studied benchmark networks and find that it outperforms all other known methods for finding the partition with maximum modularity.

Coevolution of nodes and links: Diversity-driven coexistence in cyclic competition of three species.

When three species compete cyclically in a well-mixed, stochastic system of N individuals, extinction is known to typically occur at times scaling as the system size N. This happens, for example, in rock-paper-scissors games or conserved Lotka-Volterra models in which every pair of individuals can interact on a complete graph. Here we show that if the competing individuals also have a "social temperament" to be either introverted or extroverted, leading them to cut or add links, respectively, then long-living states in which all species coexist can occur. These nonequilibrium quasisteady states only occur when both introverts and extroverts are present, thus showing that diversity can lead to stability in complex systems. In this case, it enables a subtle balance between species competition and network dynamics to be maintained.

Anomalous scaling of stochastic processes and the Moses effect.

The state of a stochastic process evolving over a time t is typically assumed to lie on a normal distribution whose width scales like t^{1/2}. However, processes in which the probability distribution is not normal and the scaling exponent differs from 1/2 are known. The search for possible origins of such "anomalous" scaling and approaches to quantify them are the motivations for the work reported here. In processes with stationary increments, where the stochastic process is time-independent, autocorrelations between increments and infinite variance of increments can cause anomalous scaling. These sources have been referred to as the Joseph effect and the Noah effect, respectively. If the increments are nonstationary, then scaling of increments with t can also lead to anomalous scaling, a mechanism we refer to as the Moses effect. Scaling exponents quantifying the three effects are defined and related to the Hurst exponent that characterizes the overall scaling of the stochastic process. Methods of time series analysis that enable accurate independent measurement of each exponent are presented. Simple stochastic processes are used to illustrate each effect. Intraday financial time series data are analyzed, revealing that their anomalous scaling is due only to the Moses effect. In the context of financial market data, we reiterate that the Joseph exponent, not the Hurst exponent, is the appropriate measure to test the efficient market hypothesis.

Reconstruction and topological characterization of the sigma factor regulatory network of Mycobacterium tuberculosis.

Accessory sigma factors, which reprogram RNA polymerase to transcribe specific gene sets, activate bacterial adaptive responses to noxious environments. Here we reconstruct the complete sigma factor regulatory network of the human pathogen Mycobacterium tuberculosis by an integrated approach. The approach combines identification of direct regulatory interactions between M. tuberculosis sigma factors in an E. coli model system, validation of selected links in M. tuberculosis, and extensive literature review. The resulting network comprises 41 direct interactions among all 13 sigma factors. Analysis of network topology reveals (i) a three-tiered hierarchy initiating at master regulators, (ii) high connectivity and (iii) distinct communities containing multiple sigma factors. These topological features are likely associated with multi-layer signal processing and specialized stress responses involving multiple sigma factors. Moreover, the identification of overrepresented network motifs, such as autoregulation and coregulation of sigma and anti-sigma factor pairs, provides structural information that is relevant for studies of network dynamics.

Quantifying randomness in real networks.

Represented as graphs, real networks are intricate combinations of order and disorder. Fixing some of the structural properties of network models to their values observed in real networks, many other properties appear as statistical consequences of these fixed observables, plus randomness in other respects. Here we employ the dk-series, a complete set of basic characteristics of the network structure, to study the statistical dependencies between different network properties. We consider six real networks--the Internet, US airport network, human protein interactions, technosocial web of trust, English word network, and an fMRI map of the human brain--and find that many important local and global structural properties of these networks are closely reproduced by dk-random graphs whose degree distributions, degree correlations and clustering are as in the corresponding real network. We discuss important conceptual, methodological, and practical implications of this evaluation of network randomness, and release software to generate dk-random graphs.

Symmetry in critical random Boolean network dynamics.

Using Boolean networks as prototypical examples, the role of symmetry in the dynamics of heterogeneous complex systems is explored. We show that symmetry of the dynamics, especially in critical states, is a controlling feature that can be used both to greatly simplify analysis and to characterize different types of dynamics. Symmetry in Boolean networks is found by determining the frequency at which the various Boolean output functions occur. There are classes of functions that consist of Boolean functions that behave similarly. These classes are orbits of the controlling symmetry group. We find that the symmetry that controls the critical random Boolean networks is expressed through the frequency by which output functions are utilized by nodes that remain active on dynamical attractors. This symmetry preserves canalization, a form of network robustness. We compare it to a different symmetry known to control the dynamics of an evolutionary process that allows Boolean networks to organize into a critical state. Our results demonstrate the usefulness and power of using the symmetry of the behavior of the nodes to characterize complex network dynamics, and introduce an alternative approach to the analysis of heterogeneous complex systems.

The role of complementary bipartite visual analytical representations in the analysis of SNPs: a case study in ancestral informative markers.

OBJECTIVE: Several studies have shown how sets of single-nucleotide polymorphisms (SNPs) can help to classify subjects on the basis of their continental origins, with applications to case-control studies and population genetics. However, most of these studies use dimensionality-reduction methods, such as principal component analysis, or clustering methods that result in unipartite (either subjects or SNPs) representations of the data. Such analyses conceal important bipartite relationships, such as how subject and SNP clusters relate to each other, and the genotypes that determine their cluster memberships. METHODS: To overcome the limitations of current methods of analyzing SNP data, the authors used three bipartite analytical representations (bipartite network, heat map with dendrograms, and Circos ideogram) that enable the simultaneous visualization and analysis of subjects, SNPs, and subject attributes. RESULTS: The results demonstrate (1) novel insights into SNP data that are difficult to derive from purely unipartite views of the data, (2) the strengths and limitations of each method, revealing the role that each play in revealing novel insights, and (3) implications for how the methods can be used for the analysis of SNPs in genomic studies associated with disease. CONCLUSION: The results suggest that bipartite representations can reveal new patterns in SNP data compared with existing unipartite representations. However, the novel insights require multiple representations to discover, verify, and comprehend the complex relationships. The results therefore motivate the need for a complementary visual analytical framework that guides the use of multiple bipartite representations to analyze complex relationships in SNP data.

Robust detection of hierarchical communities from Escherichia coli gene expression data.

Determining the functional structure of biological networks is a central goal of systems biology. One approach is to analyze gene expression data to infer a network of gene interactions on the basis of their correlated responses to environmental and genetic perturbations. The inferred network can then be analyzed to identify functional communities. However, commonly used algorithms can yield unreliable results due to experimental noise, algorithmic stochasticity, and the influence of arbitrarily chosen parameter values. Furthermore, the results obtained typically provide only a simplistic view of the network partitioned into disjoint communities and provide no information of the relationship between communities. Here, we present methods to robustly detect co-regulated and functionally enriched gene communities and demonstrate their application and validity for Escherichia coli gene expression data. Applying a recently developed community detection algorithm to the network of interactions identified with the context likelihood of relatedness (CLR) method, we show that a hierarchy of network communities can be identified. These communities significantly enrich for gene ontology (GO) terms, consistent with them representing biologically meaningful groups. Further, analysis of the most significantly enriched communities identified several candidate new regulatory interactions. The robustness of our methods is demonstrated by showing that a core set of functional communities is reliably found when artificial noise, modeling experimental noise, is added to the data. We find that noise mainly acts conservatively, increasing the relatedness required for a network link to be reliably assigned and decreasing the size of the core communities, rather than causing association of genes into new communities.

Canalization in the critical states of highly connected networks of competing Boolean nodes.

Canalization is a classic concept in developmental biology that is thought to be an important feature of evolving systems. In a Boolean network, it is a form of network robustness in which a subset of the input signals controls the behavior of a node regardless of the remaining input. It has been shown that Boolean networks can become canalized if they evolve through a frustrated competition between nodes. This was demonstrated for large networks in which each node had K=3 inputs. Those networks evolve to a critical steady state at the border of two phases of dynamical behavior. Moreover, the evolution of these networks was shown to be associated with the symmetry of the evolutionary dynamics. We extend these results to the more highly connected K>3 cases and show that similar canalized critical steady states emerge with the same associated dynamical symmetry, but only if the evolutionary dynamics is biased toward homogeneous Boolean functions.

All scale-free networks are sparse.

We study the realizability of scale-free networks with a given degree sequence, showing that the fraction of realizable sequences undergoes two first-order transitions at the values 0 and 2 of the power-law exponent. We substantiate this finding by analytical reasoning and by a numerical method, proposed here, based on extreme value arguments, which can be applied to any given degree distribution. Our results reveal a fundamental reason why large scale-free networks without constraints on minimum and maximum degree must be sparse.

Efficient and exact sampling of simple graphs with given arbitrary degree sequence.

Uniform sampling from graphical realizations of a given degree sequence is a fundamental component in simulation-based measurements of network observables, with applications ranging from epidemics, through social networks to Internet modeling. Existing graph sampling methods are either link-swap based (Markov-Chain Monte Carlo algorithms) or stub-matching based (the Configuration Model). Both types are ill-controlled, with typically unknown mixing times for link-swap methods and uncontrolled rejections for the Configuration Model. Here we propose an efficient, polynomial time algorithm that generates statistically independent graph samples with a given, arbitrary, degree sequence. The algorithm provides a weight associated with each sample, allowing the observable to be measured either uniformly over the graph ensemble, or, alternatively, with a desired distribution. Unlike other algorithms, this method always produces a sample, without back-tracking or rejections. Using a central limit theorem-based reasoning, we argue, that for large , and for degree sequences admitting many realizations, the sample weights are expected to have a lognormal distribution. As examples, we apply our algorithm to generate networks with degree sequences drawn from power-law distributions and from binomial distributions.

Anomalous ordering in inhomogeneously strained materials.

We study a continuous quasi-two-dimensional order-disorder phase transition that occurs in a simple model of a material that is inhomogeneously strained due to the presence of dislocation lines. Performing Monte Carlo simulations of different system sizes and using finite size scaling, we measure critical exponents describing the transition of ß=0.18±0.02, γ=1.0±0.1, and α=0.10±0.02. Comparable exponents have been reported in a variety of physical systems. These systems undergo a range of different types of phase transitions, including structural transitions, exciton percolation, and magnetic ordering. In particular, similar exponents have been found to describe the development of magnetic order at the onset of the pseudogap transition in high-temperature superconductors. Their common universal critical exponents suggest that the essential physics of the transition in all of these physical systems is the same as in our simple model. We argue that the nature of the transition in our model is related to surface transitions although our model has no free surface.

Phase diagram for a two-dimensional, two-temperature, diffusive XY model.

Using Monte Carlo simulations, we determine the phase diagram of a diffusive two-temperature conserved order parameter XY model. When the two temperatures are equal the system becomes the equilibrium XY model with the continuous Kosterlitz-Thouless (KT) vortex-antivortex unbinding phase transition. When the two temperatures are unequal the system is driven by an energy flow from the higher temperature heat-bath to the lower temperature one and reaches a far-from-equilibrium steady state. We show that the nonequilibrium phase diagram contains three phases: A homogenous disordered phase and two phases with long range, spin texture order. Two critical lines, representing continuous phase transitions from a homogenous disordered phase to two phases of long range order, meet at the equilibrium KT point. The shape of the nonequilibrium critical lines as they approach the KT point is described by a crossover exponent φ=2.52±0.05. Finally, we suggest that the transition between the two phases with long-range order is first-order, making the KT-point where all three phases meet a bicritical point.

Collectively optimal routing for congested traffic limited by link capacity.

We show that the capacity of a complex network that models a city street grid to support congested traffic can be optimized by using routes that collectively minimize the maximum ratio of betweenness to capacity in any link. Networks with a heterogeneous distribution of link capacities and with a heterogeneous transport load are considered. We find that overall traffic congestion and average travel times can be significantly reduced by a judicious use of slower and smaller capacity links.

Nonstationary increments, scaling distributions, and variable diffusion processes in financial markets.

Fat-tailed distributions have been reported in fluctuations of financial markets for more than a decade. Sliding interval techniques used in these studies implicitly assume that the underlying stochastic process has stationary increments. Through an analysis of intraday increments, we explicitly show that this assumption is invalid for the Euro-Dollar exchange rate. We find several time intervals during the day where the standard deviation of increments exhibits power law behavior in time. Stochastic dynamics during these intervals is shown to be given by diffusion processes with a diffusion coefficient that depends on time and the exchange rate. We introduce methods to evaluate the dynamical scaling index and the scaling function empirically. In general, the scaling index is significantly smaller than previously reported values close to 0.5. We show how the latter as well as apparent fat-tailed distributions can occur only as artifacts of the sliding interval analysis.

Transport optimization on complex networks.

We present a comparative study of the application of a recently introduced heuristic algorithm to the optimization of transport on three major types of complex networks. The algorithm balances network traffic iteratively by minimizing the maximum node betweenness with as little path lengthening as possible. We show that by using this optimal routing, a network can sustain significantly higher traffic without jamming than in the case of shortest path routing. A formula is proved and tested with numerical simulation that allows quick computation of the average number of hops along the path and of the average travel times once the betweennesses of the nodes are computed. Using this formula, we show that routing optimization preserves the small-world character exhibited by networks under shortest path routing, and that it significantly reduces the average travel time on congested networks with only a negligible increase in the average travel time at low loads. Finally, we study the correlation between the weights of the links in the case of optimal routing and the betweennesses of the nodes connected by them.

Emergent criticality from coevolution in random Boolean networks.

The coevolution of network topology and dynamics is studied in an evolutionary Boolean network model that is a simple model of a gene regulatory network. We find that a critical state emerges spontaneously resulting from the interplay between topology and dynamics during the evolution. The final evolved state is shown to be independent of initial conditions. The network appears to be driven to a random Boolean network with uniform in-degree of 2 in the large-network limit. However, for biologically realized network sizes, significant finite-size effects are observed including a broad in-degree distribution and an average in-degree connections between 2 and 3. These results may be important for explaining the properties of gene regulatory networks.

Optimal transport on complex networks.

We present a heuristic algorithm for the optimization of transport on complex networks. Previously proposed network transport optimization algorithms aim at avoiding or reducing link overload. Our algorithm balances traffic on a network by minimizing the maximum node betweenness with as little path lengthening as possible, thus being useful in cases when networks are jamming due to node congestion. By using the resulting routing, a network can sustain significantly higher traffic without jamming than in the case of shortest path routing.