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

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

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

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

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

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

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

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

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

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

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