Abstract: Betweenness centrality has been a long subject of study in network science since it was introduced by Freeman in 1977. This centrality measure asses the importance of nodes in a graph, it has been used for example in social, biological and research collaboration networks. Moreover, betweenness centralit has been used in graph partitioning and community detection in the well-known Girvan-Newan algorithm.
A simple approach to compute betweenness centrality for all the nodes of a static graph is to use Floyd-Warshall algorithm that runs in O(n^3). Brandes in 2001 published an algorithm that runs in O(nm + n^2 log n ) on weighted graphs, it is still considered one of the best theoretical results on the question.
Betweenness centrality has also been extended to temporal graphs. Temporal graphs have edges that bear labels according to the time of the interactions between the nodes. Betweenness centrality has been extended to the temporal graph settings, and the notion of paths has been extended to temporal paths. Recent results by Buss et al. and Rymar et al. extended Brandes algorithm to the temporal setting with a general algorithm running in O(n^2mT^2), where T is the number of time units. Their results rise 2 questions, one is about the nature of temporal paths and the other considering the extension of Brandes algorithm to the temporal setting. In the seminar we will discuss these issues and address them. We will see that we are able to deploy Brandes algorithm to its full extent and improve the running time of these recent results to O(nmT + n^2Tlog(nT)). We will also discuss how Brandes algorithm can also be generalized to stream graphs which are dynamic graphs with possible continuous time.
Bio: Since September 2021 I started a postdoc position at Sorbonne Université in the ComplexNetworks team. I am mostly working on graph metrics and graph random generation. My main subjects of interest are graph theory, dynamic graphs, combinatorics, random generation, analysis of algorithms and evolution processes than can model data structures and phylogenetic trees.
During my PhD I mostly worked around the enumeration, asymptotics and properties of increasing trees with label repetitions and finding connections with classical combinatorial objects. I also worked on the average tree compaction of some classes of increasing trees.
PDF
