{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T18:31:52Z","timestamp":1772908312811,"version":"3.50.1"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,4,1]],"date-time":"2009-04-01T00:00:00Z","timestamp":1238544000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2009,4]]},"abstract":"<jats:p>\n            We discover communities from social network data and analyze the community evolution. These communities are inherent characteristics of human interaction in online social networks, as well as paper citation networks. Also, communities may evolve over time, due to changes to individuals' roles and social status in the network as well as changes to individuals' research interests. We present an innovative algorithm that deviates from the traditional two-step approach to analyze community evolutions. In the traditional approach, communities are first detected for each time slice, and then compared to determine correspondences. We argue that this approach is inappropriate in applications with noisy data. In this paper, we propose\n            <jats:italic>FacetNet<\/jats:italic>\n            for analyzing communities and their evolutions through a robust\n            <jats:italic>unified<\/jats:italic>\n            process. This novel framework will discover communities and capture their evolution with temporal smoothness given by historic community structures. Our approach relies on formulating the problem in terms of maximum a posteriori (MAP) estimation, where the community structure is estimated both by the observed networked data and by the prior distribution given by historic community structures. Then we develop an iterative algorithm, with proven low time complexity, which is guaranteed to converge to an optimal solution. We perform extensive experimental studies, on both synthetic datasets and real datasets, to demonstrate that our method discovers meaningful communities and provides additional insights not directly obtainable from traditional methods.\n          <\/jats:p>","DOI":"10.1145\/1514888.1514891","type":"journal-article","created":{"date-parts":[[2009,4,21]],"date-time":"2009-04-21T14:14:44Z","timestamp":1240323284000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":218,"title":["Analyzing communities and their evolutions in dynamic social networks"],"prefix":"10.1145","volume":"3","author":[{"given":"Yu-Ru","family":"Lin","sequence":"first","affiliation":[{"name":"Arizona State University, Tempe, AZ"}]},{"given":"Yun","family":"Chi","sequence":"additional","affiliation":[{"name":"NEC Laboratories America, Cupertino, CA"}]},{"given":"Shenghuo","family":"Zhu","sequence":"additional","affiliation":[{"name":"NEC Laboratories America, Cupertino, CA"}]},{"given":"Hari","family":"Sundaram","sequence":"additional","affiliation":[{"name":"Arizona State University, Tempe, AZ"}]},{"given":"Belle L.","family":"Tseng","sequence":"additional","affiliation":[{"name":"YAHOO! Inc., Santa Clara, CA"}]}],"member":"320","published-online":{"date-parts":[[2009,4,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281290"},{"key":"e_1_2_1_2_1","unstructured":"Bach F. R. and Jordan M. I. 2006. Learning spectral clustering with application to speech separation. J. Mach. Lean. Resea. 7.   Bach F. R. and Jordan M. I. 2006. Learning spectral clustering with application to speech separation. J. Mach. Lean. Resea. 7."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150467"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281212"},{"key":"e_1_2_1_5_1","volume-title":"Spectral Graph Theory","author":"Chung F. R. K.","unstructured":"Chung , F. R. K. 1997. Spectral Graph Theory . American Mathematical Society . Chung, F. R. K. 1997. Spectral Graph Theory. American Mathematical Society."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014118"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/347090.347121"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775233"},{"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\/1081870.1081893"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367590"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/WI.2007.30"},{"key":"e_1_2_1_14_1","unstructured":"Lovasz L. and Plummer M. 1986. Matching Theory. Akad\u00e9miai Kiad\u00f3 North Holland Budapest.  Lovasz L. and Plummer M. 1986. Matching Theory. Akad\u00e9miai Kiad\u00f3 North Holland Budapest."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081895"},{"key":"e_1_2_1_16_1","article-title":"Finding and evaluating community structure in networks","author":"Newman M. E. J.","year":"2004","unstructured":"Newman , M. E. J. and Girvan , M. 2004 . Finding and evaluating community structure in networks . Phys. Rev. E. Newman, M. E. J. and Girvan, M. 2004. Finding and evaluating community structure in networks. Phys. Rev. E.","journal-title":"Phys. Rev. E."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the SIAM International Conference on Data Mining.","author":"Ning H.","unstructured":"Ning , H. , Xu , W. , Chi , Y. , Gong , Y. , and Huang , T . 2007. Incremental spectral clustering with application to monitoring of evolving blog communities . In Proceedings of the SIAM International Conference on Data Mining. Ning, H., Xu, W., Chi, Y., Gong, Y., and Huang, T. 2007. Incremental spectral clustering with application to monitoring of evolving blog communities. In Proceedings of the SIAM International Conference on Data Mining."},{"key":"e_1_2_1_18_1","unstructured":"Page L. Brin S. Motwani R. and Winograd T. 1998. The PageRank citation ranking: Bringing order to the web. In Tech. Rep. Stanford Digital Library Technologies Project Stanford University Stanford CA.  Page L. Brin S. Motwani R. and Winograd T. 1998. The PageRank citation ranking: Bringing order to the web. In Tech. Rep. Stanford Digital Library Technologies Project Stanford University Stanford CA."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Palla G. Barabasi A.-L. and Vicsek T. 2007. Quantifying social group evolution. Nature 446.  Palla G. Barabasi A.-L. and Vicsek T. 2007. Quantifying social group evolution. Nature 446.","DOI":"10.1038\/nature05670"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1117454.1117459"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150491"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281266"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/900051.900059"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Wasserman S. and Faust K. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press.  Wasserman S. and Faust K. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press.","DOI":"10.1017\/CBO9780511815478"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the SIAM International Conference on Data Mining.","author":"White S.","unstructured":"White , S. and Smyth , P . 2005. A spectral clustering approach to finding communities in graph . In Proceedings of the SIAM International Conference on Data Mining. White, S. and Smyth, P. 2005. A spectral clustering approach to finding communities in graph. In Proceedings of the SIAM International Conference on Data Mining."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/860435.860485"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Conference on Advances in Neural Information Processing Systems.","author":"Yu K.","unstructured":"Yu , K. , Yu , S. , and Tresp , V . 2005. Soft clustering on graphs . In Proceedings of the Conference on Advances in Neural Information Processing Systems. Yu, K., Yu, S., and Tresp, V. 2005. Soft clustering on graphs. In Proceedings of the Conference on Advances in Neural Information Processing Systems."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the Confrenece on Advances in Neural Information Processing Systems.","author":"Zha H.","unstructured":"Zha , H. , He , X. , Ding , C. H. Q. , Gu , M. , and Simon , H. D . 2001. Spectral relaxation for k-means clustering . In Proceedings of the Confrenece on Advances in Neural Information Processing Systems. Zha, H., He, X., Ding, C. H. Q., Gu, M., and Simon, H. D. 2001. Spectral relaxation for k-means clustering. In Proceedings of the Confrenece on Advances in Neural Information Processing Systems."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1514888.1514891","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1514888.1514891","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:19Z","timestamp":1750253419000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1514888.1514891"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,4]]}},"alternative-id":["10.1145\/1514888.1514891"],"URL":"https:\/\/doi.org\/10.1145\/1514888.1514891","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4]]},"assertion":[{"value":"2008-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}