BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen - ECPv5.7.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
X-ORIGINAL-URL:https://www.greyc.fr
X-WR-CALDESC:évènements pour GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20230326T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20231029T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20230221T100000
DTEND;TZID=Europe/Paris:20230221T110000
DTSTAMP:20260423T182016
CREATED:20230125T164357Z
LAST-MODIFIED:20230213T105441Z
UID:11083-1676973600-1676977200@www.greyc.fr
SUMMARY:Séminaire Algorithmique : Mehdi Naima « Extending Brandes algorithm to improve betweenness centrality computation in temporal graphs with discrete and continuous time »
DESCRIPTION:Betweenness centrality has been a long subject of study in network science since it was introduced by Freeman in 1977. This centrality measure assesses the importance of nodes in a graph\, it has been used for example in social\, biological and research collaboration networks. Moreover\, betweenness centrality has been used in graph partitioning and community detection in the well-known Girvan-Newan algorithm.\n\nThis centrality measure is based on the enumeration of shortest paths passing through a node. 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(n3). Brandes in 2001 published an algorithm that runs in O(nm + n2 log n) on weighted graphs\,  it is still considered one of the best theoretical results on the question.\n\nBetweenness 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. We will see that we are able to deploy Brandes algorithm to its full extent and improve the running time of recent results to O(nmT + n2Tlog(nT)). We will also discuss how Brandes algorithm can also be generalized to stream graphs which are dynamic graphs with continuous time and dynamicity on the nodes.
URL:https://www.greyc.fr/event/seminaire-algorithmique-mehdi-naima/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,Séminaire Algo
END:VEVENT
END:VCALENDAR