Fast clustering for signed graphs based on random walk gap

Signed graphs are often used as models for social media mining, social networks analysis and nature language processing. In this paper, we study clustering algorithms for signed graphs that can be scaled for use in large-scale signed networks. A proposed mechanism, called a random walk gap (RWG), is used to extract more cluster structure information. RWG uses two types of random walks on signed graphs. The first considers positive edges only. The second takes negative edges into account. Three types of edges in signed graphs are identified and their different characteristics in terms of transition probability changes are determined for the two types of random walk graphs. Different characteristics contain different information about cluster structure and a RWG matrix is used to reflect the differences. The RWG matrix is used to adjust the weights of edges in signed graphs. This is the first study to perform a random walk on negative edges. A fast clustering for signed graphs (FCSG) algorithm is then proposed. This FCSG is compared with existing methods. The computational times for different algorithms are measured. The experiments show that the proposed FCSG algorithm gives better results than existing algorithms based on the performance criteria of imbalance and modularity.