DEMON: a local-first discovery method for overlapping communities (Rapporti tecnici/preprint/working paper)

Type
Label
  • DEMON: a local-first discovery method for overlapping communities (Rapporti tecnici/preprint/working paper) (literal)
Anno
  • 2012-01-01T00:00:00+01:00 (literal)
Alternative label
  • Coscia M., Rossetti G., Giannotti F., Pedreschi D. (2012)
    DEMON: a local-first discovery method for overlapping communities
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Coscia M., Rossetti G., Giannotti F., Pedreschi D. (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#altreInformazioni
  • Grant agreement 270833 : Tipo Progetto EU_FP7 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#url
  • http://arxiv.org/abs/1206.0629 (literal)
Note
  • PuMa (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#supporto
  • Altro (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Harvard University, Cambridge, MA, USA; Department of Computer Science, University of Pisa; CNR-ISTI, Pisa, Italy; Department of Computer Science, University of Pisa; (literal)
Titolo
  • DEMON: a local-first discovery method for overlapping communities (literal)
Abstract
  • Community discovery in complex networks is an interest- ing problem with a number of applications, especially in the knowledge extraction task in social and information net- works. However, many large networks often lack a particular community organization at a global level. In these cases, tra- ditional graph partitioning algorithms fail to let the latent knowledge embedded in modular structure emerge, because they impose a top-down global view of a network. We pro- pose here a simple local-rst approach to community dis- covery, able to unveil the modular organization of real com- plex networks. This is achieved by democratically letting each node vote for the communities it sees surrounding it in its limited view of the global system, i.e. its ego neighbor- hood, using a label propagation algorithm; nally, the local communities are merged into a global collection. We tested this intuition against the state-of-the-art overlapping and non-overlapping community discovery methods, and found that our new method clearly outperforms the others in the quality of the obtained communities, evaluated by using the extracted communities to predict the metadata about the nodes of several real world networks. We also show how our method is deterministic, fully incremental, and has a lim- ited time complexity, so that it can be used on web-scale real networks (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Prodotto
Autore CNR di
Insieme di parole chiave di
data.CNR.it