Spreading Influence in Social Networks
with Time Constraints

In a social network, agents change their behaviours and opinions on the basis of information collected from their neighbours. Generally, recent information is more influential than older information, and information that is received in a short period of time is more influential than information received during a long period of time. An example of this phenomenon is consumer reviews on websites such as Amazon. Another example is viral marketing which attempts to influence consumer adoption of products. A third example is recent communication strategies of politicians.

In this talk, I will present a graph-based model of the spread of influence in networks that generalizes previous research by including temporal information. The goal is to identify a small set of nodes that eventually influences all nodes in the graph with the restriction that influence only lasts for a bounded time interval. The problem for general graphs is computationally difficult even for approximate solutions. The talk will focus on efficient algorithms for restricted families of graphs: paths, rings, trees, and complete graphs.