Lecture
Seminar: POPNET Connects with Vincent Traag
- Date
- Thursday 27 October 2022
- Time
- Location
- Snellius and online - register below
Large network community detection by fast label propagation
Many networks exhibit some community structure. There exists a wide variety of approaches to detect communities in networks, each offering different interpretations and associated algorithms. For large networks, there is the additional requirement of speed. In this context, the so-called label propagation algorithm (LPA) was proposed, which runs in near linear time. In partitions uncovered by LPA, each node is ensured to have most links to its assigned community. We here propose a fast variant of LPA (FLPA) that is based on processing a queue of nodes whose neighbourhood recently changed. We test FLPA exhaustively on benchmark networks and empirical networks, finding that it runs up to 700 times faster than LPA. In partitions found by FLPA, we prove that each node is again guaranteed to have most links to its assigned community. Our results show that FLPA is generally preferable to LPA.
About Vincent Traag
Vincent Traag is a senior researcher at the Centre for Science and Technology Studies (CWTS) of Leiden University in the Netherlands. He leads the research line on modelling the research system within the Quantitative Science Studies (QSS) research group. His main interests are mathematical models in the social sciences with a focus on (social) networks. In addition to his scientific research, Traag also acts as a bibliometric consultant at the CWTS.
Traag obtained his Master in sociology (cum laude) from the University of Amsterdam (2008). Coming from a computer science background, and taking up mathematics during his studies in sociology, he went on to obtain a PhD in applied mathematics in Louvain-la-Neuve, Belgium (2013). During his PhD he studied methods for detecting communities in complex networks, resulting in a Python software package. In addition, he applied this methodology in several fields across the (social) sciences, ranging from citation networks to international relations. He joined the CWTS in 2015.