A Dynamic Programming Framework for Large-Scale Online Clustering on Graphs
| العنوان: | A Dynamic Programming Framework for Large-Scale Online Clustering on Graphs |
|---|---|
| المؤلفون: | Zehui Qu, Xiang Zhao, Yantao Li |
| المصدر: | Neural Processing Letters. 52:1613-1629 |
| بيانات النشر: | Springer Science and Business Media LLC, 2020. |
| سنة النشر: | 2020 |
| مصطلحات موضوعية: | 0209 industrial biotechnology, Theoretical computer science, Computational complexity theory, Computer Networks and Communications, Computer science, General Neuroscience, Complex system, Computational intelligence, 02 engineering and technology, Supernode, Dynamic programming, 020901 industrial engineering & automation, Artificial Intelligence, Scalability, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Cluster analysis, Software, Clustering coefficient |
| الوصف: | As a fundamental technique for data analysis, graph clustering grouping graph data into clusters has attracted great attentions in recent years. In this paper, we present DPOCG, a dynamic programming framework for large-scale online clustering on graphs, which improves the scalability of a wide range of graph clustering algorithms. Specifically, DPOCG first identifies the nodes whose states are unchanged compared with the states at the previous time on a large-scale graph, then constructs these unchanged nodes as supernodes, which greatly reduces the size of the graph at the current time, and collapses nodes whose degrees are less than a predefined threshold. Based on our density-based graph clustering algorithm (DGCM), DPOCG partitions the reduced graph into clusters. In addition, we theoretically analyze DPOCG in terms of supernode generation, clustering on reduced graph, and computational complexity. We evaluate DPOCG on a synthetic dataset and seven real-world datasets, respectively, and the experimental results show that DPOCG consumes less running time and improves the efficiency of clustering. |
| تدمد: | 1573-773X 1370-4621 |
| DOI: | 10.1007/s11063-020-10329-1 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::c7d0162427add7059bcb284969e18d40 https://doi.org/10.1007/s11063-020-10329-1 |
| Rights: | CLOSED |
| رقم الانضمام: | edsair.doi...........c7d0162427add7059bcb284969e18d40 |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 1573773X 13704621 |
|---|---|
| DOI: | 10.1007/s11063-020-10329-1 |