Distributed Learning Automata based Algorithm for Solving Maximum Clique Problem in Stochastic Graphs

Abstract

Many real world systems modeled as graph or networks, which the characteristics of interaction between vertices are stochastic and the probability distribution function of the vertex weight is unknown. Finding the maximum clique in a given graph is known as a NP-Hard problem, motivated by the social networks analysis. The maximum clique of an arbitrary graph G is the sub-graph C of G, Such that all vertices in C are adjacent in G and have maximum cardinality. In this paper an algorithm based on distributed learning automata is presented to solve maximum clique problem in the stochastic graph. Several experiments are designed to evaluate the proposed algorithm. Experimental results indicate that the proposed algorithm have a good performance in stochastic graph.