  There has been significant interest in the networking community on the impact
of cascade effects on the diffusion of networking technology upgrades in the
Internet. Thinking of the global Internet as a graph, where each node
represents an economically-motivated Internet Service Provider (ISP), a key
problem is to determine the smallest set of nodes that can trigger a cascade
that causes every other node in the graph to adopt the protocol. We design the
first approximation algorithm with a provable performance guarantee for this
problem, in a model that captures the following key issue: a node's decision to
upgrade should be influenced by the decisions of the remote nodes it wishes to
communicate with.
  Given an internetwork G(V,E) and threshold function \theta, we assume that
node $u$ activates (upgrades to the new technology) when it is adjacent to a
connected component of active nodes in G of size exceeding node $u$'s threshold
\theta(u). Our objective is to choose the smallest set of nodes that can cause
the rest of the graph to activate. Our main contribution is an approximation
algorithm based on linear programming, which we complement with computational
hardness results and a near-optimum integrality gap. Our algorithm, which does
not rely on submodular optimization techniques, also highlights the substantial
algorithmic difference between our problem and similar questions studied in the
context of social networks.
