The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
A framework for community identification in dynamic social networks
Abstract
We propose frameworks and algorithms for identifying communities in social networks that change over time. Communities are intuitively characterized as "unusually densely knit" subsets of a social network. This notion becomes more problematic if the social interactions change over time. Aggregating social networks over time can radically misrepresent the existing and changing community structure. Instead, we propose an optimization-based approach for modeling dynamic community structure. We prove that finding the most explanatory community structure is NP-hard and APX-hard, and propose algorithms based on dynamic programming, exhaustive search, maximum matching, and greedy heuristics. We demonstrate empirically that the heuristics trace developments of community structure accurately for several synthetic and real-world examples.
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
The neighbor-joining method: a new method for reconstructing phylogenetic trees.
(1987) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a040454 · Cited by 59,715
Rogers, E. M., Singhal, A., & Quinlan, M. M. (2019) · An Integrated Approach to Communication Theory and Research · doi:10.4324/9780203710753-35 · Cited by 37,322
Social Network Analysis: Methods and Applications
Wasserman, S., & Faust, K. (1994) · doi:10.1017/cbo9780511815478 · Cited by 17,557
Community structure in social and biological networks
Girvan, M., & Newman, M. E. J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.122653799 · Cited by 15,502 · cited 1×
“One of the most important questions in social networks is the identification of “communities”, which are loosely defined as collections of individuals who interact unusually frequently [12, 13, 16, 18, 27, 38].”
BackgroundFinding 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
Maximizing the spread of influence through a social network
Kempe, D., Kleinberg, J., & Tardos, É. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956769 · Cited by 7,326
Self-citation(2017) · The SAGE Encyclopedia of Communication Research Methods · doi:10.4135/9781483381411.n575 · Cited by 6,008
Kilzer, E., & Wolff, K. H. (1950) · The American Catholic Sociological Review · doi:10.2307/3707052 · Cited by 4,521
The Structure and Dynamics of Networks
Newman, M., Barabási, A.-L., & Watts, D. J. (2011) · Princeton University Press eBooks · doi:10.1515/9781400841356 · Cited by 2,268
Group formation in large social networks: membership, growth, and evolution
Backstrom, L., Huttenlocher, D., Kleinberg, J., & Lan, X. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150412 · Cited by 1,805
Conflict and the Web of Group-Affiliations
Illing, H. A., & Simmel, G. (1955) · The Journal of Criminal Law, Criminology, and Police Science · doi:10.2307/1139856 · Cited by 1,742
The Structure and Dynamics of Networks
Boguñá, M. (2007) · Journal of Statistical Physics · doi:10.1007/s10955-006-9267-8 · Cited by 1,485
MOLECULAR BIOLOGY AND EVOLUTION
(2012) · Information Theory and Evolution · doi:10.1142/9789814401241_0003 · Cited by 1,045
Information diffusion through blogspace
Gruhl, D., Guha, R., Liben-Nowell, D., & Tomkins, A. (2004) · Proceedings of the 13th international conference on World Wide Web · doi:10.1145/988672.988739 · Cited by 1,041
Self-organization and identification of Web communities
Flake, G. W., Lawrence, S., Giles, C. L., & Coetzee, F. M. (2002) · Computer · doi:10.1109/2.989932 · Cited by 1,018
Trawling the Web for emerging cyber-communities
Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. (1999) · Computer Networks · doi:10.1016/s1389-1286(99)00040-7 · Cited by 1,000
Getoor, L., & Diehl, C. P. (2005) · ACM SIGKDD Explorations Newsletter · doi:10.1145/1117454.1117456 · Cited by 973
Information diffusion through blogspace
Gruhl, D., Liben-Nowell, D., Guha, R., & Tomkins, A. (2004) · ACM SIGKDD Explorations Newsletter · doi:10.1145/1046456.1046462 · Cited by 927
Inferring Web communities from link topology
Gibson, D., Kleinberg, J., & Raghavan, P. (1998) · Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems links, objects, time and space---structure in hypermedia systems - HYPERTEXT '98 · doi:10.1145/276627.276652 · Cited by 768
The Complexity of Multiterminal Cuts
Dahlhaus, E., Johnson, D. S., Papadimitriou, C. H., Seymour, P. D., & Yannakakis, M. (1994) · SIAM Journal on Computing · doi:10.1137/s0097539792225297 · Cited by 662
Retrospective Birth Dating of Cells in Humans
Spalding, K. L., Bhardwaj, R. D., Buchholz, B. A., Druid, H., & Frisén, J. (2005) · Cell · doi:10.1016/j.cell.2005.04.028 · Cited by 628
Distribution de la flore alpine dans le Bassin des Dranses et dans quelques régions voisines
Jaccard, P. (1901) · E-Periodica · doi:10.5169/seals-266440 · Cited by 424
Measures of concurrency in networks and the spread of infectious disease
Kretzschmar, M., & Morris, M. (1996) · Mathematical Biosciences · doi:10.1016/0025-5564(95)00093-3 · Cited by 417
The Stoic Criterion of Identity
Sedley, D. (1982) · Phronesis · doi:10.1163/156852882x00177 · Cited by 339
The Structure and Dynamics of Networks: (Princeton Studies in Complexity)
Newman, M., Barabási, A.-Ĺ., & Watts, D. J. (2006) · Princeton University Press eBooks · Cited by 316
Fischhoff, I. R., Sundaresan, S. R., Cordingley, J., Larkin, H. M., Sellier, M.-J., & Rubenstein, D. I. (2007) · Animal Behaviour · doi:10.1016/j.anbehav.2006.10.012 · Cited by 309
Predicting epidemics on directed contact networks
Meyers, L. A., Newman, M. E. J., & Pourbohloul, B. (2006) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2005.10.004 · Cited by 283
Sundaresan, S. R., Fischhoff, I. R., Dushoff, J., & Rubenstein, D. I. (2007) · Oecologia · doi:10.1007/s00442-006-0553-6 · Cited by 269
A framework for analysis of dynamic social networks
Berger-Wolf, T. Y., & Saia, J. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150462 · Cited by 253
Self-citationDynamic Social Network Modeling and Analysis: Workshop Summary and Papers
(2003) · National Academies Press eBooks · doi:10.17226/10735 · Cited by 252
The Sociological Concept of "Group": An Empirical Test of Two Models
Freeman, L. C. (1992) · American Journal of Sociology · doi:10.1086/229972 · Cited by 249
Social structure and co-operative interactions in a wild population of guppies (Poecilia reticulata)
Croft, D. P., James, R., Thomas, P. O. R., Hathaway, C., Mawdsley, D., Laland, K. N., & Krause, J. (2006) · Behavioral Ecology and Sociobiology · doi:10.1007/s00265-005-0091-y · Cited by 233
Disease evolution on networks: the role of contact structure
Read, J. M., & Keeling, M. J. (2003) · Proceedings of the Royal Society of London. Series B: Biological Sciences · doi:10.1098/rspb.2002.2305 · Cited by 227
Natural communities in large linked networks
Hopcroft, J. E., Khan, O., Kulis, B., & Selman, B. (2003) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/956750.956816 · Cited by 143
Finding Social Groups: A Meta-Analysis of the Southern Women Data
Freeman, L. C. (2003) · Cited by 123
Disentangling association patterns in fission–fusion societies using African buffalo as an example
Cross, P. C., Lloyd‐Smith, J. O., & Getz, W. M. (2004) · Animal Behaviour · doi:10.1016/j.anbehav.2004.08.006 · Cited by 123
Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs
Uno, T. (1997) · Lecture notes in computer science · doi:10.1007/3-540-63890-3_11 · Cited by 108
Discovering Hidden Groups in Communication Networks
Baumes, J., Goldberg, M., Magdon‐Ismail, M., & Wallace, W. A. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-25952-7_28 · Cited by 90
Traffic-based feedback on the web
Aizen, J., Huttenlocher, D. P., Kleinberg, J. M., & Novak, A. F. (2004) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0307539100 · Cited by 42
Locating Hidden Groups in Communication Networks Using Hidden Markov Models
Magdon‐Ismail, M., Goldberg, M., Wallace, W. A., & Siebecker, D. (2003) · Lecture notes in computer science · doi:10.1007/3-540-44853-5_10 · Cited by 39
Social Networks in Wild Asses: Comparing Patterns and Processes among Populations
Rubenstein, D. I., Sundaresan, S. R., Fischhoff, I. R., & Saltz, D. (2007) · Lincoln (University of Nebraska) · Cited by 28
Retrospective Birth Dating of Cells
Spalding, K. L., Bhardwaj, R. D., Buchholz, B. A., Druid, H., & Frisén, J. (2005) · University of North Texas Digital Library (University of North Texas) · Cited by 7
Cited by
Holme, P., & Saramäki, J. (2012) · Physics Reports · doi:10.1016/j.physrep.2012.03.001 · Cited by 2,736
Graph based anomaly detection and description: a survey
Akoglu, L., Tong, H., & Koutra, D. (2015) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-014-0365-y · Cited by 1,504
Modern temporal network theory: a colloquium
Holme, P. (2015) · The European Physical Journal B · doi:10.1140/epjb/e2015-60657-4 · Cited by 734
Paranjape, A., Benson, A. R., & Leskovec, J. (2017) · Proceedings of the Tenth ACM International Conference on Web Search and Data Mining · doi:10.1145/3018661.3018731 · Cited by 540
Tracking the Evolution of Communities in Dynamic Social Networks
Greene, D., Doyle, D., & Cunningham, P. (2010) · 2010 International Conference on Advances in Social Networks Analysis and Mining · doi:10.1109/asonam.2010.17 · Cited by 537
Metadata
- Authors
- Tantipathananandh, C., Berger-Wolf, T., & Kempe, D.
- Venue
- Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining
- Publisher
- ACM
- Published
- 2007-08-12
- Pages
- 717-726
- OpenAlex
- W2122278421
- Cited by
- 443
- References
- 42
- FWCI
- 33.03
- 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.