The anatomy of a large query graph

In this paper, we analyze the structure of a graph derived from query logs. Previous query log analysis was mostly done with just the queries and not the actions that followed after them, while the studied graph is induced by the actions of the users. A few exceptions do consider the clicks after a query, but mainly in a small or filtered query log. In this paper, we analyze a graph produced by more than twenty million queries, showing that it is less sparse than previous results suggested. We show that our graphs strongly resemble scale-free networks and that almost all the measures of these graphs are well approximated by power laws.