Title: Technology Diffusion in Communication Networks
Authors: Sharon Goldberg and Zhenming Liu
Date: November 10, 2011
Abstract:
The deployment of new technologies in the Internet is notoriously
difficult, as evidence by the myriad of well-developed networking
technologies that still have not seen widespread adoption (e.g.,
secure routing, IPv6, etc.) A key hurdle is the fact that the
Internet lacks a centralized authority that can mandate the deployment
of a new technology. Instead, the Internet consists of thousands of
nodes, each controlled by an autonomous, profit-seeking firm, that
will deploy a new networking technology only if it obtains sufficient
local utility by doing so. For the technologies we study here, local
utility depends on the set of nodes that can be reached by traversing
paths consisting only of nodes that have already deployed the new
technology.
To understand technology diffusion in the Internet, we propose a new
model inspired by work on the spread of influence in social networks.
Unlike traditional models, where a node's utility depends only its
immediate neighbors, in our model, a node can be influenced by the
actions of remote nodes. Specifically, we assume node v activates
(i.e. deploys the new technology) when it is adjacent to a
sufficiently large connected component in the subgraph induced by the
set of active nodes; namely, of size exceeding node v's threshold
value \theta(v). We are interested in the problem of choosing the
right seedset of nodes to activate initially, so that the rest of the
nodes in the network have sufficient local utility to follow suit.
We take the graph and thresholds values as input to our problem. We
show that our problem is both NP-hard and does not admit an (1-o(1)
ln|V| approximation on general graphs. Then, we restrict our study to
technology diffusion problems where (a) maximum distance between any
pair of nodes in the graph is r, and (b) there are at most \ell
possible threshold values. Our set of restrictions is quite natural,
given that (a) the Internet graph has constant diameter, and (b) the
fact that limiting the granularity of the threshold values makes sense
given the difficulty in obtaining empirical data that parameterizes
deployment costs and benefits.
We present algorithm that obtains a solution with guaranteed
approximation rate of
O(r^2 \ell \log|V|)
which is asymptotically optimal, given our hardness results. Our
approximation algorithm is a linear-programming relaxation of an 0-1
integer program along with a novel randomized rounding scheme.