Information Spreading in Non-homogeneous Evolving Networks with node and edge deletion

Natalia Markovich, Maksim Ryzhov
A preferential attachment (PA) has been suggested to model network evolution and to explain conjectured power-law node degree distributions in real-world networks. In Markovich, Ryzhov (2022a,b), the schemes of the linear PA proposed in Wan et al. (2020) for the network evolution were suggested for information spreading. The PA and the well-known algorithm SPREAD proposed in Mosk-Aoyama, Shah (2006) were compared regarding the minimum number of evolution steps $K^*$ required to spread a single message among a fixed number of nodes in non-homogeneous directed networks. This comparison was done in Markovich, Ryzhov (2022a,b) without node and edge deletion during the evolution. The objective of the current study is to investigate the impact of the PA parameters on spreading of a single message to a fixed number of nodes in the graph when an existing node or edge is uniformly deleted at each step of the PA evolution. The results are provided for simulated and real graphs.