對(duì)稱性缺破算法是分布式算法的一個(gè)重要研究方向。近些年來,將核值維護(hù)問題作為一類對(duì)稱性缺破子問題在物理學(xué)等領(lǐng)域得到廣泛的研究。以往的核值維護(hù)算法不能高效地處理頂點(diǎn)加入/刪除這種情況下的核值維護(hù)問題。在一次算法迭代過程中,基于“匹配”的核值維護(hù)算法每個(gè)頂點(diǎn)最多只能關(guān)聯(lián)到一條邊,基于“優(yōu)邊集”的核值維護(hù)算法每個(gè)頂點(diǎn)最多只能關(guān)聯(lián)到一條優(yōu)勢(shì)邊。當(dāng)一個(gè)頂點(diǎn)加入或刪除時(shí),與該頂點(diǎn)相關(guān)聯(lián)的邊必須通過多次迭代才能處理完,這會(huì)造成大量的冗余計(jì)算從而導(dǎo)致算法的低效性。為了解決以往算法的局限性,提出了一種稱為“聯(lián)合邊集”的結(jié)構(gòu)。該“聯(lián)合邊集”結(jié)構(gòu)優(yōu)先處理具有高優(yōu)勢(shì)度的頂點(diǎn),使得與這些頂點(diǎn)相連的邊能夠在一次迭代中得到處理。通過理論證明表明,一個(gè)聯(lián)合邊集的加入或刪除仍然能夠使得圖中每一個(gè)頂點(diǎn)的核值最多變化1。與基于“匹配”和基于“優(yōu)邊集”的結(jié)構(gòu)相比,基于“聯(lián)合邊集”的結(jié)構(gòu)需要更少的迭代次數(shù)便能維護(hù)圖中每個(gè)頂點(diǎn)的核值,這將使得算法需要更少的重復(fù)訪問和冗余計(jì)算。進(jìn)一步將“聯(lián)合邊集”進(jìn)行劃分,可以將劃分得到的不相交邊集交給不同的線程進(jìn)行處理,這樣便可以利用多核處理器的優(yōu)勢(shì)得到并行的核值維護(hù)算法。除此以外,利用聯(lián)合邊集結(jié)... 

【文章來源】：華中科技大學(xué)湖北省 211工程院校 985工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：64 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

頂點(diǎn)核值的計(jì)算過程

法對(duì)很多頂點(diǎn)進(jìn)行不必要的訪問從而降低算法的性能。最后，每個(gè)頂其 2 跳鄰居內(nèi)其它頂點(diǎn)的核值計(jì)算索引信息。當(dāng)加入或刪除邊時(shí)，大要更新索引信息，這將花費(fèi)高昂的時(shí)間成本。為了解決 這些缺陷， hang 等人50]提出了一種基于 的快速核值維護(hù)在所有頂點(diǎn)之間建立了一個(gè)全序關(guān)系，并指出某個(gè)頂點(diǎn)核值的增長(zhǎng)只排在該頂點(diǎn)之后的鄰居的個(gè)數(shù)。基于 的核值維護(hù)算法克算法中存在的缺陷，提高了核值維護(hù)的運(yùn)行效率。特別是對(duì)于，能有效地減少算法運(yùn)行所消耗的時(shí)間。文章中給出了如圖 1-2 所示在頂點(diǎn) 0和頂點(diǎn) 4之間新加一條邊時(shí)， 算法需要遍歷點(diǎn)才能確認(rèn)只有頂點(diǎn) 0的核值會(huì)增加 1,而基于 的算法只需一個(gè)頂點(diǎn)便能夠找到所有核值會(huì)增加 1 的頂點(diǎn)集合。實(shí)驗(yàn)表明算法相比，基于 的核值維護(hù)算法在加邊的情況下最多升 3 個(gè)數(shù)量級(jí)。

這個(gè)結(jié)構(gòu)可以結(jié)合 算法或者基于 的找出核值真正發(fā)生變化的頂點(diǎn)集合。但是在一次迭代過程中，基于匹配能保證一個(gè)頂點(diǎn)最多加一條邊。對(duì)于一條邊 ，如果頂點(diǎn) 的核于頂點(diǎn) 的核值則稱邊 是頂點(diǎn) 的一條優(yōu)勢(shì)邊�；趦�(yōu)邊集的結(jié)構(gòu)只能次迭代中每個(gè)頂點(diǎn)最多增加或者刪除一條邊。所以當(dāng)在處理一個(gè)頂點(diǎn)并點(diǎn)增加或者刪除了多條優(yōu)勢(shì)邊時(shí)，文獻(xiàn) 53]中提出的兩種算法不能有效個(gè)高優(yōu)勢(shì)度頂點(diǎn)。慮圖 1-3 中的示例，虛線是新加的邊。頂點(diǎn) 4增加了 5 條優(yōu)勢(shì)邊，分別, 4 5, 4 6, 4 1, 4 7。頂點(diǎn) 17增加了 3 條優(yōu)勢(shì)邊，分 18, 17 14, 17 15。頂點(diǎn) 13增加了 2 條優(yōu)勢(shì)邊，分別是 13 11。對(duì)于頂點(diǎn) 4，在一次迭代過程中，基于匹配或者優(yōu)邊集的結(jié)構(gòu)最多新增的邊，這是因?yàn)轫旤c(diǎn) 4新加的 5 條邊都是頂點(diǎn) 4的優(yōu)勢(shì)邊。所以至 次迭代才能處理完頂點(diǎn) 4新增的 5 條邊。

【參考文獻(xiàn)】：
期刊論文
[1]基于圖著色的密集D2D網(wǎng)絡(luò)資源分配算法[J]. 孫彥贊,范衛(wèi)蓉,張舜卿,王濤,吳雅婷.  計(jì)算機(jī)工程. 2019(02)
[2]Learning dynamic dependency network structure with time lag[J]. Sizhen DU,Guojie SONG,Haikun HONG,Dong LIU.  Science China（Information Sciences）. 2018(05)
[3]大數(shù)據(jù)背景下機(jī)器學(xué)習(xí)算法的綜述[J]. 李成錄.  信息記錄材料. 2018(05)
[4]基于Pregel模型的分布式圖著色算法[J]. 甘瀛,王鑫,馮志勇,楊雅君.  計(jì)算機(jī)科學(xué)與探索. 2018(06)
[5]關(guān)于圖的極大獨(dú)立集的理論及生成方法[J]. 李兢,劉長(zhǎng)林,申石虎.  電子學(xué)報(bào). 1995(08)

碩士論文
[1]動(dòng)態(tài)圖中核值維護(hù)算法研究[D]. 王娜.華中科技大學(xué) 2018



本文編號(hào)：3327293