Entropy of labeled versus unlabeled networks.

The structure of a network is an unlabeled graph, yet graphs in most models of complex networks are labeled by meaningless random integers. Is the associated labeling noise always negligible, or can it overpower the network-structural signal? To address this question, we introduce and consider the sparse unlabeled versions of popular network models and compare their entropy against the original labeled versions. We show that labeled and unlabeled Erdos-Rényi graphs are entropically equivalent, even though their degree distributions are very different. The labeled and unlabeled versions of the configuration model may have different prefactors in their leading entropy terms, although this remains conjectural. Our main results are upper and lower bounds for the entropy of labeled and unlabeled one-dimensional random geometric graphs. We show that their unlabeled entropy is negligible in comparison with the labeled entropy. This means that in sparse networks the entropy of meaningless labeling may dominate the entropy of the network structure. The main implication of this result is that the common practice of using exchangeable models to reason about real-world networks with distinguishable nodes may introduce uncontrolled aberrations into conclusions made about these networks, suggesting a need for a thorough reexamination of the statistical foundations and key results of network science.

Dynamics of cold random hyperbolic graphs with link persistence.

We consider and analyze a dynamic model of random hyperbolic graphs with link persistence. In the model, both connections and disconnections can be propagated from the current to the next snapshot with probability ω∈[0,1). Otherwise, with probability 1-ω, connections are reestablished according to the random hyperbolic graphs model. We show that while the persistence probability ω affects the averages of the contact and intercontact distributions, it does not affect the tails of these distributions, which decay as power laws with exponents that do not depend on ω. We also consider examples of real temporal networks, and we show that the considered model can adequately reproduce several of their dynamical properties. Our results advance our understanding of the realistic modeling of temporal networks and of the effects of link persistence on temporal network properties.

Dynamic hidden-variable network models.

Models of complex networks often incorporate node-intrinsic properties abstracted as hidden variables. The probability of connections in the network is then a function of these variables. Real-world networks evolve over time and many exhibit dynamics of node characteristics as well as of linking structure. Here we introduce and study natural temporal extensions of static hidden-variable network models with stochastic dynamics of hidden variables and links. The dynamics is controlled by two parameters: one that tunes the rate of change of hidden variables and another that tunes the rate at which node pairs reevaluate their connections given the current values of hidden variables. Snapshots of networks in the dynamic models are equivalent to networks generated by the static models only if the link reevaluation rate is sufficiently larger than the rate of hidden-variable dynamics or if an additional mechanism is added whereby links actively respond to changes in hidden variables. Otherwise, links are out of equilibrium with respect to hidden variables and network snapshots exhibit structural deviations from the static models. We examine the level of structural persistence in the considered models and quantify deviations from staticlike behavior. We explore temporal versions of popular static models with community structure, latent geometry, and degree heterogeneity. While we do not attempt to directly model real networks, we comment on interesting qualitative resemblances to real systems. In particular, we speculate that links in some real networks are out of equilibrium with respect to hidden variables, partially explaining the presence of long-ranged links in geometrically embedded systems and intergroup connectivity in modular systems. We also discuss possible extensions, generalizations, and applications of the introduced class of dynamic network models.

Network comparison and the within-ensemble graph distance.

Quantifying the differences between networks is a challenging and ever-present problem in network science. In recent years, a multitude of diverse, ad hoc solutions to this problem have been introduced. Here, we propose that simple and well-understood ensembles of random networks-such as Erdos-Rényi graphs, random geometric graphs, Watts-Strogatz graphs, the configuration model and preferential attachment networks-are natural benchmarks for network comparison methods. Moreover, we show that the expected distance between two networks independently sampled from a generative model is a useful property that encapsulates many key features of that model. To illustrate our results, we calculate this within-ensemble graph distance and related quantities for classic network models (and several parameterizations thereof) using 20 distance measures commonly used to compare graphs. The within-ensemble graph distance provides a new framework for developers of graph distances to better understand their creations and for practitioners to better choose an appropriate tool for their particular task.

Transient chaos and associated system-intrinsic switching of spacetime patterns in two synaptically coupled layers of Morris-Lecar neurons.

Spatiotemporal chaos collapses to either a rest state or a propagating pulse solution in a single layer of diffusively coupled, excitable Morris-Lecar neurons. Weak synaptic coupling of two such layers reveals system intrinsic switching of spatiotemporal activity patterns within and between the layers at irregular times. Within a layer, switching sequences include spatiotemporal chaos, erratic and regular pulse propagation, spontaneous network wide neuron activity, and rest state. A momentary substantial reduction in neuron activity in one layer can reinitiate transient spatiotemporal chaos in the other layer, which can induce a swap of spatiotemporal chaos with a pulse state between the layers. Presynaptic input maximizes the distance between propagating pulses, in contrast to pulse merging in the absence of synapses.