Community-based framework for influence maximization problem in social networks

Abstract

Given a social graph, the influence maximization problem (IMP) is the act of selecting a group of nodes that cause maximum influence if they are considered as seed nodes of a diffusion process. IMP is an active research area in social network analysis due to its practical need in applications like viral marketing, target advertisement, and recommendation system. In this work, we propose an efficient solution for IMP based on the social network structure. The community structure is a property of real-world graphs. In fact, communities are often overlapping because of the involvement of users in many groups (family, workplace, and friends). These users are represented by overlapped nodes in the social graphs and they play a special role in the information diffusion process. This fact prompts us to propose a solution framework consisting of three phases: firstly, the community structure is discovered, secondly, the candidate seeds are generated, then lastly the set of final seed nodes are selected. The aim is to maximize the influence with the community diversity of influenced users. The study was validated using synthetic as well as real social network datasets. The experimental results show improvement over baseline methods and some important conclusions were reported.