Impact of Central Nodes in Information Propagation over Graphs

Abstract: There are many systems which can be represented as graphs, to say the least the networks in which we communicate with each other. Thorough understanding of graph structures enables better predictions of the dynamics in real life networks, such as the spreading of a disease in a community or failure propagation in a system. This thesis investigates information propagation over connected undirected graphs, where the nodes communicate mutually. Every pair of nodes can send information to one another over the edge that connects them. The information propagation is initiated by a single node, which is the source of the spreading; our interest of research lies in how the time until the information has reached the entire graph relates to the theoretical centrality of this node. Furthermore, the thesis treats a power centrality measure proposed in an earlier paper by Phillip Bonacich. Our contribution in this regard is a rigorous derivation of a closed-form expression of the mean-measure and some properties appurtenant to it. An Information Propagation Model (abbreviated IPM) is presented, devised to emulate the dynamics of mutual sharing of information between nodes. When performing this algorithm on certain Barabási–Albert graphs, results show that the centrality status of the initiator node has notable impact. In agreement with conception, in mean-limit, when the information propagation is initiated by a node with high centrality (according to the theoretical measure), the information is spread significantly faster on the graph. The IPM furthermore displays similar traits in dynamics to the SIR (susceptible-infectious-recovered) compartmental model.