Open AccessInfluence Maximization: A Time-Space Efficient Algorithm
Author(s) -
Ganming Xia
Publication year - 2019
Publication title -
iop conference series. materials science and engineering
Language(s) - English
Resource type - Journals
eISSN - 1757-899X
pISSN - 1757-8981
DOI - 10.1088/1757-899x/533/1/012048
Subject(s) - maximization , computer science , algorithm , memory footprint , spacetime , sampling (signal processing) , expectation–maximization algorithm , space (punctuation) , mathematical optimization , mathematics , maximum likelihood , statistics , physics , filter (signal processing) , quantum mechanics , computer vision , operating system
Influence maximization is the problem of finding a small subset of nodes (seed nodes) in a social network that could maximize the spread the influence. The algorithm problem of computing influence estimation and influence maximization have been extensively studied for decades. In this paper, we studied the reverse influence sampling method proposed by Byogs et al. in 2014, and some other improved algorithms. We proposed a new algorithm TESA (Time-Space Efficient Algorithm). On large social networks, TESA saves more space than existing algorithms and runs faster. We used data sets tested in the literature to evaluate TESA experimentally and showed that it was superior to the most advanced solutions in terms of running time and memory footprint.