RMDN: New Approach to Maximize Influence Spread

Influence maximization modeling and analyzing is an important problem in Online Social Networks (OSNs). Influential nodes provide information on hot topics and forward interesting information, which can yield great influence on other nodes in OSNs. For word-of-mouth viral marketing, it is critical to find influential nodes within budgets. However, finding the optimal solution to maximize the influence spread in a given OSN has been proven to be NP-Hard. The existing algorithms suffer the following three defects: (1) need acquire the topological structure of the network, which is impractical for the continuously changing networks in real life, (2) are easy to get trapped in Rich Club phenomena, (3) can not balance very well between influence spread and running time. To solve this challenging problem, based on the randomly heuristic algorithm and the scale-free property of Complex Networks, we propose RMDN (Random Maximal Degree Neighbor) and its improved version RMDN++. We prove the feasibility and scalability of RMDNs in theory. Five real datasets are used to test the effectiveness and efficiency of RMDNs under two different influence diffusion models. The result shows that our methods have a comparable performance in terms of influence spread as state-of-the-art algorithms, but decrease the time by 1-2 orders of magnitude.