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
Community discovery, Database applications, Data mining, Clustering
Pedreschi Dino, Coscia Michele, Rossetti Giulio, Giannotti Fosca
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 IDs
CNR OAI-PMH: oai:it.cnr:prodotti:274748