Графын чухал оройг илрүүлэх хувьслын алгоритм
DOI:
https://doi.org/10.22353/mjeas.v5i2.4985Keywords:
Бүлэг бүтэц, чухал оройн бодлого, комплекс сүлжээ, хоорондын төв, хувьсалын алгоритмAbstract
Энэхүү судалгааны ажлаар сүлжээ (граф)-ний чухал оройн бодлого (ЧОБ) -ыг хувьслын алгоритм (evolutionary algorithm (EA))-аар бодох аргыг судална. ЧОБ нь сүлжээнээс хамгийн цөөн тооны оройг устган, үлдэгдэл сүлжээний хамгийн том холбоост бүрдлийн (ХТХБ) хэмжээг өгөгдсөн L параметрээс бага байлгах бодлого юм. Сүүлийн жилүүдэд хийгдэж буй өгөгдөлд суурилсан судалгаагаар байгаль, нийгэм дэх сүлжээ (систем) нь бүлэг бүтэц (community structure)-тэй гэдгийг тогтоогоод байна. Энэ ажилд сүлжээний бүлэг бүтцийн мэдээллийг ЧОБ-д ашиглах шинэ аргыг танилцууллаа. Тодруулбал, бүлэг бүтцийн мэдээллийг генийн дүрслэлээр (representation) ашиглах хувьслын алгоритмыг зохиомжлов. ЧОБ-д өргөн ашиглагддаг зургаан бодит сүлжээн дээр алгоритмын ажиллагааг туршиж, Greedy1, Greedy2, Genetic algorithm гэсэн гурван аргатай харьцуулан, дэвшүүлж буй алгоритмын гүйцэтгэлийг үнэллээ. Дэвшүүлж буй алгоритм том сүлжээн дээр 10-30 дахин богино хугацаанд, 2 өгөгдөл дээр давуу шийд гаргаж байгааг туршилтын үр дүн харуулав.
Downloads
References
Arulselvan A, Commander CW, Pardalos PM, Shylo O. Managing network risk via critical node identification. Risk management in telecommunication networks, Springer. 2007:79--92.
Santos D, de~Sousa A, Monteiro P. Compact models for critical node detection in telecommunication networks. Electronic Notes in Discrete Mathematics. 2018;64:325--334.
Cantillo V, Macea LF, Jaller M. Assessing vulnerability of transportation networks for disaster response operations. Networks and Spatial Economics. 2019;19:243--273.
Sarker S, Veremyev A, Boginski V, Singh A.Critical nodes in river networks.Scientific Reports. 2019;9(1):1--11.
Tian L, Bashan A, Shi DN, Liu YY.Articulation points in complex networks.Nature communications. 2017;8(1):14223.
Arulselvan A, Commander CW, Shylo O, Pardalos PM.Cardinality-constrained critical node detection problem.Performance models and risk management in communications systems. 2011:79--91.
Veremyev A, Boginski V, Pasiliao EL.Exact identification of critical nodes in sparse networks via new compact formulations.Optimization Letters. 2014;8:1245--1259.
Arulselvan A, Commander CW, Elefteriadou L, Pardalos PM.Detecting critical nodes in sparse graphs.Computers & Operations Research. 2009;36(7):2193--2200.
Aringhieri R, Grosso A, Hosteins P, Scatamacchia R.Local search metaheuristics for the critical node problem.Networks. 2016;67(3):209--221.
Addis B, Aringhieri R, Grosso A, Hosteins P.Hybrid constructive heuristics for the critical node problem.Annals of Operations Research. 2016;238:637--649.
Alozie GU, Arulselvan A, Akartunal{i} K, Pasiliao~Jr EL.Efficient methods for the distance-based critical node detection problem in complex networks.Computers & Operations Research. 2021;131:105254.
Salemi H, Buchanan A.Solving the distance-based critical node problem.INFORMS Journal on Computing. 2022;34(3):1309--1326.
Gaarey M, Johanson D, Stockmayer L.Some simplified np-complete graph problem.Theoretical Computer Science;1(1976):237--267.
Addis B, Di~Summa M, Grosso A.Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth.Discrete Applied Mathematics. 2013;161(16-17):2349--2360.
Lalou M, Tahraoui MA, Kheddouci H.The critical node detection problem in networks: A survey.Computer Science Review. 2018;28:92--117.
Girvan M, Newman ME.Community structure in social and biological networks.Proceedings of the national academy of sciences. 2002;99(12):7821--7826.
Fortunato S, Newman ME.20 years of network community detection.Nature Physics. 2022;18(8):848--850.
Brandes U.A faster algorithm for betweenness centrality.Journal of mathematical sociology. 2001;25(2):163--177.
Geisberger R, Sanders P, Schultes D.Better approximation of betweenness centrality.In: 2008 Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM; 2008. p. 90--100.
Cousins C, Wohlgemuth C, Riondato M.BAVARIAN: Betweenness centrality approximation with variance-aware Rademacher averages.ACM Transactions on Knowledge Discovery from Data. 2023;17(6):1--47.
Fan C, Zeng L, Feng Y, Xiu B, Huang J, Liu Z.Revisiting the power of reinsertion for optimal targets of network attack.Journal of Cloud Computing. 2020;9:1--13.
Aringhieri R, Grosso A, Hosteins P, Scatamacchia R.A general evolutionary framework for different classes of critical node problems.Engineering Applications of Artificial Intelligence. 2016;55:128--145.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Mongolian Journal of Engineering and Applied Sciences
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
