‘Hubs-repelling’ Laplacian and related diffusion on graphs/networks

Linear Algebra and its Applications 596 (2020) 256–280

We define and study here a graph unsymmetric Laplacian matrix that operates a diffusive process biased towards low-degree nodes. We prove that this matrix is positive semidefine with all eigenvalues real. We also prove that the rate of convergence of a diffusive process controlled by the hubs-repelling Laplacian depends on the first nontrivial eigenvalue of this Laplacian. Such rate of convergence depends on the existence of low-degree nodes connected to high-degree ones. We find several bounds for the ‘algebraic connectivity’ based on this Laplacian. We then study two real-world scenarios with the hubs-repelling diffusion: the propagation of flight delays in the air transportation network of USA and the cost-efficient information diffusion across the human brain functional coactivation network. Finally, we find some conditions for the nodes of a network to be ‘good spreaders’ under the hubs-repelling dynamics.

We define and study here a graph unsymmetric Laplacian matrix that operates a diffusive process biased towards low-degree nodes. We prove that this matrix is positive semidefine with all eigenvalues real. We also prove that the rate of convergence of a diffusive process controlled by the hubs-repelling Laplacian depends on the first nontrivial eigenvalue of this Laplacian. Such rate of convergence depends on the existence of low-degree nodes connected to high-degree ones. We find several bounds for the ‘algebraic connectivity’ based on this Laplacian. We then study two real-world scenarios with the hubs-repelling diffusion: the propagation of flight delays in the air transportation network of USA and the cost-efficient information diffusion across the human brain functional coactivation network. Finally, we find some conditions for the nodes of a network to be ‘good spreaders’ under the hubs-repelling dynamics.