The shortest path in signed graphs

Abstract

This paper addresses the shortest path problem in a signed graph. Signed graphs are suitable for representing positive/trust and negative/mistrust relationships among the various entities (vertices) of a network. The shortest path in a signed graph can be used to understand how successive relations, even if distant, affect the dynamics of the network. More precisely, the idea is to understand how the relation between any two entities is affected when connected through a signed shortest path. We describe ILP models to obtain positive and negative shortest paths in a signed graph between all pairs of vertices. We evaluate the ILP models on social network benchmark instances and present computational results. Our results highlight potential research opportunities and challenges for the social network optimization community.