Visible to the public Nonlinear Laplacian for Digraphs and Its Applications to Network Analysis

TitleNonlinear Laplacian for Digraphs and Its Applications to Network Analysis
Publication TypeConference Paper
Year of Publication2016
AuthorsYoshida, Yuichi
Conference NameProceedings of the Ninth ACM International Conference on Web Search and Data Mining
Date PublishedFebruary 2016
Conference LocationNew York, NY, USA
ISBN Number978-1-4503-3716-8
Keywordsgraph, graph theory, Human Behavior, malware analysis, Metrics, privacy, pubcrawl, Resiliency, spectral, theory

In this work, we introduce a new Markov operator associated with a digraph, which we refer to as a nonlinear Laplacian. Unlike previous Laplacians for digraphs, the nonlinear Laplacian does not rely on the stationary distribution of the random walk process and is well defined on digraphs that are not strongly connected. We show that the nonlinear Laplacian has nontrivial eigenvalues and give a Cheeger-like inequality, which relates the conductance of a digraph and the smallest non-zero eigenvalue of its nonlinear Laplacian. Finally, we apply the nonlinear Laplacian to the analysis of real-world networks and obtain encouraging results.

Citation Keyyoshida_nonlinear_2016