Signed graph embedding, when everybody can sit closer to friends than enemies

10^th January 2013, 16:00 Ashton Lecture Theatre
Dr. Christopher Thraves Caro
Rey Juan Carlos University,
Madrid
Spain

Abstract

Signed graphs are graphs with signed edges. They are commonly used to
represent positive and negative relationships in social networks. While
balance theory and clusterizable graphs deal with signed graphs, recent
empirical studies have proved that they fail to reflect some current
practices in real social networks. In this presentation we address the
issue of drawing signed graphs and capturing such social interactions. We
relax the previous assumptions to define an embedding as a model in which
every vertex has to be placed closer to its neighbors connected via a
positive edge than its neighbors connected via a negative edge in the
resulting space. Based on this definition, we address the problem of
deciding whether a given signed graph has a drawing in the 1-dimensional
Euclidean space. We provide a polynomial time algorithm that decides if a
given complete signed graph has a drawing, and provides it when
applicable. When the input signed graph is not complete the
recognition problem has
been proved to be NP-complete. We provide a greedy heuristic that shows
interesting recognition capabilities when the input is not complete.