research-article

Sparsification of influence networks

Authors:

Michael Mathioudakis,

Francesco Bonchi,

Carlos Castillo,

Aristides Gionis,

Antti UkkonenAuthors Info & Claims

KDD '11: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 529 - 537

https://doi.org/10.1145/2020408.2020492

Published: 21 August 2011 Publication History

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

[1]

E. Adar and L. A. Adamic. Tracking information epidemics in blogspace. In Int. Conf. on Web Intelligence (WI'05).

Digital Library

[2]

F. Bass. A new product growth model for consumer durables. Management Science, 15:215--227, 1969.

Digital Library

[3]

W. Chen, C. Wang, and Y. Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In 16th Int. Conf. on Knowledge Discovery and Data Mining (KDD'10).

Digital Library

[4]

W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In 15th Int. Conf. on Knowledge% Discovery and Data Mining (KDD'09).

Digital Library

[5]

W. Chen, Y. Yuan, and L. Zhang. Scalable influence maximization in social networks under the linear threshold model. In 10th IEEE Int. Conf. on Data Mining (ICDM'10).

Digital Library

[6]

J. Coleman, H. Menzel, and E. Katz. Medical Innovations: A Diffusion Study. Bobbs Merrill, 1966.

[7]

P. Domingos and M. Richardson. Mining the network value of customers. In 7th Int. Conf. on Knowledge Discovery and Data Mining (KDD'01).

Digital Library

[8]

M. Elkin and D. Peleg. Approximating k-spanner problems for k > 2. In 8th Conf. on Integer Programming and Combinatorial Optimization, 2001.

Digital Library

[9]

N. J. Foti and J. M. Hughes and D. N. Rockmore. Nonparametric Sparsification of Complex Multiscale Networks. PLoS ONE, 6(2), 2011.

[10]

J. Goldenberg, B. Libai, and E. Muller. Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing Letters, 12(3):211--223, 2001.

[11]

M. Gomez-Rodriguez, D. Balduzzi, and B. Schölkopf. Uncovering the Temporal Dynamics of Diffusion Networks In 28th Int. Conf. on Machine Learning (ICML'11).

[12]

M. Gomez-Rodriguez, J. Leskovec, and A. Krause. Inferring networks of diffusion and influence. In 16th Int. Conf. on Knowledge Discovery and Data Mining (KDD'10).

Digital Library

[13]

A. Goyal, F. Bonchi, and L. Lakshmanan. Discovering leaders from community actions. In 17th Conf. on Inf. and Knowledge Management (CIKM'08).

Digital Library

[14]

A. Goyal, F. Bonchi, and L. V. S. Lakshmanan. Learning influence probabilities in social networks. In Third ACM Int. Conf. on Web Search and Data Mining (WSDM'10).

Digital Library

[15]

D. Gruhl, R. V. Guha, D. Liben-Nowell, and A. Tomkins. Information diffusion through blogspace. In 13th Int. Conf. on World Wide Web, (WWW'04).

Digital Library

[16]

D. Ienco, F. Bonchi, and C. Castillo. The meme ranking problem: Maximizing microblogging virality. In SIASP 2010 workshop at ICDM.

Digital Library

[17]

D. S. Johnson. Approximation algorithms for combinatorial problems. In 5th Symp. on Theory of Computing (STOC'73).

[18]

S. Jurvetson. What exactly is viral marketing? Red Herring, 78:110--112, 2000.

[19]

D. Kempe, J. M. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. In 9th Int. Conf. on Knowledge Discovery and Data Mining (KDD'03).

Digital Library

[20]

J. Leskovec, L. A. Adamic, and B. A. Huberman. The dynamics of viral marketing. TWEB, 1(1), 2007.

Digital Library

[21]

J. Leskovec, L. Backstrom, and J. M. Kleinberg. Meme-tracking and the dynamics of the news cycle. In 15th Int. Conf. on Knowledge Discovery and Data Mining (KDD'09).

Digital Library

[22]

J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen,and N. S. Glance. Cost-effective outbreak detection in networks. In 13th Int. Conf. on Knowledge Discovery and Data Mining (KDD'07).

Digital Library

[23]

J. Leskovec, A. Singh, and J. M. Kleinberg. Patterns of influence in a recommendation network. In 10th Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD'06).

Digital Library

[24]

V. Mahajan, E. Muller, and F. Bass. New product diffusion models in marketing: A review and directions for research. Journal of Marketing, 54(1):1--26, 1990.

[25]

E. Misiolek and D. Z. Chen. Two flow network simplification algorithms. Inf. Process. Lett., 97(5):197--202, 2006.

Digital Library

[26]

G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions. Mathematical Programming, 14(1), 1978.

[27]

A. Quirin et al. A new variant of the pathfinder algorithm to generate large visual science maps in cubic time. Inf. Process. Manage., 44(4), 2008.

Digital Library

[28]

M. Richardson and P. Domingos. Mining knowledge-sharing sites for viral marketing. In 8th Int. Conf. on Knowledge Discovery and Data Mining (KDD'02).

Digital Library

[29]

K. Saito, R. Nakano, and M. Kimura. Prediction of information diffusion probabilities for independent cascade model. In 12th Int. Conf. on Knowledge-Based Int. Information and Engineering Systems (KES'08).%

Digital Library

[30]

R. Schvaneveldt, F. Durso, and D. Dearholt. Network structures in proximity data. In G. Bower, editor, The Psychology of Learning and Motivation: Advances in Research and Theory, volume 24, pages 249--284. Academic Press, New York, 1989.

[31]

E. Serrano, A. Quirin, J. A. Botía, and O. Cordón. Debugging complex software systems by means of pathfinder networks. Inf. Sci., 180(5):561--583, 2010.

Digital Library

[32]

M. A. Serrano, M. Boguná, and A. Vespignani. Extracting the multiscale backbone of complex weighted networks. Proc. of the National Academy of Sciences, 106(16):6483--6488, April 2009.

[33]

H. Toivonen, S. Mahler, and F. Zhou. A framework for path-oriented network simplification. In 9th Int. Symp. on Advances in Intelligent Data Analysis (IDA'10).

Digital Library

[34]

T. Valente. Network Models of the Diffusion of Innovations. Hampton Press, 1955.

[35]

F. Zhou, S. Mahler, and H. Toivonen. Network simplification with minimal loss of connectivity. In 9th Int. Symp. on Advances in Intelligent Data Analysis (IDA'10).

[36]

A. Arenas, J. Duch, A.Fernandez, and S. Gomez. Size reduction of complex networks preserving modularity. In New Journal of Physics 9 (2007) 176.

[37]

W.S. Fung, R. Hariharan, N.J.A. Harvey, D. Panigrahi. A General Framework for Graph Sparsification. In 33th Symp. on Theory of Computing (STOC 2011).

Digital Library

Cited By

Sun ZZeng G(2024)A Two-stage Coarsening Method for a Streaming Graph with Preserving Key FeaturesProceedings of the 2024 International Conference on Generative Artificial Intelligence and Information Security10.1145/3665348.3665392(253-260)Online publication date: 10-May-2024
https://dl.acm.org/doi/10.1145/3665348.3665392
Wen ZLiu YTan SChen JZhu MHan DYin JXu MChen W(2024)Quantivine: A Visualization Approach for Large-Scale Quantum Circuit Representation and AnalysisIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.332714830:1(573-583)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3327148
Li YGao HGao YGuo JWu W(2023)A Survey on Influence Maximization: From an ML-Based Combinatorial OptimizationACM Transactions on Knowledge Discovery from Data10.1145/360455917:9(1-50)Online publication date: 18-Jul-2023
https://dl.acm.org/doi/10.1145/3604559
Show More Cited By

Index Terms

Sparsification of influence networks
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Efficient influence maximization in social networks
KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining

Influence maximization is the problem of finding a small subset of nodes (seed nodes) in a social network that could maximize the spread of influence. In this paper, we study the efficient influence maximization from two complementary directions. One is ...
On Measurement of Influence in Social Networks
ASONAM '12: Proceedings of the 2012 International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2012)

One of the issues to be resolved in social recommender systems is the identification of opinion leaders in a network. Finding effective people in societies has been a key question for many groups, e.g., marketers. The research undertaken in this paper ...
Influence clubs in social networks
ICCCI'10: Proceedings of the Second international conference on Computational collective intelligence: technologies and applications - Volume Part II

A new model "influence club" for cohesion group in a social network is proposed. It generalizes the definition of k-club and has two advantages. First, the influence between two nodes does not only depend on the their distance but also on the numbers of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '11: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining

August 2011

1446 pages

ISBN:9781450308137

DOI:10.1145/2020408

General Chair:
Chid Apte
IBM Research
,
Program Chairs:
Joydeep Ghosh
UT Austin
,
Padhraic Smyth
UC Irvine

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 August 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

KDD '11

Sponsor:

KDD '11: The 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 21 - 24, 2011

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

126
Total Citations
View Citations
1,338
Total Downloads

Downloads (Last 12 months)53
Downloads (Last 6 weeks)5

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sun ZZeng G(2024)A Two-stage Coarsening Method for a Streaming Graph with Preserving Key FeaturesProceedings of the 2024 International Conference on Generative Artificial Intelligence and Information Security10.1145/3665348.3665392(253-260)Online publication date: 10-May-2024
https://dl.acm.org/doi/10.1145/3665348.3665392
Wen ZLiu YTan SChen JZhu MHan DYin JXu MChen W(2024)Quantivine: A Visualization Approach for Large-Scale Quantum Circuit Representation and AnalysisIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.332714830:1(573-583)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3327148
Li YGao HGao YGuo JWu W(2023)A Survey on Influence Maximization: From an ML-Based Combinatorial OptimizationACM Transactions on Knowledge Discovery from Data10.1145/360455917:9(1-50)Online publication date: 18-Jul-2023
https://dl.acm.org/doi/10.1145/3604559
Holdsworth DZagorecki A(2023)A picture paints a thousand words: supporting organizational learning in the emergency services with data visualizationThe Learning Organization10.1108/TLO-01-2022-000130:2(231-250)Online publication date: 23-Mar-2023
https://doi.org/10.1108/TLO-01-2022-0001
Quinn KTerzi ECrovella MZhang ARangwala H(2022)Characterizing Covid Waves via Spatio-Temporal DecompositionProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3534678.3539136(3783-3791)Online publication date: 14-Aug-2022
https://dl.acm.org/doi/10.1145/3534678.3539136
Wickman RIves ZBonifati AEl Abbadi A(2022)SparRL: Graph Sparsification via Deep Reinforcement LearningProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3520254(2521-2523)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3520254
Zhang XSong DTao D(2022)Sparsified Subgraph Memory for Continual Graph Representation Learning2022 IEEE International Conference on Data Mining (ICDM)10.1109/ICDM54844.2022.00177(1335-1340)Online publication date: Nov-2022
https://doi.org/10.1109/ICDM54844.2022.00177
Wickman RZhang XLi W(2022)A Generic Graph Sparsification Framework using Deep Reinforcement Learning2022 IEEE International Conference on Data Mining (ICDM)10.1109/ICDM54844.2022.00158(1221-1226)Online publication date: Nov-2022
https://doi.org/10.1109/ICDM54844.2022.00158
Hayashi TNakamura A(2022)Propagation graph estimation from individuals’ time series of observed statesScientific Reports10.1038/s41598-022-10031-312:1Online publication date: 12-Apr-2022
https://doi.org/10.1038/s41598-022-10031-3
Beldi ASassi SChbeir RJemai A(2022)Schema Formalism for Semantic Summary Based on Labeled Graph from Heterogeneous DataRecent Challenges in Intelligent Information and Database Systems10.1007/978-981-19-8234-7_3(27-44)Online publication date: 24-Nov-2022
https://doi.org/10.1007/978-981-19-8234-7_3
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents