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

被引：3

作者：

肖延东

老松杨

侯绿林

白亮

机构：

[1] 国防科技大学信息系统与管理学院

来源：

物理学报 | 2013年 / 62卷 / 24期

关键词：

导航搜索; 有向网; 网络可控性;

D O I：

暂无

中图分类号：

O157.5 [图论]; O231 [控制论（控制论的数学理论）];

学科分类号：

摘要：

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

引用

页码：377 / 385

页数：9

共 5 条

[1] 基于传播免疫的复杂网络可控性研究 [J].

吕天阳 ;

朴秀峰 ;

谢文艳 ;

黄少滨 .

物理学报, 2012, 61 (17) :135-143

[2] 一种基于布朗粒子的混合搜索模型 [J].

濮存来 ;

裴文江 ;

王少平 .

物理学报, 2010, 59 (01) :103-110

[3] 节点数加速增长的复杂网络生长模型 [J].

李季 ;

汪秉宏 ;

蒋品群 ;

周涛 ;

王文旭 .

物理学报, 2006, (08) :4051-4057

[4]

Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm[J] . Reinhard Bauer,Daniel Delling,Peter Sanders,Dennis Schieferdecker,Dominik Schultes,Dorothea Wagner. Journal of Experimental Algorithmics (JEA) . 2010

[5]

A note on two problems in connexion with graphs.[J] . E. W. Dijkstra. Numerische Mathematik . 1959 (1)

← 1 →