Community Detection in Signed Social Networks

Abstract

Social networks often encode not only positive relationships — such as friendship, trust, and collaboration — but also negative ones, including rivalry, distrust, and opposition. Networks in which edges carry an explicit positive or negative sign are known as signed social networks. Community detection in such networks aims to partition the node set into cohesive groups that simultaneously maximise positive intra-community links and negative inter-community links, in accordance with structural balance theory.

This thesis addresses the problem of multi-community detection in signed so-cial networks through a hybrid exact–heuristic (matheuristic) framework named HybridVNS-ILP. The proposed algorithm combines three complementary compo-nents : (i) a balance-informed greedy construction that exploits the local sign structure to build a high-quality initial partition ; (ii) a Variable Neighborhood Search (VNS) core that explores four neighbourhood structures of increasing perturbation strength to escape local minima ; and (iii) a conflict-driven Integer Linear Programming (ILP) refinement phase that identifies the most problematic nodes and optimally reas-signs them on a restricted subgraph.

For the exact restricted-refinement variant, the method converges to a local optimum of the disagreement function f (C) in a finite number of iterations, with time com-plexity O(m log n) and space complexity O(n + m). Experimental evaluation on four benchmark signed network datasets (n ∈ {8, 12, 20, 100}, K ∈ {2, 3, 4}) demonstrates that HybridVNS-ILP outperforms Random and Greedy, and matches SLPA on the two largest datasets — Random, Signed Label Propagation, and Greedy — achieving an average improvement rate of 36.1% over the greedy baseline and exactly recovering the planted community structure on the two largest datasets. A fully documented Python implementation and an interactive graphical interface are also contributed