Algorithms for influence maximization in socio-physical networks

Hemant Gehlot (), Shreyas Sundaram () and Satish V. Ukkusuri ()
Additional contact information
Hemant Gehlot: Indian Institute of Technology Kanpur
Shreyas Sundaram: Purdue University
Satish V. Ukkusuri: Purdue University

Journal of Combinatorial Optimization, 2023, vol. 45, issue 1, No 20, 28 pages

Abstract: Abstract Given a directed graph (referred to as social network), the influence maximization problem is to find k nodes which, when influenced (or activated), would maximize the number of remaining nodes that get activated under a given set of activation dynamics. In this paper, we consider a more general version of the problem that includes an additional set (or layer) of nodes that are termed as physical nodes, such that a node in the social network is connected to one physical node. A physical node exists in one of two states at any time, opened or closed, and there is a constraint on the maximum number of physical nodes that can be opened. In this setting, an inactive node in the social network becomes active if it has at least one active neighbor in the social network and if it is connected to an opened physical node. This problem arises in scenarios such as disaster recovery, where a displaced social group (an inactive social node) decides to return back after a disaster (switches to active state) only after a sufficiently large number of groups in its social network return back and some infrastructure components (physical nodes) in its neighborhood are repaired (brought to the open state). We first show that this general problem is NP-hard to approximate within any constant factor. We then consider instances of the problem when the mapping between the social nodes and the physical nodes is bijective and characterize optimal and approximation algorithms for those instances.

Keywords: Optimization algorithms; Social networks; Influence maximization; Disaster recovery (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00946-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:45:y:2023:i:1:d:10.1007_s10878-022-00946-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00946-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().