STOR Colloquium: Mariana Olvera-Cravioto, University of California-Berkeley

Directed complex networks and ranking algorithms

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.

Refreshments will be served in the lounge area of Hanes Hall