Title: Technology Diffusion on Spiders
|Affiliation:||University of Waterloo|
In the rich literature on diffusion and cascade effects in social networks, a node’s actions are assumed to be influenced only by its neighbours. This highly-localized view of influence is not applicable in all contexts. 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.
Motivated by such cascade effects arising in network technology upgrade processes in the Internet, Goldberg and Liu (2013) introduced the following technology diffusion problem. Given a graph, and a threshold function on all nodes, a vertex activates if it is adjacent to a connected component of active nodes of size at least its threshold value. The goal is to find a subset of nodes whose initial activation would trigger a cascade activating the entire graph.
This talk will describe exact algorithms and polyhedral characterizations for both the seed minimization, and the influence maximization versions of the technology diffusion problem on spiders and cycles.
Joint work with Laura Sanita.