Diffusion in Random Networks: Impact of Degree Distribution

Vahideh Manshadi (), Sidhant Misra () and Scott Rodilitz ()
Additional contact information
Vahideh Manshadi: Yale School of Management, New Haven, Connecticut 06511
Sidhant Misra: Los Alamos National Laboratory, Santa Fe, New Mexico 87545
Scott Rodilitz: Yale School of Management, New Haven, Connecticut 06511

Operations Research, 2020, vol. 68, issue 6, 1722-1741

Abstract: Motivated by viral marketing on social networks, we study the diffusion process of a new product on a network where each agent is connected to a random subset of others. The number of contacts (i.e., degree) varies across agents, and the firm knows the degree of each agent. Further, the firm can seed a fraction of the population and incurs a fixed cost per contact. Under any bounded degree distribution and for any target adoption proportion, we compute both the cost and the time it takes to reach the target in the limit of network size. Our characterization of the diffusion process in such a general setting is the first of its kind for a problem that is generally deemed intractable and solved using approximation methods such as mean-field. Our solution indicates that the degree distribution impacts the diffusion process even beyond its first and second moments. Using our limit results, we conduct comparative statics on degree distribution and uncover a trade-off between cost-efficiency and fast growth. Fixing the average degree, a minimum-variance degree distribution incurs the minimum cost to reach any adoption proportion. On the other hand, higher variance results in faster growth for low or moderately high target adoption proportions, but it incurs higher cost. This trade-off arises partly because of an endogenous effect of diffusion on the distribution of adopters’ neighbors: as the diffusion progresses, adopters become more likely to be connected to other adopters. This highlights the benefit of our exact analysis compared to mean-field approximation methods that rely on perfect mixing of adopters and non-adopters (i.e., there is no change in the distribution of adopters’ neighbors with the progress of diffusion). Further, we study the impact of the degree distribution on optimal seeding strategies for a given seeding budget. Somewhat surprisingly, we show that to minimize cost, it is optimal to seed low-degree agents. Even if the objective is to minimize time, for certain regimes, the optimal seeding strategy is a mixture of low- and high-degree agents.

Keywords: diffusion processes; seeding; network effects (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1945 (application/pdf)

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:inm:oropre:v:68:y:2020:i:6:p:1722-1741

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().