Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
DE
EN
Books
Journals
Events
Topic Page
Marketing
Log in
Learn more about individual access
Request company access
13th International Engine Congress 2026 | 24 + 25 February 2026

Meeting Place for the Powertrain and Sustainable Fuels Community

Take part as a speaker in the 13th International Engine Congress 2026, the Meeting Place for the Powertrain, and Sustainable Fuels Community for the exchange of experience. Submit a subject proposal online about our main subject areas: Passenger car engine technology, Commercial vehicle engine technology and Sustainable Fuels & Energy!
EXTENDED SEARCH
Log in
Top
Social Network Analysis and Mining
Published in:

01-12-2016 | Original Article

Tracking local communities in streaming graphs with a dynamic algorithm

Authors: Anita Zakrzewska, David A. Bader

Published in: Social Network Analysis and Mining | Issue 1/2016

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

A variety of massive datasets, such as social networks and biological data, are represented as graphs that reveal underlying connections, trends, and anomalies. Community detection is the task of discovering dense groups of vertices in a graph. Its one specific form is seed set expansion, which finds the best local community for a given set of seed vertices. Greedy, agglomerative algorithms, which are commonly used in seed set expansion, have been previously designed only for a static, unchanging graph. However, in many applications, new data are constantly produced, and vertices and edges are inserted and removed from a graph. We present an algorithm for dynamic seed set expansion, which maintains a local community over time by incrementally updating as the underlying graph changes. We show that our dynamic algorithm outputs high-quality communities that are similar to those found when using a standard static algorithm. It works well both when beginning with an already existing graph and in the fully streaming case when starting with no data. The dynamic approach is also faster than re-computation when low latency updates are needed.
previous article A synthetic data generator for online social network graphs
next article An empirical comparison of Big Graph frameworks in the context of network analysis

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Literature
Aktunc R, Toroslu IH, Ozer M, Davulcu H (2015) A dynamic modularity based community detection algorithm for large-scale networks: DSLM. In: Proceedings of the 2015 IEEE/ACM international conference on advances in social networks analysis and mining 2015. ACM, pp 1177–1183
Andersen R, Chung F, Lang K (2006) Local graph partitioning using pagerank vectors. In: 47th Annual IEEE symposium on foundations of computer science, 2006. (FOCS’06). IEEE, pp 475–486
Andersen R, Lang KJ (2006) Communities from seed sets. In: Proceedings of the 15th international conference on World Wide Web. ACM, pp 223–232
Asur S, Parthasarathy S, Ucar D (2009) An event-based framework for characterizing the evolutionary behavior of interaction graphs. ACM Trans Knowl Discov Data (TKDD) 3(4):16
Aynaud T, Fleury E, Guillaume JL, Wang Q (2013) Communities in evolving networks: definitions, detection, and analysis techniques. In: Mukherjee A, Choudhury M, Peruani F, Ganguly N, Mitra B (eds) Dynamics on and of complex networks, vol. 2. Springer, New York, pp 159–200
Aynaud T, Guillaume JL (2010) Static community detection algorithms for evolving networks. In: WiOpt’10: modeling and optimization in mobile, Ad Hoc, and wireless networks. IEEE, pp 508–514
Bagrow JP, Bollt EM (2005) Local method for detecting communities. Phys Rev E 72(4):046–108CrossRef
Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech: Theory Exp 10:P10008CrossRef
Cazabet R, Amblard F (2014) Encyclopedia of social network analysis and mining, chapter dynamic community detection. Springer, New York, pp 404–414
Chakrabarti D, Kumar R, Tomkins A (2006) Evolutionary clustering. In: Proceedings of the 12th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 554–560
Chen J, Zaiane OR, Goebel R (2009) Detecting communities in large networks by iterative local expansion. In: International conference on computational aspects of social networks, 2009. (CASON’09). IEEE, pp 105–112
Chung FR (1997) Spectral graph theory, vol 92. American Mathematical Society, ProvidenceMATH
Clauset A (2005) Finding local community structure in networks. Phys Rev E 72(2):026–132CrossRef
Derényi I, Palla G, Vicsek T (2005) Clique percolation in random networks. Phys Rev Lett 94(16):160–202CrossRefMATH
Dinh TN, Xuan Y, Thai MT (2009) Towards social-aware routing in dynamic communication networks. In: 2009 IEEE 28th International on performance computing and communications conference (IPCCC). IEEE, pp 161–168
Evans T, Lambiotte R (2010) Line graphs of weighted networks for overlapping communities. Eur Phys J B 77(2):265–272CrossRef
Greene D, Doyle D, Cunningham P (2010) Tracking the evolution of communities in dynamic social networks. In: 2010 international conference on advances in social networks analysis and mining (ASONAM). IEEE, pp 176–183
Havemann F, Heinz M, Struck A, Gläser J (2011) Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels. J Stat Mech: Theory Exp 1:P01023
Hopcroft J, Khan O, Kulis B, Selman B (2004) Tracking evolving communities in large linked networks. Proc Natl Acad Sci 101(suppl 1):5249–5253CrossRef
Jdidia MB, Robardet C, Fleury E (2007) Communities detection and analysis of their dynamics in collaborative networks. In: ICDIM, pp 744–749
Lancichinetti A, Fortunato S, Kertész J (2009) Detecting the overlapping and hierarchical community structure in complex networks. New J Phys 11(3):033,015CrossRef
Lancichinetti A, Radicchi F, Ramasco JJ, Fortunato S (2011) Finding statistically significant communities in networks. PLoS One 6(4):e18,961CrossRef
Lee C, Reid F, McDaid A, Hurley N (2010) Detecting highly overlapping community structure by greedy clique expansion. In: 4th SNA-KDD workshop, p 3342
Lin YR, Chi Y, Zhu S, Sundaram H, Tseng BL (2009) Analyzing communities and their evolutions in dynamic social networks. ACM Trans Knowl Discov Data (TKDD) 3(2):8
Mucha PJ, Richardson T, Macon K, Porter MA, Onnela JP (2010) Community structure in time-dependent, multiscale, and multiplex networks. Science 328(5980):876–878MathSciNetCrossRefMATH
Newman ME, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69(2):026–113CrossRef
Ning H, Xu W, Chi Y, Gong Y, Huang TS (2010) Incremental spectral clustering by efficiently updating the eigen-system. Pattern Recognit 43(1):113–127CrossRefMATH
Palla G, Barabási AL, Vicsek T (2007) Quantifying social group evolution. Nature 446(7136):664–667CrossRef
Plantié M, Crampes M (2013) Survey on social community detection. In: Ramzan N, van Zwol R, Lee J-S, Clüver K, Hua X-S (eds) Social media retrieval. Springer, London, pp 65–85
Riedy J, Bader DA (2013) Multithreaded community monitoring for massive streaming graph data. In: 2013 IEEE 27th international parallel and distributed processing symposium workshops and PhD Forum (IPDPSW). IEEE, pp 1646–1655
Shang J, Liu L, Xie F, Chen Z, Miao J, Fang X, Wu C (2014) A real-time detecting algorithm for tracking community structure of dynamic networks. arXiv preprint arXiv:​1407.​2683
Spiliopoulou M (2011) Evolution in social networks: a survey. In: Aggarwal CC (ed) Social network data analytics. Springer, pp 149–175
Takaffoli M, Rabbany R, Zaïane OR (2013) Incremental local community identification in dynamic social networks. In: Proceedings of the 2013 IEEE/ACM international conference on advances in social networks analysis and mining. ACM, pp 90–94
Tang L, Liu H (2010) Community detection and mining in social media. Synth Lect Data Min Knowl Discov 2(1):1–137CrossRef
Tantipathananandh C, Berger-Wolf T, Kempe D (2007) A framework for community identification in dynamic social networks. In: Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 717–726
Waltman L, van Eck NJ (2013) A smart local moving algorithm for large-scale modularity-based community detection. The Eur Phys J B 86(11):1–14CrossRef
Xie J, Kelley S, Szymanski BK (2013) Overlapping community detection in networks: the state-of-the-art and comparative study. ACM Comput Surv (CSUR) 45(4):43CrossRefMATH
Xie J, Szymanski BK (2012)Towards linear time overlapping community detection in social networks. In: Advances in knowledge discovery and data mining. Springer, pp 25–36
Zakrzewska A, Bader DA (2015) A dynamic algorithm for local community detection in graphs. In: Proceedings of the 2015 IEEE/ACM international conference on advances in social networks analysis and mining 2015, (ASONAM 15). ACM, New York, pp 559–564
Metadata
Title
Tracking local communities in streaming graphs with a dynamic algorithm
Authors
Anita Zakrzewska
David A. Bader
Publication date
01-12-2016
Publisher
Springer Vienna
Published in
Social Network Analysis and Mining / Issue 1/2016
Print ISSN: 1869-5450
Electronic ISSN: 1869-5469
DOI
https://doi.org/10.1007/s13278-016-0374-5

Other articles of this Issue 1/2016

A supervised learning approach to link prediction in Twitter

  • Original Article

Using geolocated tweets for characterization of Twitter in Portugal and the Portuguese administrative regions

  • Original Article

Multi-source models for civil unrest forecasting

  • Original Article

Behavioral analysis and classification of spammers distributing pornographic content in social media

  • Original Article

Structure-preserving sparsification methods for social networks

  • Original Article

User characterization for online social networks

  • Review Article

Premium Partner

    Image Credits