Symposium 2013

*Abstract*

In this talk I will discuss the problem of finding top k nodes with the largest degrees in very large on-line networks. If the adjacency list of the network is known (which is not the case, for example,in the Twitter follower graph), a deterministic algorithm to find the top k list of nodes with the largest degrees requires an average complexity of O(n), where n is the number of nodes in the network. Even this modest complexity can be very high for large complex networks such as We or Twitter. Instead, I will introduce randomized Monte Carlo methods, and show theoretically and by numerical experiments that these algorithms find good quality top lists of nodes with high probability and with computational savings of orders of magnitude. I will also quickly discuss a current research on prediction of trends in social media based on the network data, for example, the structure and dynamics of retweet graphs.