基于重叠社团划分的道路网络路由搜索算法的研究

发布时间：2019-07-20 04:58

【摘要】：随着复杂网络的研究受到越来越多的关注,网络中的许多特性被不断的发现并应用到不同的领域,尤其是社团结构越来越发挥着重要的作用。本文基于复杂网络中社团发现的理论,将重叠社团应用到路由策略中,结合城市道路网络数据进行研究,进一步发现社团对城市道路网络中路由策略的重要意义。实际的道路网络中可能存在部分重叠,但是现今的很多社团划分算法都没有将社团重叠的因素考虑进去,尤其是在做分层路由算法中。网络分层的路由算法可以有效的减少网络中不必要节点的访问,降低算法的时间复杂度,在能接受的范围内得到最优解。但是,在大规模道路网络中,道路可能会存在重叠的社团,直接影响到路由算法的时间复杂度,更加会影响我们最后需要得到的最优结果。因此,在分层的路由算法中引入重叠社团的思想,找出可能存在的道路重叠节点,能够提高整体路由策略的可靠性。本文研究了基于重叠社团划分的道路网络路由搜索算法。该算法结合美国多个城市道路网络数据,对道路网络进行社团划分,找出重叠社团,降低算法的复杂度;在做路由选择时,保存网络模型最上层网络节点中有效的节点,即社团边缘节点之间的信息,再应用传统的启发式搜索算法,进行有效的路由选择。本文提出的算法可以比传统搜索算法更快的查找最短路径,在路由选择中具有更加重要的意义。
【学位授予单位】：浙江工业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：U495

【共引文献】

相关期刊论文 前5条

1 李金刚;;FCM框架下的重叠社区发现算法[J];福建电脑;2013年09期

2 杨旭华;周诗杰;;基于重叠社团划分的大规模道路网络双层路由算法[J];计算机科学;2015年S1期

3 刘维维;陈建芮;乌力吉;;基于路径相似度的社区检测方法[J];内蒙古工业大学学报(自然科学版);2015年03期

4 Shiji CHEN;Xiaolin ZHANG;;Research on overlapping structures and evolution properties of co-citation network[J];Chinese Journal of Library and Information Science;2013年01期

5 翁伟;林琛;朱顺痣;马樱;邹权;陈泽红;;基于初始划分的标签传播社区发现算法[J];厦门大学学报(自然科学版);2015年01期

相关博士学位论文 前1条

1 朱牧;复杂网络中社区发现关键技术研究[D];中国矿业大学;2014年

相关硕士学位论文 前6条

1 陈静;基于自然计算的复杂网络社区检测[D];西安电子科技大学;2013年

2 王路飞;基于计价与价格诱导的智能交通诱导系统[D];浙江大学;2014年

3 丁悦波;基于社区的机会网络缓存机制及路由算法研究[D];杭州电子科技大学;2014年

4 刘勇;复杂网络的非重叠与重叠社区检测方法[D];西安电子科技大学;2014年

5 吴美玲;动态网络社区检测在电信业客户流失分析中的应用[D];广东外语外贸大学;2014年

6 张章;顾及地理实体属性信息的网络最短路径分析算法研究[D];兰州交通大学;2014年

，

本文编号：2516490