Master student

AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI   Info

Public Audience

English

90 Minutes

Saarbrücken

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.

imprs office team

+49 681 - 93 25 1800

--email hidden

passcode not visible

logged in users only