Seminar
| Parent Program: | |
|---|---|
| Location: | SLMath: Eisenbud Auditorium, Online/Virtual |
Uncovering the past: network archaeology in growing random networks
Growing networks are present all around us (in the internet, social networks, biology , social sciences etc). A very natural family of question arise if one is interested in the sequence of events leading to the present day network: what chain of events led to this structure. More precisely, if no time labels are observed, one can wonder which were the first few vertices in the network? In which order did the following vertices appear? These questions have been studied in numerous papers in the last decade, mostly focused on retrieving the first vertex in trees. After an overview of some of the known results I will present results extending network archaeology techniques in two directions: first, techniques to retrieve the root in graphs (as opposed to trees) as well as result looking beyond the first vertex but estimating an ordering for the whole tree. I will then mention an ongoing project where I hope to prove the root-finding algorithm developed for graphs is "robust" in the sense that is has performance guarantees for a whole family of network attachment procedures (containing preferential attachment and some of its variations).
No Notes/Supplements Uploaded