nach oben

Erschienen in:

01.12.2020 | Original Article

A numerical evaluation of the accuracy of influence maximization algorithms

verfasst von: Hautahi Kingi, Li-An Daniel Wang, Tom Shafer, Minh Huynh, Mike Trinh, Aaron Heuser, George Rochester, Antonio Paredes

Erschienen in: Social Network Analysis and Mining | Ausgabe 1/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We develop an algorithm to compute exact solutions to the influence maximization problem using concepts from reverse influence sampling (RIS). We implement the algorithm using GPU resources to evaluate the empirical accuracy of theoretically guaranteed greedy and RIS approximate solutions. We find that the approximations yield solutions that are remarkably close to optimal—usually achieving greater than 99% of the optimal influence spread. This accuracy is consistent across a wide range of network structures.

Vorheriger Artikel Analyzing the relationship between relevance and extremist discourse in an alt-right network on Twitter

Nächster Artikel Correspondence analysis-based network clustering and importance of degenerate solutions unification of spectral clustering and modularity maximization

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

“Exact” solutions in this article will technically be \((1-\epsilon )\) approximations, which is consistent with the use of that term in much of the literature (Li et al. 2017, 2019).

We assume \(p_e=p\), \(\forall e\) throughout.

This is Lemma 1 in, for example, Huang et al. (2017).

The value of \(\theta \) determines both the runtime of the algorithm and \(\epsilon \). However, the relationship between \(\theta \) and \(\epsilon \) is a function of the optimal solution, as shown in Theorem 1. The literature has focused on determining increasingly tighter values of \(\theta \) to reduce the runtime through various techniques like limiting the total number of edges examined during the generation process to a pre-defined threshold (Borgs et al. 2014), using Chernoff bounds (Tang et al. 2014) and adopting martingale methods (Tang et al. 2015), among others (Nguyen et al. 2016; Huang et al. 2017). We focus on the two computational steps common to all RIS methods and set \(\theta =100{,}000\). Because this affects both the approximate and exact solutions equally, the proportional difference between the solutions is approximately independent of \(\theta \) so long as it ensures \(\epsilon<< e\), which it trivially does.

Examples of various versions of this lemma in the literature are Lemma 3 in Tang et al. (2014), Lemma 3 in Tang et al. (2015), and Lemma 5 in Nguyen et al. (2016).

The \(\beta =1\) version is not identical to the Erdős–Rényi model because it enforces each node to have at least K/2 connections, whereas there is no restriction on edges for a given node in Erdős–Rényi.

The Python code to generate all results is available at https://github.com/hautahi/IM-Evaluation.

Akbarpour M, Malladi S, Saberi A (2018) Diffusion, seeding, and the value of network information. In: Proceedings of the 2018 ACM conference on economics and computation. ACM, pp 641–641

Albert R, Jeong H, Barabási A-L (2000) Error and attack tolerance of complex networks. Nature 406(6794):378CrossRef

Bader DA, Madduri K (2008) Snap, small-world network analysis and partitioning: an open-source parallel graph framework for the exploration of large-scale networks. In: 2008 IEEE international symposium on parallel and distributed processing. IEEE, pp 1–12

Barabási A-L, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512MathSciNetCrossRef

Barnat J, Bauch P, Brim L, Ceska M (2011) Computing strongly connected components in parallel on cuda. IEEE Int Parallel Distrib Process Sympos 2011:544–555

Basaras P, Katsaros D (2019) Identifying influential spreaders in complex networks with probabilistic links. In: Social networks and surveillance for society. Springer, Cham, pp 57–84CrossRef

Bollobás B, Riordan O (2004) Robustness and vulnerability of scale-free random graphs. Internet Math 1(1):1–35MathSciNetCrossRef

Borgs C, Brautbar M, Chayes J, Lucier B (2014) Maximizing social influence in nearly optimal time. In: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms. SIAM, pp 946–957

Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 199–208

Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 1029–1038

Chen D-B, Xiao R, Zeng A (2014) Predicting the evolution of spreading on complex networks. Sci Rep 4:6108CrossRef

Cohen R, Erez K, Ben-Avraham D, Havlin S (2000) Resilience of the internet to random breakdowns. Phys Rev Lett 85(21):4626CrossRef

Domingos P, Richardson M (2001) Mining the network value of customers. In: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 57–66

Domingos P, Richardson M (2002) Mining knowledge-sharing sites for viral marketing. In: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 61–70

Emami N, Mozafari N, Hamzeh A (2018) Continuous state online influence maximization in social network. Soc Netw Anal Min 8(1):32CrossRef

Erdős P, Rényi A (1960) On the evolution of random graphs. Publ Math Inst Hung Acad Sci 5(1):17–60MathSciNetMATH

Galhotra S, Arora A, Roy S (2016) Holistic influence maximization: combining scalability and efficiency with opinion-aware models. In: Proceedings of the 2016 international conference on management of data. ACM, pp 743–758

Goyal A, Lu W, Lakshmanan LV (2011) Celf++: optimizing the greedy algorithm for influence maximization in social networks. In: Proceedings of the 20th international conference companion on world wide web. ACM, pp 47–48

Harish P, Narayanan P (2007) Accelerating large graph algorithms on the GPU using CUDA. In: International conference on high-performance computing. Springer, pp 197–208

He X, Kempe D (2016) Robust influence maximization. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp 885–894

Huang K, Wang S, Bevilacqua G, Xiao X, Lakshmanan L (2017) Revisiting the stop-and-stare algorithms for influence maximization. Proc VLDB Endow 10:913–924CrossRef

Kempe D, Kleinberg J, Tardos É (2003) 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, pp 137–146

Kim J, Kim SK, Yu H (2013) Scalable and parallelizable processing of influence maximization for large-scale social networks? In: IEEE 29th international conference on data engineering (ICDE). IEEE, pp 266–277

LaSalle D, Karypis G (2013) Multi-threaded graph partitioning. In: IEEE 27th international symposium on parallel and distributed processing. IEEE, pp 225–236

Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 420–429

Li X, Smith JD, Dinh TN, Thai MT (2017) Why approximate when you can get the exact? Optimal targeted viral marketing at scale. In: IEEE INFOCOM 2017-IEEE conference on computer communications. IEEE, pp 1–9

Li X, Smith JD, Dinh TN, Thai MT (2019) Tiptop:(almost) exact solutions for influence maximization in billion-scale networks. IEEE/ACM Trans Netw 27(2):649–661CrossRef

Liu X, Li M, Li S, Peng S, Liao X, Lu X (2013) Imgpu: GPU-accelerated influence maximization in large-scale social networks. IEEE Trans Parallel Distrib Syst 25(1):136–145

Marro J, Dickman R (2005) Nonequilibrium phase transitions in lattice models. Cambridge University Press, Aléa-SaclayMATH

Molloy M, Reed B (1995) A critical point for random graphs with a given degree sequence. Random Struct Algorithms 6(2–3):161–180MathSciNetCrossRef

Moore C, Newman ME (2000) Epidemics and percolation in small-world networks. Phys Rev E 61(5):5678CrossRef

More J, Lingam C (2019) A gradient-based methodology for optimizing time for influence diffusion in social networks. Soc Netw Anal Min 9(1):5CrossRef

Morone F, Makse HA (2015) Influence maximization in complex networks through optimal percolation. Nature 524(7563):65CrossRef

Newman ME (2001) Clustering and preferential attachment in growing networks. Phys Rev E 64(2):025102CrossRef

Nguyen HT, Thai MT, Dinh TN (2016) Stop-and-stare: optimal sampling algorithms for viral marketing in billion-scale networks. In: Proceedings of the 2016 international conference on management of data. ACM, pp 695–710

Pastor-Satorras R, Vespignani A (2001) Epidemic dynamics and endemic states in complex networks. Phys Rev E 63(6):066117CrossRef

Piraveenan M, Harré M, Kasthurirathna D (2016) Optimising influence in social networks using bounded rationality models. Soc Netw Anal Min 6:54CrossRef

Srivastava A, Chelmis C, Prasanna V (2015) The unified model of social influence and its application in influence maximization. Soc Netw Anal Min 5:66CrossRef

Tang Y, Xiao X, Shi Y (2014) Influence maximization: near-optimal time complexity meets practical efficiency. In: Proceedings of the 2014 ACM SIGMOD international conference on management of data. ACM, pp 75–86

Tang Y, Shi Y, Xiao X (2015) Influence maximization in near-linear time: a martingale approach. In: Proceedings of the 2015 ACM SIGMOD international conference on management of data. ACM, pp 1539–1554

Tang J, Tang X, Yuan J (2018) An efficient and effective hop-based approach for influence maximization in social networks. Soc Netw Anal Min 8:10CrossRef

Tsugawa S, Ohsaki H (2018) Robustness of influence maximization against non-adversarial perturbations. In: IEEE/ACM international conference on advances in social networks analysis and mining. Springer, Cham, pp 193–210

Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks. Nature 393(6684):440CrossRef

Titel: A numerical evaluation of the accuracy of influence maximization algorithms
verfasst von: Hautahi Kingi
Li-An Daniel Wang
Tom Shafer
Minh Huynh
Mike Trinh
Aaron Heuser
George Rochester
Antonio Paredes
Publikationsdatum: 01.12.2020
Verlag: Springer Vienna
Erschienen in: Social Network Analysis and Mining / Ausgabe 1/2020
Print ISSN: 1869-5450
Elektronische ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-020-00680-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2020

Efficient influence spread estimation for influence maximization

Feature selection methods for event detection in Twitter: a text mining approach

Influence of Twitter activity on the stock price of soccer clubs

YouTube of porn: longitudinal measurement, analysis, and characterization of a large porn streaming service

Design and development of a friendly user interface for building social network traceability system

A framework for improving electoral forecasting based on time-aware polling