Next: Data Structures for Graphs Up: Graph Algorithms Previous: Graph Algorithms

# The Friendship Graph

Figure: A portion of the friendship graph

To demonstrate the importance of proper modeling, let us consider a graph where the vertices are people, and there is an edge between two people if and only if they are friends. This graph is well-defined on any set of people, be they the people in your neighborhood, at your school or place of business, or even the entire world. There are many interesting aspects of people that are best understood as properties of this friendship graph.

We use this opportunity to define important graph theory terminology. ``Talking the talk'' proves to be an important part of ``walking the walk''.

• If I am your friend, does that mean you are my friend?

A graph is undirected if edge (x,y) always implies (y,x). Otherwise, the graph is said to be directed. The ``heard-of'' graph is directed, since many famous people who I have heard of have never heard of me! The ``had-sex-with'' graph is presumably undirected, since the critical operation always requires a partner. I'd like to think that the ``friendship'' graph is always an undirected graph.

• Am I my own friend?

An edge of the form (x,x) is said to be a loop. If x was y's friend several times over, we can model this relationship using multiedges, multiple edges between the same pair of vertices. A graph is said to be simple if it contains no loops and no multiple edges. Simple graphs really are often simpler to work with in practice. Therefore, we might be better off if no one was their own friend.

• How close a friend are you?

A graph is said to be weighted if each edge has an associated numerical attribute. We could model the strength of a friendship by associating each edge with an appropriate number, say from 0 (enemies) to 10 (blood brothers). The edges of a road network graph might be weighted with their length, drive-time, or speed limit, depending upon the application. A graph is said to be unweighted if all edges are assumed to be of equal weight.

Figure: Mel Brooks is my father's sister's husband's cousin

• Am I linked by some chain of friends to a star?

A path is a sequence of edges connecting two vertices. Since Mel Brooks is my father's sister's husband's cousin, there is a path in the friendship graph between me and him, shown in Figure . This is true even though the two of us have never met.

• How close is my link to that star?

If I were trying to impress you with how tight I am with Mel Brooks, I would be much better off saying that my Uncle Lenny grew up with him than to go into the details of how connected I am to Uncle Lenny. Through Uncle Lenny, I have a path of length 2 to Cousin Mel, while the path is of length 4 by blood and marriage. I could make the path even longer by linking in people who know both me and my father, or are friends of Aunt Eve and Uncle Lenny. This multiplicity of paths hints at why finding the shortest path between two nodes is important and instructive, even in non-transportation applications.

• Is there a path of friends between every two people in the world?

The ``six degrees of separation'' theory argues that there is always a short path linking every two people in the world. We say that a graph is connected if there is a path between any two vertices. A directed graph is strongly connected if there is always a directed path between any two vertices.

If a graph is not connected, we call each connected piece a connected component. If we envision tribes in remote parts of the world that have yet not been encountered, each such tribe would form a connected component in the friendship graph. A remote hermit, or extremely unpleasant fellow (see Figure ) would represent a connected component of one vertex, or an isolated vertex.

• Who has the most friends? The fewest friends?

The degree of a vertex is the number of edges adjacent to it. The most popular person defines the vertex of highest degree in the friendship graph. Remote hermits will be associated with degree-zero vertices. In dense graphs, most vertices have high degree, as opposed to sparse graphs with relatively few edges. In regular graphs, each vertex has exactly the same degree. A regular friendship graph would truly be the ultimate in social-ism.

• What is the largest clique?

A social clique is a group of mutual friends who all hang around together. A graph-theoretic clique is a complete subgraph, where each vertex pair has an edge between them. Cliques are the densest possible subgraphs. Within the friendship graph, we would expect to see large cliques corresponding to workplaces, neighborhoods, religious organizations, and schools.

• How long will it take for my gossip to get back to me?

A cycle is a path where the last vertex is adjacent to the first. A cycle in which no vertex repeats (such as 1-2-3-1 verus 1-2-3-2-1) is said to be simple. The shortest cycle in the graph defines the graph's girth, while a simple cycle that passes through every vertex once is said to be a Hamiltonian cycle. An undirected graph with no cycles is said to be a tree if it is connected; otherwise it is a forest. A directed graph with no directed cycles is said to be a DAG, or directed acyclic graph.

Next: Data Structures for Graphs Up: Graph Algorithms Previous: Graph Algorithms

Algorithms
Mon Jun 2 23:33:50 EDT 1997