The Interplay Between Dynamics and Networks: Centrality, Communities, and Cheeger Inequality

Abstract

We study the interplay between a dynamic process and the structure of the network on which it is defined. Specifically, we examine the impact of this interaction on the quality-measure of network clusters and node centrality. This enables us to effectively identify network communities and important nodes participating in the dynamics. As the first step towards this objective, we introduce an umbrella framework for defining and characterizing an ensemble of dynamic processes on a network. This framework generalizes the traditional Laplacian framework to continuous-time biased random walks and also allows us to model some epidemic processes over a network. For each dynamic process in our framework, we can define a function that measures the quality of every subset of nodes as a potential cluster (or community) with respect to this process on a given network. This 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 from the Laplacian-conductance setting to this more general setting.

arXiv commentThis is the full length version. A shorter conference paper appeared in ACM-SIGKDD 2014

References in corpus (10)

• Community detection in graphs
• Cooperative Game Theory Approaches for Network Partitioning
• Mixing patterns in networks
• Synchronization reveals topological scales in complex networks
• Network Synchronization, Diffusion, and the Paradox of Heterogeneity
• Entropy Rate of Diffusion Processes on Complex Networks
• Localization of maximal entropy random walk
• Flow graphs: interweaving dynamics and structure
• A Parameterized Centrality Metric for Network Analysis
• Spectral Clustering with Epidemic Diffusion

Cited by in corpus (9)

• Current Flow Group Closeness Centrality for Complex Networks
• CenGCN: Centralized Convolutional Networks with Vertex Imbalance for Scale-Free Graphs
• Graph Filters and the Z-Laplacian
• Generalized patterns from local and non local reactions
• Fixed-Points of Social Choice: An Axiomatic Approach to Network Communities
• Network Composition from Multi-layer Data
• Maximizing the Smallest Eigenvalue of Grounded Laplacian Matrix
• Spectral Algorithms for Temporal Graph Cuts
• Modeling the Interplay Between Individual Behavior and Network Distributions