The DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.
Facetnet: a framework for analyzing communities and their evolutions in dynamic networks
Abstract
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 FacetNet for analyzing communities and their evolutions through a robust unified process. In this novel framework, communities not only generate evolutions, they also are regularized by the temporal smoothness of evolutions. As a result, this framework will discover communities that jointly maximize the fit to the observed data and the temporal evolution. Our approach relies on formulating the problem in terms of non-negative matrix factorization, where communities and their evolutions are factorized in a unified way. 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Social Network Analysis: Methods and Applications
Wasserman, S. S., & Faust, K. (1994) · Cited by 17,993
Social Network Analysis: Methods and Applications
Wasserman, S., & Faust, K. (1994) · doi:10.1017/cbo9780511815478 · Cited by 17,557
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · Cited by 15,502
Finding and evaluating community structure in networks
Newman, M. E. J., & Girvan, M. (2004) · Physical Review E · doi:10.1103/physreve.69.026113 · Cited by 13,931
(1999) · Cited by 12,854
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 8,959
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
Graphs over time: densification laws, shrinking diameters and possible explanations
Leskovec, J., Kleinberg, J., & Faloutsos, C. (2005) · Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining · doi:10.1145/1081870.1081893 · Cited by 2,281
Quantifying social group evolution
Palla, G., Barabási, A.-L., & Vicsek, T. (2007) · Nature · doi:10.1038/nature05670 · Cited by 1,668
Kernel k-means: spectral clustering and normalized cuts
Dhillon, I. S., Guan, Y., & Kulis, B. (2004) · Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1014052.1014118 · Cited by 1,193
Structure and evolution of online social networks
Kumar, R., Novak, J., & Tomkins, A. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150476 · Cited by 1,084
Efficient identification of Web communities
Flake, G. W., Lawrence, S., & Giles, C. L. (2000) · Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/347090.347121 · Cited by 804
Spectral Relaxation for K-means Clustering
Hongyuan Zha, B., He, X., Ding, C. H. Q., Gu, M., & Simon, H. D. (2001) · neural information processing systems · Cited by 687
Chakrabarti, D., Kumar, R., & Tomkins, A. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150467 · Cited by 661
On the bursty evolution of blogspace
Kumar, R., Novak, J., Raghavan, P., & Tomkins, A. (2003) · Proceedings of the twelfth international conference on World Wide Web - WWW '03 · doi:10.1145/775152.775233 · Cited by 553
GraphScope: parameter-free mining of large time-evolving graphs
Sun, J., Faloutsos, C., Papadimitriou, S., & Yu, P. S. (2007) · Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1281192.1281266 · Cited by 532
Discovering evolutionary theme patterns from text: an exploration of temporal text mining
Mei, Q., & Zhai, C. (2005) · Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining · doi:10.1145/1081870.1081895 · Cited by 524
Dynamic social network analysis using latent space models
Sarkar, P., & Moore, A. W. (2005) · ACM SIGKDD Explorations Newsletter · doi:10.1145/1117454.1117459 · Cited by 422
A Spectral Clustering Approach To Finding Communities in Graphs
White, S., & Smyth, P. (2005) · Proceedings of the 2005 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972757.25 · Cited by 404
Evolutionary spectral clustering by incorporating temporal smoothness
Chi, Y., Song, X., Zhou, D., Hino, K., & Tseng, B. L. (2007) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1281192.1281212 · Cited by 375
Self-citationAn event-based framework for characterizing the evolutionary behavior of interaction graphs
Asur, S., Parthasarathy, S., & Ucar, D. (2009) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1631162.1631164 · Cited by 291
An event-based framework for characterizing the evolutionary behavior of interaction graphs
Asur, S., Parthasarathy, S., & Ucar, D. (2007) · Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1281192.1281290 · Cited by 166
Incremental Spectral Clustering With Application to Monitoring of Evolving Blog Communities
Ning, H., Xu, W. H., Chi, Y., Gong, Y., & Huang, T. S. (2007) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972771.24 · Cited by 113
Self-citationExtracting evolution of web communities from a series of web archives
Toyoda, M., & Kitsuregawa, M. (2003) · ACM Conference on Hypertext and Social Media (HT) · doi:10.1145/900051.900059 · Cited by 87
Cited by
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
“Based on evolutionary clustering, Lin et al. (Lin et al., 2008) introduced a framework, called FacetNet, that allows vertices to belong to more communities at the same time.”
BackgroundMethodInfluentialHolme, P., & Saramäki, J. (2012) · Physics Reports · doi:10.1016/j.physrep.2012.03.001 · Cited by 2,736
Community detection in networks: a user guide
Fortunato, S., & Hric, D. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.09.002 · Cited by 2,086
Community detection in Social Media: Performance and application considerations
Papadopoulos, S., Kompatsiaris, Y., Vakali, A., & Spyridonos, P. (2012) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-011-0224-z · Cited by 615
Managing and Mining Graph Data
(2010) · Advances in Database Systems · doi:10.1007/978-1-4419-6045-0 · Cited by 594
Metadata
- Authors
- Lin, Y.-R., Chi, Y., Zhu, S., Sundaram, H., & Tseng, B. L.
- Venue
- Proceedings of the 17th international conference on World Wide Web
- Publisher
- ACM
- Published
- 2008-04-21
- Pages
- 685-694
- OpenAlex
- W2166563561
- Cited by
- 407
- References
- 24
- FWCI
- 31.48
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.