Webwhompers

Given an undirected graph G=(V,E), we previously defined the distance between two nodes x and y as the length of a shortest path in G from x to y. Now we describe how to compute this value.

Computing distance in a graph relates to several important topics in Web science:

• Information diffusion: how does information spread over time through a population of Web users?
• Packet routing: how is a discrete piece of information transmitted between two computers via the Internet?
• Network navigation: how does one explore the connections in a network? (See "broadcast search" and "directed search" in Six Degrees for more on this.)

Computing distance in a graph is also very closely related to computing shortest paths in a graph. Finding shortest paths is a fundamental problem in computer science that is traditionally solved with breadth-first search. Our distance algorithm is a slightly simplified version of breadth-first search.

We motivate our distance algorithm with the following scenario:

1. Suppose m is a meme that is 100% contagious: any person with m will immediately share it with everyone adjacent to him.
2. Furthermore, m never changes: any person who has previously received m will forever more recognize it and be immune. (I.e., the sharing only happens the first time a person receives m.)
3. The set of people and the connections joining them do not change.
4. One person--the source--has m, and every other person does not have m.

Given the above scenario, who will receive meme m from whom, and how many steps will it take for m to reach each person in the network? Answering these questions drives the distance algorithm.

Example:

	Node 9 is the source--the only node that starts with the meme
	All nodes adjacent to 9 -- nodes 1, 3, and 8 -- receive the meme next. These nodes are distance 1 from source node 9.
	All nodes that are adjacent to 1, 3, or 8 and that have not already received the meme are next. These nodes -- 2 and 10 -- are distance 2 from source node 9.
	All nodes that are adjacent to 2 or 10 and that have not already received the meme are next. These nodes -- 5, 6, and 7 -- are distance 3 from source node 9.
	All nodes that are adjacent to 5, 6, or 7 and that have not already received the meme are next. There is one such node -- 4 -- which is distance 4 from source node 9.