A New Approach for Minimum Dominating Set Problem: A Three-Stage Solution with Malatya Centrality Metrics

Abstract

The Minimum Dominating Set (MDS) problem is a fundamental challenge in graph theory, with applications spanning diverse domains. This study introduces a novel three-stage approach for solving the MDS problem, which yields solutions at each stage of the process. Leveraging three fundamental interconnected Malatya centrality methodologies, the approach offers an effective means of addressing MDS across a spectrum of problem scales. These centrality metrics capture the centrality of the target node with its neighbors. The algorithm prioritizes nodes with elevated dominance and clustering in the initial iterations, gradually incorporating those with lower clustering into the dominant cluster in the later stages. Notably, the transaction cost is higher in the early iterations but decreases in the later ones. The empirical assessment spans various problem scenarios, encompassing synthetic datasets generated through a specific approach, examples crafted using the Erdös-Renyi model, and authentic datasets drawn from network science applications. Upon examination, it becomes evident that the proposed algorithm consistently yields robust solutions across diverse constraints. In the majority of cases, the performance of the proposed methods surpasses that of existing related algorithms. The findings of this study contribute to the evolving landscape of MDS problem-solving techniques, offering insights into the most promising avenues for future research and practical applications in network design, resource allocation, and beyond.

Keywords

• Minimum Dominating Set
• Domination Number
• Centrality
• Greedy Heuristics
• Graph Algorithms

Minimum hakim küme problemi için yeni bir yaklaşım: Malatya merkezilik metrikleri ile üç aşamalı bir çözüm

Abstract

Minimum Hâkim Küme (MDS) problemi, çeşitli alanlara yayılan uygulamalarla graf teorisinde temel bir zorluktur. Bu çalışma, sürecin her aşamasında çözümler üreten MDS problemini çözmek için yeni bir üç aşamalı yaklaşım sunmaktadır. Üç temel birbirine bağlı Malatya merkezilik metodolojisinden yararlanan yaklaşım, bir dizi problem ölçeğinde MDS'yi ele almanın etkili bir yolunu sunar. Bu merkezilik metrikleri, hedef düğümün komşularıyla olan merkeziliğini yakalar. Algoritma, ilk yinelemelerde yüksek baskınlığa ve kümelenmeye sahip düğümlere öncelik verir ve daha düşük kümelenmeye sahip olanları sonraki aşamalarda kademeli olarak baskın kümeye dahil eder. Dikkat çekici bir şekilde, işlem maliyeti erken yinelemelerde daha yüksekken sonraki yinelemelerde azalır. Ampirik değerlendirme, belirli bir yaklaşımla oluşturulan sentetik veri kümelerini, Erdös-Renyi modeli kullanılarak hazırlanmış örnekleri ve ağ bilimi uygulamalarından alınan otantik veri kümelerini kapsayan çeşitli problem senaryolarını kapsar. İnceleme sonucunda önerilen algoritmanın çeşitli kısıtlamalar arasında tutarlı bir şekilde sağlam çözümler ürettiği ortaya çıkar. Çoğu durumda, önerilen yöntemlerin performansı mevcut ilgili algoritmaların performansını aşar. Bu çalışmanın bulguları, MDS problem çözme tekniklerinin gelişen manzarasına katkıda bulunarak, ağ tasarımı, kaynak tahsisi ve ötesinde gelecekteki araştırmalar ve pratik uygulamalar için umut verici yollara dair içgörüler sunar.

Keywords

• Minimum Hakim Küme
• Hakim Düğüm Sayısı
• Merkezilik
• Açgözlü Sezgisel Yöntemler
• Graf Algoritmaları

References

1. Abed, S. A., & Rais, H. M. (2017). Hybrid bat algorithm for minimum dominating set problem. Journal of Intelligent & Fuzzy Systems, 33(4), 2329–2339. https://doi.org/10.3233/JIFS-17398
2. Aggarwal, C., Subbian, K., Butler, K., Stephens, M., Stephens, M., Chakrabarti, D., Kumar, R., Tomkins, A., Clauset, A., Moore, C., Newman, M. E. J., Csardi, G., Nepusz, T., Decelle, A., Krzakala, F., Moore, C., Zdeborov??, L., Eisinga, R., Te Grotenhuis, M., … Cov, E. R. (2014). {SNAP Datasets}: {Stanford} Large Network Dataset Collection. Physical Review Letters, Complex Sy(1).
3. Albuquerque, M., & Vidal, T. (2018). An efficient matheuristic for the minimum-weight dominating set problem. Applied Soft Computing Journal, 72. https://doi.org/10.1016/j.asoc.2018.06.052
4. Batool, K., & Niazi, M. A. (2014). Towards a methodology for validation of centrality measures in complex networks. PLoS ONE, 9(4). https://doi.org/10.1371/journal.pone.0090283
5. Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1–7), 107–117. https://doi.org/10.1016/S0169-7552(98)00110-X
6. Bujtás, C., & Klavžar, S. (2016). Improved Upper Bounds on the Domination Number of Graphs With Minimum Degree at Least Five. Graphs and Combinatorics, 32(2), 511–519. https://doi.org/10.1007/s00373-015-1585-7
7. Casado, A., Bermudo, S., López-Sánchez, A. D., & Sánchez-Oro, J. (2023). An iterated greedy algorithm for finding the minimum dominating set in graphs. Mathematics and Computers in Simulation, 207. https://doi.org/10.1016/j.matcom.2022.12.018
8. Chalupa, D. (2018). An order-based algorithm for minimum dominating set with application in graph mining. Information Sciences, 426. https://doi.org/10.1016/j.ins.2017.10.033

9. Connolly, S., Gabor, Z., Godbole, A., Kay, B., & Kelly, T. (2016). Bounds on the maximum number of minimum dominating sets. Discrete Mathematics, 339(5). https://doi.org/10.1016/j.disc.2015.12.030
10. Erdös, P., & Rényi, A. (1959). On random graphs. Publicationes Mathematicae, 6, 290–297. https://doi.org/10.2307/1999405
11. Esfahanian, A. (2013). Connectivity algorithms. In Topics in structural graph theory (pp. 268–281). Cambridge University Press. https://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
12. Estrada, E. (2011). The Structure of Complex Networks. In SIAM Review (Vol. 45, Issue 2). https://doi.org/10.1093/acprof:oso/9780199591756.001.0001
13. Gao, C., Lan, X., Zhang, X., & Deng, Y. (2013). A Bio-Inspired Methodology of Identifying Influential Nodes in Complex Networks. PLoS ONE, 8(6). https://doi.org/10.1371/journal.pone.0066732
14. Hedar, A. R., & Ismail, R. (2010). Hybrid genetic algorithm for minimum dominating set problem. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6019 LNCS(PART 4). https://doi.org/10.1007/978-3-642-12189-0_40
15. Hernández Mira, F. Á., Parra Inza, E., Sigarreta Almira, J. M., & Vakhania, N. (2022). A polynomial-time approximation to a minimum dominating set in a graph. Theoretical Computer Science, 930, 142–156. https://doi.org/10.1016/j.tcs.2022.07.020
16. Hu, J., Du, Y., Mo, H., Wei, D., & Deng, Y. (2016). A modified weighted TOPSIS to identify influential nodes in complex networks. Physica A: Statistical Mechanics and Its Applications, 444, 73–85. https://doi.org/10.1016/j.physa.2015.09.028
17. Jovanovic, R., & Tuba, M. (2013). Ant colony optimization algorithm with pheromone correction strategy for the minimum connected dominating set problem. Computer Science and Information Systems, 10(1). https://doi.org/10.2298/CSIS110927038J
18. Kapoor, K., Sharma, D., & Srivastava, J. (2013). Weighted node degree centrality for hypergraphs. Proceedings of the 2013 IEEE 2nd International Network Science Workshop, NSW 2013. https://doi.org/10.1109/NSW.2013.6609212
19. Karci, A. (2020). New Algorithms for Minimum Dominating Set in Any Graphs. Computer Science, 5(2).
20. Karcı, A., Yakut, S., & Öztemiz, F. (2022). A New Approach Based on Centrality Value in Solving the Minimum Vertex Cover Problem: Malatya Centrality Algorithm. Computer Science. https://doi.org/10.53070/bbd.1195501
21. Kunegis, J. (2013). KONECT - The koblenz network collection. WWW 2013 Companion - Proceedings of the 22nd International Conference on World Wide Web.
22. Li, J., Potru, R., & Shahrokhi, F. (2020). A Performance Study of Some Approximation Algorithms for Computing a Small Dominating Set in a Graph. Algorithms, 13(12), 339. https://doi.org/10.3390/a13120339
23. Newman, M. E. J. (2003). The Structure and Function of Complex Networks. SIAM Review, 45(2), 167–256.
24. Nguyen, M. H., Hà, M. H., Nguyen, D. N., & Tran, T. T. (2020). Solving the k-dominating set problem on very large-scale networks. Computational Social Networks, 7(1). https://doi.org/10.1186/s40649-020-00078-5
25. Okumuş, F., & Karcı, Ş. (2024). MDSA: A Dynamic and Greedy Approach to Solve the Minimum Dominating Set Problem. Applied Sciences, 14(20), 9251. https://doi.org/10.3390/app14209251
26. Ore, O. (1962). Theory of Graphs. American Mathematical Society Colloquium Publications.
27. Page, L., Brin, S., Motwani, R., & Winograd, T. (1998). The PageRank Citation Ranking: Bringing Order to the Web. World Wide Web Internet And Web Information Systems, 54(1999–66), 1–17. https://doi.org/10.1.1.31.1768
28. Potluri, A., & Singh, A. (2013). Hybrid metaheuristic algorithms for minimum weight dominating set. Applied Soft Computing Journal, 13(1). https://doi.org/10.1016/j.asoc.2012.07.009
29. Potluri, A., & Singh, A. (2011). Two hybrid meta-heuristic approaches for minimum dominating set problem. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7077 LNCS(PART 2). https://doi.org/10.1007/978-3-642-27242-4_12
30. Sanchis, L. A. (2002). Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem. Algorithmica, 33(1), 3–18. https://doi.org/10.1007/s00453-001-0101-z
31. Truta, T. M., Campan, A., & Beckerich, M. (2020). Efficient Approximation Algorithms for Minimum Dominating Sets in Social Networks. In Research Anthology on Artificial Intelligence Applications in Security (pp. 1120–1153). IGI Global. https://doi.org/10.4018/978-1-7998-7705-9.ch052
32. Tuğal, İ., & Karcı, A. (2019). Comparisons of Karcı and Shannon entropies and their effects on centrality of social networks. Physica A: Statistical Mechanics and Its Applications, 523, 352–363. https://doi.org/10.1016/j.physa.2019.02.026
33. Tuğal, İhsan, & Karcı, A. (2020). Determination of Influential Countries by Cultural and Geographical Parameters. Anemon Muş Alparslan University Social Sciences Journal. https://doi.org/10.18506/anemon.563211
34. Vazirani, V. V. (2003). Approximation Algorithms. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-662-04565-7
35. 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, 412(3), 265–269. https://doi.org/10.1016/j.tcs.2009.10.001
36. Yakut, S., Öztemiz, F., & Karci, A. (2023). A new robust approach to solve minimum vertex cover problem: Malatya vertex-cover algorithm. The Journal of Supercomputing. https://doi.org/10.1007/s11227-023-05397-8
37. Zhou, Y., Lv, G., Xiu, B., Zhang, W., & Cheng, Q. (2014). A faster approximate method to identify minimum dominating set. Proceedings of the IEEE International Conference on Software Engineering and Service Sciences, ICSESS. https://doi.org/10.1109/ICSESS.2014.6933601