×

zbMATH — the first resource for mathematics

Evolutionary optimization of three-degree influence spread in social networks based on discrete bacterial foraging optimization algorithm. (English) Zbl 07239972
Pan, Linqiang (ed.) et al., Bio-inspired computing: theories and applications. 14th international conference, BIC-TA 2019, Zhengzhou, China, November 22–25, 2019. Revised selected papers. Part I. Singapore: Springer (ISBN 978-981-15-3424-9/pbk; 978-981-15-3425-6/ebook). Communications in Computer and Information Science 1159, 77-87 (2020).
Summary: The influence maximization (IM) problem is an important issue in social network, which is to seek k nodes with maximal influence cascade such that the influence spread invoked by the k nodes in the network is maximized. The traditional approaches for resolving influence maximization, including Greedy, Distance, DegreeDiscount and PageRank, usually suffer from several drawbacks, such as high computational cost and unstable accuracy. In this paper, we propose a new optimization model, i.e., complete-three-layer-influence evaluation (CTLI), based on an improved three-degree model by considering the intra-layer and inter-layer’s communication effect. A discrete bacterial foraging optimization algorithm is proposed to optimize CTLI model. In this algorithm, the update and mutation rules for the bacteria are redefined to improve the search ability. Finally, the proposed model and algorithm are tested on four real-world social network instances. Results demonstrate that the proposed method outperforms its compared algorithms in terms of solution accuracy and computation efficiency.
For the entire collection see [Zbl 1440.68009].
MSC:
68Q07 Biologically inspired models of computation (DNA computing, membrane computing, etc.)
Software:
CELF++
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Misner, I.R., Devine, V.: The World’s Best Known Marketing Secret: Building Your Business With Word-of-Mouth Marketing. Bard Press, Austin (1994)
[2] Nail, J.: The consumer advertising backlash. Forrester Research and intelliseek Market Research Report (2004)
[3] Gong, M., Yan, J., Shen, B.: Influence maximization in social networks based on discrete particle swarm optimization. Inf. Sci. 367, 600-614 (2016). https://doi.org/10.1016/j.ins.2016.07.012
[4] Kempe, D., Kleinberg, J.: Maximizing the spread of influence through a social network. In: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137-146. ACM (2003). https://doi.org/10.1145/956750.956769
[5] Domingos, P., Richardson, M.: Mining the network value of customers. In: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 57-66. ACM (2001)
[6] Leskovec, J., Krause, A., Guestrin, C.: Cost-effective outbreak detection in networks. In: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 420-429. ACM (2007). https://doi.org/10.1145/1281192.1281239
[7] Goyal, A., Lu, W., Lakshmanan, L.: CELF++: optimizing the greedy algorithm for influence maximization in social networks. In: International Conference Companion on World Wide Web, pp. 47-48. ACM (2011). https://doi.org/10.1145/1963192.1963217
[8] Brin, S., Page, L.: The anatomy of a large-scale hypertextual web search engine. Comput. Netw. ISDN Syst. 30, 107-117 (1998)
[9] Ma, L., et al.: Cooperative two-engine multi-objective bee foraging algorithm with reinforcement learning. Knowl.-Based Syst. 133, 278-293 (2017). https://doi.org/10.1016/j.knosys.2017.07.024
[10] Passino, K.M.: Biomimicry of bacterial foraging for distributed optimization and control. IEEE Control Syst. Mag. 22(3), 52-67 (2002)
[11] Ma, L., Wang, R., Chen, M., Wang, X., Cheng, S., Shi, Y.: A novel many-objective evolutionary algorithm based on transfer learning with kriging model. Inf. Sci. 509, 437-456 (2019). https://doi.org/10.1016/j.ins.2019.01.030
[12] Marinakis, Y., Marinaki, M., Matsatsinis, N.: A hybrid discrete Artificial Bee Colony - GRASP algorithm for clustering. In: International Conference on Computers & Industrial Engineering, pp. 548-553. IEEE (2009). https://doi.org/10.1109/ICCIE.2009.5223810
[13] Ma, L., Zhu, Y., Liu, Y., Tian, L.: A novel bionic algorithm inspired by plant root foraging behaviors. Appl. Soft Comput. 37, 95-133 (2015). https://doi.org/10.1016/j.asoc.2015.08.014
[14] Ma, L., Wang, X., Huang, M., Lin, Z., Tian, L., Chen, H.: Two-level master-slave RFID networks planning via hybrid multi-objective Artificial Bee Colony optimizer. IEEE Trans. Syst. Man Cybern. Syst. 49(5), 861-880 (2019). https://doi.org/10.1109/TSMC.2017.2723483
[15] Ma, L., Hu, K., Zhu, Y., Chen, H.: Cooperative Artificial Bee Colony algorithm for multi-objective RFID network planning. J. Netw. Comput. Appl. 42, 143-162 (2014). https://doi.org/10.1016/j.jnca.2014.02.012
[16] Qin, Y., Ma, J., Gao, S.: Efficient influence maximization under TSCM: a suitable diffusion model in online social networks. Soft. Comput. 21(4), 827-838 (2016). https://doi.org/10.1007/s00500-016-2068-3 · Zbl 1381.68014
[17] Chen, W., Wang, Y., Yang, S.: Efficient influence maximization in social networks. In: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 199-208. DBLP, Paris (2009). https://doi.org/10.1145/1557019.1557047
[18] Crespi, B.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.