Edge-Dual Graph Preserving Sign Prediction for Signed Social Networks

Though existing works of sign prediction have reasonable prediction performances, they suffer from the data sparseness problem, especially for the negative link prediction. Most nodes in signed social networks are connected to very limited number of other nodes, which could not provide enough knowledge for sign prediction. This paper, therefore, proposes a novel edge-dual graph preserving sign prediction model, which reconstructs the signed social network by converting the original graph into the edge-dual graph, uses Jaccard coefficient to measure the node similarity and applies support vector machine classifier to predict signs. The proposed method reconstructs the graph by converting edges of the original graph into nodes of the edge-dual graph, and creating edges for the edge-dual graph according to the connections of edges in the original graph. It is mathematically and experimentally verified that the sparseness of the signed social networks can be significantly reduced by the proposed method. Using the publicly available data sets, it is verified that the average degree of signed social networks can be 7 to 8 times enlarged by the proposed method and the sign prediction accuracy can be improved around 10% comparing with the existing works.