Picture of DNA strand

Pioneering chemical biology & medicinal chemistry through Open Access research...

Strathprints makes available scholarly Open Access content by researchers in the Department of Pure & Applied Chemistry, based within the Faculty of Science.

Research here spans a wide range of topics from analytical chemistry to materials science, and from biological chemistry to theoretical chemistry. The specific work in chemical biology and medicinal chemistry, as an example, encompasses pioneering techniques in synthesis, bioinformatics, nucleic acid chemistry, amino acid chemistry, heterocyclic chemistry, biophysical chemistry and NMR spectroscopy.

Explore the Open Access research of the Department of Pure & Applied Chemistry. Or explore all of Strathclyde's Open Access research...

Consensus dynamics on random rectangular graphs

Estrada, Ernesto and Sheerin, Matthew (2015) Consensus dynamics on random rectangular graphs. Physica D: Nonlinear Phenomena. ISSN 0167-2789

[img]
Preview
Text (Estrada-Sheerin-PDNP-2015-Consensus-dynamics-on-random-rectangular)
Estrada_Sheerin_PDNP_2015_Consensus_dynamics_on_random_rectangular.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo

Download (1MB)| Preview

    Abstract

    A random rectangular graph (RRG) is a generalization of the random geometric graph (RGG) in which the nodes are embedded into a rectangle with side lengths aa and b=1/ab=1/a, instead of on a unit square [0,1]2. Two nodes are then connected if and only if they are separated at a Euclidean distance smaller than or equal to a certain threshold radius r. When a=1 the RRG is identical to the RGG. Here we apply the consensus dynamics model to the RRG. Our main result is a lower bound for the time of consensus, i.e., the time at which the network reaches a global consensus state. To prove this result we need first to find an upper bound for the algebraic connectivity of the RRG, i.e., the second smallest eigenvalue of the combinatorial Laplacian of the graph. This bound is based on a tight lower bound found for the graph diameter. Our results prove that as the rectangle in which the nodes are embedded becomes more elongated, the RRG becomes a ’large-world’, i.e., the diameter grows to infinity, and a poorly-connected graph, i.e., the algebraic connectivity decays to zero. The main consequence of these findings is the proof that the time of consensus in RRGs grows to infinity as the rectangle becomes more elongated. In closing, consensus dynamics in RRGs strongly depend on the geometric characteristics of the embedding space, and reaching the consensus state becomes more difficult as the rectangle is more elongated.