Aurélie Faure de Pebeyre, Fabien Tarissan et Julien Sopena

The development of wireless devices led the scientific community

to focus more and more on systems of interaction composed of

moving entities. In this context, different models have been

proposed in an attempt to capture properties of the observed

dynamics. Among those models, the edge-Markovian evolving graph

model is appealing since it enables to highlight temporal

dependencies in the evolution of the graphs. This model relies on

two parameters accounting respectively for the creation and

suppression of links in the graph. Thus it assumes that these two

parameters are sufficient to characterise the dynamics during all

the evolution of the graph. In this paper, we test this

hypothesis by confronting the model to 6 datasets recording real

traces of evolving networks. In particular, we study the

proportion of created and deleted links over the time. The

results show that 5 of the 6 case studies present an

heterogeneous distribution of those fractions which contradicts

the underlying hypothesis of the model. Besides, in order to

understand the importance this might have as regard structural

properties of real networks, we also study the impact the

Markovian model has on the mean degree over the time. It turns

out that even in the suitable case, the model fails to reproduce

correctly this property which indicates its inadequacy for even

more complex properties of real evolving networks

AurĂ©lie Faure de Pebeyre, Fabien Tarissan et Julien Sopena