A hybrid algorithm based on community detection and multi attribute decision making for influence maximization. (June 2018)

• Record Type: Journal Article
• Authors: Jalayer, Masoud; Azheian, Morvarid; Agha Mohammad Ali Kermani, Mehrdad
• Is Part Of: Computers & industrial engineering. Volume 120(2018)
• Page Start: 234
• Page End: 250
• Publication Date: 2018-06
• Subjects: Influence maximization -- Social network analysis -- Community detection -- SIR model; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2018.04.049
• Languages: English
• ISSNs: 0360-8352

Abstract

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.