Evolutionary Approach for k-Max Influence Problem

Authors

  • Hema Banati Dyal Singh College, University of Delhi
  • Monika Bajaj Department of Computer Science, University of Delhi

Keywords:

Evolutionary Algorithm, E-Marketing, k-Max Influence Problem

Abstract

In the cut throat competitive environment of e-markets, research is currently being directed towards developing marketing strategies to promote products in minimum cost. Companies aim for maximum influence of their promotional activities at minimalistic cost. The problem of Maximizing influence spread with the limited seeding budget (k) in large network is denoted as k-Max-Influence problem and proven to be NP-Hard. Various methods have been proposed to tackle this problem. Although these methods are able to find the
best seeds but suffer from high computation cost on estimating the influence function or require global knowledge of the network. This paper explores the viability of evolutionary algorithms for this problem vis-à-vis the contemporary greedy approach. It compares two prominent evolutionary algorithms i.e. Differential Evolution (DE) and Firefly (FA) for their suitability to k-Max-Influence problem. Experimental study was conducted on Epinions, Wiki-Vote, Slashdot, NetHEPT and NetPHY datasets. The results revealed that both evolutionary approaches DE and FA perform better as compared to Greedy approach with respect to maximum influence incurred as well as gain achieved by increasing the value of k. Amongst the evolutionary approaches FA outperform DE in all cases. The results show that FA maintains the consistency in its results and has higher probability to score over DE and Greedy.

Downloads

Download data is not yet available.

Downloads

Published

2013-04-01

How to Cite

Hema Banati, & Monika Bajaj. (2013). Evolutionary Approach for k-Max Influence Problem. Journal of Network and Innovative Computing, 1, 10. Retrieved from https://cspub-jnic.org/index.php/jnic/article/view/26

Issue

Vol. 1 (2013)

Section

Original Article

License

You are free to:

  1. Share — copy and redistribute the material in any medium or format for any purpose, even commercially.
  2. Adapt — remix, transform, and build upon the material for any purpose, even commercially.
  3. The licensor cannot revoke these freedoms as long as you follow the license terms.

Under the following terms:

  1. Attribution — You must give appropriate credit , provide a link to the license, and indicate if changes were made . You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
  2. No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.

Notices:

You do not have to comply with the license for elements of the material in the public domain or where your use is permitted by an applicable exception or limitation .

No warranties are given. The license may not give you all of the permissions necessary for your intended use. For example, other rights such as publicity, privacy, or moral rights may limit how you use the material.