技術(shù)領(lǐng)域

本發(fā)明屬于計算機(jī)技術(shù)領(lǐng)域、網(wǎng)絡(luò)拓?fù)浜蛨D論領(lǐng)域，特別涉及一種面向大規(guī)模網(wǎng)絡(luò)的拓?fù)涑闃臃椒ǎ梢愿鶕?jù)要求從大規(guī)模的網(wǎng)絡(luò)拓?fù)渲谐槿〉贸隹煞从炒笠?guī)模網(wǎng)絡(luò)拓?fù)涮卣鞯木W(wǎng)絡(luò)拓?fù)涑闃咏Y(jié)果，包括有向網(wǎng)絡(luò)和無向網(wǎng)絡(luò)，為用戶提供拓?fù)涑闃咏Y(jié)果以用于可計算機(jī)程序?qū)崿F(xiàn)的網(wǎng)絡(luò)拓?fù)溲芯克惴ā?/p>

背景技術(shù)

目前，隨著對大規(guī)模網(wǎng)絡(luò)的深入研究，以“星型網(wǎng)絡(luò)”、“總線網(wǎng)絡(luò)”、“環(huán)型網(wǎng)絡(luò)”等為代表的粗粒度網(wǎng)絡(luò)拓?fù)溲芯恳呀?jīng)不再滿足要求，對大規(guī)模網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行細(xì)粒度級研究的需求逐漸增多，如在大型網(wǎng)絡(luò)（尤其是互聯(lián)網(wǎng)）基礎(chǔ)結(jié)構(gòu)建設(shè)、網(wǎng)絡(luò)拓?fù)湟?guī)劃中使用圖論算法和圖譜密度算法對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行細(xì)粒分析和量化研究等。但一方面大規(guī)模網(wǎng)絡(luò)拓?fù)浔旧黼y于形成鄰接矩陣，或即使形成了鄰接矩陣，由于其規(guī)模過大而不適于可計算機(jī)程序?qū)崿F(xiàn)的圖論算法和圖譜密度算法分析，導(dǎo)致計算不可行；另一方面，從大規(guī)模網(wǎng)絡(luò)拓?fù)溧徑泳仃囍兄苯咏厝⌒∫?guī)模鄰接矩陣，并將其用于算法分析中，在計算機(jī)程序?qū)崿F(xiàn)上雖然可行，但卻不能保證所截取的小規(guī)模鄰接矩陣所表現(xiàn)出的拓?fù)涮卣髋c大規(guī)模網(wǎng)絡(luò)拓?fù)涮卣鞯囊恢滦裕@是因?yàn)榇笠?guī)模網(wǎng)絡(luò)通常具有復(fù)雜網(wǎng)絡(luò)特性，這類網(wǎng)絡(luò)拓?fù)渲幸话愦嬖谥S多度值非常大的節(jié)點(diǎn)，因此采樣時如果將其所有直接連接的節(jié)點(diǎn)都采到，那么鄰接矩陣中所表現(xiàn)出的網(wǎng)絡(luò)拓?fù)洌蠖嘀皇悄骋粺峁?jié)點(diǎn)及其相鄰一跳或幾跳距離的多個子節(jié)點(diǎn)，而不能很好地反映更廣范圍內(nèi)網(wǎng)絡(luò)的特征。針對這一問題，需要設(shè)計一種面向大規(guī)模網(wǎng)絡(luò)的拓?fù)涑闃臃椒ǎㄟ^該方法從大規(guī)模網(wǎng)絡(luò)中抽取得出抽樣拓?fù)浣Y(jié)果，包括有向網(wǎng)絡(luò)拓?fù)浜蜔o向網(wǎng)絡(luò)拓?fù)洌茨芊从炒笠?guī)模網(wǎng)絡(luò)拓?fù)涮卣鳎譂M足各種圖論算法和圖譜密度算法的計算可行性，使用戶細(xì)粒級的拓?fù)溲芯克惴ê蛨D譜密度算法可以計算機(jī)程序?qū)崿F(xiàn)。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種面向大規(guī)模網(wǎng)絡(luò)的拓?fù)涑闃臃椒ǎ摲椒梢詮拇笠?guī)模的網(wǎng)絡(luò)拓?fù)渲谐槿〉贸霾粊G失原網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征的拓?fù)涑闃咏Y(jié)果并形成拓?fù)溧徑泳仃嚕ㄓ邢蚓W(wǎng)絡(luò)和無向網(wǎng)絡(luò)。

采用的技術(shù)方案是：

首先針對大規(guī)模網(wǎng)絡(luò)拓?fù)涞臏y量結(jié)果，對每一條存在的連接，分別將源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)以字段值的形式存儲在數(shù)據(jù)庫中；然后從數(shù)據(jù)庫中選擇初始源節(jié)點(diǎn)，根據(jù)網(wǎng)絡(luò)范圍控制算法，掃描數(shù)據(jù)庫，記錄與初始節(jié)點(diǎn)直接連接的目標(biāo)節(jié)點(diǎn)，選擇有效的目標(biāo)節(jié)點(diǎn)加入隊列，記錄與目標(biāo)節(jié)點(diǎn)連接的所有邊，檢查并控制抽樣結(jié)果的連通性；如果記錄的網(wǎng)絡(luò)節(jié)點(diǎn)和邊的規(guī)模未達(dá)到預(yù)定目標(biāo)，則重復(fù)上述采樣過程。否則將抽樣結(jié)果形成拓?fù)溧徑泳仃嚒?/p>

本發(fā)明的工作流程和步驟為：

1、將大規(guī)模網(wǎng)絡(luò)拓?fù)錅y量結(jié)果形成數(shù)據(jù)庫；

2、確定拓?fù)涑跏脊?jié)點(diǎn)。抽樣的初始節(jié)點(diǎn)可以通過隨機(jī)方式隨取，也可以由用戶指定；

3、從初始節(jié)點(diǎn)開始，掃描并記錄直接連接節(jié)點(diǎn)。根據(jù)網(wǎng)絡(luò)范圍控制算法控制抽樣拓?fù)涓采w的網(wǎng)絡(luò)范圍，以使抽樣拓?fù)浣Y(jié)果盡可能覆蓋較大范圍網(wǎng)絡(luò)，并將符合要求的節(jié)點(diǎn)記錄在拓?fù)涑闃咏Y(jié)果中；

4、控制拓?fù)渲械倪B接，對抽樣的節(jié)點(diǎn)，記錄其所有連接，包括有向連接和無向連接；并將符合要求的連接記錄在拓?fù)涑闃咏Y(jié)果中；

5、檢查并控制抽樣拓?fù)浣Y(jié)果的連通性；

6、重復(fù)(2)-(5)步驟，直到拓?fù)涑闃咏Y(jié)果大小達(dá)到給定規(guī)模。將其生成鄰接矩陣并輸出。

本發(fā)明可以提供一種面向大規(guī)模網(wǎng)絡(luò)的拓?fù)涑槿》椒ǎㄟ^該方法抽樣得到的網(wǎng)絡(luò)拓?fù)洌床粊G失大規(guī)模網(wǎng)絡(luò)的拓?fù)涮卣鳎挚梢宰鳛榇笠?guī)模網(wǎng)絡(luò)拓?fù)涞拇恚瑸橛脩籼峁┮环N適于細(xì)粒度算法分析、且可計算機(jī)程序?qū)崿F(xiàn)的抽樣結(jié)果，解決了大規(guī)模網(wǎng)絡(luò)拓?fù)錈o法直接進(jìn)行細(xì)粒度量化分析的問題。

附圖說明

圖1是本發(fā)明的方法工作流程圖。

1.測量結(jié)果數(shù)據(jù)庫化模塊??2.?拓?fù)涑跏脊?jié)點(diǎn)確定模塊??3.?節(jié)點(diǎn)隨機(jī)選定模塊??4.?節(jié)點(diǎn)指定模塊??5.網(wǎng)絡(luò)范圍控制模塊??6.?連接控制模塊??7.?拓?fù)溥B通控制模塊??8.?結(jié)果判定模塊??9.?鄰接矩陣生成模塊?10.?隨機(jī)產(chǎn)生?11.?用戶指定??12.?已達(dá)到網(wǎng)絡(luò)規(guī)模??13.?未達(dá)到網(wǎng)絡(luò)規(guī)模。

具體實(shí)施方式

結(jié)合圖例進(jìn)一步說明本發(fā)明的方案和工作流程。

如圖1所示，一種面向大規(guī)模網(wǎng)絡(luò)的拓?fù)涑闃臃椒ǎ淞鞒讨饕y量結(jié)果數(shù)據(jù)庫化模塊1，拓?fù)涑跏脊?jié)點(diǎn)確定模塊2，節(jié)點(diǎn)隨機(jī)選定模塊3，節(jié)點(diǎn)指定模塊4，網(wǎng)絡(luò)范圍控制模塊5，連接控制模塊6，拓?fù)溥B通控制模塊7，結(jié)果判定模塊8，鄰接矩陣生成模塊9等模塊；以及四種判定條件，包括隨機(jī)產(chǎn)生判定條件10，用戶指定判定條件11，已達(dá)到網(wǎng)絡(luò)規(guī)模判定條件12，未達(dá)到網(wǎng)絡(luò)規(guī)模判定條件13。