Tracking evolving communities in large linked networks. Export

@article{citeulike:100373, abstract = {We are interested in tracking changes in large-scale data by periodically creating an agglomerative clustering and examining the evolution of clusters (communities) over time. We examine a large real-world data set: the NEC CiteSeer database, a linked network of >250,000 papers. Tracking changes over time requires a clustering algorithm that produces clusters stable under small perturbations of the input data. However, small perturbations of the CiteSeer data lead to significant changes to most of the clusters. One reason for this is that the order in which papers within communities are combined is somewhat arbitrary. However, certain subsets of papers, called natural communities, correspond to real structure in the CiteSeer database and thus appear in any clustering. By identifying the subset of clusters that remain stable under multiple clustering runs, we get the set of natural communities that we can track over time. We demonstrate that such natural communities allow us to identify emerging communities and track temporal changes in the underlying structure of our network data.}, address = {Department of Computer Science, Cornell University, Ithaca, NY 14853, USA.}, author = {Hopcroft, J. and Khan, O. and Kulis, B. and Selman, B.}, citeulike-article-id = {100373}, citeulike-linkout-0 = {http://dx.doi.org/10.1073/pnas.0307750100}, citeulike-linkout-1 = {http://view.ncbi.nlm.nih.gov/pubmed/14757820}, citeulike-linkout-2 = {http://www.hubmed.org/display.cgi?uids=14757820}, day = {6}, doi = {10.1073/pnas.0307750100}, issn = {0027-8424}, journal = {Proc Natl Acad Sci U S A}, keywords = {citation\_networks, community\_detection, social\_networks}, month = {April}, pages = {5249--5253}, posted-at = {2006-10-05 16:15:51}, priority = {3}, title = {Tracking evolving communities in large linked networks.}, url = {http://dx.doi.org/10.1073/pnas.0307750100}, volume = {101 Suppl 1}, year = {2004} }

TY - JOUR ID - citeulike:100373 L3 - citeulike-article-id:100373 N2 - We are interested in tracking changes in large-scale data by periodically creating an agglomerative clustering and examining the evolution of clusters (communities) over time. We examine a large real-world data set: the NEC CiteSeer database, a linked network of >250,000 papers. Tracking changes over time requires a clustering algorithm that produces clusters stable under small perturbations of the input data. However, small perturbations of the CiteSeer data lead to significant changes to most of the clusters. One reason for this is that the order in which papers within communities are combined is somewhat arbitrary. However, certain subsets of papers, called natural communities, correspond to real structure in the CiteSeer database and thus appear in any clustering. By identifying the subset of clusters that remain stable under multiple clustering runs, we get the set of natural communities that we can track over time. We demonstrate that such natural communities allow us to identify emerging communities and track temporal changes in the underlying structure of our network data. JF - Proc Natl Acad Sci U S A SN - 0027-8424 AD - Department of Computer Science, Cornell University, Ithaca, NY 14853, USA. EP - 5253 TI - Tracking evolving communities in large linked networks. VL - 101 Suppl 1 SP - 5249 KW - citation_networks KW - community_detection KW - social_networks AU - Hopcroft, J AU - Khan, O AU - Kulis, B AU - Selman, B PY - 2004/04/06/ UR - http://dx.doi.org/10.1073/pnas.0307750100 ER -