TY - GEN
T1 - Incremental structural clustering for dynamic networks
AU - Chen, Yazhong
AU - Li, Rong Hua
AU - Dai, Qiangqiang
AU - Li, Zhenjun
AU - Qiao, Shaojie
AU - Mao, Rui
N1 - Publisher Copyright:
© 2017, Springer International Publishing AG.
PY - 2017
Y1 - 2017
N2 - Graph clustering is a fundamental tool for revealing cohesive structures in networks. The structural clustering algorithm for networks (\mathsf {SCAN}) is an important approach for this task, which has attracted much attention in recent years. The \mathsf {SCAN} algorithm can not only use to identify cohesive structures, but it is also able to detect outliers and hubs in a static network. Most real-life networks, however, frequently evolve over time. Unfortunately, the \mathsf {SCAN} algorithm is very costly to handle such dynamic networks. In this paper, we propose an efficient incremental structural clustering algorithm for dynamic networks, called \mathsf {ISCAN}. The \mathsf {ISCAN} algorithm can efficiently maintain the clustering structures without recomputing the clusters from scratch. We conduct extensive experiments in eight large real-world networks. The results show that our algorithm is at least three orders of magnitude faster than the baseline algorithm.
AB - Graph clustering is a fundamental tool for revealing cohesive structures in networks. The structural clustering algorithm for networks (\mathsf {SCAN}) is an important approach for this task, which has attracted much attention in recent years. The \mathsf {SCAN} algorithm can not only use to identify cohesive structures, but it is also able to detect outliers and hubs in a static network. Most real-life networks, however, frequently evolve over time. Unfortunately, the \mathsf {SCAN} algorithm is very costly to handle such dynamic networks. In this paper, we propose an efficient incremental structural clustering algorithm for dynamic networks, called \mathsf {ISCAN}. The \mathsf {ISCAN} algorithm can efficiently maintain the clustering structures without recomputing the clusters from scratch. We conduct extensive experiments in eight large real-world networks. The results show that our algorithm is at least three orders of magnitude faster than the baseline algorithm.
UR - http://www.scopus.com/inward/record.url?scp=85031422067&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-68783-4_9
DO - 10.1007/978-3-319-68783-4_9
M3 - Conference contribution
AN - SCOPUS:85031422067
SN - 9783319687827
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 123
EP - 134
BT - Web Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings
A2 - Chen, Lu
A2 - Bouguettaya, Athman
A2 - Klimenko, Andrey
A2 - Dzerzhinskiy, Fedor
A2 - Klimenko, Stanislav V.
A2 - Zhang, Xiangliang
A2 - Li, Qing
A2 - Gao, Yunjun
A2 - Jia, Weijia
PB - Springer Verlag
T2 - 18th International Conference on Web Information Systems Engineering, WISE 2017
Y2 - 7 October 2017 through 11 October 2017
ER -