Self-Avoiding Pruning Random Walk on Signed Network

Abstract

A signed network represents how a set of nodes are connected by two logically contradictory types of links: positive and negative links. Examples are signed product networks where two products can be complementary (purchased together) or substitutable (purchased instead of each other). Such contradictory types of links may play dramatically different roles in the spreading process of information, opinion etc. In this work, we propose a Self-Avoiding Pruning (SAP) random walk on a signed network to model e.g. a user's purchase activity on a signed network of products and information/opinion diffusion on a signed social network. Specifically, a SAP walk starts at a random node. At each step, the walker moves to a positive neighbour that is randomly selected and its previously visited node together with its negative neighbours are removed. We explored both analytically and numerically how signed network features such as link density and degree distribution influence the key performance of a SAP walk: the evolution of the pruned network resulting from the node removals of a SAP walk, the length of a SAP walk and the visiting probability of each node. Our findings in signed network models are further partially verified in two real-world signed networks.