Group Betweenness Centrality on Dynamic Graphs
Master thesis
Permanent lenke
https://hdl.handle.net/11250/3029438Utgivelsesdato
2022Metadata
Vis full innførselSamlinger
Beskrivelse
Full text not available
Sammendrag
Denne oppgaven utforsker muligheten for å utvide den populære datagruvedrift operasjonen mellomplasseringssentralitet, på engelsk betweenness centrality. Vi utvider operasjonen til å kunne regne ut viktigheten av flere grupper med noder samtidig i en graf som endrer seg over tid. Ved denne utvidelsen presenterer vi en ny algoritme, dynamisk algoritme for mellomplasseringssentralitet for grupper av noder. Denne algoritmen er den første, ikke trivielle algoritmen som kan regne ut viktigheten av grupper på en graf som endrer seg over tid
Våre funn viser at vår nye algoritme presterer bedre enn dagens toppmoderne algoritme i mange viktige tilfeller
Denne oppgaven utforsker og presenterer lignende akademisk arbeid og presenterer en kvalitativ analyse for hvilke algoritmer fra gruppe mellomplasseringssentralitet og dynamisk mellomplasseringssentralitet som burde kombineres til en ny løsning. Ved å gjøre det mulig å regne ut viktigheten av grupper i en graf som endrer seg over tid vil man mer effektivt kunne tilegne seg ny kunnskap om gruppedynamikk og hvordan viktige grupper samspiller i en graf. This thesis expands on the commonly used data mining operation betweenness centrality. It combines an extension to the group case and the dynamic incrementally updating case, creating a novel dynamic group betweenness centrality algorithm. The algorithm is the first non-trivial algorithm that can calculate the group betweenness centrality of multiple different groups in a single run, and still have an updated state after an edge is removed or added to a graph.
Our findings indicate that our novel dynamic group betweenness centrality algorithm correctly updates the betweenness centrality score for an incoming edge stream faster than the state of the art for most cases.
Our thesis explores and presents similar work from both the dynamic betweenness domain and the group betweenness domain and presents a qualitative evaluation on how best to combine them. More efficient, dynamically updating group betweenness will allow us to monitor important groups and their influence over a graph over time, revealing information about group dynamics in a more efficient and accessible manner than before.