TY - JOUR
T1 - Reciprocity, community detection, and link prediction in dynamic networks
AU - Safdari, Hadiseh
AU - Contisciani, Martina
AU - De Bacco, Caterina
N1 - Publisher Copyright:
© 2022 The Author(s). Published by IOP Publishing Ltd.
PY - 2022/3/1
Y1 - 2022/3/1
N2 - Many complex systems change their structure over time, in these cases dynamic networks can provide a richer representation of such phenomena. As a consequence, many inference methods have been generalized to the dynamic case with the aim to model dynamic interactions. Particular interest has been devoted to extend the stochastic block model and its variant, to capture community structure as the network changes in time. While these models assume that edge formation depends only on the community memberships, recent work for static networks show the importance to include additional parameters capturing structural properties, as reciprocity for instance. Remarkably, these models are capable of generating more realistic network representations than those that only consider community membership. To this aim, we present a probabilistic generative model with hidden variables that integrates reciprocity and communities as structural information of networks that evolve in time. The model assumes a fundamental order in observing reciprocal data, that is an edge is observed, conditional on its reciprocated edge in the past. We deploy a Markovian approach to construct the network's transition matrix between time steps and parameters' inference is performed with an expectation-maximization algorithm that leads to high computational efficiency because it exploits the sparsity of the dataset. We test the performance of the model on synthetic dynamical networks, as well as on real networks of citations and email datasets. We show that our model captures the reciprocity of real networks better than standard models with only community structure, while performing well at link prediction tasks.
AB - Many complex systems change their structure over time, in these cases dynamic networks can provide a richer representation of such phenomena. As a consequence, many inference methods have been generalized to the dynamic case with the aim to model dynamic interactions. Particular interest has been devoted to extend the stochastic block model and its variant, to capture community structure as the network changes in time. While these models assume that edge formation depends only on the community memberships, recent work for static networks show the importance to include additional parameters capturing structural properties, as reciprocity for instance. Remarkably, these models are capable of generating more realistic network representations than those that only consider community membership. To this aim, we present a probabilistic generative model with hidden variables that integrates reciprocity and communities as structural information of networks that evolve in time. The model assumes a fundamental order in observing reciprocal data, that is an edge is observed, conditional on its reciprocated edge in the past. We deploy a Markovian approach to construct the network's transition matrix between time steps and parameters' inference is performed with an expectation-maximization algorithm that leads to high computational efficiency because it exploits the sparsity of the dataset. We test the performance of the model on synthetic dynamical networks, as well as on real networks of citations and email datasets. We show that our model captures the reciprocity of real networks better than standard models with only community structure, while performing well at link prediction tasks.
KW - community detection
KW - dynamical networks
KW - networks
KW - probabilistic inference
UR - http://www.scopus.com/inward/record.url?scp=85126859045&partnerID=8YFLogxK
U2 - 10.1088/2632-072X/ac52e6
DO - 10.1088/2632-072X/ac52e6
M3 - Article
AN - SCOPUS:85126859045
SN - 2632-072X
VL - 3
JO - Journal of Physics: Complexity
JF - Journal of Physics: Complexity
IS - 1
M1 - 015010
ER -