Nonlinear Laplacian for Digraphs and Its Applications to Network Analysis
| Title | Nonlinear Laplacian for Digraphs and Its Applications to Network Analysis |
| Publication Type | Conference Paper |
| Year of Publication | 2016 |
| Authors | Yoshida, Yuichi |
| Conference Name | Proceedings of the Ninth ACM International Conference on Web Search and Data Mining |
| Date Published | February 2016 |
| Publisher | ACM |
| Conference Location | New York, NY, USA |
| ISBN Number | 978-1-4503-3716-8 |
| Keywords | graph, graph theory, Human Behavior, malware analysis, Metrics, privacy, pubcrawl, Resiliency, spectral, theory |
| Abstract | 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. |
| URL | https://dl.acm.org/doi/10.1145/2835776.2835785 |
| DOI | 10.1145/2835776.2835785 |
| Citation Key | yoshida_nonlinear_2016 |