Population-based metaheuristic approach to increase the efficiency of controllability processes on temporal networks using Parallel Temporal Max-Min Ant System
摘要
The optimization of controllability in complex networks, particularly temporal ones, has been a significant focus in recent research, often leveraging metaheuristic approaches. This paper introduces a novel population-based metaheuristic approach to enhance the efficiency of controllability processes in temporal networks by leveraging a Temporal Max-Min Ant System (TMAS). The problem of identifying the Minimum set of Driver Nodes (MDS) for structural controllability in temporal networks is known to be NP-hard, rendering exact methods computationally infeasible for large-scale instances. Unlike prior methods that rely on greedy heuristics or sequential metaheuristics, our proposed method combines the explorative power of a parallelized TMAS (PTMAS) with an exact maximum flow algorithm to efficiently identify near-optimal driver node sets. The integration of strict pheromone bounding mechanisms prevents premature convergence and promotes robust exploration of the solution space. Experimental evaluations on multiple real-world temporal networks demonstrate that our method significantly outperforms existing conventional methods, reducing the number of required driver nodes by up to 20%, achieving full controllability up to 36% faster, and reducing 32% in execution time on average. The parallel implementation further reduces execution time by nearly 50% compared to sequential variants, confirming the scalability and practical applicability of the proposed approach for complex temporal network control.