Optimization of Seed Selection for Information Diffusion with High Level Synthesis

Abstract

Information diffusion is where a message or data is passed from vertex to vertex in a network via edges. Information diffusion is often used for simulations in network research because it estimates how information propagates through a network. A set of vertices that in initial state contains the data is known as the \textit{seed nodes}. The diffusion starts at the seed nodes and propagates over the network. Finding the optimal seed nodes is a crucial part of information diffusion. The seed nodes are the optimal targets to start passing messages during a disaster scenario, vaccinate to prevent the spreading of a disease or even targets for viral marketing. Finding these seed nodes is an NP-hard problem and require a significant amount of computation. One common used model in information diffusion is the \textit{independent cascade model} (ICM). ICM can be performed as a \textit{sparse matrix-vector multiplication} (SPMV). By using a application specific hardware accelerator, we can accelerate the diffusion process and consequently, the seed selection. Recently, \textit{high-level synthesis} (HLS) have been getting more attention. HLS transform high-level implementation and algorithms to low-level designs. With HLS we designed a application specific \textit{intellectual property core} (IP-core) which we then implemented on the FPGA and perform seed selection.