IDEAS home Printed from https://ideas.repec.org/a/wsi/ijmpcx/v32y2021i06ns0129183121500790.html
   My bibliography  Save this article

A sequential seed scheduling heuristic based on determinate and latent margin for influence maximization problem with limited budget

Author

Listed:
  • Jianxin Tang

    (School of Computer and Communication, Lanzhou University of Technology, Lanzhou, Gansu 730050, P. R. China)

  • Fuqing Zhao

    (School of Computer and Communication, Lanzhou University of Technology, Lanzhou, Gansu 730050, P. R. China)

  • Ruisheng Zhang

    (#x2020;School of Information Science and Engineering, Lanzhou University Lanzhou, Gansu 730000, P. R. China)

  • Baoqiang Chai

    (#x2020;School of Information Science and Engineering, Lanzhou University Lanzhou, Gansu 730000, P. R. China)

  • Shilu Di

    (School of Computer and Communication, Lanzhou University of Technology, Lanzhou, Gansu 730050, P. R. China)

Abstract

The influence maximization problem in social networks aims to select a subset of most influential nodes, denoted as seed set, to maximize the influence diffusion of the seed nodes. The majority of existing works on this problem would ignite all the seed nodes simultaneously at the beginning of the diffusion process and let the influence diffuses passively in the network. However, it cannot depict the practical dynamics exactly of viral marketing campaigns in reality and fails to provide driving policies to control over the diffusion. In this paper, we focus on the dynamic influence maximization problem with limited budget to study the scheduling strategies including which influential node is to be seeded during the diffusion process and when to seed it at the right time. A time-dependent seed activating feedback scheme is modeled firstly by considering the time factor and its impact on the influence obligation in diffusion process. Then a scheduling heuristic based on determinate and latent margin is proposed to evaluate the marginal return of candidate nodes and activate the right seed node to promote the viral marketing. Extensive experiments on four social networks show that the proposed algorithm achieves significantly better results than a typical static influence maximization algorithm based on swarm intelligence and can improve the influence propagation under the time-dependent diffusion model comparing with the centrality-based scheduling heuristics.

Suggested Citation

  • Jianxin Tang & Fuqing Zhao & Ruisheng Zhang & Baoqiang Chai & Shilu Di, 2021. "A sequential seed scheduling heuristic based on determinate and latent margin for influence maximization problem with limited budget," International Journal of Modern Physics C (IJMPC), World Scientific Publishing Co. Pte. Ltd., vol. 32(06), pages 1-18, June.
  • Handle: RePEc:wsi:ijmpcx:v:32:y:2021:i:06:n:s0129183121500790
    DOI: 10.1142/S0129183121500790
    as

    Download full text from publisher

    File URL: http://www.worldscientific.com/doi/abs/10.1142/S0129183121500790
    Download Restriction: Access to full text is restricted to subscribers

    File URL: https://libkey.io/10.1142/S0129183121500790?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wsi:ijmpcx:v:32:y:2021:i:06:n:s0129183121500790. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Tai Tone Lim (email available below). General contact details of provider: http://www.worldscinet.com/ijmpc/ijmpc.shtml .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.