OPTIMAL WEIGHTED EVOLUTIONARY ALGORITHM FOR THE DOMINATING SET PROBLEM IN LARGE SCALE SOCIAL NETWORK
Abstract
In graph theory, the minimum dominating set (MDS) problem is pivotal for optimizing network controllability and observability, especially in managing large-scale wireless ad hoc and sensor networks efficiently. However, existing algorithms often struggle with the inherent complexity of the MDS problem and fail to deliver accurate solutions due to intricate connectivity constraints. To address these challenges, this study presents an optimal weighted evolutionary algorithm tailored for tackling MDS problems across various scales of social networks. The proposed approach leverages the improved snow leopard optimization (ISLO) algorithm to effectively reduce graph size. By strategically fixing portions of vertices within or outside the candidate solution, ISLO avoids redundant search spaces, thereby enhancing efficiency. Additionally, the deep optimized lightning search (DOLS) algorithm is integrated into the vertex selection strategy during local search. This refinement process efficiently adds or removes vertices, further improving the search procedure. Extensive experiments are conducted on diverse social networks to evaluate the proposed algorithm's performance. Comparative analysis against state-of-the-art algorithms show that ISLO-DOLS excels in problem-solving tasks on large-scale social networks. Its ability to yield superior solutions underscores its effectiveness in optimizing network management strategies.