Incremental K-clique clustering in dynamic social networks

• Published in: The Artificial intelligence review 2012-08, Vol.38 (2), p.129-147
• Main Authors: Duan, Dongsheng, Li, Yuhua, Li, Ruixuan, Lu, Zhengding
• Format: Article
• Language: English
• Subjects: Algorithms; Artificial Intelligence; Clustering; Computer Science; Social network analysis; Social networks
• ISSN: 0269-2821; 1573-7462
• DOI: 10.1007/s10462-011-9250-x

Clustering entities into dense parts is an important issue in social network analysis. Real social networks usually evolve over time and it remains a problem to efficiently cluster dynamic social networks. In this paper, a dynamic social network is modeled as an initial graph with an infinite change stream, called change stream model , which naturally eliminates the parameter setting problem of snapshot graph model. Based on the change stream model, the incremental version of a well known k -clique clustering problem is studied and incremental k -clique clustering algorithms are proposed based on local DFS (depth first search) forest updating technique. It is theoretically proved that the proposed algorithms outperform corresponding static ones and incremental spectral clustering algorithm in terms of time complexity. The practical performances of our algorithms are extensively evaluated and compared with the baseline algorithms on ENRON and DBLP datasets. Experimental results show that incremental k -clique clustering algorithms are much more efficient than corresponding static ones, and have no accumulating errors that incremental spectral clustering algorithm has and can capture the evolving details of the clusters that snapshot graph model based algorithms miss.