document: Sparsification of influence networks 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 .
doc_bio_tags: O O B O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O