Efficient identification of maximum independent sets in stochastic multilayer graphs with learning automata
Investigating the maximum independent set in stochastic multilayer graphs provides critical insights into the structural and dynamical properties of complex networks. Recently, stochastic multilayer graphs effectively model the intricate interactions and interdependencies inherent in real-world syst...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-12-01
|
| Series: | Results in Engineering |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2590123024014786 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850054409257484288 |
|---|---|
| author | Mohammad Mehdi Daliri Khomami Mohammad Reza Meybodi Alireza Rezvanian |
| author_facet | Mohammad Mehdi Daliri Khomami Mohammad Reza Meybodi Alireza Rezvanian |
| author_sort | Mohammad Mehdi Daliri Khomami |
| collection | DOAJ |
| description | Investigating the maximum independent set in stochastic multilayer graphs provides critical insights into the structural and dynamical properties of complex networks. Recently, stochastic multilayer graphs effectively model the intricate interactions and interdependencies inherent in real-world systems, including social, biological, and transportation networks. The identification of a maximum independent set -comprising nodes without direct connections- offers a significant understanding of phenomena such as information diffusion, resource allocation, and epidemic spread within complex social networks. For instance, independent sets play a crucial role in identifying influencers -individuals who profoundly impact their peers, propagating information or opinions widely. In this paper, we introduce the stochastic version of the maximum independent set and propose five algorithms based on learning automata to identify maximum independent sets in the stochastic multilayer graphs. Our approach utilizes learning automata to provide a guided sampling from candidate independent sets of the stochastic multilayer graph, aiming to identify the independent set with the maximum expected value while utilizing fewer vertex samples than standard methods that do not incorporate the learning. In addition to proving several mathematical properties of the proposed approach, simulations conducted across diverse stochastic multilayer graphs demonstrate that our learning automata-based algorithms outperform traditional approaches, achieving higher convergence rates and requiring fewer samples. |
| format | Article |
| id | doaj-art-d508a5ed0fee4b44a8dca91a7d5bafcb |
| institution | DOAJ |
| issn | 2590-1230 |
| language | English |
| publishDate | 2024-12-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Results in Engineering |
| spelling | doaj-art-d508a5ed0fee4b44a8dca91a7d5bafcb2025-08-20T02:52:16ZengElsevierResults in Engineering2590-12302024-12-012410322410.1016/j.rineng.2024.103224Efficient identification of maximum independent sets in stochastic multilayer graphs with learning automataMohammad Mehdi Daliri Khomami0Mohammad Reza Meybodi1Alireza Rezvanian2Soft computing laboratory, Department of Computer Engineering, Amirkabir University of Technology (Tehran Polytechnic), Tehran, IranSoft computing laboratory, Department of Computer Engineering, Amirkabir University of Technology (Tehran Polytechnic), Tehran, IranDepartment of Computer Engineering, University of Science and Culture, Tehran, Iran; Corresponding author.Investigating the maximum independent set in stochastic multilayer graphs provides critical insights into the structural and dynamical properties of complex networks. Recently, stochastic multilayer graphs effectively model the intricate interactions and interdependencies inherent in real-world systems, including social, biological, and transportation networks. The identification of a maximum independent set -comprising nodes without direct connections- offers a significant understanding of phenomena such as information diffusion, resource allocation, and epidemic spread within complex social networks. For instance, independent sets play a crucial role in identifying influencers -individuals who profoundly impact their peers, propagating information or opinions widely. In this paper, we introduce the stochastic version of the maximum independent set and propose five algorithms based on learning automata to identify maximum independent sets in the stochastic multilayer graphs. Our approach utilizes learning automata to provide a guided sampling from candidate independent sets of the stochastic multilayer graph, aiming to identify the independent set with the maximum expected value while utilizing fewer vertex samples than standard methods that do not incorporate the learning. In addition to proving several mathematical properties of the proposed approach, simulations conducted across diverse stochastic multilayer graphs demonstrate that our learning automata-based algorithms outperform traditional approaches, achieving higher convergence rates and requiring fewer samples.http://www.sciencedirect.com/science/article/pii/S2590123024014786Independent setLearning automataMultilayer graphsStochastic multilayer graphsLearning Automata |
| spellingShingle | Mohammad Mehdi Daliri Khomami Mohammad Reza Meybodi Alireza Rezvanian Efficient identification of maximum independent sets in stochastic multilayer graphs with learning automata Results in Engineering Independent set Learning automata Multilayer graphs Stochastic multilayer graphs Learning Automata |
| title | Efficient identification of maximum independent sets in stochastic multilayer graphs with learning automata |
| title_full | Efficient identification of maximum independent sets in stochastic multilayer graphs with learning automata |
| title_fullStr | Efficient identification of maximum independent sets in stochastic multilayer graphs with learning automata |
| title_full_unstemmed | Efficient identification of maximum independent sets in stochastic multilayer graphs with learning automata |
| title_short | Efficient identification of maximum independent sets in stochastic multilayer graphs with learning automata |
| title_sort | efficient identification of maximum independent sets in stochastic multilayer graphs with learning automata |
| topic | Independent set Learning automata Multilayer graphs Stochastic multilayer graphs Learning Automata |
| url | http://www.sciencedirect.com/science/article/pii/S2590123024014786 |
| work_keys_str_mv | AT mohammadmehdidalirikhomami efficientidentificationofmaximumindependentsetsinstochasticmultilayergraphswithlearningautomata AT mohammadrezameybodi efficientidentificationofmaximumindependentsetsinstochasticmultilayergraphswithlearningautomata AT alirezarezvanian efficientidentificationofmaximumindependentsetsinstochasticmultilayergraphswithlearningautomata |