Rumor source identification, contagion processes, and dynamics of social network formation and evolution

Spencer, Sam W

Permalink

https://hdl.handle.net/2142/109438 Copy

Description

Title

Rumor source identification, contagion processes, and dynamics of social network formation and evolution

Author(s)

Spencer, Sam W

Issue Date

2020-12-04

Director of Research (if dissertation) or Advisor (if thesis)

Varshney, Lav

Doctoral Committee Chair(s)

Varshney, Lav

Committee Member(s)

• Srikant, R
• Beck, Carolyn
• Sundaram, Hari

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Social Networks
• Discrete Choice Models
• Rational Inattention
• Rumor Source Estimation
• Contact Tracing
• Contagion Processes
• Epidemics
• Hypergraphs

Abstract

In this dissertation, we consider two distinct, yet complementary, classes of inquiry. First we consider problems dealing with information flow, where function follows form. We look at how certain network structures affect information propagation in those networks, and what consequence that holds for inferences about such flows. We examine the problem of rumor source identification in line graphs. As the size of the infected region grows arbitrarily large, we show that unlike the single source case, where the likelihood function concentrates near the midpoint of the infected region, the support of the likelihood function in the two-source case remains widely distributed over the middle half of the infected region. This makes the rumor sources impossible to localize with high probability on any scale smaller than that of the infection size itself. We then turn our attention to a class of trees called extended star networks. We present and analyze a highly tractable approximation, the types center, to the ML source estimate using the method of types. We show empirically that this approximator is exact for some small test cases. We prove that the approximation error is at most logarithmic in the size of the infection, providing highly efficient source identification on large networks (especially compared to the accuracy in similar problems, such as the sqrt(n) best possible accuracy estimate in a line network). We also show that this estimator has different qualitative properties than rumor centrality on extended star networks. We propose a heuristic-based generalization of this approach to other types of trees, the relative-leaf counting algorithm. In simulations on regular and non-regular trees, its performance is competitive with rumor centrality (which is optimal for d-regular trees), while requiring less computation time. We also generalize that result to a class of hypertrees which, although somewhat structurally analogous, provides a much richer representation space. In particular, this approach can be used to estimate patient zero sources, even when the infection has been propagated via large group gatherings rather than person-to-person spread, and when it is spreading through interrelated social bubbles with varying degrees of overlap. In contact tracing contexts, this estimator may be used to identify the source of a local outbreak, which can then be used for forward tracing or for further backward tracing (by similar or other means) to an upstream source. Secondly, we consider problems where form follows function --- the intended goals of a self-organized network (or its constituent nodes) affect the structure that it takes on. We introduce the idea of multilayer networks consisting of awareness layers and active layers. Nodes themselves seek to build (or weight) links in active layers based on information available through their connections in awareness layers. Using simulation-based methods, along with analytical approaches where the opportunity arises, we examine the properties of generative models of such networks, using both noiseless and noisy maximization techniques, and discuss their application to discrete choice models. We then use the multinomial logit model for discrete choice to analyze a large corpus of county-to-county trade data in freight, electronics, and agricultural goods. We estimate parameters for the gravity model and price elasticity for each buyer, and show that purchasing patterns are more concentrated than would be expected, especially for buyers with many suppliers. These findings are consistent with the theory of rational inattention, and illustrate the role of information in the trade-off between market efficiency and sustainability.

Graduation Semester

2020-12

Type of Resource

Thesis

Permalink

http://hdl.handle.net/2142/109438

Copyright and License Information

Copyright 2020 Sam W. Spencer

Owning Collections