Technology Diffusion in Communication Networks

Details Technology Diffusion in Communication Networks Technology Diffusion in Communication Networks

2012-02-14

arxiv.org/abs/1202.2928v2

Computer Science

Social and Information Networks

Scientific paper

In the rich and growing literature on diffusion and cascade effects in social networks, it is assumed that a node's actions are influenced only by its immediate neighbors in the social network. However, there are other contexts in which this highly-local view of influence is not applicable. The diffusion of technologies in communication networks is one important example; here, a node's actions should also be influenced by remote nodes that it can communicate with using the new technology. We propose a new model of technology diffusion inspired by the networking literature on this topic. Given the communication network $G(V,E)$, we assume that node $u$ activates (i.e. deploys 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)$. We focus on an algorithmic problem that is well understood in the context of social networks, but thus far has only heuristic solutions in the context of communication networks: determining the smallest seedset of early adopter nodes, that once activated, cause a cascade that eventually causes all other nodes in the network to activate as well. Our main result is a near-optimal approximation algorithm that returns a seedset that is an $O(r\ell \log|V|)$-factor larger than then the optimal seedset, where $r$ is the graph diameter and each node's threshold can take on one of at most $\ell$ possible values. Our results highlight the substantial algorithmic difference between our problem and the work in diffusion on social networks.

Affiliated with

Also associated with

No associations

Rating

Technology Diffusion in Communication Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Technology Diffusion in Communication Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Technology Diffusion in Communication Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-88618