[發(fā)明專利]一種改變復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)控制類別的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201711261943.X
• 申請(qǐng)日: 2017-12-04
• 公開(kāi)（公告）號(hào): CN108009061B
• 公開(kāi)（公告）日: 2020-04-14
• 發(fā)明（設(shè)計(jì)）人: 張錫哲;李倩
• 申請(qǐng)（專利權(quán)）人: 東北大學(xué)
• 主分類號(hào): G06F11/22
• 分類號(hào): G06F11/22;G06N3/06;G06N3/08
• 代理公司: 北京易捷勝知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11613
• 代理人: 韓國(guó)勝

本發(fā)明提供一種改變復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)控制類別的方法，方法包括：針對(duì)待處理的冗余節(jié)點(diǎn)n，獲取網(wǎng)絡(luò)中能夠通過(guò)交錯(cuò)路徑到達(dá)冗余節(jié)點(diǎn)n的所有未飽和節(jié)點(diǎn)；構(gòu)造以冗余節(jié)點(diǎn)n為起點(diǎn)的交錯(cuò)網(wǎng)絡(luò)；采用最小割算法處理交錯(cuò)網(wǎng)絡(luò)，獲取冗余節(jié)點(diǎn)n與交錯(cuò)路徑上所有未飽和節(jié)點(diǎn)斷開(kāi)時(shí)所需要?jiǎng)h除的最少邊的集合；識(shí)別網(wǎng)絡(luò)中包括冗余節(jié)點(diǎn)n的交錯(cuò)環(huán)，并基于識(shí)別的交錯(cuò)環(huán)，確定出破壞交錯(cuò)環(huán)所需刪除的連邊；刪除最少邊的集合中的所有連邊，以及刪除確定出的用于破壞交錯(cuò)環(huán)所需刪除的連邊；在網(wǎng)絡(luò)中選擇一條從冗余節(jié)點(diǎn)n出發(fā)的交錯(cuò)路徑，刪除選擇的交錯(cuò)路徑中的一個(gè)匹配邊，使得冗余節(jié)點(diǎn)n轉(zhuǎn)換為輸入節(jié)點(diǎn)。上述方法極大的降低了轉(zhuǎn)化代價(jià)，具有更高的效率。

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

本發(fā)明涉及網(wǎng)絡(luò)技術(shù)，特別是一種改變復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)控制類別的方法。

背景技術(shù)

現(xiàn)實(shí)生活中許多事物及其之間的關(guān)系都可以建模為網(wǎng)絡(luò)，如社會(huì)系統(tǒng)中的人際關(guān)系網(wǎng)、科學(xué)家協(xié)作網(wǎng)、流行病傳播網(wǎng)和交通網(wǎng),生態(tài)系統(tǒng)中的神經(jīng)元網(wǎng)、基因調(diào)控網(wǎng)和蛋白質(zhì)交互網(wǎng)和食物鏈網(wǎng)絡(luò),科技系統(tǒng)中的電話網(wǎng)、因特網(wǎng)和萬(wàn)維網(wǎng)等。對(duì)這種日益復(fù)雜的網(wǎng)絡(luò)系統(tǒng)的結(jié)構(gòu)及行為分析是理解其內(nèi)在規(guī)律的前提。要保證這些系統(tǒng)的正常運(yùn)作，就有必要研究復(fù)雜網(wǎng)絡(luò)的控制。例如，在交通網(wǎng)絡(luò)中，為盡量避免交通擁塞，可以通過(guò)增加道路或拓寬道寬來(lái)減緩交通堵塞現(xiàn)象，對(duì)哪些道路或路口進(jìn)行操作才能起到作用？在食物鏈網(wǎng)絡(luò)中，物種受環(huán)境影響而滅絕影響了食物鏈的結(jié)構(gòu)，如何來(lái)保證生態(tài)系統(tǒng)的可持續(xù)性？在因特網(wǎng)中，對(duì)那些節(jié)點(diǎn)施加控制能保證網(wǎng)絡(luò)的穩(wěn)定性，調(diào)整哪些節(jié)點(diǎn)的通信從而維持網(wǎng)絡(luò)的正常通信狀態(tài)？社交網(wǎng)絡(luò)中，選擇哪些節(jié)點(diǎn)進(jìn)行信息發(fā)布或調(diào)控，使得控制消息傳播的影響范圍？這些都可借助對(duì)復(fù)雜網(wǎng)絡(luò)控制的研究來(lái)分析。

為了控制復(fù)雜網(wǎng)絡(luò)，需要向網(wǎng)絡(luò)中的部分節(jié)點(diǎn)輸入控制信號(hào)，通過(guò)節(jié)點(diǎn)間邊的連接，驅(qū)動(dòng)網(wǎng)絡(luò)的所有節(jié)點(diǎn)達(dá)到期望的狀態(tài)，這些用來(lái)輸入控制信號(hào)的節(jié)點(diǎn)稱為驅(qū)動(dòng)節(jié)點(diǎn)。為了完全控制網(wǎng)絡(luò)所有節(jié)點(diǎn)的狀態(tài)，所需的最少的驅(qū)動(dòng)節(jié)點(diǎn)集合稱為最小驅(qū)動(dòng)節(jié)點(diǎn)集(MIS)。網(wǎng)絡(luò)的一個(gè)MIS可以通過(guò)尋找網(wǎng)絡(luò)的最大匹配來(lái)得到。具體的，對(duì)于網(wǎng)絡(luò)任意的最大匹配，未匹配點(diǎn)即為驅(qū)動(dòng)節(jié)點(diǎn)。

對(duì)一個(gè)實(shí)際網(wǎng)絡(luò)G＝(V,E)，頂點(diǎn)集V，邊集E，其節(jié)點(diǎn)數(shù)為N＝|V|，邊數(shù)為L(zhǎng)＝|E|。將圖G對(duì)應(yīng)的二分圖表示為B＝(V⁺,V^-,E)，對(duì)于二分圖B的最大匹配M，V^-中的未匹配點(diǎn)稱為驅(qū)動(dòng)節(jié)點(diǎn)，V⁺中的未匹配點(diǎn)稱為未飽和點(diǎn)。由于網(wǎng)絡(luò)中可能存在多個(gè)最大匹配，因此，網(wǎng)絡(luò)存在多個(gè)可能的最小驅(qū)動(dòng)節(jié)點(diǎn)集。如果一個(gè)節(jié)點(diǎn)屬于某一個(gè)最小驅(qū)動(dòng)節(jié)點(diǎn)集，則稱其為輸入節(jié)點(diǎn)；如果一個(gè)節(jié)點(diǎn)不出現(xiàn)在任何最小驅(qū)動(dòng)節(jié)點(diǎn)集，則稱其為冗余節(jié)點(diǎn)。其中，輸入節(jié)點(diǎn)是指所有可能驅(qū)動(dòng)節(jié)點(diǎn)，驅(qū)動(dòng)節(jié)點(diǎn)是指當(dāng)前最大匹配下的驅(qū)動(dòng)節(jié)點(diǎn)。

圖1示出了一個(gè)簡(jiǎn)單網(wǎng)絡(luò)及其節(jié)點(diǎn)類別的示意圖。圖1中，A圖為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖；B圖為兩個(gè)不同的最小驅(qū)動(dòng)節(jié)點(diǎn)集示意圖，分別為{1，3}和{1，2}；C圖為節(jié)點(diǎn)的控制分類示意圖，其中輸入節(jié)點(diǎn)為{1，2，3}，冗余節(jié)點(diǎn)為{4}。

上述節(jié)點(diǎn)分類在實(shí)際網(wǎng)絡(luò)應(yīng)用中，具有重要的應(yīng)用價(jià)值。例如，輸入節(jié)點(diǎn)代表控制信號(hào)的可能輸入位置，冗余節(jié)點(diǎn)表示控制信號(hào)在網(wǎng)絡(luò)中的傳遞節(jié)點(diǎn)。現(xiàn)有工作表明在人類蛋白質(zhì)交互網(wǎng)絡(luò)中，冗余節(jié)點(diǎn)傾向?yàn)榘┌Y的相關(guān)基因或藥物靶標(biāo)節(jié)點(diǎn)，并且通過(guò)改變網(wǎng)絡(luò)拓?fù)潢P(guān)系，將冗余節(jié)點(diǎn)改變?yōu)轵?qū)動(dòng)節(jié)點(diǎn)，可能是疾病狀態(tài)和健康狀態(tài)轉(zhuǎn)換的關(guān)鍵因素。因此深入研究復(fù)雜網(wǎng)絡(luò)控制中的節(jié)點(diǎn)類型轉(zhuǎn)換，具有重要的實(shí)際意義。

現(xiàn)有技術(shù)中公開(kāi)了一種網(wǎng)絡(luò)控制模式轉(zhuǎn)換的問(wèn)題，即將一個(gè)集中控制模式的網(wǎng)絡(luò)轉(zhuǎn)換為分散控制模式或?qū)⒁粋€(gè)分散控制模式的網(wǎng)絡(luò)轉(zhuǎn)換為集中控制模式。其中，集中模式對(duì)應(yīng)網(wǎng)絡(luò)中絕大多數(shù)節(jié)點(diǎn)為冗余節(jié)點(diǎn)。分散模式對(duì)應(yīng)網(wǎng)絡(luò)中絕大多數(shù)節(jié)點(diǎn)為輸入節(jié)點(diǎn)。具體地，通過(guò)將網(wǎng)絡(luò)中的邊全部反向來(lái)可以實(shí)現(xiàn)模式之間的相互轉(zhuǎn)換。上述網(wǎng)絡(luò)控制模式轉(zhuǎn)換的方案通過(guò)反向特定的一小部分邊，甚至是某一條邊就可以實(shí)現(xiàn)模式轉(zhuǎn)換。但是，如何選擇這些特定邊，如何找到最少的邊，并未給出方法。