ETD

Archivio digitale delle tesi discusse presso l'Università di Pisa

Tesi etd-02042011-113617


Tipo di tesi
Tesi di laurea magistrale
Autore
MONTANARI, SANDRO
URN
etd-02042011-113617
Titolo
Some instances of Community discovery in graphs and hypergraphs
Dipartimento
SCIENZE MATEMATICHE, FISICHE E NATURALI
Corso di studi
INFORMATICA
Relatori
relatore Prof. Luccio, Fabrizio
Parole chiave
  • LS-sets
  • betweenness
  • distributed algorithms
  • cohesive group
Data inizio appello
11/03/2011
Consultabilità
Completa
Riassunto
In chapter 1, we introduce the problem of Community Discovery in graphs, and explain the terminology adopted in our work.
In chapter 2, we look at some classical definitions of communities, LS sets and Betweenness Clustering. After a brief explanation of their properties, we show and analyse the algorithms for their identification.
In chapter 3, we introduce the concept of local community and show some definitions of this kind: k-cores and alpha sets. Since finding all the local communities of a graph can be infeasible, we therefore propose an algorithm for the identification of maximal local communities in a distributed environment.
In chapter 4, we extend community discovery to hypergraphs, and show that the concept of local communities can be generalised to hyper communities. Furthermore, we propose an alternative distributed algorithm with a better running time than the one for graphs, exploiting an increased level of concurrency.
At the end we summarize our results, and put the basis for possible future works on this subject.
File