This is a gentle reminder that the next OWPS will be today from 15:00 to 17:00 CEST time. There will be two talks on the topic of exploration driven analysis of random graphs. The talks will touch upon general techniques and specific applications of these techniques.

Title, abstract and the zoom link are below the signature and can be found on the website https://www.owprobability.org/one-world-probability-seminar.

-----------------------

Talk 1 : Mariana Olvera-Cravioto, University of North Carolina at Chapel Hill

Local limits and preferential attachment graphs

This talk is meant to provide an overview of local weak convergence techniques for a large class of directed random graphs, including static models such as the Erdos-Renyi, Chung-Lu, stochastic block model, and configuration models, as well as dynamic models such as the collapsed branching process and the directed preferential attachment graph. We explain how local limits can be used to study important structural graph properties, including centrality measures such as the PageRank distribution. We further use the insights obtained from our analysis of centrality measures to explain how static models and evolving models differ in how large degree vertices are distributed within the graph and how they shape their neighborhoods. In particular, we show that the empirically accepted “power-law hypothesis” on scale-free graphs, which states that the PageRank distribution follows a power-law with the same tail index as the in-degree distribution,  holds in most static models but not in the dynamic models we study.

This is joint work with: Sayan Banerjee and Prabhanka Deka.

Talk 2 : Sayan Banerjee, University of North Carolina at Chapel Hill

Exploration-driven networks

We propose and investigate a class of random networks where incoming vertices locally explore the graph before attaching to an existing vertex. Specific instances of these networks correspond to uniform attachment, linear preferential attachment and attachment with probability proportional to vertex PageRanks. We obtain local weak limits for such networks and use them to derive asymptotics for the limiting empirical degree and PageRank distribution. We also quantify asymptotics for the degree and PageRank of fixed vertices, including the root, and the height of the network. Two distinct regimes are seen to emerge, based on the expected exploration distance of incoming vertices, which we call the ‘fringe’ and ‘non-fringe’ regimes. These regimes are shown to exhibit different qualitative and quantitative properties. In particular, networks in the non-fringe regime undergo ‘condensation’ where the root degree grows at the same rate as the network size. Networks in the fringe regime do not exhibit condensation. Interesting phase transition phenomena are exhibited for the height of the tree and the limiting PageRank distribution. The latter connects to the well-known power-law hypothesis and the proposed class of models `interpolate’ between the PageRank behavior of static and dynamic graphs discussed in Mariana’s talk.

Based on joint works with Mariana Olvera-Cravioto, Shankar Bhamidi and Xiangying (Zoe) Huang.

Zoom-link: https://zoom.us/j/3766827761

Meeting ID: 376 682 7761

Passcode: sPNKq1