Human Wayfinding in Information Networks. West, Leskovec. WWW 2012.


  1. How do people navigate information spaces?
  2. People have to find a path between topics through wikipedia links
  3. 30,000 trajectories, from 10k users
  4. “We find that human wayfinding, while mostly very efficient, differs from shortest paths in characteristic ways.  Most subjects navigate through high-degree hubs in the early phase, while their search is guided by content features thereafter.”
  5. A couple of things to consider:
    1. Do people switch between strategies?
    2. May be that safer, more reliable modes of search are slower on average than other modes that may either produce a very short path, or lead not lead to the solution – sometimes ‘out of the box’ thinking leads to short connections but it also may be fruitless
  6. Also, can you model where someone will go next with only information up to the current step in the trajectory?
  7. Based on existing online game wikispeedia
  8. “back” button in browser is allowed
  9. On average, human trajectories are only 1-click longer than median optimal solution
    1. This is possible because of the nature of the network; a few high-degree hubs means everything is connected in a pretty short path, has “small-world” property (median shortest path length is only 3, mean is about the same)
  10. On average, people click back once per trajectory, also average drop out rate of 10% per step, pretty independent of how long the current trajectory was
  11. Earlier results show that theoretically, short path lengths are expected “if the probability of a node linking to its r-th closest fellow node decays as 1/r.”  This is basically borne out
  12. Empirical analysis considers problems that have optimal path-length of 3
  13.  “Making progress is easiest far from and close to the target.”  That is, clicks in the middle of navigation are less likely to actually make progress of getting you to the goal more quickly
    1. In the beginning, get to a hub, rapidly gets you closer (shorter paths go through bigger hubs)
  14. “Conceptual distance to the target decreases steadily”
  15. “Clicks are most predictable far from and close to the target.”
  16. Similarity dominates decision making earlier (over degree, which is otherwise used earlier and then transfers to similarity) on more successful, shorter paths
  17. Go into some more depth in how strategies depend on particular aspects of target that a person knows
    1. They mostly try to get in, and stay in the obvious topic, but sometimes other strategies are commonly used depending on the particular topic
  18. Then they move on to how to predict where a person would click next
    1. A “Human Markov Model”, and a few others
    2. Based on hand-designed, but sensible features
  19. After observing a couple of clicks, the best model is accurate 80% of the time for all subsequent clicks
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: