A hybrid algorithm based on community detection and multi attribute decision making for influence maximization

作者：Jalayer Masoud; Azheian Morvarid; Kermani Mehrdad Agha Mohammad Ali^*

来源：COMPUTERS & INDUSTRIAL ENGINEERING, 2018, 120: 234-250.

DOI：10.1016/j.cie.2018.04.049

• Influence maximization
• Social network analysis
• Community detection
• SIR model

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.

• 出版日期2018-6