{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:49:54Z","timestamp":1773481794176,"version":"3.50.1"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>\n            Recently, dynamic networks are attracting increasing interest due to their high potential in capturing natural and social phenomena over time. Discovery of evolutionary communities in dynamic networks has become a critical task. The previous evolutionary clustering methods usually adopt the temporal smoothness framework, which has a desirable feature of controlling the balance between temporal noise and true concept drift of communities. They, however, have some major drawbacks: (1) assuming only a fixed number of communities over time; and (2) not allowing arbitrary start\/stop of community over time. The forming of new communities and dissolving of existing communities are very common phenomena in real dynamic networks. In this paper, we propose a new\n            <jats:italic>particle-and-density based<\/jats:italic>\n            evolutionary clustering method that efficiently discovers a variable number of communities of arbitrary forming and dissolving. We first model a dynamic network as a collection of lots of particles called\n            <jats:italic>nano-communities<\/jats:italic>\n            , and a community as a densely connected subset of particles, called a\n            <jats:italic>quasi l-clique-by-clique<\/jats:italic>\n            (shortly,\n            <jats:italic>l-KK<\/jats:italic>\n            ). Each particle contains a small amount of information about the evolution of data or patterns, and the quasi\n            <jats:italic>l-KK<\/jats:italic>\n            s inherent in a given dynamic network provide us with\n            <jats:italic>guidance<\/jats:italic>\n            on how to find a variable number of communities of arbitrary forming and dissolving. We propose a density-based clustering method that efficiently finds temporally smoothed local clusters of high quality by using a\n            <jats:italic>cost embedding technique<\/jats:italic>\n            and optimal modularity. We also propose a\n            <jats:italic>mapping method<\/jats:italic>\n            based on information theory that makes sequences of smoothed local clusters as close as possible to data-inherent quasi\n            <jats:italic>l-KK<\/jats:italic>\n            s. The result of the mapping method allows us to easily identify the stage of each community among the three stages:\n            <jats:italic>evolving, forming<\/jats:italic>\n            , and\n            <jats:italic>dissolving<\/jats:italic>\n            . Experimental studies, by using various data sets, demonstrate that our method improves the clustering accuracy, and at the same time, the time performance by an order of magnitude compared with the current state-of-the art method.\n          <\/jats:p>","DOI":"10.14778\/1687627.1687698","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"622-633","source":"Crossref","is-referenced-by-count":177,"title":["A particle-and-density based evolutionary clustering method for dynamic networks"],"prefix":"10.14778","volume":"2","author":[{"given":"Min-Soo","family":"Kim","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}]},{"given":"Jiawei","family":"Han","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281290"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_2_1_3_1","first-page":"806","volume-title":"Proc. VLDB","author":"Bansal N.","year":"2007","unstructured":"N. Bansal , F. Chiang , N. Koudas , and F. W. Tompa . Seeking stable clusters in the blogosphere . In Proc. VLDB 2007 , pages 806 -- 817 . N. Bansal, F. Chiang, N. Koudas, and F. W. Tompa. Seeking stable clusters in the blogosphere. In Proc. VLDB 2007, pages 806--817."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150467"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281212"},{"key":"e_1_2_1_6_1","volume-title":"http:\/\/www.informatik.uni-trier.de\/ley\/db","author":"DBLP","year":"2009","unstructured":"DBLP bibliographic data. http:\/\/www.informatik.uni-trier.de\/ley\/db , 2009 . DBLP bibliographic data. http:\/\/www.informatik.uni-trier.de\/ley\/db, 2009."},{"key":"e_1_2_1_7_1","first-page":"323","volume-title":"Proc. VLDB","author":"Ester M.","year":"1998","unstructured":"M. Ester , H.-P. Kriegel , J. Sander , M. Wimmer , and X. Xu . Incremental clustering for mining in a data warehousing environment . In Proc. VLDB 1998 , pages 323 -- 333 . M. Ester, H.-P. Kriegel, J. Sander, M. Wimmer, and X. Xu. Incremental clustering for mining in a data warehousing environment. In Proc. VLDB 1998, pages 323--333."},{"key":"e_1_2_1_8_1","first-page":"226","volume-title":"Proc. KDD","author":"Ester M.","year":"1996","unstructured":"M. Ester , H.-P. Kriegel , J. Sander , and X. Xu . A density-based algorithm for discovering clusters in large spatial databases with noise . In Proc. KDD 1996 , pages 226 -- 231 . M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proc. KDD 1996, pages 226--231."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2391952.2391999"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150476"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247546"},{"key":"e_1_2_1_12_1","first-page":"026120","article-title":"Vertex similarity in networks","volume":"73","author":"Leicht E. A.","year":"2006","unstructured":"E. A. Leicht , P. Holme , and M. E. J. Newman . Vertex similarity in networks . Physical Review , E73 : 026120 , 2006 . E. A. Leicht, P. Holme, and M. E. J. Newman. Vertex similarity in networks. Physical Review, E73:026120, 2006.","journal-title":"Physical Review"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401948"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367590"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081895"},{"key":"e_1_2_1_17_1","volume-title":"http:\/\/www.jhowell.net\/cf\/scores\/scoresindex.htm","author":"NCAA Football Division 1-A schedule data.","year":"2009","unstructured":"NCAA Football Division 1-A schedule data. http:\/\/www.jhowell.net\/cf\/scores\/scoresindex.htm , 2009 . NCAA Football Division 1-A schedule data. http:\/\/www.jhowell.net\/cf\/scores\/scoresindex.htm, 2009."},{"key":"e_1_2_1_18_1","first-page":"066133","article-title":"Fast algorithm for detecting community structure in networks","volume":"69","author":"Newman M. E. J.","year":"2004","unstructured":"M. E. J. Newman . Fast algorithm for detecting community structure in networks . Physical Review , E69 : 066133 , 2004 . M. E. J. Newman. Fast algorithm for detecting community structure in networks. Physical Review, E69:066133, 2004.","journal-title":"Physical Review"},{"issue":"2","key":"e_1_2_1_19_1","first-page":"026113","article-title":"Finding and evaluating community structure in networks","volume":"69","author":"Newman M. E. J.","year":"2004","unstructured":"M. E. J. Newman and M. Girvan . Finding and evaluating community structure in networks . Physical Review , E69 ( 2 ): 026113 , 2004 . M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review, E69(2):026113, 2004.","journal-title":"Physical Review"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281266"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401972"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281269"},{"key":"e_1_2_1_23_1","volume-title":"http:\/\/reality.media.mit.edu\/download.php","author":"Telephone","year":"2007","unstructured":"Telephone traffic data. http:\/\/reality.media.mit.edu\/download.php , 2007 . Telephone traffic data. http:\/\/reality.media.mit.edu\/download.php, 2007."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511815478"},{"key":"e_1_2_1_25_1","volume-title":"Introduction to Graph Theory","author":"West D. B.","year":"2001","unstructured":"D. B. West . Introduction to Graph Theory . Prentice Hall , second edition, 2001 . D. B. West. Introduction to Graph Theory. Prentice Hall, second edition, 2001."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281280"},{"key":"e_1_2_1_27_1","volume-title":"NIPS","author":"Yu K.","year":"2005","unstructured":"K. Yu , S. Yu , and V. Tresp . Soft clustering on graphs . NIPS , 2005 . K. Yu, S. Yu, and V. Tresp. Soft clustering on graphs. NIPS, 2005."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2007.4"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066236"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687698","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:30:25Z","timestamp":1672227025000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687698"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687698"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687698","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}