TI-SC: top-k influential nodes selection based on community detection and scoring criteria in social networks
- PDF / 8,153,800 Bytes
- 20 Pages / 595.276 x 790.866 pts Page_size
- 5 Downloads / 185 Views
ORIGINAL RESEARCH
TI‑SC: top‑k influential nodes selection based on community detection and scoring criteria in social networks Hamid Ahmadi Beni1 · Asgarali Bouyer1 Received: 25 June 2019 / Accepted: 1 February 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract 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. Keywords Social network · Viral marketing · Influence maximization · Seed node · Community detection
1 Introduction Social Network Analysis (SNA) studies the structure and information flow in the social network. The social network is a set of nodes and links with a specific type of relationships and interactions, such as friendship, like or dislike, love, etc. One of the most important issues in social networks is the investigation of finding influential nodes. If an influential node is identified individually without considering the position of other influential nodes in the network, it is defined an influential spreader detection problem (Berahmand et al. 2018, 2019). However, identifying the set of influential nodes with regard to the topological effects of these nodes in relation to each other is called the influence maximization problem (Samadi and Bouyer 2019).
* Asgarali Bouyer [email protected]; [email protected] Hamid Ahmadi Beni [email protected] 1
Azarbaijan Shahid Madani University, Tabriz, Iran
An example of the applications of influence maximization is viral marketing. Viral marketing through social networks has now become imperative for maximizing t
Data Loading...
