Maximum independent set in multiplex social networks and its application to influence maximization

Identifying the most influential spreaders as an influence maximization problem (IMP) has become one of the most compelling topics in social network analysis due to its successes in viral marketing. In this paper, we first assume the network model to be a multiplex network, consisting of layers where each layer represents a different type of association among users based on their activities. We then define the concept of the maximum independent set (MIS) problem within multiplex networks. Next, we propose MIS as a potential solution to the MIP for identifying the initial candidate set of spreaders. Finally, we develop a learning automaton framework to solve the MIS in multiplex networks and to demonstrate its applicability for influence maximization. Theoretical properties of the MIS in multiplex networks are provided, along with various experiments on both artificial and real networks to showcase the performance of the proposed algorithm.