TY - GEN
T1 - Recovering Communities in Temporal Networks Using Persistent Edges
AU - Avrachenkov, Konstantin
AU - Dreveton, Maximilien
AU - Leskelä, Lasse
N1 - Funding Information:
This work has been done within the project of Inria - Nokia Bell Labs “Distributed Learning and Control for Network Analysis” and was partially supported by COSTNET Cost Action CA15109.
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
KW - Graph clustering
KW - Spectral methods
KW - Stochastic block model
KW - Temporal networks
UR - http://www.scopus.com/inward/record.url?scp=85121851101&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-91434-9_22
DO - 10.1007/978-3-030-91434-9_22
M3 - Conference article in proceedings
AN - SCOPUS:85121851101
SN - 978-3-030-91433-2
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 243
EP - 254
BT - Computational Data and Social Networks - 10th International Conference, CSoNet 2021, Proceedings
A2 - Mohaisen, David
A2 - Jin, Ruoming
PB - Springer
T2 - International Conference on Computational Data and Social Networks
Y2 - 15 November 2021 through 17 November 2021
ER -