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

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

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

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

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

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

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

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

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

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

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