Deformed Laplacians and spectral ranking in directed networks

DOI10.1016/J.ACHA.2017.09.002zbMATH Open1433.05191arXiv1511.00492OpenAlexW2442203778MaRDI QIDQ2325540FDOQ2325540

Authors: Michaël Fanuel, Johan A. K. Suykens 

Publication date: 26 September 2019

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Abstract: A deformation of the combinatorial Laplacian is proposed, consisting in a generalization of several existing Laplacians. As particular cases of this construction, the dilation Laplacians are shown to be useful tools for ranking in directed networks of pairwise comparisons. The eigenvector with the smallest eigenvalue of the dilation Laplacians has the same sign on any connected graph, and provides directly a ranking score of its nodes. The ranking method, phrased in terms of a group synchronization problem, is applied to artificial and real data, and its performance is compared with other ranking strategies. A main feature of this approach is the presence of a deformation parameter enabling the emphasis of the top-$k$ objects in the ranking. Furthermore, inspired by these results, a family of random walks interpolating between the undirected random walk and the Pagerank random walk is also proposed.

Full work available at URL: https://arxiv.org/abs/1511.00492

Recommendations

• The deformed graph Laplacian and its applications to network centrality analysis
• On the graph Laplacian and the rankability of data
• Statistical ranking and combinatorial Hodge theory
• Ranking nodes in general networks: a Markov multi-chain approach
• Statistical ranking using the \(\ell^{1}\)-norm on graphs

zbMATH Keywords

rankingrandom walkssynchronizationdirected graphsdiscrete Laplacians

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Random walks on graphs (05C81)

Cites Work

• Title not available (Why is that?)
• Morse theory for cell complexes
• Statistical ranking and combinatorial Hodge theory
• Supersymmetry and Morse theory
• Title not available (Why is that?)
• Magnetic interpretation of the nodal defect on graphs
• Title not available (Why is that?)
• Max-algebra and pairwise comparison matrices
• Vector diffusion maps and the connection Laplacian
• Geometric diffusions as a tool for harmonic analysis and structure definition of data: diffusion maps
• Cramer-Rao bounds for synchronization of rotations
• A Cheeger Inequality for the Graph Connection Laplacian
• Manifold regularization: a geometric framework for learning from labeled and unlabeled examples
• Spanning forests and the vector bundle Laplacian
• Witten-Morse theory for cell complexes
• Nodal count of graph eigenfunctions via magnetic perturbation
• Discrete magnetic Laplacian
• Optimal data collection for informative rankings expose well-connected graphs
• Analysis of crowdsourced sampling strategies for HodgeRank with sparse random graphs
• Spectral ranking using seriation
• HodgeRank is the limit of Perron Rank

Cited In (5)

• Title not available (Why is that?)
• Hermitian normalized Laplacian matrix for directed networks
• The geometry of synchronization problems and learning group actions
• An extension of the angular synchronization problem to the heterogeneous setting
• On the graph Laplacian and the rankability of data

This page was built for publication: Deformed Laplacians and spectral ranking in directed networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2325540)