2012 DEMONALocalFirstDiscoveryMethod

• (Coscia et al., 2012) ⇒ Michele Coscia, Giulio Rossetti, Fosca Giannotti, and Dino Pedreschi. (2012). “DEMON: A Local-first Discovery Method for Overlapping Communities.” In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2012). ISBN:978-1-4503-1462-6 doi:10.1145/2339530.2339630

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222012%22+DEMON%3A+A+Local-first+Discovery+Method+for+Overlapping+Communities
• http://dl.acm.org/citation.cfm?id=2339530.2339630&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; community discovery; complex networks; data mining

Abstract

Community discovery in complex networks is an interesting problem with a number of applications, especially in the knowledge extraction task in social and information networks. However, many large networks often lack a particular community organization at a global level. In these cases, traditional 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 propose here a simple local-first approach to community discovery, able to unveil the modular organization of real complex 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 neighborhood, using a label propagation algorithm; finally, 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 limited time complexity, so that it can be used on web-scale real networks.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2012 DEMONALocalFirstDiscoveryMethod	Fosca Giannotti Dino Pedreschi Michele Coscia Giulio Rossetti			DEMON: A Local-first Discovery Method for Overlapping Communities				10.1145/2339530.2339630		2012