Real World: Social Networks

Math for CS · Axiom Academy

LESSON Graphs in Social Networks How graph theory models friendships, influence, and community structure A social network is naturally a graph: people are vertices and relationships are edges . Facebook friendships are undirected (mutual), while Twitter follows are directed (one-way). Social graph: where = set of users and = set of connections. For undirected networks, . Real social networks are enormous. Facebook has over 3 billion users (vertices) and hundreds of billions of friendships (edges). Yet the mathematical tools of graph theory — degree, paths, components — apply at any scale. Degree and Degree Distribution The degree of a vertex is the number of edges incident to it: . In a social network, this is the number of friends or followers. Average degree: (each edge contributes to two vertices' degrees). Social networks have a power-law degree distribution : most people have few connections, but a small number of "hubs" have enormous degree. Formally: This means the network is scale-free : there is no "typical" number of friends. Celebrities may have millions of followers while most users have under 200. Stanley Milgram's 1967 experiment found that any two Americans are connected by roughly 6 intermediaries. In graph terms: Small-world property: The average shortest path length between any two vertices grows as , even though the graph is sparse.

This is the written version of the interactive lesson above. See the full Math for CS course.