Sayan Banerjee (UNC)
Title: Persistence and root detection algorithms in growing networks
Abstract: Motivated by questions in Network Archaeology, we investigate statistics of dynamic networks that are persistent, that is, they fixate almost surely after some random time as the network grows. We consider generalized attachment models of network growth where at each time n, an incoming vertex attaches itself to the network through m n edges attached one-by-one to existing vertices with probability proportional to an arbitrary function f of their degree. We identify the class of attachment functions f for which the maximal degree vertex persists and obtain asymptotics for its index when it does not. We also show that for tree networks, the centroid of the tree persists and use it to device polynomial time root finding algorithms and quantify their efficacy. Our methods rely on an interplay between dynamic random networks and their continuous time embeddings.
This is joint work with Shankar Bhamidi.
Link:
Meeting ID: 970 9325 9428
Passcode: problab