Capturing the interplay of dynamics and networks through parameterizations of Laplacian operators

PeerJ Computer Science

Shang-hua Teng¹  Kristina Lerman²  Rumi Ghosh³  Xiaoran Yan⁴ 

[1] Computer Science Department, University of Southern California, Marina Del Rey, CA, United States;Information Sciences Institute, University of Southern California, Marina Del Rey, CA, United States;Robert Bosch, LLC, Palo Alto, CA, United States;School of Informatics and Computing, Indiana University, Bloomington, IN, United States;

关键词: Network;    Community structure;    Spectral graph theory;    Centrality;    Dynamical process;   

DOI  :  10.7717/peerj-cs.57

来源: DOAJ

【 摘 要 】

We study the interplay between a dynamical process and the structure of the network on which it unfolds using the parameterized Laplacian framework. This framework allows for defining and characterizing an ensemble of dynamical processes on a network beyond what the traditional Laplacian is capable of modeling. This, in turn, allows for studying the impact of the interaction between dynamics and network topology on the quality-measure of network clusters and centrality, in order to effectively identify important vertices and communities in the network. Specifically, for each dynamical process in this framework, we define a centrality measure that captures a vertex’s participation in the dynamical process on a given network and also define a function that measures the quality of every subset of vertices as a potential cluster (or community) with respect to this process. We show that the subset-quality function generalizes the traditional conductance measure for graph partitioning. We partially justify our choice of the quality function by showing that the classic Cheeger’s inequality, which relates the conductance of the best cluster in a network with a spectral quantity of its Laplacian matrix, can be extended to the parameterized Laplacian. The parameterized Laplacian framework brings under the same umbrella a surprising variety of dynamical processes and allows us to systematically compare the different perspectives they create on network structure.

【 授权许可】

Unknown