A hybrid algorithm based on community detection and multi attribute decision making for influence maximization. (June 2018) - Jalayer, Masoud; Azheian, Morvarid; Agha Mohammad Ali Kermani, Mehrdad
Highlights: A novel greedy and hybrid algorithm proposed for influence maximization. The proposed algorithm is based on Hespanha and Topsis. The efficiency of the algorithm is evaluated using eight datasets. Abstract: Influence maximization problem is trying to identify a set of K nodes by which the spread of influence, diseases or information is maximized. The optimization of influence by finding such a set is NP-hard problem and a key issue in analyzing complex networks. In this paper, a new greedy and hybrid approach based on a community detection algorithm and an MADM technique (TOPSIS) is proposed to cope with the problem, called, 'Greedy TOPSIS and Community-Based' (GTaCB) algorithm. The paper concisely introduces community detection and TOPSIS technique, then it presents the pseudo-code of the proposed algorithm. Afterwards, it compares the performance of the solution which is found by GTaCB with some well-known greedy algorithms, based on Degree Centrality, Closeness Centrality, Betweenness Centrality, PageRank as well as TOPSIS, from two aspects: diffusion quality and diffusion speed. In order to evaluate the performance of GTaCB, computational experiments on eight different types of real-world networks are provided. The tests are conducted via one of the renowned epidemic diffusion models, namely, Susceptible-Infected-Recovered (SIR) model. The simulations exhibit that in most of the cases the proposed algorithm significantly outperforms the others, chiefly as number of initial nodes or probability of infection increases.