基于貝葉斯統(tǒng)計學習理論的高維空間多類別大樣本量形態(tài)變化模式識別

1、復雜網絡簡介,LiuChang,目錄,背景基本概念網絡模型基本搜索算法,目錄,背景,技術網絡,WWW,電力網,因特網,社會網絡,朋友關系網,科學引文網,科學家合著網,交通運輸網絡,航空網,道路交通網,城市公共交通網,,生物網絡,神經網絡,蛋白質相互作用網絡,生態(tài)網絡,復雜網絡（Complex Network）,復雜網絡（Complex Network）,定義 具有自組織、自相似、吸引子、小世界、無標度中部分或全部性質

2、的網絡稱為復雜網絡。,復雜網絡研究進程,1736，歐拉：哥尼斯堡七橋→圖論1950，Erdos, Renyi: 隨機圖論20世紀60年代末，弱連接的強度(Mark Granovetter)1998，Strogatz, Barabasi: 小世界實驗世紀之交，新紀元,為什么現在才開始研究復雜網絡？,計算機技術的發(fā)展：使我們擁有各種網絡的數據庫，并有可能對大規(guī)模的網絡進行實證研究普適性的發(fā)現：許多實際網絡具有相同的

3、定性性質且已有的理論不能描述和解釋理論研究的發(fā)展小世界網絡 (Small World Network), 無標度網絡 (Scale-free Network)統(tǒng)計物理學的研究手段,目錄,基本概念,對網絡結構的描述,度（Degree）：朋友的個數 介數（Betweenness）：經過我的最短路徑的條數集聚系數（群系數）（Clustering coefficient）：朋友的朋友還是不是朋友的情況最短路徑（

4、Shortest path）：兩個頂點之間邊數最少的路徑,,,,,,,,,聚類系數（clustering coefficient）,假設一個節(jié)點 有 條邊與它相連，這 個節(jié)點就是節(jié)點 的鄰居，則節(jié)點的聚類系數就是 的鄰居節(jié)點互相連接的邊數和鄰居節(jié)點全部連接的所有邊數的比值。,clustering coefficient,用 表示節(jié)點的聚類系數，其中鄰居節(jié)點相互連接的邊數用 表示，這些鄰居節(jié)點全部連接的所有邊數為 。網

5、絡的全局聚類系數 是所有節(jié)點 的聚類系數的平均值。,目錄,網絡模型,復雜網絡的結構,四種結構模型：規(guī)則網絡 小世界網絡隨機網絡 無標度網絡,規(guī)則網絡,,,,,,小世界網絡模型,WS小世界模型構造算法（隨機化重連）1、從最近鄰耦合網絡開始2、隨機化重連：以概率p隨機地重新連接網絡中的每個邊，即將邊的一個端點保持不變，而另一個端點取為網

6、絡中隨機選擇的一個節(jié)點。其中規(guī)定，任意兩個不同的節(jié)點之間至多只能有一條邊，并且每一個節(jié)點都不能有邊與自身相連。,小世界網絡模型,NW小世界模型構造算法（隨機化加邊）1、一個環(huán)狀的規(guī)則網絡開始2、隨機化加邊：以概率p在隨機選取的一對節(jié)點之間加上一條邊。其中，任意兩個不同節(jié)點之間至多只能有一條邊，并且每一個節(jié)點都不能有邊與自身相連。改變p值可以實現從最近鄰耦合網絡(p=0)向全局耦合網絡(p=1)轉變。當p足夠小和N足夠大時，NW小

7、世界模型本質上等同于WS小世界模型。,小世界網絡模型,,無標度網絡,BA無標度模型構造算法1、增長：從一個具有 個節(jié)點的網絡開始，每次引入一個新的節(jié)點，并連到 個已存在的節(jié)點上，這里2、優(yōu)先連接：一個新節(jié)點與一個已經存在的節(jié)點 相連接的概率 與節(jié)點 的度 ,節(jié)點 的度 滿足：,目錄,基本搜索算法,基本搜索算法,廣度優(yōu)先搜索算法深度優(yōu)先搜索算法最大度搜索算法隨機游走搜索算法K遍歷器隨機游走與最大度相結合

8、的混合算法,廣度優(yōu)先搜索算法（BFS）,首先查詢源節(jié)點的所有鄰居節(jié)點中是否存在目標節(jié)點，若存在，則將其返回給源節(jié)點；若不存在，鄰居節(jié)點將信息專遞給它們各自的鄰居節(jié)點，重復上述過程，直到找到目標節(jié)點為止。,深度優(yōu)先搜索算法（DFS）,DFS在源節(jié)點的鄰居節(jié)點中沿著樹的深度遍歷樹的節(jié)點,盡可能深的搜索樹的分支。當節(jié)點i的所有鄰居節(jié)點都已經被查詢過，搜索將回到把查詢信息傳遞給節(jié)點i那個起始節(jié)點。重復這一過程直到已發(fā)現目標節(jié)點為止。,最大度

9、搜索算法（DS）,DS是搜索其鄰居中最大節(jié)點度的節(jié)點。若該節(jié)點是目標節(jié)點,則返回信息。否則,繼續(xù)搜索最大節(jié)點度的節(jié)點的鄰居節(jié)點,直到搜索到目標節(jié)點為止。,隨機游走搜索算法（RWS）,隨機游走算法判斷源節(jié)點是不是目標節(jié)點,如果是,則停止搜索。否則,隨機選擇一個鄰居將信息傳送過去,直到找到目標節(jié)點為止。隨機游走的搜索步數大,但是在搜索的過程中信息產生量少,這樣在網絡中就不會產生很大的流量。,3種隨機游走算法,1 無限制隨機游走2

10、不返回上一步節(jié)點的隨機游走3 不重復訪問節(jié)點的隨機游走,K遍歷器隨機游走與最大度相結合的混合算法(KRDS),網絡中每個節(jié)點都知道它們鄰居節(jié)點的信息源節(jié)點隨機選擇k個鄰居節(jié)點傳送信息,若發(fā)現目標節(jié)點,則將返回信息。否則,它們分別選擇它們鄰居中度最大的節(jié)點傳遞信息。,K遍歷器隨機游走與最大度相結合的混合算法(KRDS),如果依然沒有搜索到目標節(jié)點,則用隨機游走進行查詢。重復這個過程直到搜索到目標節(jié)點為止。在該算法中,k有一