Search

A diverse variety of processes-including recurrent disease episodes, neuron firing, and communication patterns among humans-can be described using interevent time (IET) distributions. Many such processes are ongoing, although event sequences are only available during a finite observation window. Because the observation time window is more likely to begin or end during long IETs than during short ones, the analysis of such data is susceptible to a bias induced by the finite observation period. In this paper, we illustrate how this length bias is born and how it can be corrected without assuming any particular shape for the IET distribution. To do this, we model event sequences using stationary renewal processes, and we formulate simple heuristics for determining the severity of the bias. To illustrate our results, we focus on the example of empirical communication networks, which are temporal networks that are constructed from communication events. The IET distributions of such systems guide efforts to build models of human behavior, and the variance of IETs is very important for estimating the spreading rate of information in networks of temporal interactions. We analyze several well-known data sets from the literature, and we find that the resulting bias can lead to systematic underestimates of the variance in the IET distributions and that correcting for the bias can lead to qualitatively different results for the tails of the IET distributions.

It is common in the study of networks to investigate intermediate-sized (or "meso-scale") features to try to gain an understanding of network structure and function. For example, numerous algorithms have been developed to try to identify "communities," which are typically construed as sets of nodes with denser connections internally than with the remainder of a network. In this paper, we adopt a complementary perspective that communities are associated with bottlenecks of locally biased dynamical processes that begin at seed sets of nodes, and we employ several different community-identification procedures (using diffusion-based and geodesic-based dynamics) to investigate community quality as a function of community size. Using several empirical and synthetic networks, we identify several distinct scenarios for "size-resolved community structure" that can arise in real (and realistic) networks: (1) the best small groups of nodes can be better than the best large groups (for a given formulation of the idea of a good community); (2) the best small groups can have a quality that is comparable to the best medium-sized and large groups; and (3) the best small groups of nodes can be worse than the best large groups. As we discuss in detail, which of these three cases holds for a given network can make an enormous difference when investigating and making claims about network community structure, and it is important to take this into account to obtain reliable downstream conclusions. Depending on which scenario holds, one may or may not be able to successfully identify "good" communities in a given network (and good communities might not even exist for a given community quality measure), the manner in which different small communities fit together to form meso-scale network structures can be very different, and processes such as viral propagation and information diffusion can exhibit very different dynamics. In addition, our results suggest that, for many large realistic networks, the output of locally biased methods that focus on communities that are centered around a given seed node (or set of seed nodes) might have better conceptual grounding and greater practical utility than the output of global community-detection methods. They also illustrate structural properties that are important to consider in the development of better benchmark networks to test methods for community detection.

Networks often possess mesoscale structures, and studying them can yield insights into both structure and function. It is most common to study community structure, but numerous other types of mesoscale structures also exist. In this paper, we examine core-periphery structures based on both density and transport. In such structures, core network components are well-connected both among themselves and to peripheral components, which are not well-connected to anything. We examine core-periphery structures in a wide range of examples of transportation, social, and financial networks-including road networks in large urban areas, a rabbit warren, a dolphin social network, a European interbank network, and a migration network between counties in the United States. We illustrate that a recently developed transport-based notion of node coreness is very useful for characterizing transportation networks. We also generalize this notion to examine core versus peripheral edges, and we show that the resulting diagnostic is also useful for transportation networks. To examine the properties of transportation networks further, we develop a family of generative models of roadlike networks. We illustrate the effect of the dimensionality of the embedding space on transportation networks, and we demonstrate that the correlations between different measures of coreness can be very different for different types of networks.

We investigate algorithms to find short paths in spatial networks with stochastic edge weights. Our formulation of the problem of finding short paths differs from traditional formulations because we specifically do not make two of the usual simplifying assumptions: (1) we allow edge weights to be stochastic rather than deterministic and (2) we do not assume that global knowledge of a network is available. We develop a decentralized routing algorithm that provides en route guidance for travelers on a spatial network with stochastic edge weights without the need to rely on global knowledge about the network. To guide a traveler, our algorithm uses an estimation function that evaluates cumulative arrival probability distributions based on distances between pairs of nodes. The estimation function carries a notion of proximity between nodes and thereby enables routing without global knowledge. In testing our decentralized algorithm, we define a criterion that makes it possible to discriminate among arrival probability distributions, and we test our algorithm and this criterion using both synthetic and real networks.

We study ensembles of globally coupled, nonidentical phase oscillators subject to correlated noise, and we identify several important factors that cause noise and coupling to synchronize or desynchronize a system. By introducing noise in various ways, we find an estimate for the onset of synchrony of a system in terms of the coupling strength, noise strength, and width of the frequency distribution of its natural oscillations. We also demonstrate that noise alone can be sufficient to synchronize nonidentical oscillators. However, this synchrony depends on the first Fourier mode of a phase-sensitivity function, through which we introduce common noise into the system. We show that higher Fourier modes can cause desynchronization due to clustering effects, and that this can reinforce clustering caused by different forms of coupling. Finally, we discuss the effects of noise on an ensemble in which antiferromagnetic coupling causes oscillators to form two clusters in the absence of noise.

The traditional way of studying temporal networks is to aggregate the dynamics of the edges to create a static weighted network. This implicitly assumes that the edges are governed by Poisson processes, which is not typically the case in empirical temporal networks. Accordingly, we examine the effects of non-Poisson inter-event statistics on the dynamics of edges, and we apply the concept of a generalized master equation to the study of continuous-time random walks on networks. We show that this equation reduces to the standard rate equations when the underlying process is Poissonian and that its stationary solution is determined by an effective transition matrix whose leading eigenvector is easy to calculate. We conduct numerical simulations and also derive analytical results for the stationary solution under the assumption that all edges have the same waiting-time distribution. We discuss the implications of our work for dynamical processes on temporal networks and for the construction of network diagnostics that take into account their nontrivial stochastic nature.

Granular media, whose features range from the particle scale to the force-chain scale and the bulk scale, are usually modeled as either particulate or continuum materials. In contrast with each of these approaches, network representations are natural for the simultaneous examination of microscopic, mesoscopic, and macroscopic features. In this paper, we treat granular materials as spatially embedded networks in which the nodes (particles) are connected by weighted edges obtained from contact forces. We test a variety of network measures to determine their utility in helping to describe sound propagation in granular networks and find that network diagnostics can be used to probe particle-, curve-, domain-, and system-scale structures in granular media. In particular, diagnostics of mesoscale network structure are reproducible across experiments, are correlated with sound propagation in this medium, and can be used to identify potentially interesting size scales. We also demonstrate that the sensitivity of network diagnostics depends on the phase of sound propagation. In the injection phase, the signal propagates systemically, as indicated by correlations with the network diagnostic of global efficiency. In the scattering phase, however, the signal is better predicted by mesoscale community structure, suggesting that the acoustic signal scatters over local geographic neighborhoods. Collectively, our results demonstrate how the force network of a granular system is imprinted on transmitted waves.

The study of networks has become a substantial interdisciplinary endeavor that encompasses myriad disciplines in the natural, social, and information sciences. Here we introduce a framework for constructing taxonomies of networks based on their structural similarities. These networks can arise from any of numerous sources: They can be empirical or synthetic, they can arise from multiple realizations of a single process (either empirical or synthetic), they can represent entirely different systems in different disciplines, etc. Because mesoscopic properties of networks are hypothesized to be important for network function, we base our comparisons on summaries of network community structures. Although we use a specific method for uncovering network communities, much of the introduced framework is independent of that choice. After introducing the framework, we apply it to construct a taxonomy for 746 networks and demonstrate that our approach usefully identifies similar networks. We also construct taxonomies within individual categories of networks, and we thereby expose nontrivial structure. For example, we create taxonomies for similarity networks constructed from both political voting data and financial data. We also construct network taxonomies to compare the social structures of 100 Facebook networks and the growth structures produced by different types of fungi.

Mean-field analysis is an important tool for understanding dynamics on complex networks. However, surprisingly little attention has been paid to the question of whether mean-field predictions are accurate, and this is particularly true for real-world networks with clustering and modular structure. In this paper, we compare mean-field predictions to numerical simulation results for dynamical processes running on 21 real-world networks and demonstrate that the accuracy of such theory depends not only on the mean degree of the networks but also on the mean first-neighbor degree. We show that mean-field theory can give (unexpectedly) accurate results for certain dynamics on disassortative real-world networks even when the mean degree is as low as 4.

We investigate financial market correlations using random matrix theory and principal component analysis. We use random matrix theory to demonstrate that correlation matrices of asset price changes contain structure that is incompatible with uncorrelated random price changes. We then identify the principal components of these correlation matrices and demonstrate that a small number of components accounts for a large proportion of the variability of the markets that we consider. We characterize the time-evolving relationships between the different assets by investigating the correlations between the asset price time series and principal components. Using this approach, we uncover notable changes that occurred in financial markets and identify the assets that were significantly affected by these changes. We show in particular that there was an increase in the strength of the relationships between several different markets following the 2007-2008 credit and liquidity crisis.

We demonstrate that a tree-based theory for various dynamical processes operating on static, undirected networks yields extremely accurate results for several networks with high levels of clustering. We find that such a theory works well as long as the mean intervertex distance ℓ is sufficiently small--that is, as long as it is close to the value of ℓ in a random network with negligible clustering and the same degree-degree correlations. We support this hypothesis numerically using both real-world networks from various domains and several classes of synthetic clustered networks. We present analytical calculations that further support our claim that tree-based theories can be accurate for clustered networks, provided that the networks are "sufficiently small" worlds.

We present a systematic study of the existence and stability of discrete breathers that are spatially localized in the bulk of a one-dimensional chain of compressed elastic beads that interact via Hertzian contact. The chain is diatomic, consisting of a periodic arrangement of heavy and light spherical particles. We examine two families of discrete gap breathers: (1) an unstable discrete gap breather that is centered on a heavy particle and characterized by a symmetric spatial energy profile and (2) a potentially stable discrete gap breather that is centered on a light particle and is characterized by an asymmetric spatial energy profile. We investigate their existence, structure, and stability throughout the band gap of the linear spectrum and classify them into four regimes: a regime near the lower optical band edge of the linear spectrum, a moderately discrete regime, a strongly discrete regime that lies deep within the band gap of the linearized version of the system, and a regime near the upper acoustic band edge. We contrast discrete breathers in anharmonic Fermi-Pasta-Ulam (FPU)-type diatomic chains with those in diatomic granular crystals, which have a tensionless interaction potential between adjacent particles, and note that the asymmetric nature of the tensionless interaction potential can lead to hybrid bulk-surface localized solutions.

We investigate the propagation and scattering of highly nonlinear waves in disordered granular chains composed of diatomic (two-mass) units of spheres that interact via Hertzian contact. Using ideas from statistical mechanics, we consider each diatomic unit to be a "spin," so that a granular chain can be viewed as a spin chain composed of units that are each oriented in one of two possible ways. Experiments and numerical simulations both reveal the existence of two different mechanisms of wave propagation: in low-disorder chains, we observe the propagation of a solitary pulse with exponentially decaying amplitude. Beyond a critical level of disorder, the wave amplitude instead decays as a power law, and the wave transmission becomes insensitive to the level of disorder. We characterize the spatiotemporal structure of the wave in both propagation regimes and propose a simple theoretical interpretation for a transition between the two regimes. Our investigation suggests that an elastic spin chain can be used as a model system to investigate the role of heterogeneities in the propagation of highly nonlinear waves.

We study localized modes in uniform one-dimensional chains of tightly packed and uniaxially compressed elastic beads in the presence of one or two light-mass impurities. For chains composed of beads of the same type, the intrinsic nonlinearity, which is caused by the Hertzian interaction of the beads, appears not to support localized, breathing modes. Consequently, the inclusion of light-mass impurities is crucial for their appearance. By analyzing the problem's linear limit, we identify the system's eigenfrequencies and the linear defect modes. Using continuation techniques, we find the solutions that bifurcate from their linear counterparts and study their linear stability in detail. We observe that the nonlinearity leads to a frequency dependence in the amplitude of the oscillations, a static mutual displacement of the parts of the chain separated by a defect, and for chains with two defects that are not in contact, it induces symmetry-breaking bifurcations.

We formulate a spectral graph-partitioning algorithm that uses the two leading eigenvectors of the matrix corresponding to a selected quality function to split a network into three communities in a single step. In so doing, we extend the recursive bipartitioning methods developed by Newman [M. E. J. Newman, Proc. Natl. Acad. Sci. U.S.A. 103, 8577 (2006); Phys. Rev. E 74, 036104 (2006)] to allow one to consider the best available two-way and three-way divisions at each recursive step. We illustrate the method using simple "bucket brigade" examples and then apply the algorithm to examine the community structures of the coauthorship graph of network scientists and of U. S. Congressional networks inferred from roll call voting similarities.

We investigate the propagation of highly nonlinear solitary waves in heterogeneous, periodic granular media using experiments, numerical simulations, and theoretical analysis. We examine periodic arrangements of particles in experiments in which stiffer and heavier beads (stainless steel) are alternated with softer and lighter ones (polytetrafluoroethylene beads). We find good agreement between experiments and numerics in a model with Hertzian interactions between adjacent beads, which in turn agrees very well with a theoretical analysis of the model in the long-wavelength regime that we derive for heterogeneous environments and general bead interactions. Our analysis encompasses previously studied examples as special cases and also provides key insights into the influence of the dimer lattice on the properties (width and propagation speed) of the highly nonlinear wave solutions.

We analyze gap solitons in trapped Bose-Einstein condensates (BECs) in optical lattice potentials under Feshbach resonance management. Starting with an averaged Gross-Pitaevsky equation with a periodic potential, we employ an envelope-wave approximation to derive coupled-mode equations describing the slow BEC dynamics in the first spectral gap of the optical lattice. We construct exact analytical formulas describing gap soliton solutions and examine their spectral stability using the Chebyshev interpolation method. We show that these gap solitons are unstable far from the threshold of local bifurcation and that the instability results in the distortion of their shape. We also predict the threshold of the power of gap solitons near the local bifurcation limit.

We analyze spatiotemporal structures in the Gross-Pitaevskii equation to study the dynamics of quasi-one-dimensional Bose-Einstein condensates (BECs) with mean-field interactions. A coherent structure ansatz yields a parametrically forced nonlinear oscillator, to which we apply Lindstedt's method and multiple-scale perturbation theory to determine the dependence of the intensity of periodic orbits ("modulated amplitude waves") on their wave number. We explore BEC band structure in detail using Hamiltonian perturbation theory and supporting numerical simulations.