二進制遞歸網路的多故障容錯性分析

《二進制遞歸網路的多故障容錯性分析》是依託電子科技大學,由董強擔任醒目負責人的青年科學基金項目。

基本介紹

• 中文名：二進制遞歸網路的多故障容錯性分析
• 依託單位：電子科技大學
• 項目類別：青年科學基金項目
• 項目負責人：董強

項目摘要

並行計算系統的性能很大程度上取決於連線計算結點的互連網路的有效性。為了保證系統在某些結點出現故障時仍能繼續運行的能力，非常有必要研究互連網路的容錯性。二進制遞歸網路（BRN）具有結構規則、易於分割等優點，是理論研究和實際套用中頗受歡迎的網路結構。現有的BRN容錯性研究成果大多基於故障數小於連通度、網路仍然連通的少故障假設，不能反映故障數大於連通度、網路不再連通的多故障模式下網路被破壞的程度。本項目針對BRN多故障容錯性研究中的3個關鍵科學問題開展研究，首先，提出最大連通分支規模和基於鄰接矩陣特徵值的特徵連通度參數，解決不連通網路容錯性度量問題；其次，研究故障網路中最大遞歸子網路規模和最長圈/路徑嵌入性，給出容錯性好的網路具有的特徵；最後，基於小世界網路理論改進BRN，設計容錯性好的小世界立方體網路。預期成果能夠完善互連網路容錯性度量體系，為我國高性能可信計算機的發展提供理論依據和技術支持。

結題摘要

現實世界中許多系統都可以抽象為網路模型。為了保證網路受到結點攻擊時的數據交換能力，非常有必要研究網路的容錯性。本項目從哈密爾頓圈存在性、關鍵傳播結點識別及其在推薦系統中的套用3個方面開展研究。首先，針對現有廣義蜂窩環網路上哈密爾頓圈構造方法不完備的問題，我們設計了奇數階的廣義蜂窩環網路中哈密爾頓圈的一系列構造方法，並證明了這些方法的正確性和完備性。其次，我們提出VoteRank算法來識別複雜網路中的一組去中心化的、具有最優傳播能力的重要節點，真實網路上的SIR和SI實驗結果表明，該算法在時間複雜度、信息傳播速度和最終影響範圍上都優於現有方法。最後，我們在現有基於網路結構的推薦算法中考慮用戶社交網路、用戶偏好的時間效應、可調參數的遍歷等信息，並在真實數據集上將其與原始算法進行對比，實驗結果表明改進算法進一步提高了推薦結果的準確率和多樣性。基於上述研究成果，我們總計發表7篇SCI期刊論文，另有1篇論文被SCI期刊Physica A錄用待發表，1篇論文已投稿SCI期刊Mobile Information Systems，目前正在審稿中。