Speaker: Desmond J Higham, University of Strathclyde
Title: Models and Algorithms for Dynamic Networks
The digital revolution is generating novel large scale examples of connectivity patterns that change over time. This scenario may be formalized as a graph with a fixed set of nodes whose edges switch on and off. For example, the data may describe interacting mobile phone users, emailers, on-line chat room participants, Facebookers or Tweeters. Time-dependent correlations between brain regions during the execution of a functional task is another high profile example. To model and simulate the key properties of such evolving networks, we can use a discrete time Markov chain setting, where edges appear and disappear according to appropriate probabilistic laws. In this way, we can generalize some of the classic `static' models that have been successful in network science. In particular, I will propose and analyse a natural `triad-closure' mechanism that quantifies effects observed in social network analysis---new friendships are more likely between individuals who share current friends. I will also discuss computational algorithms that quantify the `centrality' of a node in this time-dependent setting. Illustrations involving real data sets will be given.