Top

Published in:

2021 | OriginalPaper | Chapter

Maximizing Group Coverage in Social Networks

Authors : Yuting Zhong, Longkun Guo, Peihuang Huang

Published in: Parallel and Distributed Computing, Applications and Technologies

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Groups play a crucial role in decision-making of social networks, since individual decision-making is often influenced by groups. This brings the Group Influence Maximization (GIM) problem which aims to maximize the expected number of activated groups by finding k seed nodes. The GIM problem has been proved NP-hard while computing the objective function is \(\#P\)-hard under Independent Cascade (IC) model. We propose an algorithm called Maximizing Group Coverage (MGC) which greedily selects the best node based on evaluating the contribution of nodes to the groups, ensuring the success of approximating the maximization of the number of activated groups. Finally, we compare the MGC algorithm with the baseline algorithm called Maximum Coverage (MC) through experiments, demonstrating that MGC outperforms MC under IC model regarding the average number of activated groups.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Approximation Algorithms for the General Cluster Routing Problem

next chapter LightLayers: Parameter Efficient Dense and Convolutional Layers for Image Classification

Pedro, D., Matt, R.: Mining the network value of customers. In: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 57–66 (2001)

Pablo, A.E., Pablo, V., Kazumi, S.: Selecting the most influential nodes in social networks. In: 2007 International Joint Conference on Neural Networks, pp. 2397–2402. IEEE (2007)

Wei, C., Yajun, W., Siyu, Y.: Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 199–208 (2009)

Wei, C., Yifei, Y., Li, Z.: Scalable influence maximization in social networks under the linear threshold model. In 2010 IEEE International Conference on Data Mining, pp. 88–97. IEEE (2010)

Amit, G., Wei, L., Laks, V.S.L.: Simpath: an efficient algorithm for influence maximization under the linear threshold model. In: 2011 IEEE 11th International Conference on Data Mining, pp. 211–220. IEEE (2011)

Guo-Liang, L., Ya-Ping, C., Jian-Hua, F., Yao-Qiang, X.: Influence maximization on multiple social networks. Chinese J. Comput. 39(4), 643–656 (2016)

David, K., Jon, K., Éva, T.: Maximizing the spread of influence through a social network. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146 (2003)

Jure, L., Andreas, K., Carlos, G., Christos, F., Jeanne, V., Natalie, G.: Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 420–429 (2007)

Amit, G., Wei, L., Laks, V.S.L.: Celf++ optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th International Conference Companion on World Wide Web, pp. 47–48 (2011)

10.

Christian, B., Michael, B., Jennifer, C., Brendan, L.: Maximizing social influence in nearly optimal time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 946–957. SIAM (2014)

11.

Youze, T., Xiaokui, X., Yanchen, S.: Influence maximization: near-optimal time complexity meets practical efficiency. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, pp. 75–86 (2014)

12.

Youze, T., Yanchen, S., Xiaokui, X.: Influence maximization in near-linear time: a martingale approach. In: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pp. 1539–1554 (2015)

13.

Hung, T.N., My, T.T., Thang, N.D.: Stop-and-stare: optimal sampling algorithms for viral marketing in billion-scale networks. In: Proceedings of the 2016 International Conference on Management of Data, pp. 695–710 (2016)

14.

Tianyu, C., Xindong, W., Song, W., Xiaohua, H.: Oasnet: an optimal allocation approach to influence maximization in modular social networks. In: Proceedings of the 2010 ACM Symposium on Applied Computing, pp. 1088–1094 (2010)

15.

Yu, W., Gao, C., Guojie, S., Kunqing, X.: Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1039–1048 (2010)

16.

Jin-chao, J., Lan, H., Zhe, W., Hong-ming, L., San-yi, L.: A new approach to maximizing the spread of influence based on community structure. J. Jilin University (Science Edition), 1, 23 (2011)

17.

Huang, H., Shen, H., Meng, Z., Chang, H., He, H.: Community-based influence maximization for viral marketing. Appl. Intell. 49(6), 2137–2150 (2019). https://doi.org/10.1007/s10489-018-1387-8CrossRef

18.

Bozorgi, A., Samet, S., Kwisthout, J., Wareham, T.: Community-based influence maximization in social networks under a competitive linear threshold model. Knowledge-Based Syst. 134, 149–158 (2017)CrossRef

19.

Zhu, J., Ghosh, S., Weili, W.: Group influence maximization problem in social networks. IEEE Trans. Comput. Soc. Syst. 6(6), 1156–1164 (2019)CrossRef

20.

Schoenebeck, G., Tao, B.: Beyond worst-case (in) approximability of nonsubmodular influence maximization. ACM Trans. Comput. Theory (TOCT) 11(3), 1–56 (2019)MathSciNetCrossRef

21.

Francis, B., et al.: Learning with submodular functions: a convex optimization perspective. Found. Trends® Machine Learn. 6(2–3), 145–373 (2013)

22.

Wei, L., Wei, C., Laks, V.S.L.: From competition to complementarity: comparative influence diffusion and maximization. Proc. VLDB Endowment, 9(2), 60–71 (2015)

23.

Benedek, R., Rik, S.: Characteristic functions on graphs: birds of a feather, from statistical descriptors to parametric models. In: The 29th ACM Conference on Information and Knowledge Management, abs/2005.07959 (2020)

Title: Maximizing Group Coverage in Social Networks
Authors: Yuting Zhong
Longkun Guo
Peihuang Huang
Publisher: Springer International Publishing
Book: Parallel and Distributed Computing, Applications and Technologies
Print ISBN: 978-3-030-69243-8

Electronic ISBN: 978-3-030-69244-5

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-69244-5_24

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner