Lecture

Facebook Social Graph: Structure and Small-World Phenomenon

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

DH-500: Computational Social Media

The course integrates concepts from media studies, machine learning, multimedia, and network science to characterize social practices and analyze content in platforms like Twitter/X, Instagram, YouTube, and TikTok. Students will learn computational methods ...

Description

This lecture explores the structure of the Facebook social graph, discussing the small-world phenomenon and the concept of four degrees of separation. It delves into Stanley Milgram's small-world experiment, the average number of friends on Facebook, and homophily in user connections. The presentation also covers the methodology to understand Facebook users, graph models, path lengths, and the connectivity within the platform. It concludes with insights on the shrinking degrees of separation over time and the homophily trend among users.

Instructor

Daniel Gatica-Perez

Expertise Social computing, social media, ubiquitous computing, crowdsourcing, machine learning. Current work My research integrates theories and methods from ubiquitous computing, social media, machine learning, and social sciences to understand human behavior in daily life and to create applications for social good.My current research interests include:* Mobile crowdsourcing and social media analytics for social good.* Crowdsourcing for cities.* Social video analytics, with focus on conversational behavio

Official source

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related concepts (23)

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network. In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v.

Glossary of graph theory

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

Path (graph theory)

In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges). A directed path (sometimes called dipath) in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction. Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts.

Vertex (graph theory)

In discrete mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices). In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another.

Related lectures (34)

Facebook Research: User Analysis, Motivations, Identity, and Privacy

Covers Facebook research on user analysis, motivations, identity, and privacy.

Fixed Points in Graph Theory

Focuses on fixed points in graph theory and their implications in algorithms and analysis.

Linear Transformations: Matrices and Kernels

Covers linear transformations, matrices, kernels, and properties of invertible matrices.

Neural Signals and Connectomes

Explores neural signals, connectomes, graph theory, and multi-voxel pattern analysis in fMRI trials.

Graph Models and Brain Connectomics

Explores graph theory in brain connectomics, MRI applications, network analysis relevance, and individual fingerprinting.