2014 ScalableDiffusionAwareOptimizat

• (Khalil et al., 2014) ⇒ Elias Boutros Khalil, Bistra Dilkina, and Le Song. (2014). “Scalable Diffusion-aware Optimization of Network Topology.” 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.2623704

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222014%22+Scalable+Diffusion-aware+Optimization+of+Network+Topology
• http://dl.acm.org/citation.cfm?id=2623330.2623704&preflayout=flat#citedby

Quotes

Author Keywords

• Approximation; data mining; diffusion networks; network optimization; supermodularity

Abstract

How can we optimize the topology of a networked system to bring a flu under control, propel a video to popularity, or stifle a network malware in its infancy? Previous work on information diffusion has focused on modeling the diffusion dynamics and selecting nodes to maximize / minimize influence. Only a paucity of recent studies have attempted to address the network modification problems, where the goal is to either facilitate desirable spreads or curtail undesirable ones by adding or deleting a small subset of network nodes or edges. In this paper, we focus on the widely studied linear threshold diffusion model, and prove, for the first time, that the network modification problems under this model have supermodular objective functions. This surprising property allows us to design efficient data structures and scalable algorithms with provable approximation guarantees, despite the hardness of the problems in question. Both the time and space complexities of our algorithms are linear in the size of the network, which allows us to experiment with millions of nodes and edges. We show that our algorithms outperform an array of heuristics in terms of their effectiveness in controlling diffusion processes, often beating the next best by a significant margin.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2014 ScalableDiffusionAwareOptimizat	Elias Boutros Khalil Bistra Dilkina Le Song			Scalable Diffusion-aware Optimization of Network Topology				10.1145/2623330.2623704		2014