網路科學中譜圖理論

《網路科學中譜圖理論》是依託上海交通大學，由張曉東擔任項目負責人的面上項目。

基本介紹

• 中文名：網路科學中譜圖理論
• 項目類別：面上項目
• 項目負責人：張曉東
• 依託單位：上海交通大學

項目摘要

網路科學是由統計物理、計算機科學、生物科學、社會科學、數學（圖論）等學科相互交叉形成的一門新學科，其中譜圖理論是網路科學重要組成部分和研究網路科學重要的數學方法和工具。本項目著重研究網路科學中提出的數學問題和網路數學模型。主要圍繞能夠揭示確定性的圖、（偽）隨機圖、給定度分布隨機圖、小世界網路、無標度網路等網路拓撲結構和動力學行為中重要的不變數和特徵（包括平均距離、直徑、團數、匹配、聚集係數、介數、節點中心、社團劃分、度分布及其相關性等）與網路的特徵值（包括譜密度、譜稀疏性和譜隙等）和特徵向量（特徵空間）之間的內在定性關係以及定量刻畫開展深入細緻地研究和探索。研究反映和揭示各種隨機圖的本質和性質的偽隨機圖理論和譜極值理論。本項目通過提出網路科學研究的新思路以及採用新手段來發展和完善網路科學堅實的數學理論基礎與網路科學研究的數學方法，同時拓展組合矩陣論與圖論的廣度和深度。

結題摘要

網路科學是由統計物理、計算機科學、生物科學、社會科學、數學（圖論）等學科相互交叉形成的一門新學科，其中譜圖理論是網路科學重要組成部分和研究網路科學重要的數學方法和工具。本項目主要圍繞具有給定結構的網路，特別具有隨機圖某種性質的確定性的圖、偽隨機圖、經典隨機圖以及它的各種推廣的隨機網路包括給定度分布的隨機圖、小世界網路和無標度網路等拓撲結構和動力學行為與代表它們的不同類型的矩陣包括鄰接矩陣、拉普拉斯矩陣、無符號拉普拉斯矩陣、距離矩陣等特徵值和特徵向量之間關係開展細緻深入的研究。在國內外重要期刊上一共發表了 27篇 SCI 論文，組織了第八屆組合論國際學術會議。 本項目的重要結果包括下面九個方面， 第一、解決了Sills 和 Wang等人提出關於距離矩陣的譜與圖的拓撲參數和度分布的兩個猜想； 第二、證明了Lin 等人提出關於完全多部圖可以由它們的距離譜所確定的猜想。第三、建立了圖的拉普拉斯係數、圖的譜、圖的匹配多項式、圖的參數、圖的能量等之間聯繫。第四、建立了小世界網路的拉譜拉斯譜與等周常數之間重要的不等式。從數學上嚴格證明了小世界網路具有大的聚集係數和小的直徑。第五、 提出了一種基於公共近鄰和距離的新算法用來提高複雜網路中丟失的鏈路預測精度。第六、全部解決了Gorgol關於極值圖論不含k個頂點為3的路的並的邊的極值以及極圖的情況的猜想。第七、給出給定弧的最大譜半徑的上界， 並且刻畫達到極值的所有極圖。第八、基於有限域構造了一類代數CAYLEY 圖， 該類圖具有很好的偽隨機的性質和特徵。 第九、得到了樹的拓撲結構的性質與樹的局部子樹之間關係。本項目研究成果著重揭示網路拓撲結構和動力學行為中重要的不變數與網路的特徵值和特徵向量之間的內在定性關係以及定量刻畫。這些關於圖譜理論的新的結果和新的方法將可能套用到線性系統快速算法、圖的稀疏化、局部的隨機遊動、網路科學等領域。 另一方面這些研究成果和新方法將豐富和發展譜圖理論的研究內容和深度，建立譜圖理論與其他學科之間，例如計算機科學、算法理論等，內在聯繫，同時拓展組合矩陣論與圖論的廣度和深度。本項目研究成果為網路科學研究進一步提供數學理論根據和新的數學方法和技巧。