Solving Minimum Dominating Set in Multiplex Networks Using Learning Automata

摘要

The dominating set (DS) problem has noticed the selecting a subset of vertices that every vertex in the graph is either is adjacent to one or more nodes of this subset. The DS with the minimum cardinality is called MDS (minimum dominating set). The MDS problem has several applications in different domains, such as network monitoring, routing, epidemic control and social network. The MDS is known as the NP-Hard problem. Nevertheless, the existing research has focused on the MDS problem to single networks. However, in many real structures, there exist a complex structure involving a set of components combined up by different connections and known as multiplex networks. In this paper, we introduce a learning automaton (LA) based algorithm for find the MDS problem in multiplex networks. In the proposed algorithm, each node of the multiplex network is considered an LA with two actions of a candidate or non-candidate corresponding to the dominating set and non-dominating set. By selecting candidate DS and evaluation mechanisms, the algorithm tries to find a dominating set with the smallest cardinality and as the algorithm proceeds, a candidate solution converges to the optimal solution of the MDS of multiplex networks. With the aid of learning and the behavior of learning automata for finding solution, this algorithm which is present in this paper reduces the number of dominating set, in multiplex networks iteratively. Experimental results demonstrate that in many well-known datasets, the proposed algorithm is efficient with respect to the evaluation measure.