一种基于网络最大可控子图的导航搜索模型

A navigation search model based on subnet of maximum controllability

基于网络可控性模型提出了最大可控子图的概念,在此基础上提出了一种基于最大可控子图的导航搜索模型.模型中基于最大可控子图的加边策略用最小的代价解决了有向网络搜索中存在的粒子因"无路可走"而终止搜索的问题;基于最大可控子图部署导航节点,仅用节点总数2%左右的导航点,就使全网搜索时间接近导航网络的平均最短路径.通过在ER和SF网络上的实验表明,全网搜索时间与网络的可控性有关,可控性越好,添加的边数量越少,同时会使网络中导航节点分布越多,越能提高网络的搜索效率.

In this paper, we propose a concept of subnet of maximum controllability based on the model of network controllability, and set up the navigation search model based on the subnet of maximum controllability, called NMSMC. The strategy of adding links that is based on the subnet of maximum controllability is to solve, with the minimum cost, the terminating search, the problem that arises from no way for particles to search in the directed network. Based on the subnet of maximum controllability to deploy navigation nodes,the search time of the whole network can be made close to the average shortest path of the navigation network,which the number of navigation nodes is only 2% of the total nodes. The experimental results of the ER and SF networks show that the search efficiency is strongly correlated with the network controllability. The better the controllability, the less the adding links are, which can lead to the fact that the more the navigation nodes are distributed in the network, the more the search efficiency of the network can be enhanced.