Customized influence maximization in attributed social networks: heuristic and meta-heuristic algorithms

Abstract

Abstract The influence maximization problem is one of the most fundamental topics in social networks. However, most existing studies have focused on non-attributed networks, neglecting the consideration of users’ properties during information propagation. Additionally, specific scenarios may involve external queries that target a particular subset of users, which has not been adequately addressed in prior research. To address these limitations, this study first formulates the customized influence maximization (CIM) problem in the context of attributed social networks. The node score and influence probability are derived by fully considering the user’s attributes and the external queries. Then, we develop two algorithms to identify a group of most influential nodes in CIM. The first is a heuristic algorithm based on discounted degree, which is able to find relatively high-quality solutions in a short time. The second is a meta-heuristic algorithm, which makes several adjustments to the original ant colony algorithm to make it efficient to the CIM problem. Specifically, multiple CIM-related heuristics are derived, and a heuristic adaptation strategy is designed to automatically assign the heuristic information to ants according to the search environments and stages. Extensive experiments show the promising performance of our proposed algorithms in terms of accuracy, efficiency, and robustness.

Keywords

• Influence maximization
• Social networks
• User attributes
• Ant colony system