research-article

Increasing Coverage of Information Diffusion Processes by Reducing the Number of Initial Seeds

Authors:

Jarosław Jankowski,

Radosław Michalski,

Artur KarczmarczykAuthors Info & Claims

ASONAM '17: Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017

Pages 713 - 720

https://doi.org/10.1145/3110025.3110148

Published: 31 July 2017 Publication History

Abstract

Initialization of information spreading processes within complex networks is usually based on selection of initial nodes as a seed set. While most methods are choosing seeds in a single stage, another possible option is a partial budget usage in the first stage and spending the remaining budget while the process develops. In this paper we analyze how the ratio of seeds used in the primary and supporting stages affects the performance in terms of number of activated nodes and its duration. We have used real networks and agent based simulations with various parameters including different propagation probabilities, nodes selection strategies and number of seeds. Results show that coverage can be improved by minimizing the number of seeds used in primary seeding and increasing it in supporting seeding. Delaying the use of supporting seeds better supports natural diffusion processes and avoids selection of seeds with high potential to be activated anyway.

References

[1]

E. Bakshy, I. Rosenn, C. Marlow, and L. Adamic, "The role of social networks in information diffusion," in Proceedings of the 21st international conference on World Wide Web. ACM, 2012, pp. 519--528.

Digital Library

[2]

L. Wang and B. C. Wood, "An epidemiological approach to model the viral propagation of memes," Applied Mathematical Modelling, vol. 35, no. 11, pp. 5442--5447, 2011.

[3]

G. Christodoulou, C. Georgiou, and G. Pallis, "The role of twitter in youtube videos diffusion," Web Information Systems Engineering-WISE 2012, pp. 426--439, 2012.

Digital Library

[4]

J. Y. Ho and M. Dempsey, "Viral marketing: Motivations to forward online content," Journal of Business research, vol. 63, no. 9, pp. 1000--1006, 2010.

[5]

K. Kandhway and J. Kuri, "How to run a campaign: Optimal control of sis and sir information epidemics," Applied Mathematics and Computation, vol. 231, pp. 79--92, 2014.

Digital Library

[6]

R. Van der Lans, G. Van Bruggen, J. Eliashberg, and B. Wierenga, "A viral branching model for predicting the spread of electronic word of mouth," Marketing Science, vol. 29, no. 2, pp. 348--365, 2010.

Digital Library

[7]

J. Jankowski, R. Michalski, and P. Kazienko, "The multidimensional study of viral campaigns as branching processes," in International Conference on Social Informatics. Springer, 2012, pp. 462--474.

Digital Library

[8]

F. D. Sahneh, C. Scoglio, and P. Van Mieghem, "Generalized epidemic mean-field model for spreading processes over multilayer complex networks," IEEE/ACM Transactions on Networking, vol. 21, no. 5, pp. 1609--1620, 2013.

Digital Library

[9]

E. M. Rogers, Diffusion of innovations. Simon and Schuster, 2010.

[10]

D. Kempe, J. Kleinberg, and É. Tardos, "Maximizing the spread of influence through a social network," in Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2003, pp. 137--146.

Digital Library

[11]

E. Ackerman, O. Ben-Zwi, and G. Wolfovitz, "Combinatorial model and bounds for target set selection," Theoretical Computer Science, vol. 411, no. 44--46, pp. 4017--4022, 2010.

[12]

Y. Wu, Y. Yang, F. Jiang, S. Jin, and J. Xu, "Coritivity-based influence maximization in social networks," Physica A: Statistical Mechanics and its Applications, vol. 416, pp. 467--480, 2014.

[13]

O. Ben-Zwi, D. Hermelin, D. Lokshtanov, and I. Newman, "Treewidth governs the complexity of target set selection," Discrete Optimization, vol. 8, no. 1, pp. 87--96, 2011.

Digital Library

[14]

O. Hinz, B. Skiera, C. Barrot, and J. U. Becker, "Seeding strategies for viral marketing: An empirical comparison," Journal of Marketing, vol. 75, no. 6, pp. 55--71, 2011.

[15]

A. Goyal, W. Lu, and L. V. Lakshmanan, "Celf++: optimizing the greedy algorithm for influence maximization in social networks," in Proceedings of the 20th international conference companion on World wide web. ACM, 2011, pp. 47--48.

Digital Library

[16]

J.-X. Zhang, Q. D. Duan-Bing Chen, and Z.-D. Zhao, "Identifying a set of influential spreaders in complex networks," Scientific reports, vol. 6, 2016.

[17]

J.-L. He, Y. Fu, and D.-B. Chen, "A novel top-k strategy for influence maximization in complex networks with community structure," PloS one, vol. 10, no. 12, p. e0145283, 2015.

[18]

M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, and H. A. Makse, "Identification of influential spreaders in complex networks," Nature physics, vol. 6, no. 11, pp. 888--893, 2010.

[19]

J. Jankowski, P. Bródka, P. Kazienko, B. K. Szymanski, R. Michalski, and T. Kajdanowicz, "Balancing speed and coverage by sequential seeding in complex networks." Scientific reports, vol. 7, no. 1, p. 891, 2017.

[20]

A. Sela, I. Ben-Gal, A. S. Pentland, and E. Shmueli, "Improving information spread through a scheduled seeding approach," in Advances in Social Networks Analysis and Mining (ASONAM), 2015 IEEE/ACM International Conference on. IEEE, 2015, pp. 629--632.

Digital Library

[21]

J. Jankowski, "Dynamic rankings for seed selection in complex networks: Balancing costs and coverage," Entropy, vol. 19, no. 4, p. 170, 2017.

[22]

J. Jankowski and R. Michalski, "Increasing coverage of information spreading in social networks with supporting seeding," in The Second International Conference on Data Mining and Big Data DMBD2017, IEEE Conference Record 41362. Springer, LNCS, in press.

[23]

G. Bello-Orgaz, J. J. Jung, and D. Camacho, "Social big data: Recent achievements and new challenges," Information Fusion, vol. 28, pp. 45--59, 2016.

Digital Library

[24]

J. L. Iribarren and E. Moro, "Impact of human activity patterns on the dynamics of information diffusion," Physical review letters, vol. 103, no. 3, p. 038702, 2009.

[25]

R. Pfitzner, A. Garas, and F. Schweitzer, "Emotional divergence influences information spreading in twitter." ICWSM, vol. 12, pp. 2--5, 2012.

[26]

R. Michalski, T. Kajdanowicz, P. Bródka, and P. Kazienko, "Seed selection for spread of influence in social networks: Temporal vs. static approach," New Generation Computing, vol. 32, no. 3--4, pp. 213--235, 2014.

[27]

M. Salehi, R. Sharma, M. Marzolla, M. Magnani, P. Siyari, and D. Montesi, "Spreading processes in multilayer networks," IEEE Transactions on Network Science and Engineering, vol. 2, no. 2, pp. 65--83, 2015.

[28]

L. Seeman and Y. Singer, "Adaptive seeding in social networks," in Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on. IEEE, 2013, pp. 459--468.

Digital Library

[29]

C. Granell, S. Gómez, and A. Arenas, "Competing spreading processes on multiplex networks: awareness and epidemics," Physical review E, vol. 90, no. 1, p. 012808, 2014.

[30]

M. E. Newman, "Scientific collaboration networks. i. network construction and fundamental results," Physical review E, vol. 64, no. 1, p. 016131, 2001.

[31]

M. E. Newman, "The structure of scientific collaboration networks," Proceedings of the National Academy of Sciences, vol. 98, no. 2, pp. 404--409, 2001.

[32]

D. J. Watts and S. H. Strogatz, "Collective dynamics of small world networks," nature, vol. 393, no. 6684, pp. 440--442, 1998.

[33]

M. E. Newman, "Finding community structure in networks using the eigenvectors of matrices," Physical review E, vol. 74, no. 3, p. 036104, 2006.

[34]

J. Leskovec, J. Kleinberg, and C. Faloutsos, "Graph evolution: Densification and shrinking diameters," ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 1, no. 1, p. 2, 2007.

Digital Library

[35]

M. Ley, "The dblp computer science bibliography: Evolution, research issues, perspectives," in International symposium on string processing and information retrieval. Springer, 2002, pp. 1--10.

[36]

U. Stelzl, U. Worm, M. Lalowski, C. Haenig, F. H. Brembeck, H. Goehler, M. Stroedicke, M. Zenkner, A. Schoenherr, S. Koeppen et al., "A human protein-protein interaction network: a resource for annotating the proteome," Cell, vol. 122, no. 6, pp. 957--968, 2005.

[37]

J.-F. Rual, K. Venkatesan, T. Hao, T. Hirozane-Kishikawa, A. Dricot, N. Li, G. F. Berriz, F. D. Gibbons, M. Dreze, N. Ayivi-Guedehoussou et al., "Towards a proteome-scale map of the human protein--protein interaction network," Nature, vol. 437, no. 7062, pp. 1173--1178, 2005.

Cited By

Tang JZhao FZhang RChai BDi S(2021)A sequential seed scheduling heuristic based on determinate and latent margin for influence maximization problem with limited budgetInternational Journal of Modern Physics C10.1142/S012918312150079032:06(2150079)Online publication date: 3-Mar-2021
https://doi.org/10.1142/S0129183121500790

Increasing Coverage of Information Diffusion Processes by Reducing the Number of Initial Seeds
1. Human-centered computing
  1. Human computer interaction (HCI)
    1. Interaction paradigms
2. Information systems
  1. Information retrieval

Recommendations

A Dynamic Vote-Rank Based Approach for Effective Sequential Initialization of Information Spreading Processes Within Complex Networks
Computational Science – ICCS 2020
Abstract
Seed selection is one of the key factors influencing information spread within networks. Whereas most solutions are based on single-stage seeding at the beginning of the process, performance increases when additional seeds are used. This enables ...
Brief Announcement: Active Information Spread in Networks
PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

Identifying the most influential spreaders is an important issue for the study of the dynamics of information diffusion in complex networks. In this paper we analyze the following spreading model. Initially, a few nodes know a piece of information and ...
Robust partitional clustering by outlier and density insensitive seeding

The leading partitional clustering technique, k-means, is one of the most computationally efficient clustering methods. However, it produces a local optimal solution that strongly depends on its initial seeds. Bad initial seeds can also cause the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASONAM '17: Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017

July 2017

698 pages

ISBN:9781450349932

DOI:10.1145/3110025

Copyright © 2017 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: 31 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

ASONAM '17

Sponsor:

SIGKDD

ASONAM '17: Advances in Social Networks Analysis and Mining 2017

July 31 - August 3, 2017

Sydney, Australia

Acceptance Rates

Overall Acceptance Rate 116 of 549 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
70
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tang JZhao FZhang RChai BDi S(2021)A sequential seed scheduling heuristic based on determinate and latent margin for influence maximization problem with limited budgetInternational Journal of Modern Physics C10.1142/S012918312150079032:06(2150079)Online publication date: 3-Mar-2021
https://doi.org/10.1142/S0129183121500790

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