Recovering Communities in Temporal Networks Using Persistent Edges

Konstantin Avrachenkov*, Maximilien Dreveton, Lasse Leskelä

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

1 Citation (Scopus)

Abstract

This article studies the recovery of static communities in a temporal network. We introduce a temporal stochastic block model where dynamic interaction patterns between node pairs follow a Markov chain. We render this model versatile by adding degree correction parameters, describing the tendency of each node to start new interactions. We show that in some cases the likelihood of this model is approximated by the regularized modularity of a time-aggregated graph. This time-aggregated graph involves a trade-off between new edges and persistent edges. A continuous relaxation reduces the regularized modularity maximization to a normalized spectral clustering. We illustrate by numerical experiments the importance of edge persistence, both on simulated and real data sets.

Original languageEnglish
Title of host publicationComputational Data and Social Networks - 10th International Conference, CSoNet 2021, Proceedings
EditorsDavid Mohaisen, Ruoming Jin
PublisherSpringer
Pages243-254
Number of pages12
ISBN (Print)978-3-030-91433-2
DOIs
Publication statusPublished - 2021
MoE publication typeA4 Conference publication
EventInternational Conference on Computational Data and Social Networks - Virtual, Online
Duration: 15 Nov 202117 Nov 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Volume13116 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Computational Data and Social Networks
Abbreviated titleCSoNet
CityVirtual, Online
Period15/11/202117/11/2021

Keywords

  • Graph clustering
  • Spectral methods
  • Stochastic block model
  • Temporal networks

Fingerprint

Dive into the research topics of 'Recovering Communities in Temporal Networks Using Persistent Edges'. Together they form a unique fingerprint.

Cite this