Type

Text

Type

Dissertation

Advisor

Skiena, Steven | Gao, Jie. | Bender, Michael A. | Jones, Jason.

Date

2017-08-01

Keywords

Complex Contagions | Computer science | Contagions | Preferential Attachment Network | Small World Networks | Social Networks | Stochastic Processes

Department

Department of Computer Science.

Language

en_US

Source

This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree

Identifier

http://hdl.handle.net/11401/78133

Publisher

The Graduate School, Stony Brook University: Stony Brook, NY.

Format

application/pdf

Abstract

Social behavior changes manifest contagion-like properties similar to epidemic diseases and rumors when they spread in socio-economic networks. While the spread of disease and information has been the subject of numerous research studies in different disciplines of science for decades, only recently the spread of behavior changes has seen attention as a research topic. Some of these behavior changes are beneficial/profitable (adopting a healthy lifestyle), while some others are destructive/undesirable (teenage smoking). In order to effectively promote desirable behavior changes and discourage undesirable ones, the first step is to understand how they spread in social networks. This dissertation studies \emph{complex contagions}, a family of models that characterize the spread of behavior changes as contagions that requires social reaffirmation from multiple contacts. Three main approaches are pursued: theoretical analysis of proposed models, simulation verifications and data-driven investigations. A family of general characterization theorems on the conditions under which complex contagions spread wide and fast is given. These characterizations theorems are further confirmed and verified through simulations and data analyses. The theoretical characterization considers two models of complex contagions. In the \emph{$k$-complex contagion model}, a network node adopts the contagion when at least $k$ of its neighbors/contacts have already adopted it. In the \emph{general threshold model}, the required number of adopted neighbors may differ from node to node. A collection of social network topologies such as small-world networks (Newman-Watts and Kleinberg's models), time-evolving networks (Preferential Attachment models) and our newly proposed \emph{Stochastic Attachment Network}. These analyses cover various aspects in the spread of complex contagions including their extent (whether the contagion covers the entire underlying network), speed (how fast/slow the contagion spreads), the role of early adopters (random or a fixed set of nodes), and the critical properties (degree distribution, distribution of edges) of the underlying social network model. Given a set of early adopters and an instance of the social network, it is proved that computing the extent of a $k$-complex contagion is $\Po$-complete. This means that categorizing the sufficient conditions for a $k$-complex contagion to cover a social network in general is impossible and the best one can do is to simulate the process. The data-driven analyses on the speed and extent of a complex contagion (under both contagion models) over the DBLP co-authorship network and the Stanford web network, have shown that our new proposed ``Stochastic Attachment Network'' model can capture the real world behavior of the complex contagion much better than the Configuration Model. | 155 pages

Download

Share

COinS