Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Efficiently Estimationg Primitive Graph Properties
Speaker:Arpit Merchant
coming from:International Institute of Information Technology Hyderabad - India
Speakers Bio:Master student
Event Type:PhD Application Talk
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Monday, 19 June 2017
Duration:90 Minutes
Building:E1 4
The ubiquity and popularity of online social networks in recent years has given rise to an increasing need to analyze their properties and learn more about their underlying structures. While it would be computationally expensive to traverse entire networks, their public interfaces allow random sampling of users. In this talk, I present a versatile, yet simple algorithm (that relies on such public APIs only) and a novel estimator for approximating the degree distribution, along with theoretical arguments explaining its correctness. I also describe experiments of our algorithm performed over a wide range of real-world data which show that it, to the best of our knowledge, significantly outperforms current methods in terms of accuracy, using storage less than 0.1% of the original network size. And lastly, I show simple variants of our algorithm that efficiently estimate related properties such as degree-wise clustering coefficients and average degree.
Name(s):imprs office team
Phone:+49 681 - 93 25 1800
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Caroline Brill/MPI-INF, 06/14/2017 01:30 PM
Last modified:
halma/MPII/DE, 03/21/2019 12:00 AM
  • Caroline Brill, 06/14/2017 01:37 PM -- Created document.