Rapporto tecnico, 2012, ENG

DEMON: a local-first discovery method for overlapping communities

Coscia M., Rossetti G., Giannotti F., Pedreschi D.

Harvard University, Cambridge, MA, USA; Department of Computer Science, University of Pisa; CNR-ISTI, Pisa, Italy; Department of Computer Science, University of Pisa;

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

Keywords

Community discovery, Database applications, Data mining, Clustering

CNR authors

Pedreschi Dino, Coscia Michele, Rossetti Giulio, Giannotti Fosca

CNR institutes

ISTI – Istituto di scienza e tecnologie dell'informazione "Alessandro Faedo"

ID: 274748

Year: 2012

Type: Rapporto tecnico

Creation: 2013-12-17 12:38:50.000

Last update: 2020-12-24 11:08:24.000

External links

OAI-PMH: Dublin Core

OAI-PMH: Mods

OAI-PMH: RDF

URL: http://arxiv.org/abs/1206.0629

External IDs

CNR OAI-PMH: oai:it.cnr:prodotti:274748