• Dongsheng Duan, Yuhua Li, Ruixuan Li, Zhengding Lu

• 出版社：Springer
• 页数：：1-19
• 出版年：2012

Abstract Clustering entities into dense parts is an important issue in social network anal-ysis. Real social networks usually evolve over time and it remains a problem to ef?cientlycluster dynamic social networks. In this paper, a dynamic social network is modeled as aninitial graph with an in?nite change stream, called change stream model, which naturallyeliminates the parameter setting problem of snapshot graph model. Based on the changestream model, the incremental version of a well known k-clique clustering problem is stud-ied and incremental k-clique clustering algorithms are proposed based on local DFS (depth?rst search) forest updating technique. It is theoretically proved that the proposed algorithmsoutperform corresponding static ones and incremental spectral clustering algorithm in termsof time complexity. The practical performances of our algorithms are extensively evaluatedand compared with the baseline algorithms on ENRON and DBLP datasets. Experimentalresults show that incremental k-clique clustering algorithms are much more ef?cient thancorresponding static ones, and have no accumulating errors that incremental spectral clus-tering algorithm has and can capture the evolving details of the clusters that snapshot graphmodel based algorithms miss

• Incremental k-clique clustering ? Dynamic social network ?Change stream model