dc.description.abstract |
<p>Networks -- abstract objects composed of \emph{vertices} connected by \emph{edges},
are ubiquitous in the real world. </p><p>Examples such as social networks, the world
wide web, and neural networks in the brain</p><p>are constantly evolving in their
topology, the state of their vertices, or a combination of the two.</p><p>This dissertation
presents a computational and theoretical study of three models of network dynamics,
one corresponding to each of these modes of evolution.</p><p>The first study models
the disintegration of a social network of voters with binary opinions, who prefer
to be connected to others with the same opinion. </p><p>We study two versions of the
model: the network evolves by voters in discordant ties choosing to either </p><p>adopt
the opinion of their neighbors, or to rewire their ties to some randomly chosen voter
of (i) the same, or (ii) any, opinion. </p><p>We examine how the probability of rewiring,
and the initial fraction $\rho_{\textrm{i}}$ in the minority, </p><p>determine the
final minority fraction $\rho_{\textrm{f}}$, when the network has bifurcated. </p><p>In
case (i), there is a critical probability, that is independent of $\rho_{\textrm{i}}$,
above which $\rho_{\textrm{f}}$ is unchanged from $\rho_{\textrm{i}}$, </p><p>and
below which there is full concensus. </p><p>In case (ii), the behavior above the critical
probability, that now depends on $\rho_{\textrm{i}}$, is similar; but </p><p>below
it, $\rho_{\textrm{f}}$ matches the result of starting with $\rho_{\textrm{i}} = 1/2$.
Using simulations and approximate calculations, we explain why these two nearly identical
</p><p>models have such dramatically different behaviors.</p><p>The second model,
called the \emph{quadratic contact process} (QCP) involves ``birth'' and ``death''
events on a static network. </p><p>Vertices take on the binary states occupied(1)
or vacant(0). </p><p>We consider two versions of the model -- Vertex QCP, and Edge
QCP, corresponding to </p><p>birth events $1-0-1 \longrightarrow 1-1-1$ and $1-1-0
\longrightarrow</p><p>1-1-1$ respectively, where `$-$' represents an edge. </p><p>We
study the fraction of occupied vertices at steady state as a function of the birth
rate, keeping </p><p>the death rate constant. To investigate the effects </p><p>of
network topology, we study the QCP on homogeneous networks with a bounded or rapidly
decaying degree distribution, </p><p>and those with a heavy tailed degree distribution.
</p><p>From our simulation results and mean field calculations, we conclude </p><p>that
on the homogeneous networks, there is a discontinuous phase transition with a</p><p>region
of bistability, whereas on the heavy tailed networks, the</p><p>transition is continuous.
Furthermore, the critical birth rate is positive </p><p>in the former but zero in
the latter.</p><p>In the third study, we propose a general scheme for spatial networks
evolving in order to reduce their total edge lengths. </p><p>We study the properties
of the </p><p>equilbria of two networks from this class, one of which interpolate
between two well studied objects: the Erd\H{o}s-R\'{e}nyi random graph, and the random
geometric graph. </p><p>The first of our two evolutions can be used as a model for
a social network where individuals have fixed opinions about a number of issues and
adjust their ties to be connected to people with similar views. </p><p>The second
evolution which preserves the connectivity of the network has potential applications
in the design of transportation networks and other distribution systems.</p>
|
|