Journal Home > Volume 27 , Issue 5

In social network applications, individual opinion is often influenced by groups, and most decisions usually reflect the majority’s opinions. This imposes the group influence maximization (GIM) problem that selects k initial nodes, where each node belongs to multiple groups for a given social network and each group has a weight, to maximize the weight of the eventually activated groups. The GIM problem is apparently NP-hard, given the NP-hardness of the influence maximization (IM) problem that does not consider groups. Focusing on activating groups rather than individuals, this paper proposes the complementary maximum coverage (CMC) algorithm, which greedily and iteratively removes the node with the approximate least group influence until at most k nodes remain. Although the evaluation of the current group influence against each node is only approximate, it nevertheless ensures the success of activating an approximate maximum number of groups. Moreover, we also propose the improved reverse influence sampling (IRIS) algorithm through fine-tuning of the renowned reverse influence sampling algorithm for GIM. Finally, we carry out experiments to evaluate CMC and IRIS, demonstrating that they both outperform the baseline algorithms respective of their average number of activated groups under the independent cascade (IC) model.


menu
Abstract
Full text
Outline
About this article

Efficient Algorithms for Maximizing Group Influence in Social Networks

Show Author's information Peihuang Huang( )Longkun Guo( )Yuting Zhong
College of Mathematics and Data Science, Minjiang University, Fuzhou 350108, China
College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China

Abstract

In social network applications, individual opinion is often influenced by groups, and most decisions usually reflect the majority’s opinions. This imposes the group influence maximization (GIM) problem that selects k initial nodes, where each node belongs to multiple groups for a given social network and each group has a weight, to maximize the weight of the eventually activated groups. The GIM problem is apparently NP-hard, given the NP-hardness of the influence maximization (IM) problem that does not consider groups. Focusing on activating groups rather than individuals, this paper proposes the complementary maximum coverage (CMC) algorithm, which greedily and iteratively removes the node with the approximate least group influence until at most k nodes remain. Although the evaluation of the current group influence against each node is only approximate, it nevertheless ensures the success of activating an approximate maximum number of groups. Moreover, we also propose the improved reverse influence sampling (IRIS) algorithm through fine-tuning of the renowned reverse influence sampling algorithm for GIM. Finally, we carry out experiments to evaluate CMC and IRIS, demonstrating that they both outperform the baseline algorithms respective of their average number of activated groups under the independent cascade (IC) model.

Keywords: complementary maximum coverage (CMC), improved reverse influence sampling (IRIS), group influence maximization (GIM), independent cascade (IC) model

References(31)

[1]
A. Belhassena and H. Z. Wang, Trajectory big data processing based on frequent activity, Tsinghua Science and Technology, vol. 24, no. 3, pp. 317–332, 2019.
[2]
J. Li, M. Siddula, X. Z. Cheng, W. Cheng, Z. Tian, and Y. S. Li, Approximate data aggregation in sensor equipped IoT networks, Tsinghua Science and Technology, vol. 25, no. 1, pp. 44–55, 2019.
[3]
M. Meeker and L. Wu, Internet trends 2018, Tehnical report, Kleiner Perkins, 2018.
[4]
Zhu J. M., Ghosh S., and Wu W. L., Group influence maximization problem in social networks, IEEE Transactions on Computational Social Systems, vol. 6, no. 6, pp. 11561164, 2019.10.1109/TCSS.2019.2938575
[5]
J. M. Zhu, J. L. Zhu, S. Ghosh, W. L. Wu, and J. Yuan, Social influence maximization in hypergraph in social networks, IEEE Transactions on Network Science and Engineering, vol. 6, no. 4, pp. 801–811, 2019.
[6]
P. Domingos and M. Richardson, Mining the network value of customers, in Proc. 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, 2001, pp. 57–66.
DOI
[7]
D. Kempe, J. Kleinberg, and E. Tardos, Maximizing the spread of influence through a social network, in Proc. 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, 2003, pp. 137–146.
DOI
[8]
J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, Cost-effective outbreak detection in networks, in Proc. 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, CA, USA, 2007, pp. 420–429.
DOI
[9]
A. Goyal, W. Lu, and L. V. S. Lakshmanan, Celf++: Optimizing the greedy algorithm for influence maximization in social networks, in Proc. 20th International Conference Companion on World Wide Web, Hyderabad, India, 2011, pp. 47–48.
[10]
W. Chen, Y. J. Wang, and S. Y. Yang, Efficient influence maximization in social networks, in Proc. 15th ACM SIGKDD International Conference On Knowledge Discovery and Data Mining, Paris, France, 2009, pp. 199–208.
DOI
[11]
S. Wasserman and K. Faust, Social network analysis in the social and behavioral sciences, in Social Network Analysis: Methods and Applications, S. Wasserman, ed. Cambridge, UK: Cambridge University Press, 1994, pp. 1–27.
DOI
[12]
P. A. Estevez, P. Vera, and K. Saito, Selecting the most influential nodes in social networks, presented at 2007 International Joint Conference on Neural Networks, Orlando, FL, USA, 2007.
DOI
[13]
T. H. Hubert Chan, L. Ning, and Y. Zhang, Influence maximization under the non-progressive linear threshold model, presented at 14th International Workshop on Frontiers in Algorithmics, Haikou, China, 2020.
DOI
[14]
C. Borgs, M. Brautbar, J. Chayes, and B. Lucier, Maximizing social influence in nearly optimal time, in Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms, Portland, OR, USA, 2014, pp. 946–957.
DOI
[15]
Y. Z. Tang, X. K. Xiao, and Y. C. Shi, Influence maximization: Near-optimal time complexity meets practical efficiency, in Proc. 2014 ACM Sigmod International Conference On Management of Data, Sniwbird, UT, USA, 2014, pp. 75–86.
DOI
[16]
Tang Y. Z., Shi Y. C., and Xiao X. K., Influence maximization in near-linear time: A martingale approach, in Proc. 2015 ACM SIGMOD International Conference on Management of Data, Melboume, Australia, 2015, pp. 15391554.10.1145/2723372.2723734
DOI
[17]
Nguyen H. T., Thai M. T., and Dinh T. N., Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks, in Proc. 2016 International Conference on Management of Data, San Francisco, CA, USA, 2016, pp. 695710.10.1145/2882903.2915207
DOI
[18]
J. Wu and N. Wang, Approximating special social influence maximization problems, Tsinghua Science and Technology, vol. 25, no. 6, pp. 703–711, 2020.
[19]
Y. Zhang, Q. Ge, R. Fleischer, T. Jiang, and H. Zhu, Approximating the minimum weight weak vertex cover, Theoretical Computer Science, vol. 363, no. 1, pp. 99–105, 2006.
[20]
Y. Zhang and H. Zhu, Approximation algorithm for weighted weak vertex cover, Journal of Computer Science and Technology, vol. 19, no. 6, pp. 782–786, 2004.
[21]
T. Y. Cao, X. D. Wu, S. Wang, and X. H. Hu, OASNET: An optimal allocation approach to influence maximization in modular social networks, in Proc. 2010 ACM Symposium on Applied Computing, Sierre, Switzerland, 2010, pp. 1088–1094.
DOI
[22]
Y. Wang, G. Cong, G. J. Song, and K. Q. Xie, Community-based greedy algorithm for mining top-k influential nodes in mobile social networks, in Proc. 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, 2010, pp. 1039–1048.
DOI
[23]
J. C. Ji, L. Huang, Z. Wang, H. M. Li, and S. Y. Li, A new approach to maximizing the spread of influence based on community structure, (in Chinese), Journal of Jilin University (Science Edition), vol. 49, no. 1, pp. 93–97, 2011.
[24]
S. Wang, B. Li, X. J. Liu, and P. Hu, Division of community-based influence maximization algorithm, (in Chinese), Computer Engineering and Applications, vol. 52, no. 19, pp. 42–47, 2016.
[25]
J. X. Shang, S. B. Zhou, X. Li, L. C. Liu, and H. C. Wu, CoFIM: A community-based framework for influence maximization on large-scale networks, Knowledge-Based Systems, vol. 117, pp. 88–100, 2017.
[26]
J. R. Xie, B. K. Szymanski, and X. M. Liu, SLPA: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process, presented at 2011 IEEE 11th International Conference on Data Mining Workshops, Vancouver, Canada, 2011, pp. 344–349.
DOI
[27]
L. Q. Qiu, W. Jia, and X. Fan, Influence maximization algorithm based on overlapping community, Data Analysis and Knowledge Discovery, vol. 3, no. 7, pp. 94–102, 2019.
[28]
Y. C. Chen, W. Y. Zhu, W. C. Peng, W. C. Lee, and S. Y. Lee, CIM: Community-based influence maximization in social networks, ACM Transactions on Intelligent Systems and Technology, vol. 5, no. 2, pp. 1–31, 2014.
[29]
H. M. Huang, H. Shen, Z. Q. Meng, H. J. Chang, and H. W. He, Community-based influence maximization for viral marketing, Applied Intelligence, vol. 49, no. 6, pp. 2137–2150, 2019.
[30]
A. Bozorgi, S. Samet, J. Kwisthout, and T. Wareham, Community-based influence maximization in social networks under a competitive linear threshold model, Knowledge-Based Systems, vol. 134, pp. 149–158, 2017.
[31]
B. Rozemberczki and R. Sarkar, Characteristic functions on graphs: Birds of a feather, from statistical descriptors to parametric models, in Proc. 29th ACM International Conference on Information & Knowledge Management, Virtual Event Ireland, 2020, pp. 1325–1334.
DOI
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 21 June 2021
Revised: 30 July 2021
Accepted: 18 August 2021
Published: 17 March 2022
Issue date: October 2022

Copyright

© The author(s) 2022.

Acknowledgements

This work was supported by the Natural Science Foundation of Fujian Province (No. 2020J01845), the Educational Research Project for Young and Middle-Aged Teachers of Fujian Provincial Department of Education (No. JAT190613), the National Natural Science Foundation of China (Nos. 61772005 and 92067108), and the Outstanding Youth Innovation Team Project for Universities of Shandong Province (No. 2020KJN008).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return