DEMON: Uncovering Overlapping Communities with a Local-First Approach

Day - Time: 23 April 2013, h.15:00
Place: Area della Ricerca CNR di Pisa - Room: C-29

Giulio Rossetti


Community discovery in complex networks is an interesting problem witha number of applications, especially in the knowledge extraction taskin social and information networks. However, many large networks oftenlack a particular community organization at a global level. In thesecases, traditional graph partitioning algorithms fail to let thelatent knowledge embedded in modular structure emerge, because theyimpose a top-down global view of a network. DEMON is a simplelocal-first approach to community discovery, able to unveil themodular organization of real complex networks. This is achieved bydemocratically letting each node vote for the communities it seessurrounding it in its limited view of the global system, i.e. its egoneighborhood, using a label propagation algorithm; finally, the localcommunities are merged into a global collection.

NOTE: This seminar is the first one of the series of six seminarspresented by the winners of the prize "Young researchers ISTI 2013".Giulio Rossetti placed second in the PhD student category.