|dc.description.abstract||With online social networks such as Facebook and Twitter becoming globally popular, there is renewed interest in understanding the structural and dynamical properties of social networks. In this thesis we study several stochastic models arising in the context of the spread of inﬂuence or information in social networks. Our objective is to provide compact and accurate quantitative descriptions of the spread processes, to understand the eﬀects of various system parameters, and to design policies for the control of such diﬀusions.
One of the well established models for inﬂuence spread in social networks is the threshold model. An individual’s threshold indicates the minimum level of “inﬂuence” that must be exerted, by other members of the population engaged in some activity, before the individual will join the activity. We begin with the well-known Linear Threshold (LT) model introduced by Kempe et al. . We analytically characterize the expected inﬂuence for a given initial set under the LT model, and provide an equivalent interpretation in terms of acyclic path probabilities in a Markov chain. We derive explicit optimal initial sets for some simple networks and also study the eﬀectiveness of the Pagerank  algorithm for the problem of inﬂuence maximization. Using insights from our analytical characterization, we then propose a computationally eﬃcient G1-sieving algorithm for inﬂuence maximization and show that it performs on par with the greedy algorithm, through experiments on a coauthorship dataset.
The Markov chain characterisation gives only limited insights into the dynamics of inﬂuence spread and the eﬀects of the various parameters. We next provide such insights in a restricted setting, namely that of a homogeneous version of the LT model but with a general threshold distribution, by taking the ﬂuid limit of a probabilistically scaled version of the spread Markov process. We observe that the threshold distribution features in the ﬂuid limit via its hazard function. We study the eﬀect of various threshold distributions and show that the inﬂuence evolution can exhibit qualitatively diﬀerent behaviors, depending on the threshold distribution, even in a homogeneous setting. We show that under the exponential threshold distribution, the LT model becomes equivalent to the SIR (Susceptible-Infected-Recovered) epidemic model . We also show how our approach is easily amenable to networks with heterogeneous community structures.
Hundreds of millions of people today interact with social networks via their mobile devices. If the peer-to-peer radios on such devices are used, then inﬂuence spread and information spread can take place opportunistically when pairs of such devices come in proximity. In this context, we develop a framework for content delivery in mobile opportunistic networks with joint evolution of content popularity and availability. We model the evolution of inﬂuence and content spread using a multi-layer controlled epidemic model, and, using the monotonicity properties of the o.d.e.s, prove that a time-threshold policy for copying to relay nodes is delay-cost optimal.
Information spread occurs seldom in isolation on online social networks. Several contents might spread simultaneously, competing for the common resource of user attention. Hence, we turn our attention to the study of competition between content creators for a common population, across multiple social networks, as a non-cooperative game. We characterize the best response function, and observe that it has a threshold structure. We obtain the Nash equilibria and study the eﬀect of cost parameters on the equilibrium budget allocation by the content creators. Another key aspect to capturing competition between contents, is to understand how a single end-user receives and processes content. Most social networks’ interface involves a timeline, a reverse chronological list of contents displayed to the user, similar to an email inbox. We study competition between content creators for visibility on a social network user’s timeline. We study a non-cooperative game among content creators over timelines of ﬁxed size, show that the equilibrium rate of operation under a symmetric setting, exhibits a non-monotonic behavior with increasing number of players. We then consider timelines of inﬁnite size, along with a behavioral model for user’s scanning behavior, while also accounting for variability in quality (inﬂuence weight) among content creators. We obtain integral equations, that capture the evolution of average inﬂuence of competing contents on a social network user’s timeline, and study various content competition formulations involving quality and quantity.||en_US