TI-SC: top-k influential nodes selection based on community detection and scoring criteria in social networks

Autor: Asgarali Bouyer, Hamid Ahmadi Beni
Rok vydání: 2020
Předmět:
Zdroj: Journal of Ambient Intelligence and Humanized Computing. 11:4889-4908
ISSN: 1868-5145
1868-5137
DOI: 10.1007/s12652-020-01760-2
Popis: Influence maximization is a classic optimization problem to find a subset of seed nodes in a social network that has a maximum influence with respect to a propagation model. This problem suffers from the overlap of seed nodes and the lack of optimal selection of seed nodes. Kempe et al. have shown that this problem is an NP-hard problem, and the objective function is submodular. Therefore, some heuristic and greedy algorithms have been proposed to find a near-optimal solution. However, the greedy algorithm may not satisfy the accuracy of a given solution and high time-consuming problem. To overcome these problems, the TI-SC algorithm is proposed for the problem of influence maximization. The TI-SC algorithm selects the influential nodes by examining the relationships between the core nodes and the scoring ability of other nodes. After selecting each seed node, the scores are updated to reduce the overlap in selecting the seed nodes. This algorithm has efficient performance in high Rich-Club networks. The Rich-Club phenomenon causes overlapping of the influence spread among the seed nodes in most of the other methods so that the TI-SC algorithm reduces this overlapping. Furthermore, the discovered communities with low expansion are not considered in the seed node selection phase, and this is useful for reducing computational overhead. Experimental results on both synthetic and real datasets show that the proposed TI-SC algorithm significantly outperforms the state-of-the-art algorithms in terms of efficiency in both small and large-scale datasets.
Databáze: OpenAIRE
Externí odkaz: