Malatya Centrality based Algorithm for Positive Influence Dominating Set

Abstract

Social networks are used by individuals not so much for communication as for influencing each other. Social networks are modelled as graphs, and a special Dominating Set is obtained from the resulting graph. A new algorithm has been proposed for the Dominating set, where at least half of the neighbours of each node are elements of the Dominating Set. This algorithm is called as Malatya Positive Influence Algorithm, and its results for some graphs are given in this study.

Keywords

• Social Networks
• Dominating Set
• Positive Influence Dominating Set

Pozitif Etki Hakim Kümesi için Malatya Merkezlilik Tabanlı Algoritma

Abstract

Sosyal ağlar, bireyler tarafından iletişimden çok birbirlerini etkilemek için kullanılır. Sosyal ağlar grafik olarak modellenir ve ortaya çıkan grafikten özel bir Hakim Küme elde edilir. Her bir düğümün komşularının en az yarısının Hakimiyet Kümesi'nde yer aldığı Hakimiyet Kümesi için yeni bir algoritma önerilmiştir. Bu algoritma Malatya Pozitif Etki Algoritması olarak adlandırılmış olup, bazı grafikler üzerindeki sonuçları bu çalışmada verilmiştir.

Keywords

• Sosyal Ağlar
• Hakim Grup
• Olumlu Etki Yaratan Hakim Grup

References

1. Bouamama, S., Blum, C., (2021) “An Improved Greedy Heuristic for the Minimum Positive Influence Dominating Set Problem in Social Networks”, Algorithms, https://doi.org/10.3390/a14030079.
2. Chen, W., Zhong, H., Wu, L., Du, D.-Z., (2022) “A general Greedy Approximation Algorithm for finding Minimum Positive Influence Dominating sets in Social Networks”, Journal of Combinatorial Optimization , https://doi.org/10.1007/s10878-021-00812-3.
3. He, Q., Du, H., Liang, Z., (2023) “Positive Influence Maximization in Signed Networks within a Limited Time”, IEEE Transactions on Computational Social Systems, https://doi.org/ 10.1109/TCSS.2022.3192410.
4. Karci, A., Yakut, S., Öztemiz, F., (2022) “A New Approach Based on Centrality Value in Solving the Minimum Vertex Cover Problem: Malatya Centrality Algorithm”, Journal of Computer Science, Vol:7, pp:81-88.
5. Kundu, G., Choudhury, S., (2021) “ A Discrete Genetic Learning enabled PSO for Targeted Positive Influence Maximization in Consumer Review Networks”, Innovations in Systems and Software Engineering, https://doi.org/10.1007/s11334-021-00396-5.
6. Lin, G., Guan, J., Feng, H., (2018) “An ILP based memetic algorithm for finding minimum positive influence dominating sets in social networks”, Physic A, https://doi.org/10.1016/j.physa.2018.02.119.
7. Pan, J., Bu, T.-M.,(2019) ”A Fast Greedy Algorithm for Finding Minimum Positive Influence Dominating Sets in Social Networks”, 2019 IEEE INFOCOM WJSHPS: CAOS-2019: Communication and Networking Aspects of Online Social Networks, pp:360-364.
8. Okumuş, F., and Karcı,Ş., (2023) “MDSA: A Dynamic and Greedy Approach to Solve the Minimum Dominating Set Problem,” Applied Sciences 2024, Vol. 14, Page 9251, vol. 14, no. 20, p. 9251, Oct. 2024, doi: 10.3390/app14209251.

9. Okumuş, F., Karci, Ş. (2024) “MDSA: A Dynamic and Greedy Approach to Solve the Minimum Dominating Set Problem”, Applied Sciences, https://doi.org/10.3390/app14209251.
10. Shan, Y., Kang, Q., Xiao, R., Chen, Y., Kang, Y., (2022) “An Iterated Carousel Greedy Algorithm for Finding Minimum Positive Influence Dominating Sets in Social Networks”, IEEE Transactions On Computational Social Systems, Vol:9, pp:830-838.
11. Sheng, J., Chen, L., Cehn, Y., Liu, W., (2020) “Positive Influence Maximization in Signed Social Networks under Independent Cascade model”, Soft Computing, https://doi.org/10.1007/s00500-020-05195-x.
12. Sun, R., Wu, J., Jin, C., Wang, Y., Zhou, W., Yin, M., (2023) “An Efficient Local Search Algorithm for Minimum Positive Influence Dominating Set problem”, Computers and Operations Research, Vol:154, https://doi.org/10.1016/j.cor.2023.106197.
13. Wang, F., Du, H., Camacho, E., Xu, K., Lee, W., Shi, Y., Shan, S., (2011), “On positive influence dominating sets in social networks”, Theoretical Computer Science, Vol:412, pp:265-269.
14. Yakut,S., Öztemiz,F., Karci,A.,(2023) “A New Approach Based on Centrality Value in Solving the Maximum Independent Set Problem: Malatya Centrality Algorithm”, Journal of Computer Science, Vol:8, pp:16-23.
15. Yao, X., Huang, H., Du, H., (2020) “Connected positive influence dominating set in k-regular graph”, Discrete Applied Mathematics, https://doi.org/10.1016/j.dam.2020.08.010.
16. Zhong, H., Li, W., Zhang, Q., Lin, R., Tang, Y., (2025) “Efficient Approximation Algorithms for Several Positive Influence Dominating Set Problems in Social Networks”, IEEE Transactions On Computational Social Systems, https://doi.org/ 10.1109/TCSS.2025.3541230.