《網路的小世界結構及其上隨機遊動的混合時》是依託首都師範大學，由吳憲遠擔任項目負責人的面上項目。
基本介紹
- 中文名：網路的小世界結構及其上隨機遊動的混合時
- 項目類別：面上項目
- 項目負責人：吳憲遠
- 依託單位：首都師範大學
項目摘要,結題摘要,
項目摘要
小世界效應（small world effect）是現實複雜網路（real-world complex networks）的重要特徵。本項目將首先致力於研究現實複雜網路小世界性的內在形成機制。其次，我們將研究小世界網路上的隨機遊動（random walk）。通過研究小世界網路上的隨機遊動的混合時（mixing time），我們研究複雜網路上基於隨機遊動的快速抽樣方法。 本項目具體聚焦於以下兩個方面：一、分析現實複雜網路所以多為小世界的內在原因， 在此基礎上，建立合理刻畫網路演化過程的數學模型，並證明模型的小世界性。二、對建立 的新的小世界模型， 研究其上隨機遊動的混合時。通過給出過程混合時的合適的上下界估計，探討過程短時內達到混合的可能性。對第二個問題的解答，比如，證明過程在短時內達到混合，就恰好給出了複雜網路上相對於度序列的一個好的抽樣方法。
結題摘要
複雜網路是近二十年來走進人們日常生活的重要的新鮮事物，以網際網路為代表的各類網路的蓬勃發展，正改變或已經改變了客觀世界，也改變著人們的生活方式。在套用數學領域，將對複雜網路的研究納入嚴格數學的範疇，解釋並預測網路的各項結構特徵，行為特徵就成為套用數學該發展的一個新方向。本項目的主要目標是研究複雜網路的小世界機制，即網路是如何發展成小世界的。其次，我們研究小世界網路上過程：隨機遊走過程和尾達滲流過程。一類重要的複雜網路是幾何網路，其特徵是，網路的節點是歐式空間中實在的點，而建立點與點之間的連線的費用隨兩點之間的歐氏距離的增長而增長。網際網路，電力網，道路交通網等就是這樣的網路。觀察認為，幾何網路的小世界來源於人們因需求激發的有意識作為，即網路本來不是小世界的，因為我們需要小世界，於是人為改造網路，最後建設成為小世界。對幾何網路的小世界原理的數學研究源於Watts和Newman早期的工作，Newman和Watts建立數學模型證明，在非小世界網上，人為引入“shortcuts”（即直接建立遠距離節點之間的連線），可以使所得到的網路是小世界的。我們的研究基於以下觀察：只有距離足夠大的兩點，它們之間引入shortcut，才可能導致網路的小世界化。為此在最大限度地與現實相合的前提下，我們建立Poisson幾何小世界模型，證明了這個觀點。該文於2017年發表在網路數學的專業雜誌Internet Mathematics上。該結果是項目研究的主要成果，它深刻而精緻地刻畫了幾何網路的小世界機制。作為以上結果的一個補充，我們還研究了所謂“修正的Newman-Watts模型”，我們證明，以上機制不僅導致小世界，而且恰好導致小世界。項目的另一個目標是研究小世界網路上的過程。對Poisson幾何小世界模型和修正的Newman-Watts模型，我們分別研究其上的隨機遊動，我們證明它們是快速混合的，即過程以極快（相比於網路規模）的速度達到平穩分布。另一方面，對經典的小世界網路，隨機圖模型，我們研究其上的尾達滲流。我們得到兩方面的成果：一是時間常數的存在性及偏差機率的衰減速率。二是尾達時間的方差估計問題，事實上，我們證明該時間的方差可以是有限的、對數增長以及次線性增長的。方差估計問題是首達滲流關心的主要問題，我們的方法和結論對該問題的研究有重要借鑑作用，這也是我們下一段研究的主要課題。
