MLPR: Efficient influence maximization in linear threshold propagation model using linear programming
- PDF / 1,865,511 Bytes
- 10 Pages / 595.276 x 790.866 pts Page_size
- 48 Downloads / 150 Views
ORIGINAL ARTICLE
MLPR: Efficient influence maximization in linear threshold propagation model using linear programming Farzaneh Ghayour‑Baghbani1 · Masoud Asadpour1 · Heshaam Faili1 Received: 20 May 2020 / Revised: 19 September 2020 / Accepted: 28 October 2020 © Springer-Verlag GmbH Austria, part of Springer Nature 2020
Abstract Influence maximization is an important research topic in social networks that has different applications such as analyzing spread of rumors, interest, adoption of innovations, and feed ranking. The goal is to select a limited size subset of vertices (called a seed-set) in a Social Graph, so that upon their activation, a maximum number of vertices of the graph become activated, due to the influence of the vertices on each other. The linear threshold model is one of two classic stochastic propagation models that describe the spread of influence in a network. We present a new approach called MLPR (matrix multiplication, linear programming, randomized rounding) with linear programming used as its core in order to solve the influence maximization problem in the linear threshold model. Experiments on four real data sets have shown the efficiency of the MLPR method in solving the influence maximization problem in the linear threshold model. The spread of the output seed-sets is as large as when the state-of-the-art algorithms are used; however, unlike most of the existing algorithms, the runtime of our method is independent of the seed size and does not increase with it. Keywords Influence maximization · Linear program · Linear threshold model · Viral marketing
1 Introduction Influence maximization (IM) is one of the important problems in social network analysis which has recently attracted many researchers in different fields such as social science, computer science, economics, politics, and biology. A good example of an application of IM in real world is viral marketing (Chen et al. 2013). In viral marketing, some of the individuals are selected based on some chosen preferences and then free (or discounted) samples of a product are given to them. If the product is satisfactory enough, it is expected that the receivers of the free samples become advertisers of the product through word of mouth. It is hoped that the people in the network are indirectly influenced and thus hopefully buy the product, or become activated (we use this term hereafter). Many other applications could have similar scenarios, including the spread of rumors, stories, interest, trust, referrals, adoption of innovations in organizations, human and non-human epidemics, feed ranking, etc. * Masoud Asadpour [email protected] 1
Department of Electrical and Computer Engineering, University of Tehran, Tehran, Iran
The social network is modeled here as a directed graph in which vertices represent the individuals in the network and edges represent social relations among the vertices. We call this graph, the Social Graph. The initial set of nodes is called seed-set, and the number of activated nodes is called spread of the se
Data Loading...
