2014 FastInfluencebasedCoarseningfor

• (Purohit et al., 2014) ⇒ Manish Purohit, B. Aditya Prakash, Chanhyun Kang, Yao Zhang, and V.S. Subrahmanian. (2014). “Fast Influence-based Coarsening for Large Networks.” In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2014) Journal. ISBN:978-1-4503-2956-9 doi:10.1145/2623330.2623701

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222014%22+Fast+Influence-based+Coarsening+for+Large+Networks
• http://dl.acm.org/citation.cfm?id=2623330.2623701&preflayout=flat#citedby

Quotes

Author Keywords

• Coarsening; data mining; diffusion; graph mining; propagation

Abstract

Given a social network, can we quickly 'zoom-out' of the graph? Is there a smaller equivalent representation of the graph that preserves its propagation characteristics? Can we group nodes together based on their influence properties? These are important problems with applications to influence analysis, epidemiology and viral marketing applications.

In this paper, we first formulate a novel Graph Coarsening Problem to find a succinct representation of any graph while preserving key characteristics for diffusion processes on that graph. We then provide a fast and effective near-linear-time (in nodes and edges) algorithm COARSENET for the same. Using extensive experiments on multiple real datasets, we demonstrate the quality and scalability of COARSENET, enabling us to reduce the graph by 90% in some cases without much loss of information. Finally we also show how our method can help in diverse applications like influence maximization and detecting patterns of propagation at the level of automatically created groups on real cascade data.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2014 FastInfluencebasedCoarseningfor	B. Aditya Prakash Manish Purohit Chanhyun Kang Yao Zhang V.S. Subrahmanian			Fast Influence-based Coarsening for Large Networks				10.1145/2623330.2623701		2014