SSCAN:Structural Graph Clustering on Signed Networks

Structural graph clustering ( \(\textsf{SCAN}\) ) is a foundational problem about managing and profiling graph datasets, which is widely experienced across many realistic scenarios. Due to existing work on structural graph clustering focused on unsigned graphs, existing \(\textsf{SCAN}\) methods are not applicable to signed networks that can indicate friendly and antagonistic relationships. To tackle this problem, we investigate a novel structural graph clustering model, named \(\textsf{SSCAN}\) . On the basis of \(\textsf{SSCAN}\) , we propose an online approach that can efficiently compute the clusters for a given signed network. Furthermore, we also devise an efficient index structure, called \(\mathsf {SSCAN\text {-}Index^{+}}\) , which stores information about core vertices and structural similarities. The size of our proposed index can be well bounded by O(m), where m is the total amount of edges in an input signed network. Following the new index \(\mathsf {SSCAN\text {-}Index^{+}}\) , we develop an index-based query method designed to avoid invalid scans of the entire network. Extensive experimental testings on eight real signed networks prove the effectiveness and efficiency of our proposed methods.