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 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.