nach oben

Social Network Analysis and Mining

Erschienen in:

01.12.2020 | Original Article

A general method of active friending in different diffusion models in social networks

verfasst von: Shuyang Gu, Chuangen Gao, Ruiqi Yang, Weili Wu, Hua Wang, Dachuan Xu

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

Active friending is a problem in social networks that is to assist a user to build a relationship to a target user by sending invitations to a set of intermediate users; the goal is to maximize the acceptance probability at the target node taking advantage of the social influence through the network formed by the intermediate nodes. In this paper, we convert the original formulated active friending problem of nonsubmodular maximization subject to cardinality constraint into a submodular cost submodular knapsack problem in the IC model, and we show that the two problems are equivalent. We similarly make the conversion on the active friending in the LT model. Then we give a general combinatorial optimization algorithm to solve active friending problems in both the IC model and the LT model with a guaranteed approximation. We analyze the computational complexity of the problem and the algorithm performance. The effectiveness of the generalized method is verified on real data sets.

Vorheriger Artikel A new approach for affinity relationship discovery in online forums

Nächster Artikel A comparative analysis of similarity measures akin to the Jaccard index in collaborative recommendations: empirical and theoretical perspective

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

Bharathi S, Kempe D, Salek M (2007) Competitive influence maximization in social networks. In: International workshop on web and internet economics. Springer, pp 306–311

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 H, Xu W, Zhai X, Bi Y, Wang A, Du D-Z (2014) How could a boy influence a girl?. In: 2014 10th International conference on mobile ad-hoc and sensor networks. IEEE, pp 279–287

Chen W, Yuan Y, Zhang L (2010) Scalable influence maximization in social networks under the linear threshold model. In: 2010 IEEE international conference on data mining. IEEE, pp 8–97

Conforti M, Cornuéjols G (1984) Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the rado-edmonds theorem. Discrete Appl Math 7(3):251–274MathSciNetCrossRef

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

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

Goyal A, Lu W, Lakshmanan LV (2011) Simpath: an efficient algorithm for influence maximization under the linear threshold model. In 2011 IEEE 11th international conference on data mining. IEEE, pp 211–220

Iyer RK, Bilmes JA (2013) Submodular optimization with submodular cover and submodular knapsack constraints. In: Advances in neural information processing systems, pp 2436–2444

Iyer RK, Jegelka S, Bilmes JA (2013) Curvature and optimal algorithms for learning and minimizing submodular functions. In: Advances in neural information processing systems, pp 2742–2750

Jegelka S, Bilmes J (2011) Submodularity beyond submodular energies: coupling edges in graph cuts. In: CVPR 2011. IEEE, pp 1897–1904

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

Kwon J, Kim S (2010) Friend recommendation method using physical and social context. Int J Comput Sci Netw Secur 10(11):116–120

Lu Z, Zhang Z, Wu W (2017) Solution of bharathi-kempe-salek conjecture for influence maximization on arborescence. J Comb Optim 33(2):803–808MathSciNetCrossRef

Richardson M, Domingos P (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

Silva NB, Tsang R, Cavalcanti GD, Tsang J (2010) A graph-based friend recommendation system using genetic algorithm. In: IEEE congress on evolutionary computation. IEEE, pp 1–7

Sviridenko M (2004) A note on maximizing a submodular set function subject to a knapsack constraint. Oper Res Lett 32(1):41–43MathSciNetCrossRef

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

Vondrák J (2010) Submodularity and curvature: the optimal algorithm (combinatorial optimization and discrete algorithms)

Wang Z, Liao J, Cao Q, Qi H, Wang Z (2015) Friendbook: a semantic-based friend recommendation system for social networks. IEEE Trans Mob Comput 14(3):538–551CrossRef

Wang A, Wu W, Cui L (2016) On bharathi-kempe-salek conjecture for influence maximization on arborescence. J Comb Optim 31(4):1678–1684MathSciNetCrossRef

Wu W, Du D-Z, et al. (2018) An approximation algorithm for active friending in online social networks. arXiv preprint arXiv:1811.00643

Xie X (2010) Potential friend recommendation in online social network. In: Proceedings of the 2010 IEEE/ACM int’l conference on green computing and communications & int’l conference on cyber, physical and social computing. IEEE Computer Society, pp 831–835

Yang D-N, Hung H-J, Lee W-C, Chen W (2013) Maximizing acceptance probability for active friending in online social networks. In: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 713–721

Yuan J, Wu W, Li Y, Du D (2017) Active friending in online social networks. In: Proceedings of the Fourth IEEE/ACM international conference on big data computing, applications and technologies. ACM, pp 139–148

Titel: A general method of active friending in different diffusion models in social networks
verfasst von: Shuyang Gu
Chuangen Gao
Ruiqi Yang
Weili Wu
Hua Wang
Dachuan Xu
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-00653-8

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

Dynamic wavelet fingerprint for differentiation of tweet storm types

Neutrality may matter: sentiment analysis in reviews of Airbnb, Booking, and Couchsurfing in Brazil and USA

Discount advertisement in social platform: algorithm and robust analysis

FauxWard: a graph neural network approach to fauxtography detection using social media comments

Elite versus mass polarization on the Brazilian impeachment proceedings of 2016

Topics extraction in incremental short texts based on LSTM