Open AccessFast Methods for Finding Multiple Effective Influencers in Real Networks
Author(s) -
Fern Y. Hunt,
Roldan Pozo
Publication year - 2020
Publication title -
journal of research of the national institute of standards and technology
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.202
H-Index - 59
eISSN - 2165-7254
pISSN - 1044-677X
DOI - 10.6028/jres.125.036
Subject(s) - scalability , computer science , hitting time , influencer marketing , random walk , monte carlo method , random graph , graph , algorithm , combinatorics , mathematics , theoretical computer science , statistics , database , marketing , relationship marketing , business , marketing management
We present scalable first hitting time methods for finding a collection of nodes that enables the fastest time for the spread of consensusin a network. That is, given a graph G = (V;E) and a natural number k, these methods find k vertices in G that minimize the sum ofhitting times (expected number of steps of random walks) from all remaining vertices. Although computationally challenging forgeneral graphs, we exploited the characteristics of real networks and utilized Monte Carlo methods to construct fast approximationalgorithms that yield near-optimal solutions.