Cluster-based Collaborative Filtering for Sign Prediction in Social Networks with Positive and Negative Links

Social network analysis and mining get ever-increasing importance in recent years, which is mainly due to availability of large datasets and advances in computing systems. A class of social networks is those with positive and negative links. In such networks, a positive link indicates friendship (or trust), whereas links with negative sign correspond to enmity (or distrust). Predicting sign of the links in these networks is an important issue and has applications such as friendship recommendation and identifying malicious nodes in the network. In this manuscript, we proposed a new method for sign prediction in networks with positive and negative links. Our algorithm is based on, first, clustering the network into a number of clusters, and then, applying a collaborative filtering algorithm. The clusters are such that the number of inner-cluster negative links and inter-cluster positive links are minimal, i.e., the clusters are socially balanced as much as possible (a signed graph is socially balanced if it can be divided into clusters with all positive links inside the clusters and all negative links between them). We then used similarity between the clusters (based on the links between them) in a collaborative filtering algorithm. Our experiments on a number of real datasets showed that the proposed method outperformed previous methods including those based on social balance and status theories and the one based on machine learning framework (logistic regression in this work)