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.

Popular Abstract (Swedish)

Många system kan representeras som grafer, alltifrån neurala nätverk och transportnätverk till något så vardagligt som våra umgängeskretsar. Om exempelvis Andrea är vän med Jona- than, så kan vi rita ut Andrea och Jonathan som var sin prick på ett paper och låta deras vän- skap representeras av en linje. På samma sätt kan vi enkelt lägga till fler personer (prickar) och rita fler linjer till alla deras vänner. Vi har då representerat ett socialt nätverk med hjälp av en graf; i ett matematiskt sammanhang så benämns prickarna som noder och linjerna som kanter. Relationerna (kanterna) kan förstås ha många olika innebörder. I en epidemi kan kanten representera att Andrea och Jonathan kan råka smitta varandra om den ena är sjuk. I sociala medier kan kanten representera att de är ”vänner” på plattformen. Relationen som de har i dessa exempel innebär alltså att information kan överföras mellan dem. Om Andrea har en sensationell nyhet som hon berättar för Jonathan så är det möjligt att han berättar vidare nyheten för sina vänner - som i sin tur kanske berättar för sina vänner. Informationen som är nyheten sprids då över nätverket som Andrea och Jonathan ingår i. En frågeställning i det här sammanhanget är hur snabbt informationen sprids – når nyheten ut snabbare om Andrea är den som orsakar spridningen, eller Jonathan? I det här exjobbet har vi studerat just den här frågeställningen, fast under mer generella ramverk.

När man studerar omfattande, komplexa nätverk är det eftersträvansvärt att kunna iden- tifiera de mest centrala medlemmarna utifrån nätverksstrukturen. Avstampen för det här projektet bygger vidare på ett teoretiskt mått från en välciterad artikel av Philipp Bonacich, vilken mäter varje nods centralitet i en graf relativt de andra noderna. I projektet har därpå informationsflöden över grafer studerats och en spridningsmodell har för detta ändamål utvecklats; denna har tillämpats för att mäta hur stor inverkan centraliteten har för medlem- mar som orsakar spridningarna över nätverk.

I graferna som vi studerar så kommunicerar noderna med varandra, vilket innebär att de ständigt transmitterar information till deras grannar. Varje nod tilldelas även en egen Markov- kedja, vilken används för att ”aktivera” nodens roll som spridare och mottagare. Vi studerar informationsspridningar som induceras av just en enda nod, varifrån informationen fortsät- ter att spridas genom att varje nod delar med sig information till närliggande noder, så fort noden själv är mottaglig och besitter informationen. Med hjälp av olika teoretiska mått mäter vi hur pass centrala noderna är; däribland noden som informationsspridningen börjar ifrån. Resultaten kan påvisa en koppling mellan hur snabbt information kan sprida sig över vissa nätverk och den teoretiska centraliteten hos medlemmen som orsakar spridningen; vi studerar spridningar över Barabási-Albert-nätverk i synnerhet, då dessa besitter egenskaper som kan observeras i riktiga nätverk, såsom sociala nätverk. Vilken nod som initierar spridningen har signifikant betydelse för hur snabbt informationen propagerar över grafen i helhet. Är det en central nod sprids informationen snabbare, vilket ligger i linje med förväntat resultat.

• author: Mellegård, Oskar
• supervisor: Stanislav Volkov
• organization: Mathematical Statistics
• course: FMSM01 20222
• year: 2023
• type: H2 - Master's Degree (Two Years)
• subject: Mathematics and Statistics
• publication/series: Master's Theses in Mathematical Sciences
• report number: LUTFMS-3464-2023
• ISSN: 1404-6342
• other publication id: 2023:E5
• language: English
• id: 9111092
• date added to LUP: 2023-02-22 16:09:44
• date last changed: 2023-02-22 16:09:44