Event
Mariana Olvera-Cravioto - Directed complex networks and ranking algorithms
Monday, April 10

3108 Etcheverry Hall, 3:30 p.m. - 5:00 p.m.

Abstract: In the first part of this talk I will discuss a family of inhomogeneous directed random graphs for modeling complex networks such as the web graph, Twitter, ResearchGate, and other social networks. This class of graphs includes as a special case the classical Erdos-Renyi model, and can be used to replicate almost any type of predetermined degree distributions, in particular, power-law degrees such as those observed in most real-world networks. I will mention during the talk the main properties of this family of random graphs and explain how its parameters can be used to represent important data attributes that influence the connectivity of nodes in the network. 

In the second part of the talk I will explain how ranking algorithms such as Google’s PageRank can be used to identify highly influential nodes in a network, and present some recent results describing the distribution of the ranks computed by such algorithms. This work extends prior work done for the directed configuration model to the new class of inhomogeneous directed random graphs mentioned above, and provides a more natural way to model the relationship between highly ranked nodes and their attributes. If time allows, I will mention some interesting stochastic simulation challenges related to this problem. 

Bio: Mariana Olvera-Cravioto is a Visiting Associate Professor in the Department of Industrial Engineering and Operations Research at UC Berkeley. She does research in Applied Probability, in particular, she works on problems involving heavy-tailed phenomena. Her current work is focused on the analysis of information ranking algorithms and their large-scale behavior, which is closely related to the study of the solutions to certain stochastic recursions constructed on weighted branching processes. She is also interested in the analysis of complex networks, in particular, scale-free random graphs such as those used to model the web and other social networks. Some of her ongoing projects include the study of queueing networks with parallel servers and synchronization constraints and the development of efficient simulation algorithms for computing the solutions to branching distributional equations.