Deformed Laplacians and spectral ranking in directed networks

DOI10.1016/J.ACHA.2017.09.002MaRDI QIDQ2325540zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(5)

• scientific article; zbMATH DE number 7370536 (Why is no real title available?)
• 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)