Community detection in networks: a heuristic version of Girvan Newman algorithm

Complex problems in different fields can be modeled by graph data structures. An important and challenging task is the community detection, i.e. the identification of highly connected components. The Girvan Newman algorithm identifies high-quality communities but is not computationally suitable for huge graph analysis. Therefore, we propose a heuristic version of this algorithm, by considering an approximated measure of the edge betweenness. We evaluate the performances of our proposal on benchmark networks.

I grafi permettono di modellare problemi complessi di diversa natura. Una delle questioni più stimolanti e importanti è il rilevamento delle comunità, cioè l’identificazione di componenti altamente connesse. L’algoritmo di Girvan Newman è in grado di identificare tali componenti con successo, ma non è computazionalmente adatto ad un’analisi di grafi di grandi dimensioni. Pertanto, proponiamo una versione euristica di questo algoritmo, approssimando la misura di betweenness degli archi. Analizziamo le prestazioni della nostra proposta utilizzando reti benchmark.