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

《基于重叠社团划分的道路网络路由搜索算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文论文题目：基于重叠社团划分的道路网络路由搜索算法的研究作者姓名周诗杰指导教师杨旭华学科专业计算机科学与技术所在学院计算机科学与技术学院提交日期2015年4月15日浙江工业大学硕士学位论文基于重叠社团划分的道路网络路由搜索算法的研究作者姓名：周诗杰指导教师：杨旭华教授浙江工业大学计算机科学与技术学院2015年4月浙江工业大学学位论文原创巧声明，独立进行研究工作本人郑重声明：所提交的学位论文是本人在导师的指导下承经加，本论文不包含其他个人或哀瀑的研究成果。除文中己＾＾标注引用的内容外集译己经

2、发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的学运证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均己在文中声明的法律责任。以巧确方式标明。本人承担本＾（＜日期年月作者签名：或Ｔ１＾＾＾｜＾学位论文版权使用授权书本学位论文作者完全、使用学位论文的规定，同意学校保留了解学校有关保留论文被查阅和借阅。本并向国家有关部口或机构送交论文的复印件和电子版，允许全部或部分内容编入有关数据库进行检人授权浙江工业大学可Ｗ将本学位论文的扫描等复制手段保存和汇编本学位论文。

3、索、缩印或，可Ｗ采用影印本学位论文属于□年解密后适用本授权书。１、保密，在２、不保密口。＂＂Ｕ上相应方框内打Ｖ）（请在ｔ＇日期：年１月抑作者签名：若刮為ｔ日日期；）如ｒ年ｒ月（导师签名：７Ｔ雨７＾平DissertationSubmittedtoZhejiangUniversityofTechnologyfortheDegreeofMasterRESEARCHOFROUTINGALGORITHMONROADNETWORKSBASEDONOVERLAPPINGCOMMUNITIESDET

4、ECTINGCandidate:ZHOUShi-JieAdvisor:Prof.YANGXu-HuaCollegeofComputerScienceandTechnologyZhejiangUniversityofTechnologyApri2015浙江工业大学硕士学位论文基于重叠社团划分的道路网络路由搜索算法的研究摘要随着复杂网络的研究受到越来越多的关注，网络中的许多特性被不断的发现并应用到不同的领域，尤其是社团结构越来越发挥着重要的作用。本文基于复杂网络中社团发现的理论，将重叠社团应用到路由策略中，结合城市道路

5、网络数据进行研究，进一步发现社团对城市道路网络中路由策略的重要意义。实际的道路网络中可能存在部分重叠，但是现今的很多社团划分算法都没有将社团重叠的因素考虑进去，尤其是在做分层路由算法中。网络分层的路由算法可以有效的减少网络中不必要节点的访问，降低算法的时间复杂度，在能接受的范围内得到最优解。但是，在大规模道路网络中，道路可能会存在重叠的社团，直接影响到路由算法的时间复杂度，更加会影响我们最后需要得到的最优结果。因此，在分层的路由算法中引入重叠社团的思想，找出可能存在的道路重叠节点，能够提高整体路由策略的可靠性。本文

6、研究了基于重叠社团划分的道路网络路由搜索算法。该算法结合美国多个城市道路网络数据，对道路网络进行社团划分，找出重叠社团，降低算法的复杂度；在做路由选择时，保存网络模型最上层网络节点中有效的节点，即社团边缘节点之间的信息，再应用传统的启发式搜索算法，进行有效的路由选择。本文提出的算法可以比传统搜索算法更快的查找最短路径，在路由选择中具有更加重要的意义。关键词：重叠社团，社团划分，分层路由，道路网络i浙江工业大学硕士学位论文RESEARCHOFROUTINGALGORITHMONROADNETWORKSBASEDONO

7、VERLAPPINGCOMMUNITIESDETECTINGABSTRACTThestudyofcomplexnetworksisgettingmoreandmoreattention;manyfeaturesofthenetworkareconstantlybeenfoundandappliedtodifferentfields,especiallythecommunitystructurefeature.Basedonthetheoryofcommunitydetectingincomplexnetworks,

8、combiningtheoverlappingcommunitywiththerouting,usingtheurbanroadnetworkdata,wearefurtherfindingthatthecommunityhassignificancetotheroutingstrategy.Inmanyrealnetworks,communitiesmay