Degree and Similarity based Search in Networks
Decentralized search in networks is an important algorithmic problem in the study of complex networks and graph mining. It has a large number of practical applications, including shortest paths search in social network relationship, web pages search in WWW, querying files in peer-to-peer file sharing networks and so on. In this paper, we present a probabilistic analysis of this search problem that produces a surprisingly simple and effective method. Based on the analysis, we introduce a new decentralized search strategy named Product Search. In this strategy, for every step we forward the message to the neighbor with the minimum product of neighbors degree and common neighbors size. We compare this strategy with other common strategies like degree-based search, random walk and breadth-first search. And the results show that the product search outperforms others. We also find that the degree-based search does not do well in high clustering power-law networks, and traditional graph statistical properties such as average path length and skewed degree distribution fail to fully explain the level of search-ability in a network.
Graph Mining Decentralized Search Algorithm Degree Similarity
Bin Wu Qing Ke Yuxiao Dong
School of Computer Science Beijing University of Posts and Telecommunications,Beijing, China
国际会议
上海
英文
1315-1318
2011-07-26（万方平台首次上网日期，不代表论文的发表时间）