Excess degree, degree distributions and the friendship paradox (NC6-1)
Channel: Complexity Papers
Date: 19/04/2024

This is part 1 of lecture 6 in the Networks and Complexity course. In this video we discuss the friendship paradox and discover how to compute a networks degree distribution and the mean excess degree. 

SOURCES 
- Facebook analysis: Johan Ugander et al.: arxiv:1111.4503, 2011 https://arxiv.org/abs/1111.4503
- Markettville Girls: SL Feld Am. J. Soc. 96, 1464, 1991, based on JS Coleman "The adolescent society", Free Press (New York).
- Origin of excess degree: M. E. J. Newman, Assortative mixing in networks, Physical Review Letters, 89 (2002), p. 208701.

FURTHER MATERIAL
- This course will be published as a book with Springer (It's not out yet)
- Additional exercises and solutions (will be available eventually)

OTHER LECTURES IN THIS COURSE 
01 - https://youtu.be/AriHQz6x3uY - Brute force, number of networks, Minimum spanning tree, greedy algorithms 
02 - https://youtu.be/LDKjs_t7oUk - Shortest path, branch and bound, Dijkstra's algorithm 
03 - https://youtu.be/Mnaf2Y_ydq8 - Königsberg bridge problem, Trial & Error, Chinese Postman, Hierholzers algorithm
04 - COMING SOON
05 - https://youtu.be/8Q5kUlGxe6g - The small world, diameter of network, organizing principles, clustering coefficient
06 - This Video  
10 - https://youtu.be/5pAILvyFoNw - Attacks on Networks, robustness, vaccinations and infrastructure resilience

CONTENTS
00:00 Introduction
00:46 Introductory examples
04:23 Mean degree
08:48Excess degree distribution
15:29 Mean excess degree computation
16:44 Mean excess degree in context
18:05 Facebook
20:44 End