Computing distance, part one

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:

 0Node 9 is the source--the only node that starts with the meme
 1All nodes adjacent to 9 -- nodes 1, 3, and 8 -- receive the meme next. These nodes are distance 1 from source node 9.
 2All 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.
 3All 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.
 4

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.

 

 

 

 
Joomla Templates by Joomlashack