摘要
搜索是复杂网络上的一项基本功能,设计搜索策略的一个重要目标是在每个节点上维护尽可能少的信息,并且搜索效率尽可能高。针对复杂网络搜索提出了一种新的标记策略(labelingscheme)。通过将网络嵌入到较简单的度量空间和对节点重新命名,使每个节点只需要知道邻居节点的名字,因而在节点上存放很少的信息,而搜索使用的路径长度限制在较小的范围内。由于许多真实的复杂网络都是无标度网络,利用它们的拓扑特征,该策略在这类网络上能够获得很高的搜索效率,绝大部分情况下搜索使用的路径都是最优路径。与已知的几种标记策略相比,仿真结果表明该策略的总体性能更好。
Search is one of the basic tasks in complex networks, and it’s vital for design of search schemes that can search efficiently while maintaining little information at each node in networks. A novel labeling scheme for search in complex networks was proposed. In the scheme, a network was embedded into a simpler metric space and the nodes of the network were renamed, making each node only keep the information of its direct neighbors, while the path lengths of search were bounded tightly. For many realistic complex networks are scale-free networks, by utilizing their topological properties, the scheme can perform fairly well on these network topologies, i.e., most of paths used in the scheme are optimal. Simulations show the scheme performed better than prior related schemes on the whole.
出处
《系统仿真学报》
CAS
CSCD
北大核心
2010年第6期1485-1489,共5页
Journal of System Simulation
基金
国家自然科学基金(60673168
90818004)
关键词
搜索
复杂网络
标记策略
路由
度量空间嵌入
search
complex networks
labeling schemes
routing
metric embeddings
