An Efficient Influence Maximization Algorithm Considering Both Positive and Negative Relationships

As large-scale social networks flourish, influence maximization problem has become a hot topic in recent years. Existing studies consider only positive relationships in social networks. However, it is completely ignored that both positive and negative relationships may exist at the same time in many Online Social Networks (OSNs), e.g. Epinions and Slashdot. In this work, we propose an efficient influence maximization algorithm, namely Hybrid Potential-influence Greedy algorithm with Negative opinions (HPG-N) that uses the advantages of cumulative feature for influence maximization in both Linear Threshold model (LT) and its extension LT-N that incorporates negative opinion diffusion. We aim at solving the problem of influence maximization in social networks considering both positive and negative relationships with greater diffusion scope and more effectiveness than other algorithms. The algorithm we proposed can solve the problem of maximizing the positive influence spread effectively in real-world networks with both positive and negative relationships. In the heuristic stage, to seek seeds more quickly, we seek for those nodes, which can provide the greatest potential influence as seeds. In the greedy stage, we improve the traditional greedy algorithm to expand the scope of influence as much as possible. Experimental results show that our algorithm significantly performs better than baseline algorithms in the aspect of running time.