Influencing busy people in a social network

Kaushik Sarkar, Hari Sundaram

Research output: Contribution to journalArticlepeer-review


We identify influential early adopters in a social network, where individuals are resource constrained, to maximize the spread of multiple, costly behaviors. A solution to this problem is especially important for viral marketing. The problem of maximizing influence in a social network is challenging since it is computationally intractable. We make three contributions. First, we propose a new model of collective behavior that incorporates individual intent, knowledge of neighbors actions and resource constraints. Second, we show that the multiple behavior influence maximization is NP-hard. Furthermore, we show that the problem is submodular, implying the existence of a greedy solution that approximates the optimal solution to within a constant. However, since the greedy algorithm is expensive for large networks, we propose efficient heuristics to identify the influential individuals, including heuristics to assign behaviors to the different early adopters. We test our approach on synthetic and real-world topologies with excellent results. We evaluate the effectiveness under three metrics: unique number of participants, total number of active behaviors and network resource utilization. Our heuristics produce 15-51% increase in expected resource utilization over the naïve approach.

Original languageEnglish (US)
Article numbere0162014
JournalPloS one
Issue number10
StatePublished - Oct 2016

ASJC Scopus subject areas

  • General Biochemistry, Genetics and Molecular Biology
  • General Agricultural and Biological Sciences
  • General


Dive into the research topics of 'Influencing busy people in a social network'. Together they form a unique fingerprint.

Cite this