Diffusion in Random Networks: Impact of Degree Distribution

• 成果类型: Article
• 署名作者: Manshadi, Vahideh; Misra, Sidhant; Rodilitz, Scott
• 署名单位: Yale University; United States Department of Energy (DOE); Los Alamos National Laboratory
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1945
• 发表日期: 2020
• 页码: 1722-1741
• 关键词: diffusion processes; seeding; network effects

摘要

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.