CHRONICLE: A two-stage density-based clustering algorithm for dynamic networks

Min Soo Kim, Jiawei Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Information networks, such as social networks and that extracted from bibliographic data, are changing dynamically over time. It is crucial to discover time-evolving communities in dynamic networks. In this paper, we study the problem of finding time-evolving communities such that each community freely forms, evolves, and dissolves for any time period. Although the previous t-partite graph based methods are quite effective for discovering such communities from large-scale dynamic networks, they have some weak points such as finding only stable clusters of single path type and not being scalable w.r.t. the time period. We propose CHRONICLE, an efficient clustering algorithm that discovers not only clusters of single path type but also clusters of path group type. In order to find clusters of both types and also control the dynamicity of clusters, CHRONICLE performs the two-stage density-based clustering, which performs the 2nd-stage density-based clustering for the t-partite graph constructed from the 1st-stage density-based clustering result for each timestamp network. For a given data set, CHRONICLE finds all clusters in a fixed time by using a fixed amount of memory, regardless of the number of clusters and the length of clusters. Experimental results using real data sets show that CHRONICLE finds a wider range of clusters in a shorter time with a much smaller amount of memory than the previous method.

Original languageEnglish (US)
Title of host publicationDiscovery Science - 12th International Conference, DS 2009, Proceedings
Pages152-167
Number of pages16
DOIs
StatePublished - Nov 16 2009
Event12th International Conference on Discovery Science, DS 2009 - Porto, Portugal
Duration: Oct 3 2009Oct 5 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5808 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th International Conference on Discovery Science, DS 2009
CountryPortugal
CityPorto
Period10/3/0910/5/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'CHRONICLE: A two-stage density-based clustering algorithm for dynamic networks'. Together they form a unique fingerprint.

  • Cite this

    Kim, M. S., & Han, J. (2009). CHRONICLE: A two-stage density-based clustering algorithm for dynamic networks. In Discovery Science - 12th International Conference, DS 2009, Proceedings (pp. 152-167). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5808 LNAI). https://doi.org/10.1007/978-3-642-04747-3_14