# Identify search strategy over network

Imagine a website. Each page is a vector, each hyperlink an edge.

Many people connect to this website. I collect the pages visited and the links clicked. The data-set is made up of all these "paths" of what each user clicked or looked at.

Now I have some working hypothesis on a "visitor strategy" to generate these paths. Say, strategy A is "click a link at random". Strategy B is "click a link at random, but higher probability of clicking a link from the index page", and so on.

I'd like to know if there is a statistical method that given many paths can tell me which strategy is a more accurate description of the users.

Intuitively I could use the hypothetical strategies to simulate many paths and then somehow measure the "distance" from these simulated paths to the real ones I have, but I am confused how to do it properly.

There are two ways I can think about the problem. The easier way would involve simply counting how many times one webpage sends a user to another webpage. The harder way would follow each user's path across the different pages she traverses within the website. The difference lies in whether or not to pay attention to an edge or a path traversed by a user. I will discuss the easier way here.

First, you'll need to create a directed network that contains all realized hyperlinks from one page to another. This network will outline which paths are possible. One page (ego) has an outgoing edge to another page (alter) if it (eg) hyperlinks to the other page (alter).

Second, you'll need to set an edge attribute weight equal to the number of times users click the hyperlink on one page, directing her to another page.

Third, from this network, list each path in the network. For each path, sum the weights for each edge in it.

Fourth, create a simulated network that produces the same paths in the third step, yet with different weights. There are a few ways to do so, but I would recommend using a method that reassigns the weights for each page's outgoing edges (perhaps by permutation to control for the distribution). Be sure to keep the network structure in the first step constant and perform this step for each vertex, one at a time. Simulating the network in this method controls for many relevant effects (indegree and outdegree distribution, the available paths, the number of clicks directing a user away from a page), though its downside results in webpages with more (or fewer) visitors than empirically observed.

Fifth, create a simulated network in the fourth step many times and for each one repeat the third step such that each path has the simulated edge weights added. This step will result in a random distribution for each path.

Sixth, compare the simulated path weights to the observed ones to test your hypothesis.

• That's a pretty neat idea to work with. Do you have any references by any chance? – CarrKnight Oct 17 '14 at 1:18
• There's literature on Conditional Uniform Graph (CUG) tests. The tnet package in R has some documentation on shuffling weights ('rg_reshuffling_w()'): Molloy, M., Reed, B., 1995. A critical point for random graphs with a given degree sequence. Random Structures and Algorithms 6, 161-180. Opsahl, T., Colizza, V., Panzarasa, P., Ramasco, J. J., 2008. Prominence and control: The weighted rich-club effect. Physical Review Letters 101 (168702). arXiv:0804.0417. – BenjaminLind Oct 17 '14 at 6:16