Maximize Influence Diffusion in Social Networks with Spreading Distance and 2-Step Neighborhood Overlapping Effects

Abstract

There are mainly two problems about influence maximization: On one hand, although greedy algorithm can accurately locate seed nodes, the high time complexity of such algorithm is unable to be applied in large-scale social networks; on the other hand, traditional heuristic algorithms generally have no ideal diffusion results in spite of quickly finding out seed nodes. With the disadvantage of these proposed influence maximization algorithm, this paper introduces the conception of limited spreading distance based on traditional independent cascade model. Then a neighborhood influence discount heuristic algorithm (NIDH) based on 2-step neighborhood and overlapping effect is put forward from the perspective of information propagation dynamics. Experimental results show that, with respect to other algorithms, NIDH algorithm can more accurately locate seed nodes with larger spreading ability and acceptable time complexity.