Social networks are in continuous evolution, and its spreading has attracted the interest of both practitioners and the scientific community. In the last decades, several new interesting problems have aroused in the context of social networks, mainly due to an overabundance of information, usually named as infodemic. This problem emerges in several areas, such as viral marketing, disease prediction and prevention, and misinformation, among others. Then, it is interesting to identify the most influential users in a network to analyze the information transmitted, resulting in Social Influence Maximization (SIM) problems. In this research, the Budget Influence Maximization Problem (BIMP) is tackled. BIMP proposes a realistic scenario where the cost of selecting each node is different. This is modeled by having a budget that can be spent to select the users of a network, where each user has an associated cost. Since BIMP is a hard optimization problem, a metaheuristic algorithm based on Greedy Randomized Adaptive Search (GRASP) framework is proposed.
- Paper link: https://doi.org/10.1007/s12652-023-04680-z
- Impact Factor: 3.662
- Quartil: Q2 - 57/190 - Computer Science, Artificial Intelligence | Q2 - 75/246 - Computer Science, Information Systems | 2021
- Journal: Journal of Ambient Intelligence and Humanized Computing
All txt format instances can be found also in instances folder.
The code´s folder contains the proyect with our algorithmic proposal. We use IntellIj IDE, the proyect can be build with maven, we also add the required java libraries.
The following excel document contains all the final results divided by instance. It also contains the final tables and the network information table.
- Tables.xlsx
You can just run the BIMP.jar as follows.
All the parameters can be customized in the following file: ./source/src/main/resources/application.yml
java -jar BIMP.jar --instances.path.default="./instances"
Also you can modify the parameters in the launch command, for instance:
java -jar BIMP.jar ---instances.path.default="./instances" --algorithm.proyectName="GRASP_1" --algorithm.FO=2
If you want new instances just replace folder instances. Solution folder contains an excel with the results.
Please cite our paper if you use it in your own work:
Bibtext
@Article{Lozano2023_BIMP,
author={Lozano-Osorio, Isaac and S{\'a}nchez-Oro, Jes{\'u}s and Duarte, Abraham},
title={An efficient and effective GRASP algorithm for the Budget Influence Maximization Problem},
journal={Journal of Ambient Intelligence and Humanized Computing},
year={2023},
month={Sep},
day={21},
abstract={Social networks are in continuous evolution, and its spreading has attracted the interest of both practitioners and the scientific community. In the last decades, several new interesting problems have aroused in the context of social networks, mainly due to an overabundance of information, usually named as infodemic. This problem emerges in several areas, such as viral marketing, disease prediction and prevention, and misinformation, among others. Then, it is interesting to identify the most influential users in a network to analyze the information transmitted, resulting in Social Influence Maximization (SIM) problems. In this research, the Budget Influence Maximization Problem (BIMP) is tackled. BIMP proposes a realistic scenario where the cost of selecting each node is different. This is modeled by having a budget that can be spent to select the users of a network, where each user has an associated cost. Since BIMP is a hard optimization problem, a metaheuristic algorithm based on Greedy Randomized Adaptive Search (GRASP) framework is proposed.},
issn={1868-5145},
doi={10.1007/s12652-023-04680-z}
}
RIS
TY - JOUR
AU - Lozano-Osorio, Isaac
AU - Sánchez-Oro, Jesús
AU - Duarte, Abraham
PY - 2023
DA - 2023/09/21
TI - An efficient and effective GRASP algorithm for the Budget Influence Maximization Problem
JO - Journal of Ambient Intelligence and Humanized Computing
AB - Social networks are in continuous evolution, and its spreading has attracted the interest of both practitioners and the scientific community. In the last decades, several new interesting problems have aroused in the context of social networks, mainly due to an overabundance of information, usually named as infodemic. This problem emerges in several areas, such as viral marketing, disease prediction and prevention, and misinformation, among others. Then, it is interesting to identify the most influential users in a network to analyze the information transmitted, resulting in Social Influence Maximization (SIM) problems. In this research, the Budget Influence Maximization Problem (BIMP) is tackled. BIMP proposes a realistic scenario where the cost of selecting each node is different. This is modeled by having a budget that can be spent to select the users of a network, where each user has an associated cost. Since BIMP is a hard optimization problem, a metaheuristic algorithm based on Greedy Randomized Adaptive Search (GRASP) framework is proposed.
SN - 1868-5145
UR - https://doi.org/10.1007/s12652-023-04680-z
DO - 10.1007/s12652-023-04680-z
ID - Lozano-Osorio2023
ER -
AMA Style
Lozano-Osorio I, Sánchez-Oro J, Duarte A. An efficient and effective GRASP algorithm for the Budget Influence Maximization Problem. Journal of Ambient Intelligence and Humanized Computing. Published online 21 September 2023. doi:10.1007/s12652-023-04680-z
Chicago/Turabian Style
Lozano-Osorio, Isaac, Jesús Sánchez-Oro, and Abraham Duarte. ‘An Efficient and Effective GRASP Algorithm for the Budget Influence Maximization Problem’. Journal of Ambient Intelligence and Humanized Computing, 21 September 2023. https://doi.org/10.1007/s12652-023-04680-z.