Graph conductance, synchronization, and a new bottleneck measure
Abstract
As a quantification of the main bottleneck to flow over a graph, the network property of conductance plays an important role in the process of synchronization of network-coupled dynamical systems. Diffusive coupling terms serve not only to exchange information between nodes within a networked system, but ultimately to dissipate the entropy of the collective dynamic state down toward that which can be associated with a single dynamic node when the synchronization manifold is stable. While the graph conductance can characterize the coupling strength that is required to maintain widespread synchronization across a majority of the nodes in such a system, it offers no guarantee for a stable synchronization manifold, which involves all nodes in the system. We define a new measure called the synchronization bottleneck of a graph, which we denote by $\Xi$; this new network property provides a quantification of the limiting bottleneck of the flow between any subset of nodes (regardless of its order) and the rest of the networked system. This quantity does control the coupling strength required for a stable synchronization manifold for a large class of dynamical systems. Solving for this quantity is combinatorial, as is the case with conductance, but heuristics based on this optimization problem can guide decentralized strategies for improving global synchronizability.