Search in complex network - Lim, Kian Shin. (2009)
Decentralized searching finds targeted nodes in network without asking help from server, but using local information only. (1) By examining and evaluating several degree‐based decentralized algorithms and related factors, this final year report shows how does the searching efficiency affected by the nodal degree, memory, searching mechanism and network topology. It is also found that the benefit of using more memory can be achieved by using better searching mechanism. With the careful design of the searching algorithm, it is possible to improve the searching efficiency in terms of success rate and delivery time. In this final year report, the effects of four chosen factors to the degreebased decentralized algorithms had been examined in different chapters. The 4 factors are the effect of average nodal degree, effect of memory, effect of backtracking and effect of clusters. The simulation results show that larger average nodal degree, larger memory size and more backtracking steps and smaller modularity in a network imply better searching efficiency. The mechanism of those effects were revealed the in this report and an improvement for the degree‐based decentralized algorithm was proposed.