An algorithm for weighted positive influence dominating set based on learning automata

摘要

The problem of Influence Maximization (IM) in social network refers to determining a set of nodes that can maximize the spread of influence. IM problem has been applied in many domains such as marketing, advertising and public opinion monitoring. In recent years, different type of algorithms reported in the literature. A type of algorithms for this problem is based on dominating set. In these algorithms, the IM problem is considered as a version of dominating set problem. A limitation of most of these algorithms, the graph of the social network is assumed to be a un-weighted graph which is not a realistic assumption. The other drawback of these algorithms is that they generally omit the crucial characteristics of the social networks such as different level of influence and dynamic interaction among individuals. In order to solve these problems and based on the realistic nature of the social network, it seems that the Minimum Weighted Positive Influence Dominating Set (MWPIDS) problem can support the mentioned characteristics because it consider the weight of the graph. In this paper, a learning automaton based algorithm is proposed to reveal MWPIDS in the social network graphs. In the proposed algorithm, each vertex of the social network graph is equipped with a learning automaton that determines the beeing candidate or non-candidate of the corresponding vertex to be in WPIDS or not. Owing to adaptive decision making characteristics of learning automata, the proposed algorithm significantly reduces the number of candidate solution. The proposed algorithm, based on learning automata, iteratively decreases the weight of the obtained positive influence dominating. In order to evaluate the proposed algorithm, several experiments have been conducted on real social network datasets which compared to the state-of-the art methods. Experimental results show the superiority of the proposed algorithm over the previous algorithms.