【摘要】：復(fù)雜網(wǎng)絡(luò)能控性問題是復(fù)雜網(wǎng)絡(luò)研究的一個核心問題。在過去的十年中復(fù)雜網(wǎng)絡(luò)能控性研究蓬勃發(fā)展并且涌現(xiàn)了大批出色的成果。但是卻很少有人關(guān)注任意拓?fù)浣Y(jié)構(gòu)的有向網(wǎng)絡(luò)能控的最小被控點集合和最優(yōu)輸入配置問題。針對復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)能控中的最小被控點集合和最優(yōu)輸入配置、復(fù)雜網(wǎng)絡(luò)精確能控中的最小驅(qū)動點集合和被控點集合、復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)能控性恢復(fù)等問題做了相關(guān)研究。主要研究內(nèi)容如下:針對最少的驅(qū)動節(jié)點被不同的輸入控制不一定能保證網(wǎng)絡(luò)能控這一問題研究了網(wǎng)絡(luò)能控的最小被控點集合和最優(yōu)輸入配置問題。首先,證明了最少驅(qū)動節(jié)點被不同的輸入控制能否保證網(wǎng)絡(luò)的能控性與網(wǎng)絡(luò)是否包含具有完美匹配的不可達(dá)強連通分量有關(guān)。其次結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)能控的輸入可達(dá)和完美匹配條件,指出了求解網(wǎng)絡(luò)能控的最小被控點集合和最優(yōu)輸入配置的關(guān)鍵是找到具有最大交集的最小不被匹配節(jié)點集合和最小不可達(dá)狀態(tài)節(jié)點集合�？紤]到復(fù)雜網(wǎng)絡(luò)一般具有大規(guī)模的特性,給出了帶有約束的組合優(yōu)化算法和基于最大權(quán)完美匹配的多項式算法來求解具有最大交集的最小不被匹配節(jié)點集合和最小不可達(dá)狀態(tài)節(jié)點集合。在一些模型和實證網(wǎng)絡(luò)上的仿真結(jié)果表明網(wǎng)絡(luò)的結(jié)構(gòu)能控性與網(wǎng)絡(luò)是否含有具有完美匹配的不可達(dá)強連通分量有關(guān),這一結(jié)果有助于更好地理解網(wǎng)絡(luò)能控性與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之間的關(guān)系。針對復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)能控的研究框架不適用于有向加權(quán)或者無向網(wǎng)絡(luò)的能控性這一問題,在Yuan等人的復(fù)雜網(wǎng)絡(luò)精確能控的基礎(chǔ)之上,研究了復(fù)雜網(wǎng)絡(luò)精確能控中的最小驅(qū)動點集合和被控點集合問題。首先,通過實例說明了不同的最小驅(qū)動點集合對網(wǎng)絡(luò)的控制力是不同的并引入了節(jié)點控制力的概念來衡量節(jié)點在網(wǎng)絡(luò)能控中的作用。其次根據(jù)節(jié)點的控制力,給出了求解最小驅(qū)動點集合的算法。在一些模型和實證網(wǎng)絡(luò)上的實驗結(jié)果表明利用該算法求解的最小驅(qū)動點集合在很多模型和實際網(wǎng)絡(luò)中可以保證網(wǎng)絡(luò)的精確能控性。最后針對最小驅(qū)動點集合在某些網(wǎng)絡(luò)中不能保證網(wǎng)絡(luò)能控的情況和求解網(wǎng)絡(luò)精確能控的最小被控點集合問題已被證明是NP-hard的現(xiàn)狀,給出了一種求解被控點集合的啟發(fā)式算法。針對一個完全能控的網(wǎng)絡(luò),惡意的攻擊或者隨機的節(jié)點、連邊失效都可能破壞網(wǎng)絡(luò)的能控性,引入能控缺乏度的概念衡量網(wǎng)絡(luò)能控缺乏的程度。對于能控缺乏度大于零的網(wǎng)絡(luò)圍繞最小輸入和最少需控制的節(jié)點提出了一種網(wǎng)絡(luò)修復(fù)算法。在真實網(wǎng)絡(luò)和ER隨機網(wǎng)絡(luò)、BA無標(biāo)度網(wǎng)絡(luò)上的仿真結(jié)果表明修復(fù)復(fù)雜網(wǎng)絡(luò)的代價與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之間有密切的關(guān)系。
[Abstract]:The controllability of complex networks is a core problem in the study of complex networks. In the past decade, the research on controllability of complex networks has flourished and a large number of outstanding achievements have emerged. However, few people pay attention to the problem of the minimum controlled point set and the optimal input configuration of the directed network with arbitrary topology. This paper studies the minimum controlled point set and optimal input configuration in complex network structure, the minimum driving point set and controlled point set in complex network, and the controllability recovery of complex network structure. The main contents of this paper are as follows: aiming at the problem that the least number of driving nodes under different input control does not guarantee the network controllability, the problem of the minimum set of controlled points and the optimal input configuration of the network is studied. Firstly, it is proved that whether the least drive nodes can be controlled by different inputs can guarantee the controllability of the network and whether the network contains unreachable and strongly connected components with perfect matching. Secondly, considering the input reachability and perfect matching condition of network structure, It is pointed out that the key to solve the minimum controlled point set and the optimal input configuration of the network is to find the minimum unmatched node set with the largest intersection and the minimum unreachable state node set. Considering that complex networks generally have large-scale characteristics, A combinatorial optimization algorithm with constraints and a polynomial algorithm based on maximum weight perfect matching are proposed to solve the minimum unmatched node set and the minimum unreachable state node set with maximum intersection. Simulation results on some models and empirical networks show that the structural controllability of the network is related to whether the network contains unreachable strongly connected components with perfect matching. This result is helpful to better understand the relationship between network controllability and network topology. The research framework of complex network structure controllability is not suitable for the controllability of directed weighted or undirected networks, and is based on the precise controllability of complex networks proposed by Yuan et al. The minimum set of driving points and the set of controlled points in complex networks are studied. Firstly, it is shown that the control forces of different sets of minimum driving points are different to the network, and the concept of node control force is introduced to measure the role of nodes in network controllability. Secondly, according to the control force of nodes, an algorithm for solving the minimum set of driving points is given. Experimental results on some models and empirical networks show that the minimum set of driving points solved by this algorithm can ensure the precise controllability of the networks in many models and practical networks. Finally, for the case that the minimum set of driving points can not guarantee the controllability of the network in some networks, and the problem of solving the minimum controlled set of precisely controllable points of the network has been proved to be the status quo of NP-hard. A heuristic algorithm for solving the set of controlled points is presented. For a completely controllable network, malicious attacks or random nodes, even the edge failure may destroy the controllability of the network. The concept of controllability deficiency is introduced to measure the degree of network controllability. A network repair algorithm is proposed for networks with controllable deficiency greater than zero around the minimum input and the least number of nodes that need to be controlled. In real networks and ER stochastic networks, the simulation results on BA scale-free networks show that the cost of repairing complex networks is closely related to the network topology.
【學(xué)位授予單位】：青島大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 趙明;周濤;陳關(guān)榮;汪秉宏;;復(fù)雜網(wǎng)絡(luò)上動力系統(tǒng)同步的研究進(jìn)展Ⅱ——如何提高網(wǎng)絡(luò)的同步能力[J];物理學(xué)進(jìn)展;2008年01期

2 朱小龍;張海天;劉暢;;邊介數(shù)標(biāo)準(zhǔn)偏差對復(fù)雜網(wǎng)絡(luò)同步能力的表達(dá)[J];江漢大學(xué)學(xué)報(自然科學(xué)版);2011年03期

3 榮智海;唐明;汪小帆;吳枝喜;嚴(yán)鋼;周濤;;復(fù)雜網(wǎng)絡(luò)2012年度盤點[J];電子科技大學(xué)學(xué)報;2012年06期

4 呂金虎;;復(fù)雜網(wǎng)絡(luò)的同步：理論、方法、應(yīng)用與展望[J];力學(xué)進(jìn)展;2008年06期

5 陳艷;杜園;吳薇;李常品;;節(jié)點狀態(tài)不同的兩個耦合網(wǎng)絡(luò)的同步[J];應(yīng)用數(shù)學(xué)與計算數(shù)學(xué)學(xué)報;2009年02期

6 陳關(guān)榮;;漫談系統(tǒng)與網(wǎng)絡(luò)[J];復(fù)雜系統(tǒng)與復(fù)雜性科學(xué);2010年Z1期

7 李興娜;劉恒;徐英;;星型脈沖耦合網(wǎng)絡(luò)同步的研究[J];泰山學(xué)院學(xué)報;2012年06期

8 梁義;王興元;;結(jié)點含時滯的具有零和非零時滯耦合的復(fù)雜網(wǎng)絡(luò)混沌同步[J];物理學(xué)報;2013年01期

9 王樹國;姚洪興;;非線性變時滯耦合復(fù)雜網(wǎng)絡(luò)的牽制控制[J];江蘇大學(xué)學(xué)報(自然科學(xué)版);2012年05期

10 劉興偉;張仲榮;張建剛;;復(fù)雜網(wǎng)絡(luò)同步理論在公交調(diào)度中的應(yīng)用[J];黑龍江科技學(xué)院學(xué)報;2010年05期

相關(guān)會議論文 前10條

1 孫偉剛;王如彬;李常品;;兩個復(fù)雜網(wǎng)絡(luò)的同步及其控制研究[A];第五屆全國復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會議論文（摘要）匯集[C];2009年

2 段志生;;復(fù)雜網(wǎng)絡(luò)同步與多智能體一致性控制的統(tǒng)一方法[A];第四屆全國動力學(xué)與控制青年學(xué)者研討會論文摘要集[C];2010年

3 李琨;;Robustness synchronizability of complex network[A];第五屆全國復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會議論文（摘要）匯集[C];2009年

4 范瑾;汪小帆;李翔;;具有相同度分布網(wǎng)絡(luò)的同步性與結(jié)構(gòu)特性分析[A];2006全國復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會議論文集[C];2006年

5 黃燕;吳亮;;演化的雪堆模型中的同步[A];蘇州市自然科學(xué)優(yōu)秀學(xué)術(shù)論文匯編(2008-2009)[C];2010年

6 趙軍產(chǎn);陸君安;吳曉群;;復(fù)雜動力網(wǎng)絡(luò)的優(yōu)化牽制控制[A];第四屆全國網(wǎng)絡(luò)科學(xué)學(xué)術(shù)論壇暨研究生暑期學(xué)校論文集[C];2008年

7 王海俠;陸啟韶;;四種規(guī)則耦合網(wǎng)絡(luò)同步穩(wěn)定性的理論和數(shù)值比較[A];第九屆全國動力學(xué)與控制學(xué)術(shù)會議會議手冊[C];2012年

8 趙明;;復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)與動力學(xué)行為之間的相互關(guān)系——以同步為研究視角[A];2009年第五屆全國網(wǎng)絡(luò)科學(xué)論壇論文集[C];2009年

9 呂金虎;;復(fù)雜網(wǎng)絡(luò)的同步：理論、方法、應(yīng)用與展望[A];第四屆全國網(wǎng)絡(luò)科學(xué)學(xué)術(shù)論壇暨研究生暑期學(xué)校論文集[C];2008年

10 段志生;;復(fù)雜網(wǎng)絡(luò)同步控制[A];第五屆全國復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會議論文（摘要）匯集[C];2009年

相關(guān)重要報紙文章 前10條

1 記者 郭宏鵬 實習(xí)生 溫遠(yuǎn)灝;電視網(wǎng)絡(luò)同步現(xiàn)場直播[N];法制日報;2014年

2 文莉莎;網(wǎng)絡(luò)首映《大灌籃》被迫推遲 新媒體無法同步首映[N];第一財經(jīng)日報;2008年

3 劉家紅 余作才 王國裕;桂林現(xiàn)場網(wǎng)絡(luò)同步拍賣涉訴資產(chǎn)[N];人民法院報;2012年

4 本報記者 范毅波;企業(yè)網(wǎng)絡(luò)“核裂變”[N];網(wǎng)絡(luò)世界;2002年

5 記者 劉礪平;數(shù)字時代如何過好“數(shù)字暑假”[N];新華每日電訊;2005年

6 高敘壯;人才同步抓 網(wǎng)絡(luò)同步建 課題同步練[N];戰(zhàn)士報;2006年

7 中興通訊;PTN技術(shù)承載無線高速路[N];通信產(chǎn)業(yè)報;2009年

8 吳錫平;文學(xué)在影視和網(wǎng)絡(luò)擠壓下[N];華夏時報;2002年

9 陳宇;VPN服務(wù)點對點[N];中國計算機報;2004年

10 ;IP over WDM與ATM和SDH的比較[N];人民郵電;2001年

相關(guān)博士學(xué)位論文 前10條

1 韓玉娟;復(fù)雜網(wǎng)絡(luò)的分群一致及穩(wěn)定控制研究[D];復(fù)旦大學(xué);2014年

2 周旋;牽制控制復(fù)雜網(wǎng)絡(luò)的同步及影響同步的參數(shù)問題[D];武漢大學(xué);2012年

3 王勁毅;基于若干控制策略的幾類復(fù)雜網(wǎng)絡(luò)同步研究[D];深圳大學(xué);2015年

4 何廣;帶有切換參數(shù)的復(fù)雜網(wǎng)絡(luò)的同步與控制問題分析[D];東華大學(xué);2016年

5 鄒云蕾;布爾控制網(wǎng)絡(luò)的系統(tǒng)分解[D];南京師范大學(xué);2016年

6 尹紅麗;復(fù)雜網(wǎng)絡(luò)能控性研究[D];青島大學(xué);2016年

7 杜瑞瑾;復(fù)雜網(wǎng)絡(luò)上的同步與滲流研究[D];江蘇大學(xué);2013年

8 傅晨波;復(fù)雜網(wǎng)絡(luò)同步若干問題研究[D];浙江大學(xué);2013年

9 朱軍芳;網(wǎng)絡(luò)上集體行為的動力學(xué)研究[D];中國科學(xué)技術(shù)大學(xué);2010年

10 王立夫;復(fù)雜網(wǎng)絡(luò)同步問題的研究[D];東北大學(xué);2010年

相關(guān)碩士學(xué)位論文 前10條

1 閆兵兵;基于滑�？刂评碚摰木W(wǎng)絡(luò)同步的研究[D];遼寧師范大學(xué);2015年

2 段之宇;EEG信號構(gòu)建的復(fù)雜腦網(wǎng)絡(luò)同步性研究[D];太原理工大學(xué);2016年

3 王希;基于隨機分塊模型的靜息態(tài)功能腦網(wǎng)絡(luò)可信度優(yōu)化[D];太原理工大學(xué);2016年

4 鐘杰;耦合布爾網(wǎng)絡(luò)的同步與控制問題研究[D];東南大學(xué);2015年

5 賈俊波;增長網(wǎng)絡(luò)及其上的疾病傳播[D];中北大學(xué);2016年

6 張啟超;復(fù)雜網(wǎng)絡(luò)若干同步控制問題研究[D];東北大學(xué);2014年

7 李爽;一類復(fù)雜網(wǎng)絡(luò)的同步研究[D];北方工業(yè)大學(xué);2016年

8 丁程丹;帶脈沖的部分耦合網(wǎng)絡(luò)的同步問題研究[D];東南大學(xué);2016年

9 陳鵬;復(fù)雜網(wǎng)絡(luò)上動力學(xué)系統(tǒng)部分同步現(xiàn)象的研究[D];廣西師范大學(xué);2016年

10 盧自寶;復(fù)雜網(wǎng)絡(luò)的牽制同步研究[D];大連海事大學(xué);2010年

，

本文編號：2419108