network exploration

a network exploration algorithm. The frequency of a node of degree \(d\) being visit approaches \(\frac{d}{2m}\)

Algorithm: in each step, select a neighbor at random, and move to it. example -

1. arrange neighbor in an order
2. generate a random number \(i\) in \([0,1)\)
3. go to the $\text{floor}(d * i)$th neighbor

Algorithms that operats on network

• network exploration algorithms

Algorithm of network exploration that favours node with fewer degree.

Algorithm:

1. select a neighbor at random
2. set probability of moving to it as \(\frac{d_\test{self}}{d_\text{neighbor}}\) (which is smaller when neighbor have more links, therefore favor node with less links)
3. If the probability is larger than 1 (neighbor have fewer links), move to neighbort
4. if not, generate a random number in \([0,1)\), if it is larger than the probability, then move to the neighbor/otherwise don’t move