Description

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

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.

Reuse Permissions
  • Downloads
    PDF (3.4 MB)

    Details

    Title
    • Influencing Busy People in a Social Network
    Contributors
    Date Created
    2016-10-06
    Resource Type
  • Text
  • Collections this item is in
    Identifier
    • Digital object identifier: 10.1371/journal.pone.0162014
    • Identifier Type
      International standard serial number
      Identifier Value
      1045-3830
    • Identifier Type
      International standard serial number
      Identifier Value
      1939-1560
    Note
    • The article is published at http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0162014

    Citation and reuse

    Cite this item

    This is a suggested citation. Consult the appropriate style guide for specific citation guidelines.

    Sarkar, K., & Sundaram, H. (2016). Influencing Busy People in a Social Network. Plos One, 11(10). doi:10.1371/journal.pone.0162014

    Machine-readable links