B1594
Title: Exploration-driven networks
Authors: Sayan Banerjee - University of North Carolina, Chapel Hill (United States) [presenting]
Shankar Bhamidi - University of North Carolina at Chapel Hill (United States)
Xiangying Huang - University of North Carolina at Chapel Hill (United States)
Abstract: The aim is to propose and investigate a class of random networks where incoming vertices locally traverse the network in the direction of the root for a random number of steps before attaching to the terminal vertex. Specific instances of these networks correspond to uniform attachment, linear preferential attachment and attachment with probability proportional to vertex Page-ranks. Local weak limits are obtained for such networks and are used to derive asymptotics for the limiting empirical degree and PageRank distribution. Asymptotics are also quantified 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. A non-trivial phase transition phenomenon is also displayed for the PageRank distribution, which connects to the well-known power-law hypothesis.
