Even Trolls Are Useful: Efficient Link Classification in Signed Networks
This work addresses link classification for signed social networks, offering a faster and more accurate solution, though it appears incremental as it builds on existing psychological assumptions and network analysis methods.
The paper tackles link classification in signed social networks by developing an efficient algorithm based on a binary user behavior assumption, demonstrating that it outperforms competitors while being significantly faster on three real-world datasets.
We address the problem of classifying the links of signed social networks given their full structural topology. Motivated by a binary user behaviour assumption, which is supported by decades of research in psychology, we develop an efficient and surprisingly simple approach to solve this classification problem. Our methods operate both within the active and batch settings. We demonstrate that the algorithms we developed are extremely fast in both theoretical and practical terms. Within the active setting, we provide a new complexity measure and a rigorous analysis of our methods that hold for arbitrary signed networks. We validate our theoretical claims carrying out a set of experiments on three well known real-world datasets, showing that our methods outperform the competitors while being much faster.