When local and global clustering of networks diverge

Estrada, Ernesto (2016) When local and global clustering of networks diverge. Linear Algebra and its Applications, 488. pp. 249-263. ISSN 0024-3795

[img]
Preview
Text (Estrada-LAA2015-when-local-and-global-clustering-of-networks-diverge)
Estrada_LAA2015_when_local_and_global_clustering_of_networks_diverge.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo

Download (173kB)| Preview

    Abstract

    The average Watts-Strogatz clustering coecient and the network transitivity are widely used descriptors for characterizing the transitivity of relations in real-world graphs (networks). These indices are bounded between zero and one, with low values indicating poor transtivity and large ones indicating a high proportion of closed triads in the graphs. Here, we prove that these two indices diverge for windmill graphs when the number of nodes tends to infinity. We also give evidence that this divergence occurs in many real-world networks, especially in citation and collaboration graphs. We obtain analytic expressions for the eigenvalues and eigenvectors of the adjacency and the Laplacian matrices of the windmill graphs. Using this information we show the main characteristics of two dynamical processes when taking place on windmill graphs: synchronization and epidemic spreading. Finally, we show that many of the structural and dynamical properties of a real-world citation network are well reproduced by the appropriate windmill graph, showing the potential of these graphs as models for certain classes of real-world networks.