2023/11/01 by Muhieddine Shebaro, Shebaro, Muhieddine, Jelena Tešić +1
Physics and Astronomy · Computer Science · Mathematics · #Complex Network Analysis Techniques #Advanced Graph Neural Networks #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2311.00869
Structural balance modeling for signed graph networks presents how to model the sources of conflicts. The state-of-the-art focuses on computing the frustration index of a signed graph, a critical step toward solving problems in social and sensor networks and scientific modeling. The proposed approaches do not scale to large signed networks of tens of millions of vertices and edges. This paper proposes two efficient algorithms, a tree-based graphBpp and a gradient descent-based graphL. We show that both algorithms outperform state-of-art in terms of efficiency and effectiveness for discovering the balanced state for any network size. We introduce the first comparison for large graphs for the exact, tree-based, and gradient descent-based methods. The speedup of the methods is around 300+ times faster than the state-of-the-art for large signed graphs. We find that the exact method excels at optimally finding the frustration for small graphs only. graphBpp scales this approximation to large signed graphs at the cost of accuracy. graphL produces a state with a lower frustration at the cost of selecting a proper variable initialization and hyperparameter tuning.