Scalable Influence Maximization Using Ant Colony Optimization with Attribute-Based Scouting
Article Sidebar
Main Article Content
Abstract
Influence Maximization (IM) is a vital problem in social network analysis that focuses on identifying a small subset of influential nodes to maximize the spread of information across a network. Traditional influence maximization algorithms, including greedy and heuristic-based methods, often struggle with scalability and efficiency, especially when applied to large-scale networks. To overcome these limitations, we propose a novel Hybrid Ant Colony Optimization (HybridACO) algorithm that integrates a neighbor scouting strategy based on attribute similarity. This approach utilizes the inherent network structure by combining the global search capability of Ant Colony Optimization (ACO) with a local scouting mechanism that selects nodes based on their neighbors' influence potential and attribute similarity. By integrating attribute-driven scouting, HybridACO ensures that the selected nodes are not only topologically influential but also contextually relevant for the diffusion process. Comprehensive evaluations on both synthetic and real-world benchmark networks show that the proposed algorithm significantly surpasses existing state-of-the-art (SOTA) methods in influence spread, computational efficiency, and robustness.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
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 (TIST), vol. 5, no. 2, pp. 1–31, 2014.
A. Goyal, W. Lu and L. V. Lakshmanan, “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.
J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen and N. Glance, “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.
W. Chen, Y. Wang and S. Yang, “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.
P. Domingos and M. Richardson, “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.
. Kempe, J. Kleinberg and E. Tardos, “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.
M. Kimura and K. Saito, “Tractable models for information diffusion in social networks,” in European Conference on Principles of Data Mining and Knowledge Discovery, pp. 259–271, 2006.
W. Chen, C. Wang and Y. Wang, “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, pp. 1029–1038, 2010.
S. S. Singh, A. Kumar, K. Singh and B. Biswas, “LAPSO-IM: A learning-based influence maximization approach for social networks,” Applied Soft Computing, vol. 82, p. 105554, 2019.
S. S. Singh, K. Singh, A. Kumar and B. Biswas, “ACO-IM: Maximizing influence in social networks using ant colony optimization,” Soft Computing, vol. 24, no. 13, pp. 10181–10203, 2020.
M. Gong, J. Yan, B. Shen, L. Ma, and Q. Cai, “Influence maximization in social networks based on discrete particle swarm optimization,” Information Sciences, vol. 367, pp. 600–614, 2016.
C. Salavati and A. Abdollahpouri, “Identifying influential nodes based on ant colony optimization to maximize profit in social networks,” Swarm and Evolutionary Computation, vol. 51, p. 100614, 2019.
Z. Aghaee, M. M. Ghasemi, H. A. Beni, A. Bouyer and A. Fatemi, “A survey on metaheuristic algorithms for the influence maximization problem in social networks,” Computing, vol. 103, pp. 2437–2477, 2021.
M. Sumathi, N. Vijayaraj, S. P. Raja and M. Raj-kamal, “HHO-ACO hybridized load balancing technique in cloud computing,” International Journal of Information Technology, vol. 15, no. 3, pp. 1357–1365, 2023.
J. K. C. Revanna and N. Y. B. Al-Nakash, “Metaheuristic link prediction (MLP) using an AI-based ACO-GA optimization model for solving vehicle routing problem,” International Journal of Information Technology, vol. 15, no. 7, pp. 3425–3439, 2023.
Y. Y. Raghav and V. Vyas, “ACBSO: A hybrid solution for load balancing using ant colony and bird swarm optimization algorithms,” International Journal of Information Technology, vol. 15, no. 5, pp. 2847–2857, 2023.
Q. Jiang, Z. Peng, X. Xie, K. Du, G. Hu and Y. Liu, “Preparation of high active Pt/C cathode electrocatalyst for direct methanol fuel cell by citrate-stabilized method,” Trans. Nonferrous Metals Soc. China, vol. 20, no. 1, pp. 127–132, 2010.
J. C. Liang, Y. J. Gong, X. K. Wu and Y. Scalable Influence Maximization Using Ant Colony Optimization with Attribute-Based Scouting 681 Li, “Customized influence maximization in attributed social networks: Heuristic and metaheuristic algorithms,” Complex and Intelligent Systems, vol. 10, no. 1, pp. 1409–1424, 2024.
I. Khatri, A. Choudhry, A. Rao, A. Tyagi, D. K. Vishwakarma and M. Prasad, “Influence maximization in social networks using discretized Harris Hawks Optimization algorithm,” Applied Soft Computing, vol. 149, p. 111037, 2023.
M. Roy and I. Pan, “Most Influential Node Selection in Social Network using Genetic Algorithm,” 2018 Fourth International Conference on Research in Computational Intelligence and Communication Networks (ICRCICN), Kolkata, India, pp. 214-220, 2018.
H. Huang, H. Shen, and Z. Meng, "Community-based influence maximization in attributed networks,” Appl. Intell., vol. 50, no. 2, pp. 354–364, 2020
D. Bucur and G. Iacca, “Influence maximization in social networks with genetic algorithms,” in Applications of Evolutionary Computation: 19th European Conference Proceedings, Part I, Springer Interna-tional Publishing, pp. 379–392, 2016.
J. Tang, R. Zhang, Y. Yao, F. Yang, Z. Zhao, R. Hu and Y. Yuan, “Identification of top-k influential nodes based on enhanced discrete particle swarm optimization for influence maximization,” Physica A: Statistical Mechanics and its Applications, vol. 513, pp. 477–496, 2019.
M. Roy and I. Pan, “Lazy forward differential evolution for influence maximization in large data networks,” SN Computer Science, vol. 1, no. 2, p. 107, 2020.
H. Zhou, Y. Li and Z. Wu, “A hybrid ACO-SA approach for influence maximization in social networks,” Journal of Computational Science, vol. 54, p. 101368, 2021.
M. Dorigo, M. Birattari and T. Stutzle, “Ant colony optimization,” in IEEE Computational Intelligence Magazine, vol. 1, no. 4, pp. 28-39, Nov. 2006
M. Friedman, “The use of ranks to avoid the assumption of normality implicit in the analysis of variance,” Journal of the American Statistical Association, vol. 32, no. 200, pp. 675–701, 1937.
P. Nemenyi, “Distribution-free multiple comparisons,” Ph.D. dissertation, Princeton Univ., Princeton, NJ, 1963.
