2011 SparsificationofInfluenceNetwor

• (Mathioudakis et al., 2011) ⇒ Michael Mathioudakis, Francesco Bonchi, Carlos Castillo, Aristides Gionis, and Antti Ukkonen. (2011). “Sparsification of Influence Networks.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020492

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Sparsification+of+Influence+Networks
• http://dl.acm.org/citation.cfm?id=2020408.2020492&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; data mining; influence; propagation; social networks

Abstract

We present Spine, an efficient algorithm for finding the "backbone" of an influence network. Given a social graph and a log of past propagations, we build an instance of the independent-cascade model that describes the propagations. We aim at reducing the complexity of that model, while preserving most of its accuracy in describing the data.

We show that the problem is inapproximable and we present an optimal, dynamic-programming algorithm, whose search space, albeit exponential, is typically much smaller than that of the brute force, exhaustive-search approach. Seeking a practical, scalable approach to sparsification, we devise Spine, a greedy, efficient algorithm with practically little compromise in quality.

We claim that sparsification is a fundamental data-reduction operation with many applications, ranging from visualization to exploratory and descriptive data analysis. As a proof of concept, we use Spine on real-world datasets, revealing the backbone of their influence-propagation networks. Moreover, we apply Spine as a pre-processing step for the influence-maximization problem, showing that computations on sparsified models give up little accuracy, but yield significant improvements in terms of scalability.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 SparsificationofInfluenceNetwor	Francesco Bonchi Aristides Gionis Carlos Castillo Michael Mathioudakis Antti Ukkonen			Sparsification of Influence Networks				10.1145/2020408.2020492		2011