Information Spreading in Random Graphs Evoving by Norros-Reittu Model

2025/05/14 by Natalia M. Markovich, Markovich, N. M., D. V. Osipov +1
Physics and Astronomy · #FOS: Mathematics #Opinion Dynamics and Social Influence #Probability (math.PR) #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2505.09713

openalex publication_date 2025/05/14 · openalex created_date 2025/10/15 · openalex updated_date 2026/07/28

Abstract

The paper is devoted to the spreading of a message within the random graph evolving by the Norros-Reittu preferential attachment model. The latter model forms random Poissonian numbers of edges between newly added nodes and existing ones. For a pre-fixed time T^*, the probability mass functions of the number of nodes obtained the message and the total number of nodes in the graph, as well as the distribution function of their ratio are derived. To this end, the success probability to disseminate the message from the node with the message to the node without message is proved. The exposition is illustrated by the simulation study.

Citations

• Stochastic heterogeneous SIR model with infection-age dependent infectivity on large random graphs
• Contagion dynamics in time-varying metapopulation networks with node's activity and attractiveness
• The Poisson binomial distribution -- Old & New
• The Poisson Binomial Distribution— Old & New
• Are Extreme Value Estimation Methods Useful for Network Data?

Related

• Quasirandom Rumor Spreading
• Constrained information transmission on Erdös-Rényi graphs
• Virus spread and voter model on random graphs with multiple type nodes
• Preferential Attachment and Vertex Arrival Times
• Random Information Spread in Networks