Selection of top-K influential users based on radius-neighborhood degree, multi-hops distance and selection threshold

摘要

Abstract Influence maximization in the social network becomes increasingly important due to its various benefit and application in diverse areas. In this paper, we propose DERND D-hops that adapt the radius-neighborhood degree to a directed graph which is an improvement of our previous algorithm RND d-hops. Then, we propose UERND D-hops algorithm for the undirected graph which is based on radius-neighborhood degree metric for selection of top-K influential users by improving the selection process of our previous algorithm RND d-hops. We set up in the two algorithms a selection threshold value that depends on structural properties of each graph data and thus improves significantly the selection process of seed set, and use a multi-hops distance to select most influential users with a distinct range of influence. We then, determine a multi-hops distance in which each consecutive seed set should be chosen. Thus, we measure the influence spread of selected seed set performed by our algorithms and existing approaches on two diffusion models. We, therefore, propose an analysis of time complexity of the proposed algorithms and show its worst time complexity. Experimental results on large scale data of our proposed algorithms demonstrate its performance against existing algorithms in term of influence spread within a less time compared with our previous algorithm RND d-hops thanks to a selection threshold value.