Abstract

We will discuss the statistics and ergodicity properties of cycles in the topology of large-scale graphs, and likewise the roles of communities and subcommunities in understanding large-scale graphs. In “Statistics of Cycles: How Loopy is your Network?” we study the distribution of cycles of length \( h \) in large networks (of size \( N \gg 1 \)) and find it to be an excellent ergodic estimator, even in the extremely inhomogeneous case of scale-free networks. The distribution is sharply peaked around a characteristic cycle length, \( h_m \sim N^{\alpha} \).

We will also discuss “Communication and Synchronization in Disconnected Networks with Dynamic Topology: Moving Neighborhood Networks,” in which we consider systems that are well modeled as networks that evolve in time, which we call \( \textit{Moving Neighborhood Networks} \). These models are relevant in studying cooperative behavior of swarms and other phenomena where emergent interactions arise from ad hoc networks. The question is whether information can manage to propagate through an instantaneously disconnected network. We prove that if a network of oscillators synchronizes for the static time-average of the topology, then the network will synchronize with the time-varying topology if the time-average is achieved sufficiently fast. Fast switching, fast on the time-scale of the coupled oscillators, overcomes the desynchronizing decoherence suggested by instantaneously disconnected networks. Our new fast-switching stability criterion gives sufficiency of a fast-switching network leading to synchronization.