国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于改進(jìn)K-Shell的社會(huì)網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)挖掘算法

2023-08-10 07:03:00李蜜佳衛(wèi)紅權(quán)李英樂劉樹新
關(guān)鍵詞:復(fù)雜度準(zhǔn)確率中心

李蜜佳 衛(wèi)紅權(quán) 李英樂 劉樹新

(中國(guó)人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué) 河南 鄭州 450001)

0 引 言

對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行深度挖掘和分析在理論和現(xiàn)實(shí)中具有重要意義[1]。社會(huì)網(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)的一個(gè)領(lǐng)域,包括人際關(guān)系網(wǎng)、Twitter網(wǎng)和論文合著網(wǎng)等。社會(huì)網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn),由于在網(wǎng)絡(luò)中的結(jié)構(gòu)地位以及活躍度的不同,所起的作用也不同,其中有一部分節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)局部或者全局影響較大,這類節(jié)點(diǎn)就叫做關(guān)鍵節(jié)點(diǎn)。通過挖掘社會(huì)網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn),可以滿足我們的很多實(shí)際需求。比如在產(chǎn)品推銷網(wǎng)絡(luò)中,商家可以消耗最少的資源實(shí)現(xiàn)產(chǎn)品最高效的推廣;在輿論傳播網(wǎng)絡(luò)中,政府可以使用最少的干預(yù)手段去宣傳輿論或者禁止謠言;在犯罪嫌疑人關(guān)系網(wǎng)絡(luò)中,警察可以快速鎖定團(tuán)伙頭目,進(jìn)而集中警力抓捕。

目前,在關(guān)鍵節(jié)點(diǎn)挖掘方面,研究人員已經(jīng)從不同的角度探索了很多算法。在基于鄰居節(jié)點(diǎn)中心性的方法中,度中心性的方法用節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)量來衡量節(jié)點(diǎn)重要性,計(jì)算復(fù)雜度低,但是僅考慮了節(jié)點(diǎn)局部重要性,沒有考慮節(jié)點(diǎn)的網(wǎng)絡(luò)位置及其他全局信息,準(zhǔn)確性不高。Chen等[2]提出了一種半局部中心性方法,該方法只統(tǒng)計(jì)節(jié)點(diǎn)的四層鄰居的信息,比局部中心性的方法更準(zhǔn)確且計(jì)算復(fù)雜度低,適合于大規(guī)模網(wǎng)絡(luò),但是由于該方法沒有考慮鄰居節(jié)點(diǎn)所處的不同層次,影響了關(guān)鍵節(jié)點(diǎn)挖掘的準(zhǔn)確性。之后,Chen等[3]綜合考慮了度中心性與聚集系數(shù),又提出ClusterRank中心性,該方法適用于大規(guī)模網(wǎng)絡(luò),但把網(wǎng)絡(luò)視為無向的,與多數(shù)現(xiàn)實(shí)情況不符。趙曉暉[4]綜合考慮節(jié)點(diǎn)的半局部中心性和聚類系數(shù),提出了一種歸一化的局部中心性節(jié)點(diǎn)影響力度量算法。Kitsak等[5]認(rèn)為節(jié)點(diǎn)距離網(wǎng)絡(luò)核心越近,所產(chǎn)生的影響力也就越大,由此提出K-Shell分解法,該方法計(jì)算復(fù)雜度低,在分析大規(guī)模網(wǎng)絡(luò)方面應(yīng)用較多,但是僅對(duì)節(jié)點(diǎn)進(jìn)行粗粒度劃分,準(zhǔn)確性不高。對(duì)此,嚴(yán)沛[6]在K-Shell的基礎(chǔ)上,使用雙向搜索樹方法提高算法準(zhǔn)確性。

在基于路徑中心性的方法中,Hage等[7]認(rèn)為節(jié)點(diǎn)的影響力與節(jié)點(diǎn)到其他節(jié)點(diǎn)的距離有關(guān),提出離心中心性,該算法很容易受到特殊值的影響。Freeman[8]提出接近中心性(Closeness Centrality),節(jié)點(diǎn)的緊密度越大,越靠近網(wǎng)絡(luò)中心,也就越重要。Freeman[9]提出介數(shù)中心性(Betweenness Centrality),將節(jié)點(diǎn)的重要性由通過該節(jié)點(diǎn)的最短路徑數(shù)目來表示,這兩種算法準(zhǔn)確度高但計(jì)算復(fù)雜度也高。與介數(shù)中心性僅考慮最短路徑不同,Katz中心性[10]考慮節(jié)點(diǎn)對(duì)之間的所有路徑,并根據(jù)路徑長(zhǎng)度對(duì)路徑加權(quán),這種算法的時(shí)間復(fù)雜度也比較高。

在基于特征向量的方法中,Bonacich[10]提出特征向量中心性(Eigenvector Centrality),認(rèn)為一個(gè)節(jié)點(diǎn)的重要性要綜合考慮其鄰居節(jié)點(diǎn)的數(shù)量和質(zhì)量。Poulin等[11]假設(shè)每個(gè)節(jié)點(diǎn)都在社會(huì)網(wǎng)絡(luò)中被提名,節(jié)點(diǎn)的重要性與節(jié)點(diǎn)本身及其鄰居節(jié)點(diǎn)被提名次數(shù)有關(guān),由此提出一種累計(jì)提名中心性(Cumulative Nomination Centrality),該算法比特征向量中心性收斂要快。Google引擎使用的PageRank算法[12]是特征向量中心性的變體,該算法綜合考慮指向該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)目和鄰居節(jié)點(diǎn)自身的重要性。Lü等[13]提出LeaderRank方法,引入背景節(jié)點(diǎn)使原網(wǎng)絡(luò)變?yōu)閺?qiáng)連通網(wǎng)絡(luò),從而替代了PageRank算法中的跳轉(zhuǎn)概率c,性能較PageRank有較大提升。

基于路徑和特征向量中心性的關(guān)鍵節(jié)點(diǎn)挖掘算法雖然準(zhǔn)確度高,但是普遍時(shí)間復(fù)雜度高,無法在大規(guī)模網(wǎng)絡(luò)上進(jìn)行應(yīng)用;度中心性、K-Shell分解法等時(shí)間復(fù)雜度低的算法雖然適用于大型網(wǎng)絡(luò),但是其準(zhǔn)確度又不理想,其劃分結(jié)果難以滿足精細(xì)化節(jié)點(diǎn)重要性劃分的實(shí)際需求。

基于此,本文對(duì)K-Shell分解法進(jìn)行改進(jìn),在分解過程中綜合考慮節(jié)點(diǎn)的度數(shù)與節(jié)點(diǎn)被刪除時(shí)所處的迭代層次,以解決K-Shell劃分結(jié)果粗粒化的問題。隨后采用一種用微觀結(jié)構(gòu)去替代原有完整網(wǎng)絡(luò)的算法,根據(jù)改進(jìn)的K-Shell節(jié)點(diǎn)排名提取核心網(wǎng)絡(luò),并結(jié)合PageRank值對(duì)核心網(wǎng)絡(luò)中所有節(jié)點(diǎn)做定量分析,找出影響較大的節(jié)點(diǎn),最終形成分層次的重要節(jié)點(diǎn)劃分。在三個(gè)實(shí)際網(wǎng)絡(luò)中進(jìn)行實(shí)驗(yàn)驗(yàn)證,結(jié)果表明本文方法具有較低的時(shí)間復(fù)雜度,計(jì)算結(jié)果也更準(zhǔn)確。

1 算法設(shè)計(jì)

圖G的鄰接矩陣A=(aij)N×N,A=(aij)N×N是一個(gè)N階方陣,其中:

式中:aij為節(jié)點(diǎn)i與j連接。

1.1 K-Shell分解法

Kitsak等[5]指出在度量節(jié)點(diǎn)重要性時(shí),需要考慮節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的位置,他們認(rèn)為處在網(wǎng)絡(luò)核心位置的節(jié)點(diǎn)會(huì)產(chǎn)生較大的影響力,并提出了K-Shell分解法。

例如,圖1是一個(gè)由15個(gè)節(jié)點(diǎn)和19條邊組成的無權(quán)無向網(wǎng)絡(luò)圖。

圖1 無向網(wǎng)絡(luò)

針對(duì)圖1所示的無向網(wǎng)絡(luò),具體分解過程如下:刪除網(wǎng)絡(luò)中所有度為1的節(jié)點(diǎn)及連邊,記迭代層數(shù)為1。觀察剩余網(wǎng)絡(luò)中是否仍有度為1的節(jié)點(diǎn),如果有,刪除節(jié)點(diǎn)及連邊,迭代層數(shù)記作2。循環(huán)去除,直至網(wǎng)絡(luò)中沒有度為1的節(jié)點(diǎn),此時(shí)將所有被刪除節(jié)點(diǎn)K-Shell值記作1。依次迭代,刪除網(wǎng)絡(luò)中度為2、3、4、5、…的節(jié)點(diǎn),直至所有節(jié)點(diǎn)都被刪除。圖2為按照K-Shell分解法對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的劃分結(jié)果。

圖2 K-Shell分解

圖3 SIR模型狀態(tài)轉(zhuǎn)移

對(duì)圖1網(wǎng)絡(luò)記錄K-Shell分解全過程如表1所示。

表1 K-Shell分解過程

1.2 改進(jìn)的K-Shell分解法

K-Shell方法計(jì)算復(fù)雜度低,在分析大規(guī)模網(wǎng)絡(luò)方面應(yīng)用較多,但也存在不足。第一,K-Shell分解法不區(qū)分入度與出度,而社交網(wǎng)絡(luò)基本都屬于有向網(wǎng)絡(luò)[14],節(jié)點(diǎn)受關(guān)注的程度由節(jié)點(diǎn)的入度表示,節(jié)點(diǎn)的合群程度由出度表示,忽略入度與出度的不同,會(huì)使一些節(jié)點(diǎn)以較小的代價(jià)通過建立與核心位置節(jié)點(diǎn)的單向連邊來提高自身核數(shù),從而導(dǎo)致挖掘結(jié)果出現(xiàn)較大偏差。第二,K-Shell分解法屬于粗粒度劃分,把屬于同一層的節(jié)點(diǎn)都看作同等地位,忽略了節(jié)點(diǎn)度和節(jié)點(diǎn)被刪除時(shí)所處迭代層數(shù)的影響,導(dǎo)致大量節(jié)點(diǎn)被劃分到同一層。如在圖2的網(wǎng)絡(luò)中,節(jié)點(diǎn)1和節(jié)點(diǎn)4被K-Shell分解法劃分到同一層,K-Shell值相同,但顯然節(jié)點(diǎn)4比節(jié)點(diǎn)1重要。

對(duì)此,本文對(duì)算法作如下改進(jìn):

(1) 針對(duì)社交網(wǎng)絡(luò)多為有向網(wǎng)絡(luò)的特點(diǎn),將傳統(tǒng)的K-Shell在分解過程中不區(qū)分節(jié)點(diǎn)入度出度的做法,改為僅考慮入度對(duì)節(jié)點(diǎn)進(jìn)行剝離。

詳細(xì)分解步驟為:

偽代碼如下:

輸入:nodes list V,Links list B。

Ks=1;

n=1;

while(|V|≠0)

add removal node i into set Vk-core(n);

add removal node i into set Vk-core(Ks);

end while

delete node i and related links;

update V and E;

n++;

end while

core++;

end while

1.3 inKD-Pr算法

PageRank算法[12]是谷歌搜索引擎的核心算法。它認(rèn)為一個(gè)節(jié)點(diǎn)的重要性取決于指向它的節(jié)點(diǎn)的數(shù)目和質(zhì)量。該算法作為有向網(wǎng)絡(luò)節(jié)點(diǎn)排序最經(jīng)典的算法,被廣泛應(yīng)用于對(duì)網(wǎng)頁(yè)的排序、對(duì)社交網(wǎng)絡(luò)上用戶的排序等。作為全局性算法,PageRank計(jì)算結(jié)果較準(zhǔn)確,但時(shí)間復(fù)雜度高于K-Shell分解法。由于兩種算法相關(guān)性不大,本文綜合了兩種算法的優(yōu)勢(shì),構(gòu)建關(guān)鍵節(jié)點(diǎn)挖掘模型的步驟如下:

(1) 根據(jù)社會(huì)網(wǎng)絡(luò)相關(guān)數(shù)據(jù),構(gòu)建鄰接矩陣。

(2) 用改進(jìn)的K-Shell分解法對(duì)網(wǎng)絡(luò)所有節(jié)點(diǎn)快速打分。

(3) 按照得分高低,依次刪除外圍大約80%的不重要的節(jié)點(diǎn)及其連邊,減小網(wǎng)絡(luò)規(guī)模。

(4) 對(duì)步驟(3)中提取的核心網(wǎng)絡(luò),運(yùn)用PageRank算法計(jì)算出每個(gè)節(jié)點(diǎn)的p值,并進(jìn)行歸一化和無量綱化處理。

本文算法框架被稱作inKD-Pr算法。

2 評(píng)估標(biāo)準(zhǔn)及數(shù)據(jù)集介紹

2.1 評(píng)估標(biāo)準(zhǔn)

本文采用SIR(Susceptible-Infective-Removal)模型[15],將節(jié)點(diǎn)的最大傳播力作為節(jié)點(diǎn)重要性評(píng)價(jià)標(biāo)準(zhǔn)。SIR模型是Kermack等提出的傳染病模型中最經(jīng)典的模型,現(xiàn)在普遍應(yīng)用于疾病傳播、謠言傳播等領(lǐng)域。

SIR模型將網(wǎng)絡(luò)節(jié)點(diǎn)分為三類:易感狀態(tài)S,指?jìng)€(gè)體可能會(huì)被處于感染狀態(tài)的鄰居節(jié)點(diǎn)感染;感染狀態(tài)I,指節(jié)點(diǎn)已被感染且具備感染力;免疫狀態(tài)R,指節(jié)點(diǎn)失去感染其他節(jié)點(diǎn)的能力。剛開始傳播時(shí),處在感染狀態(tài)I的節(jié)點(diǎn),以β的概率感染處在S狀態(tài)的鄰居節(jié)點(diǎn),隨后,處在I狀態(tài)的節(jié)點(diǎn)以概率γ轉(zhuǎn)變成為R狀態(tài),不再參與傳染。重復(fù)上述步驟直至網(wǎng)絡(luò)到達(dá)穩(wěn)態(tài)。模型可用微分方程表示如下:

在SIR模型中,全部節(jié)點(diǎn)的數(shù)量N=S(t)+I(t)+R(t),其中S(t)、I(t)、R(t)分別為在t時(shí)刻網(wǎng)絡(luò)中三種狀態(tài)節(jié)點(diǎn)的數(shù)量。

不同挖掘算法的優(yōu)劣可通過各算法挖掘的重要節(jié)點(diǎn)在SIR模型上的傳播范圍來衡量。設(shè)置一個(gè)(組)重要節(jié)點(diǎn)為S狀態(tài)在SIR模型上進(jìn)行傳播,觀察最終穩(wěn)態(tài)時(shí)處于R狀態(tài)的節(jié)點(diǎn)數(shù)量。如果一種算法的挖掘結(jié)果可使網(wǎng)絡(luò)流傳播地又快又廣,即可說明該算法挖掘效果優(yōu)于其他算法。

2.2 數(shù)據(jù)集

科布倫茨數(shù)據(jù)資料庫(kù)是公布在網(wǎng)上,供從事大規(guī)模數(shù)據(jù)處理的人員用來進(jìn)行網(wǎng)絡(luò)科學(xué)及相關(guān)領(lǐng)域研究的工具。本文選取了該資料庫(kù)三個(gè)有向無權(quán)的網(wǎng)絡(luò)數(shù)據(jù)集作為實(shí)驗(yàn)網(wǎng)絡(luò),數(shù)據(jù)集信息如表2所示。

表2 數(shù)據(jù)集的基本特性

(1) Physicians社交網(wǎng)絡(luò)數(shù)據(jù)集:節(jié)點(diǎn)代表醫(yī)生,邊表示一位醫(yī)生遇到問題會(huì)向另一位醫(yī)生求助。

(2) Blogs超鏈接數(shù)據(jù)集:節(jié)點(diǎn)代表用戶,邊表示一個(gè)用戶鏈接了另一個(gè)用戶。

(3) Ciation數(shù)據(jù)集:節(jié)點(diǎn)表示一個(gè)機(jī)場(chǎng),邊表示從一個(gè)機(jī)場(chǎng)到另一個(gè)機(jī)場(chǎng)的航班。

這三個(gè)數(shù)據(jù)集的基本情況如表2所示,稀疏性表示網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)間存在連邊的概率,即網(wǎng)絡(luò)中存在的連邊數(shù)量占網(wǎng)絡(luò)中所有可能連邊數(shù)的比例。在有向無環(huán)網(wǎng)絡(luò)中,網(wǎng)絡(luò)的稀疏性=m/[n(n-1)],其中:m為網(wǎng)絡(luò)中邊的數(shù)目;n為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)。

3 仿真驗(yàn)證

3.1 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證本文方法的有效性,選取3種排序方法對(duì)比分析,分別是度中心性、PageRank算法、LeaderRank算法。

本文采用單一節(jié)點(diǎn)傳播的方式,分別對(duì)排名前k(為了分析方便,設(shè)置k=10)的節(jié)點(diǎn)進(jìn)行SIR模型檢測(cè),每個(gè)節(jié)點(diǎn)都作為單一感染源進(jìn)行傳播,運(yùn)行300次取均值,每種算法的有效性由該算法挖掘出的排名前10的節(jié)點(diǎn)傳播能力總和來表示。這里將免疫率γ取為0.5。對(duì)于感染概率β,如該值太小,很難在一個(gè)較小的網(wǎng)絡(luò)區(qū)域中區(qū)分開不同算法[16]。當(dāng)β非常高,不管是從哪個(gè)節(jié)點(diǎn)開始傳播,最后傳播范圍都將覆蓋幾乎整個(gè)網(wǎng)絡(luò),導(dǎo)致無法區(qū)分節(jié)點(diǎn)的作用。對(duì)此,本文使用一個(gè)溫和的感染概率β=0.3。

3.2 實(shí)驗(yàn)結(jié)果

如圖4所示,將免疫狀態(tài)的節(jié)點(diǎn)的累計(jì)數(shù)量繪制成時(shí)間的函數(shù),累計(jì)免疫節(jié)點(diǎn)隨時(shí)間增加,最終達(dá)到穩(wěn)定狀態(tài)。在網(wǎng)絡(luò)規(guī)模較小時(shí)(如Physicians數(shù)據(jù)集),度中心性的表現(xiàn)要優(yōu)于inKD-Pr算法和PageRank算法,但是度中心性算法的準(zhǔn)確率與網(wǎng)絡(luò)規(guī)模有關(guān),當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)增多時(shí),準(zhǔn)確率呈現(xiàn)顯著下降趨勢(shì)。這種現(xiàn)象與度中心性本身的算法有關(guān),度中心性僅以節(jié)點(diǎn)的局部信息作為衡量標(biāo)準(zhǔn),而沒有考慮節(jié)點(diǎn)所處位置、更高階鄰居等因素,這就導(dǎo)致一些邊緣節(jié)點(diǎn)可以通過與大量普通節(jié)點(diǎn)建立連邊來提高度值,而這樣的算法,在inKD-Pr算法中完全占不到優(yōu)勢(shì),inKD-Pr算法以節(jié)點(diǎn)入度為參考值去提取核心網(wǎng)絡(luò),既刪除了大量非核心節(jié)點(diǎn),同時(shí)也確保了一些節(jié)點(diǎn)無法通過僅僅依靠增加出度而進(jìn)入到核心網(wǎng)絡(luò)中。Blogs網(wǎng)絡(luò)上,度中心性算法和PageRank算法、inKD-Pr算法曲線近乎一致,即由這三種算法挖掘的前10名重要節(jié)點(diǎn)在網(wǎng)絡(luò)中的傳播能力基本相同。

(a) Physicians網(wǎng)絡(luò)

LeaderRank算法和PageRank算法在準(zhǔn)確度方面的穩(wěn)定性較佳但算法復(fù)雜度高。LeaderRank算法的準(zhǔn)確率始終優(yōu)于PageRank算法,這是因?yàn)樾枰罅繉?shí)驗(yàn)才能獲取PageRank算法中的阻尼系數(shù)s,且會(huì)改變?cè)瓉淼木仃嚱Y(jié)構(gòu)。而LeaderRank[17]在PageRank的基礎(chǔ)上,加入一個(gè)與其他節(jié)點(diǎn)都有雙向連邊的節(jié)點(diǎn),實(shí)現(xiàn)網(wǎng)絡(luò)的強(qiáng)連通,以此得到一個(gè)無參數(shù)的算法。實(shí)驗(yàn)證明,這種算法比PageRank算法更準(zhǔn)確。

inKD-Pr算法在網(wǎng)絡(luò)規(guī)模小的時(shí)候準(zhǔn)確率比較低,這是因?yàn)镵-Shell算法對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)只能做粗粒度的劃分。節(jié)點(diǎn)的K-Shell值越大,節(jié)點(diǎn)就越重要[5]。但具體到兩個(gè)節(jié)點(diǎn),只有K-Shell值相差很大,比如在10倍以上時(shí),節(jié)點(diǎn)影響力才有顯著差距。而在小規(guī)模網(wǎng)絡(luò)中,節(jié)點(diǎn)的K-Shell值相差都不大,這就導(dǎo)致部分重要節(jié)點(diǎn)在用K-Shell分解法提取核心網(wǎng)絡(luò)時(shí)被刪除。在本文的實(shí)驗(yàn)中可以看到,隨著網(wǎng)絡(luò)規(guī)模變大,這種算法的準(zhǔn)確度也越高。在Ciation網(wǎng)絡(luò)中,inKD-Pr算法的準(zhǔn)確率甚至優(yōu)于LeaderRank算法,這是因?yàn)镵-Shell分解法可以有效剔除一些大度節(jié)點(diǎn)的干擾。

3.3 準(zhǔn)確率分析

本文將各算法挖掘出的Top-10節(jié)點(diǎn)與SIR模型挖掘出的Top-10節(jié)點(diǎn)進(jìn)行對(duì)比,比值為各算法挖掘Top-10節(jié)點(diǎn)的準(zhǔn)確率。表3的結(jié)果表明,網(wǎng)絡(luò)規(guī)模越大,度中心性挖掘算法的準(zhǔn)確性越低。相比,在不同規(guī)模的網(wǎng)絡(luò)中,PageRank算法和LeaderRank算法具有更好的穩(wěn)定性。本文提出的inKD-Pr算法隨著網(wǎng)絡(luò)規(guī)模增大,準(zhǔn)確率也越高。但由于SIR模型每一次傳播到達(dá)穩(wěn)態(tài)需要的時(shí)間比較長(zhǎng),本文最大只選取節(jié)點(diǎn)數(shù)為12 000多的社交網(wǎng)絡(luò)進(jìn)行計(jì)算。從實(shí)驗(yàn)結(jié)果可以預(yù)見,網(wǎng)絡(luò)規(guī)模越大,inKD-Pr算法挖掘重要節(jié)點(diǎn)的效果會(huì)更好。

表3 各算法挖掘出的Top-10節(jié)點(diǎn)準(zhǔn)確率與SIR模型對(duì)比

3.4 時(shí)間復(fù)雜度分析

本文提出的inKD-Pr算法是在K-Shell分解法的基礎(chǔ)上進(jìn)行改進(jìn)的,可近似看作O(n),與K-Shell分解法相同。PageRank的計(jì)算復(fù)雜度為O(mI),度中心性的時(shí)間復(fù)雜度為O(n),介數(shù)中心性的時(shí)間復(fù)雜度為O(mn),其中:n和m分別為網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊的數(shù)量;I為迭代次數(shù)。從表4可以看出,本文所提出的inKD-Pr算法計(jì)算復(fù)雜度相對(duì)較低。

表4 部分重要節(jié)點(diǎn)挖掘算法時(shí)間復(fù)雜度

4 結(jié) 語

猜你喜歡
復(fù)雜度準(zhǔn)確率中心
剪掉和中心無關(guān)的
在打造“兩個(gè)中心”中彰顯統(tǒng)戰(zhàn)擔(dān)當(dāng)作為
乳腺超聲檢查診斷乳腺腫瘤的特異度及準(zhǔn)確率分析
健康之家(2021年19期)2021-05-23 11:17:39
不同序列磁共振成像診斷脊柱損傷的臨床準(zhǔn)確率比較探討
2015—2017 年寧夏各天氣預(yù)報(bào)參考產(chǎn)品質(zhì)量檢驗(yàn)分析
一種低復(fù)雜度的慣性/GNSS矢量深組合方法
高速公路車牌識(shí)別標(biāo)識(shí)站準(zhǔn)確率驗(yàn)證法
別讓托養(yǎng)中心成“死亡中心”
求圖上廣探樹的時(shí)間復(fù)雜度
某雷達(dá)導(dǎo)51 頭中心控制軟件圈復(fù)雜度分析與改進(jìn)
甘洛县| 濮阳县| 陕西省| 武功县| 封开县| 汨罗市| 长丰县| 托克逊县| 项城市| 哈密市| 定陶县| 台中市| 呼和浩特市| 仪陇县| 内江市| 九龙县| 黎平县| 拉萨市| 阿瓦提县| 台东市| 遵义县| 深圳市| 新巴尔虎左旗| 盖州市| 中宁县| 揭东县| 烟台市| 黄浦区| 涞水县| 腾冲县| 普陀区| 年辖:市辖区| 类乌齐县| 浮梁县| 布尔津县| 枣庄市| 乐业县| 麻栗坡县| 弥勒县| 株洲市| 嵊泗县|