Recovering Static and Time-Varying Communities Using Persistent Edges

Konstantin Avrachenkov*, Maximilien Dreveton, Lasse Leskela

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

26 Downloads (Pure)

Abstract

This article focuses on spectral methods for recovering communities in temporal networks. In the case of fixed communities, spectral clustering on the simple time-aggregated graph (i.e., the weighted graph formed by the sum of the interactions over all temporal snapshots) does not always produce satisfying results. To utilise information carried by temporal correlations, we propose to employ different weights on freshly appearing and persistent edges. We show that spectral clustering on such weighted graphs can be explained as a relaxation of the maximum likelihood estimator of an extension of the degree-corrected stochastic block model with Markov interactions. We also study the setting of evolving communities, for which we use the prediction at time t-1 as an oracle for inferring the community labels at time t. We demonstrate the accuracy of the proposed methods on synthetic and real data sets.

Original languageEnglish
Pages (from-to)2087-2099
Number of pages13
JournalIEEE Transactions on Network Science and Engineering
Volume11
Issue number2
DOIs
Publication statusPublished - 1 Mar 2024
MoE publication typeA1 Journal article-refereed

Keywords

  • Graph clustering
  • spectral methods
  • stochastic block model
  • temporal networks

Fingerprint

Dive into the research topics of 'Recovering Static and Time-Varying Communities Using Persistent Edges'. Together they form a unique fingerprint.

Cite this