Michal Ratajczak Undergraduate Dissertation 2017/18

Rumor spreading in Geometric Inhomogeneous Random Graphs

Supervised by D.Sudholt

Abstract

This study aims to investigate how information is propagated through networks, specifically Geometric Inhomogeneous Random Graphs (which will be referred to by their abbreviation, GIRGs), and how different parameters effect the propagation time. A computer model will be implemented to generate and analyse examples of such networks. The specific type of information propagation studied is rumor spreading, using the well known pull-push model and two novel proposed variations. The results show that GIRGs, when using the PUSH-PULL model, propagate a rumor in Θ(log n) rounds. This is in agreement with studies done on real-world networks and networks generated with other models. Results for the two proposed variants of the PUSH-PULL model show that in network where each node v has some probability P_v to spread a rumor, where P_v is drawn form a symmetrical Gaussian distribution, it is sufficient to only know the mean value to accurately predict the propagation time. The study also finds that randomly informing a small percentage of nodes (as opposed to a single node) before propagating a rumor with the standard PUSH-PULL model greatly reduces the number of rounds it takes to inform all nodes.