Technology Diffusion (Guest Post from Zhenming Liu)

My student, Zhenming Liu, writes about some of his recent work:

Sharon Goldberg and I recently submitted a paper about technology diffusion in the context of communication networks. There has been lots of work in this area in the networking literature; while networking researchers and practitioners usually know what technology they want to deploy in the network (e.g. Secure BGP, QoS, IPv6, etc.), they often don't know how to get the economically-motivated nodes in the network to adopt it. What sort of utility models could capture an economically-motivated node's decision to adopt a communication technology? Some assumptions Sharon has found in the literature (and used in her own work) include:

• A node's utility depends on the number of other nodes it can communicate with using the new technology. This is sometimes known as Metcalfe's Law.
• Two nodes can communicate with each other only if there is a path between them such that every node on the path has deployed the new technology.

Thus, unlike existing works on viral marketing in social networks -- where a node's utility function depends only on its immediate neighbors-- in our setting, node utility is non-local. We considered the following question:

Given a communication network $G(V, E)$, we assume that node $u$ activates (i.e., deploys the new technology) if it is adjacent to a connected component of active nodes in $G$ of size exceeding node $u$’s threshold $\theta(u)$. Our goal is to find an efficient algorithm that determines the smallest seedset of early adopter nodes, that once activated, causes a cascade that eventually causes all other nodes in the networks to activate as well.

We designed an approximation algorithm that returns a seedset which is at most $O(r\ell \log |V|)$ larger than the optimal seedset, where $r$ is the graph diameter and each node's threshold can take on one of at most $\ell$ possible values.

1. We seem to have the first tractable model that considers cascade effects with non-local influence in a graph; in the social network literature, the influences are local, while the networking literature considers non-local influences, but thus far has not developed any approximation algorithms.
2. Our algorithm substantially deviates from the greedy strategies we see in almost all influence maximization papers for social networks today. After reading lots of papers in this area and writing some ourselves (e.g. this and this), my colleagues and I started to suspect that a “computational dichotomy” exists among these problems: either the problem is deadly hard or greedy algorithms already work well. Our new result demonstrates that this is not the case, at least when influence is non-local.
3. Finally, our randomized algorithm makes use of a linear program, which is quite surprising because the problem seems highly non-linear; we managed to linearize the process by first carefully restricting our search space, while paying the price of only constant approximation loss.

I hope this paper will lead to more work on diffusion processes with non-local influences; studying other relevant models, or developing more efficient algorithms would both be interesting.