Title: Sign prediction and community detection in directed signed networks based on random walk theory

Authors: Baofang Hu; Hong Wang; Yuanjie Zheng

Addresses: School of Information Science and Engineering, Shandong Normal University, Jinan 250014, China; School of Information Technology, Shandong Women's University, Jinan 250014, China; Shandong Provincial Key Laboratory for Distributed, Computer Software Novel Technology, Shandong Normal University, Jinan 250014, China ' School of Information Science and Engineering, Shandong Normal University, Jinan 250014, China; Shandong Provincial Key Laboratory for Distributed, Computer Software Novel Technology, Shandong Normal University, Jinan 250014, China ' School of Information Science and Engineering, Shandong Normal University, Jinan 250014, China; Shandong Provincial Key Laboratory for Distributed, Computer Software Novel Technology, Shandong Normal University, Jinan 250014, China

Abstract: Previous studies on social networks often focused on networks with only positive edges between node pairs. As a significant extension, we applied the random walk theory based on graphs with both positive and negative edges. In particular, we derived the commute time similarity between node pairs in directed signed networks and proved that its corresponding Laplace spectral was a legal kernel to compute the similarities between node pairs. We utilised the similarity distance to predict the sign and direction of the edges on two real social networks based on the idea of collaborative filtering, and the experimental results showed that the method provided good performance. We also utilised the defined Laplacian spectrum of the directed signed networks to detect the community structure in two real-world networks and three synthetic networks and the algorithm achieved good performance.

Keywords: directed signed network; random walk; community detection; sign prediction; collaborative filtering.

DOI: 10.1504/IJES.2019.098295

International Journal of Embedded Systems, 2019 Vol.11 No.2, pp.200 - 209

Received: 18 May 2016
Accepted: 09 Apr 2017

Published online: 13 Mar 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article