基于重疊社團(tuán)劃分的道路網(wǎng)絡(luò)路由搜索算法的研究

《基于重疊社團(tuán)劃分的道路網(wǎng)絡(luò)路由搜索算法的研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、碩士學(xué)位論文論文題目：基于重疊社團(tuán)劃分的道路網(wǎng)絡(luò)路由搜索算法的研究作者姓名周詩(shī)杰指導(dǎo)教師楊旭華學(xué)科專(zhuān)業(yè)計(jì)算機(jī)科學(xué)與技術(shù)所在學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院提交日期2015年4月15日浙江工業(yè)大學(xué)碩士學(xué)位論文基于重疊社團(tuán)劃分的道路網(wǎng)絡(luò)路由搜索算法的研究作者姓名：周詩(shī)杰指導(dǎo)教師：楊旭華教授浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2015年4月浙江工業(yè)大學(xué)學(xué)位論文原創(chuàng)巧聲明，獨(dú)立進(jìn)行研究工作本人鄭重聲明：所提交的學(xué)位論文是本人在導(dǎo)師的指導(dǎo)下承經(jīng)加，本論文不包含其他個(gè)人或哀瀑的研究成果。除文中己＾＾標(biāo)注引用的內(nèi)容外集譯己經(jīng)

2、發(fā)表或撰寫(xiě)過(guò)的研究成果，也不含為獲得浙江工業(yè)大學(xué)或其它教育機(jī)構(gòu)的學(xué)運(yùn)證書(shū)而使用過(guò)的材料。對(duì)本文的研究作出重要貢獻(xiàn)的個(gè)人和集體，均己在文中聲明的法律責(zé)任。以巧確方式標(biāo)明。本人承擔(dān)本＾（＜日期年月作者簽名：或Ｔ１＾＾＾｜＾學(xué)位論文版權(quán)使用授權(quán)書(shū)本學(xué)位論文作者完全、使用學(xué)位論文的規(guī)定，同意學(xué)校保留了解學(xué)校有關(guān)保留論文被查閱和借閱。本并向國(guó)家有關(guān)部口或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢人授權(quán)浙江工業(yè)大學(xué)可Ｗ將本學(xué)位論文的掃描等復(fù)制手段保存和匯編本學(xué)位論文。

3、索、縮印或，可Ｗ采用影印本學(xué)位論文屬于□年解密后適用本授權(quán)書(shū)。１、保密，在２、不保密口。＂＂Ｕ上相應(yīng)方框內(nèi)打Ｖ）（請(qǐng)?jiān)冢簦掌冢耗辏痹乱郑崳娮髡吆灻喝艄螢椋羧眨崳娙掌?；）如ｒ年ｒ月（?dǎo)師簽名：７Ｔ雨７＾平DissertationSubmittedtoZhejiangUniversityofTechnologyfortheDegreeofMasterRESEARCHOFROUTINGALGORITHMONROADNETWORKSBASEDONOVERLAPPINGCOMMUNITIESDET

4、ECTINGCandidate:ZHOUShi-JieAdvisor:Prof.YANGXu-HuaCollegeofComputerScienceandTechnologyZhejiangUniversityofTechnologyApri2015浙江工業(yè)大學(xué)碩士學(xué)位論文基于重疊社團(tuán)劃分的道路網(wǎng)絡(luò)路由搜索算法的研究摘要隨著復(fù)雜網(wǎng)絡(luò)的研究受到越來(lái)越多的關(guān)注，網(wǎng)絡(luò)中的許多特性被不斷的發(fā)現(xiàn)并應(yīng)用到不同的領(lǐng)域，尤其是社團(tuán)結(jié)構(gòu)越來(lái)越發(fā)揮著重要的作用。本文基于復(fù)雜網(wǎng)絡(luò)中社團(tuán)發(fā)現(xiàn)的理論，將重疊社團(tuán)應(yīng)用到路由策略中，結(jié)合城市道路

5、網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行研究，進(jìn)一步發(fā)現(xiàn)社團(tuán)對(duì)城市道路網(wǎng)絡(luò)中路由策略的重要意義。實(shí)際的道路網(wǎng)絡(luò)中可能存在部分重疊，但是現(xiàn)今的很多社團(tuán)劃分算法都沒(méi)有將社團(tuán)重疊的因素考慮進(jìn)去，尤其是在做分層路由算法中。網(wǎng)絡(luò)分層的路由算法可以有效的減少網(wǎng)絡(luò)中不必要節(jié)點(diǎn)的訪問(wèn)，降低算法的時(shí)間復(fù)雜度，在能接受的范圍內(nèi)得到最優(yōu)解。但是，在大規(guī)模道路網(wǎng)絡(luò)中，道路可能會(huì)存在重疊的社團(tuán)，直接影響到路由算法的時(shí)間復(fù)雜度，更加會(huì)影響我們最后需要得到的最優(yōu)結(jié)果。因此，在分層的路由算法中引入重疊社團(tuán)的思想，找出可能存在的道路重疊節(jié)點(diǎn)，能夠提高整體路由策略的可靠性。本文

6、研究了基于重疊社團(tuán)劃分的道路網(wǎng)絡(luò)路由搜索算法。該算法結(jié)合美國(guó)多個(gè)城市道路網(wǎng)絡(luò)數(shù)據(jù)，對(duì)道路網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分，找出重疊社團(tuán)，降低算法的復(fù)雜度；在做路由選擇時(shí)，保存網(wǎng)絡(luò)模型最上層網(wǎng)絡(luò)節(jié)點(diǎn)中有效的節(jié)點(diǎn)，即社團(tuán)邊緣節(jié)點(diǎn)之間的信息，再應(yīng)用傳統(tǒng)的啟發(fā)式搜索算法，進(jìn)行有效的路由選擇。本文提出的算法可以比傳統(tǒng)搜索算法更快的查找最短路徑，在路由選擇中具有更加重要的意義。關(guān)鍵詞：重疊社團(tuán)，社團(tuán)劃分，分層路由，道路網(wǎng)絡(luò)i浙江工業(yè)大學(xué)碩士學(xué)位論文RESEARCHOFROUTINGALGORITHMONROADNETWORKSBASEDONO

7、VERLAPPINGCOMMUNITIESDETECTINGABSTRACTThestudyofcomplexnetworksisgettingmoreandmoreattention;manyfeaturesofthenetworkareconstantlybeenfoundandappliedtodifferentfields,especiallythecommunitystructurefeature.Basedonthetheoryofcommunitydetectingincomplexnetworks,

8、combiningtheoverlappingcommunitywiththerouting,usingtheurbanroadnetworkdata,wearefurtherfindingthatthecommunityhassignificancetotheroutingstrategy.Inmanyrealnetworks,communitiesmay