SHEEP: Signed Hamiltonian Eigenvector Embedding for Proximity

arXiv2302.07129MaRDI QIDQ6426438FDOQ6426438

Authors: Shazia'Ayn Babul, Renaud Lambiotte 

Publication date: 14 February 2023

Abstract: We introduce a spectral embedding algorithm for finding proximal relationships between nodes in signed graphs, where edges can take either positive or negative weights. Adopting a physical perspective, we construct a Hamiltonian which is dependent on the distance between nodes, such that relative embedding distance results in a similarity metric between nodes. The Hamiltonian admits a global minimum energy configuration, which can be reconfigured as an eigenvector problem, and therefore is computationally efficient to compute. We use matrix perturbation theory to show that the embedding generates a ground state energy, which can be used as a statistical test for the presence of strong balance, and to develop an energy-based approach for locating the optimal embedding dimension. Finally, we show through a series of experiments on synthetic and empirical networks, that the resulting position in the embedding can be used to recover certain continuous node attributes, and that the distance to the origin in the optimal embedding gives a measure of node extremism.

This page was built for publication: SHEEP: Signed Hamiltonian Eigenvector Embedding for Proximity

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