An Efficient Influence Maximization Algorithm Based on Clique in Social Networks

Abstract

Influence Maximization is to find a subset of influential nodes so that they can spread influence to the largest range in a network. The study on influence maximization is of great importance, and many solutions have been developed, including greedy algorithm which provides the provable approximate guarantee. However, greedy algorithm is very time-consuming, it is unrealistic to apply it to large-scale networks. Heuristic algorithms, which are efficient in influential nodes identifying, usually cannot provide any performance guarantee. To solve above problems, we propose an efficient influence maximization algorithm based on clique (called IMC for short). Our proposed algorithm extracts the cliques in a network and utilizes the information of clique to reduce network size and obtains candidate node set, finally, k most influential nodes are identified from the candidate set. Extensive experiments on 14 real-world networks based on independent cascade model show that our proposed algorithm outperforms state-of-the-art influence maximization algorithms, and achieves comparable influence spread to CELF with less running time.

Keywords

• Social networks
• influence maximization
• greedy algorithm
• maximal complete subgraph
• clique