復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論1

1、復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第一章第一章 緒論緒論第一章 緒論l1.1 引言l1.2 網(wǎng)絡(luò)科學理論發(fā)展的三個時期l1.3 復(fù)雜網(wǎng)絡(luò)的概念和特性l1.4 數(shù)理統(tǒng)計基礎(chǔ)l1.5 圖論的基本概念l1.6 復(fù)雜網(wǎng)絡(luò)的研究內(nèi)容和意義l1.7 本書內(nèi)容安排2 21.1 引言網(wǎng)絡(luò)無處不在：水利網(wǎng)、航海網(wǎng)、公路網(wǎng)、鐵路網(wǎng)、 信息網(wǎng)、電力網(wǎng)、商業(yè)網(wǎng)網(wǎng)絡(luò)如此廣泛、如此重要。 如何開辟出一條研究思路，揭示網(wǎng)絡(luò)拓撲結(jié)構(gòu)的形成機制，探索網(wǎng)絡(luò)的演化規(guī)律和整體行為，認識網(wǎng)絡(luò)內(nèi)部深奧的動力學特性，挖掘網(wǎng)絡(luò)展現(xiàn)出的廣泛、潛在的應(yīng)用價值等問題，正引起國內(nèi)外學術(shù)界的高度重視。3 31.1 引言 21世紀是復(fù)雜性和網(wǎng)絡(luò)化的世紀。

2、 從20世紀七八十年代開始，在國際上形成了非線性科學和復(fù)雜性問題的研究熱潮。 尤其是20世紀90年代以來，人類已經(jīng)生活在一個充滿各種各樣復(fù)雜網(wǎng)絡(luò)的世界中，許多復(fù)雜性問題都可以從復(fù)雜網(wǎng)絡(luò)的角度去研究。 從網(wǎng)絡(luò)觀點重新認識事物并帶來革命性變化的典型實例Google的誕生。它的PageRank算法利用了WWW的網(wǎng)絡(luò)結(jié)構(gòu)。4 41.1 引言 隨著生命科學的發(fā)展、網(wǎng)絡(luò)時代的到來以及人們交流和經(jīng)濟活動的全球化，人們早就開始觀察和思考生命網(wǎng)絡(luò)、技術(shù)網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、社會網(wǎng)絡(luò)等呈現(xiàn)的一些普遍現(xiàn)象或問題。所有這些問題看上去互不相關(guān)，實際上這些都是復(fù)雜網(wǎng)絡(luò)所反映的普遍規(guī)律和復(fù)雜網(wǎng)絡(luò)領(lǐng)域?qū)W者們所要研究的課題。 近10

3、年來，復(fù)雜網(wǎng)絡(luò)的研究正滲透到眾多不同的學科。推進復(fù)雜性科學的交叉研究，深入探索和科學理解復(fù)雜網(wǎng)絡(luò)的定性特征與定量規(guī)律，使它獲得廣泛的應(yīng)用，對全球科學和社會的發(fā)展具有十分重大的長遠意義。5 5返回 目錄1.2 網(wǎng)絡(luò)科學理論發(fā)展的三個時期1.2.1 規(guī)則網(wǎng)絡(luò)理論階段1.2.2 隨機網(wǎng)絡(luò)理論階段1.2.3 復(fù)雜網(wǎng)絡(luò)理論階段6 61.2.1 規(guī)則網(wǎng)絡(luò)理論階段 規(guī)則網(wǎng)絡(luò)理論的發(fā)展得益于圖論和拓撲學等應(yīng)用數(shù)學的發(fā)展。圖論是一種強有力的研究工具和研究方法。歷史上著名的四個圖論問題：1.哥尼斯堡七橋問題 哥尼斯堡是當時東普魯士的首都，今俄羅斯加里寧格勒市，普萊格爾河橫貫其中，這條河上建有七座橋，將河中間的兩個

4、島和河岸聯(lián)結(jié)起來，如圖所示。有人在閑暇散步時提出：能不能每座橋都只走一遍，最后又回到原來的位置。7 71.2.1 規(guī)則網(wǎng)絡(luò)理論階段 大數(shù)學家歐拉用一種獨特的方法給出了解答。他把兩座小島和河的兩岸分別看作四個點，而把七座橋看作這四個點之間的連線，于是這個問題就簡化成：能不能用一筆就把這個圖形畫出來？經(jīng)過進一步的分析，歐拉得出結(jié)論：不可能每座橋都走一遍，最后回到原來的位置，并且給出了所有能夠一筆畫出來的圖形所應(yīng)具有的條件。2.哈密頓問題 英國數(shù)學家哈密頓于1859年以游戲的形式提出：把一個正十二面體的二十個節(jié)點看成二十個城市，要求找出一條經(jīng)過每個城市恰好一次而回到出發(fā)點的路線，如圖所示。這條路線就

5、稱“哈密頓圈”。8 81.2.1 規(guī)則網(wǎng)絡(luò)理論階段 換一種說法，對于一個給定的網(wǎng)絡(luò)，在確定起點和終點后，如果存在一條路徑能夠穿過該網(wǎng)絡(luò)，就稱該網(wǎng)絡(luò)存在“哈密頓路徑”。哈密頓路徑問題在20世紀70年代初，終于被證明是“NP完備”的，也就是說具有這樣性質(zhì)的問題，難于找到一個有效的算法。實際上對于某些節(jié)點數(shù)不到100的網(wǎng)絡(luò)，利用現(xiàn)有最好的算法和計算機可能也需要幾百年才能確定是否存在一條這樣的路徑。3.四色猜想 1852年，畢業(yè)于倫敦大學的格思里來到一家科研單位做地圖著色工作時，發(fā)現(xiàn)了一個有趣的現(xiàn)象：每幅地圖都可以用四種顏色著色，使得有共同邊界的國家著上不同的顏色。這個結(jié)論能不能從數(shù)學上加以嚴格證明呢

6、？9 91.2.1 規(guī)則網(wǎng)絡(luò)理論階段 18781880年兩年間，著名的律師兼數(shù)學家肯普和泰勒兩人分別提交了證明四色猜想的論文，宣布證明了四色定理。但是到了1890年，數(shù)學家赫伍德以自己的精確計算指出了肯普的證明存在漏洞，而不久之后，泰勒的證明也被人們否定了。 進入20世紀以來，隨著電子計算機的問世，由于演算速度迅速提高，加之人機對話的出現(xiàn)，大大加快了對四色猜想證明的進程。1976年，美國伊利諾斯大學哈肯和阿佩爾在大學里的兩臺不同的電子計算機上，用了1200個小時，作了100億判斷，終于完成了四色定理的證明。四色猜想的計算機證明，轟動了世界。它不僅解決了一個歷時100多年的難題，而且成為了數(shù)學史

7、上一系列新思維的起點。10101.2.1 規(guī)則網(wǎng)絡(luò)理論階段4.旅行商問題 給定N個節(jié)點和任意一對節(jié)點vi，vj之間的距離為dist（vi，vj），要求找出一條閉合的回路，該回路經(jīng)過每個節(jié)點有且僅有一次，并且該回路的費用最?。ㄟ@里的費用是指每段路徑的距離和）。 實際上，旅行商問題就是加權(quán)的哈密頓路徑問題，因此求解旅行商問題的精確解是NP難的。若將問題限定在歐氏平面上，就稱為歐幾里德旅行商問題，但是它也是NP難的。因此，通常用來解決TSP問題的解法都是近似算法。第一個歐幾里德旅行商問題的多項式近似算法是由Arora于1998年使用隨機平面分割和動態(tài)規(guī)劃方法給出的。11111.2.2 隨機網(wǎng)絡(luò)理論階

8、段 1959年，兩個匈牙利著名的數(shù)學家Erds和Rnyi建立了著名的隨機圖理論，用相對簡單的隨機圖來描述網(wǎng)絡(luò)，簡稱ER隨機圖理論。ER隨機圖理論對圖論理論研究的影響長達近40年，以至于在隨后的近半個世紀，隨機圖一直是科學家研究真實網(wǎng)絡(luò)最有力的武器。 隨機網(wǎng)絡(luò)是指在由N個節(jié)點構(gòu)成的圖中以概率p隨機連接任意兩個節(jié)點而成的網(wǎng)絡(luò)，即兩個節(jié)點之間連邊與否不再是確定的事，而是由概率p決定?；蚝唵蔚卣f，在由N個節(jié)點構(gòu)成的圖中，可以存在N（N1）/2條邊，從中隨機連接M條邊所構(gòu)成的網(wǎng)絡(luò)就叫隨機網(wǎng)絡(luò)。如果選擇M=pN（N1）/2，則這兩種構(gòu)造隨機網(wǎng)絡(luò)模型的方法就可以聯(lián)系起來。12121.2.2 隨機網(wǎng)絡(luò)理論階段

9、 隨機圖和經(jīng)典圖之間最大的區(qū)別在于引入了隨機的方法，使得圖的空間變得更大，其數(shù)學性質(zhì)也發(fā)生了巨大的變化。Erds和Rnyi系統(tǒng)研究了當N時隨機圖性質(zhì)與概率p的關(guān)系，他們發(fā)現(xiàn)：隨機網(wǎng)絡(luò)的許多重要的性質(zhì)都是隨著網(wǎng)絡(luò)規(guī)模的擴大而突然出現(xiàn)的，也就是說對于給定概率p，隨著網(wǎng)絡(luò)規(guī)模的擴大，要么幾乎所有的隨機圖具有某種性質(zhì)，要么幾乎每一個圖都不具有該性質(zhì)。 Erds數(shù)：Erds本人的Erds數(shù)是0；曾與Erds合作發(fā)表過文章的人的Erds數(shù)是1；沒有與Erds合作發(fā)表過文章，但與Erds數(shù)為1的人合作發(fā)表過文章的人，其Erds數(shù)是2；幾乎每一個當代數(shù)學家都有一個有限的Erds數(shù)，而且這個數(shù)往往非常小，小得出

10、乎本人的預(yù)料。13131.2.3 復(fù)雜網(wǎng)絡(luò)理論階段1.小世界效應(yīng)的發(fā)現(xiàn) 美國的瓦茨和斯特羅加茨于1998年發(fā)表了題為“小世界”網(wǎng)絡(luò)的群體動力行為的論文，推廣了“六度分離”的科學假設(shè)，提出了小世界網(wǎng)絡(luò)模型?！傲确蛛x”最早來自于20世紀60年代美國哈佛大學心理學家Milgram對社會調(diào)查的推斷，是指在大多數(shù)人中，任意兩個素不相識的人通過朋友的朋友，平均最多通過6個人就能夠彼此認識?！癒evin Bacon”游戲 /14141.2.3 復(fù)雜網(wǎng)絡(luò)理論階段2.社會網(wǎng)絡(luò)中弱連接優(yōu)勢的發(fā)現(xiàn) 哈佛大學Granovetter的弱連接優(yōu)勢理論指出：與一個人的工作和事

11、業(yè)關(guān)系最密切的社會關(guān)系并不是“強連接”，而常常是“弱連接”?！叭踹B接”雖然不如“強連接”那樣堅固，卻有著極快的、可能具有低成本和高效能的傳播效率。而在強連接關(guān)系下，成員彼此之間具有相似的態(tài)度，他們高度的互動頻率通常會強化原本認知的觀點而降低了與其它觀點的融合，故強連接網(wǎng)絡(luò)通常不能提供創(chuàng)新機會。相對于強連接關(guān)系，弱連接則能夠在不同的團體間傳遞非冗余性的訊息，使得網(wǎng)絡(luò)成員能夠增加修正原先觀點的機會。因此，擁有更多弱連接的人擁有信息流通的優(yōu)勢，往往可得到更多工作機會和業(yè)務(wù)選擇機會。15151.2.3 復(fù)雜網(wǎng)絡(luò)理論階段16163.無標度性質(zhì)的發(fā)現(xiàn) Barabsi等人于1999年發(fā)表了題為隨機網(wǎng)絡(luò)中標度

12、的涌現(xiàn)的論文，提出了一個無標度網(wǎng)絡(luò)模型，指出在復(fù)雜網(wǎng)絡(luò)中節(jié)點的度分布具有冪指數(shù)函數(shù)的規(guī)律（節(jié)點的度是指與該節(jié)點連接的邊數(shù)，而度分布是指網(wǎng)絡(luò)中所有節(jié)點的度的分布情況），其度分布可以用冪律形式 進行描述。 無標度網(wǎng)絡(luò)中，絕大部分的節(jié)點的度相對較低，而存在少量的度相對很高的節(jié)點，因此這類網(wǎng)絡(luò)也成為非均勻網(wǎng)絡(luò)。大量復(fù)雜系統(tǒng)都存在這種少數(shù)但高連通的遵循冪律分布的節(jié)點，可稱為“集散節(jié)點”。許多不同的復(fù)雜系統(tǒng)，其網(wǎng)絡(luò)結(jié)構(gòu)都是無標度網(wǎng)絡(luò)，都是由少數(shù)集散節(jié)點主控的系統(tǒng)。( )P kk1.2.3 復(fù)雜網(wǎng)絡(luò)理論階段4.復(fù)雜網(wǎng)絡(luò)研究的新時代 對于大量真實的網(wǎng)絡(luò)系統(tǒng)而言，它們既不是規(guī)則網(wǎng)絡(luò)，也不是隨機網(wǎng)絡(luò)，而是介于兩者

13、之間的某種網(wǎng)絡(luò)。 復(fù)雜網(wǎng)絡(luò)研究在過去10年才得到迅速發(fā)展，其原因有以下幾個方面： 計算機技術(shù)的迅猛發(fā)展。 普適性的發(fā)現(xiàn)。 理論研究也有了突破。1717返回 目錄1.3 復(fù)雜網(wǎng)絡(luò)的概念和特性1.3.1 復(fù)雜網(wǎng)絡(luò)的概念1.3.2 復(fù)雜網(wǎng)絡(luò)的特性18181.3.1 復(fù)雜網(wǎng)絡(luò)的概念1.系統(tǒng)和網(wǎng)絡(luò) 系統(tǒng)是由相互作用和相互依賴的若干組成部分結(jié)合的具有特定功能的有機整體。 從三個方面理解系統(tǒng)的概念： 系統(tǒng)是由若干要素（部分）組成的。 系統(tǒng)有一定的結(jié)構(gòu)。 系統(tǒng)有一定的功能。系統(tǒng)有如下的屬性：集合性、相關(guān)性、層次性、整體 性、涌現(xiàn)性、對環(huán)境的適應(yīng)性19191.3.1 復(fù)雜網(wǎng)絡(luò)的概念 從圖論意義上理解網(wǎng)絡(luò)，網(wǎng)絡(luò)是

14、指由節(jié)點和連線構(gòu)成的圖。有時用帶箭頭的連線表示從一個節(jié)點到另一個節(jié)點存在的某種順序關(guān)系。有時在節(jié)點或連線旁標出數(shù)值，稱為點權(quán)或線權(quán)，有時不標任何數(shù)。 網(wǎng)絡(luò)和系統(tǒng)通常是密切聯(lián)系的，如果用節(jié)點表示系統(tǒng)的各個組成部分即系統(tǒng)的元素，兩個節(jié)點之間的連線表示系統(tǒng)元素之間的相互作用，那么網(wǎng)絡(luò)就為研究系統(tǒng)提供了一種新的描述方式。20201.3.1 復(fù)雜網(wǎng)絡(luò)的概念2.復(fù)雜性 復(fù)雜性還不能算作一個嚴格的科學概念，人們也沒有給出一個公認的復(fù)雜性定義。 復(fù)雜性是相對于簡單性而存在的，它是在客觀事物的聯(lián)系、運動和變化中表現(xiàn)出來的一種狀態(tài)，表達了一種不可還原的特征，而不是孤立、靜止和顯而易見的特性。復(fù)雜性科學打破了線性、

15、均衡、簡單還原的傳統(tǒng)范式，極大地促進了科學的發(fā)展。3.復(fù)雜系統(tǒng) 一般認為復(fù)雜系統(tǒng)具有以下特征：非線性與動態(tài)性、非周期性和開放性、奇怪吸引性、結(jié)構(gòu)自相似性（分形）。另外，復(fù)雜系統(tǒng)還具有突現(xiàn)性、不穩(wěn)性、不確定性、不可預(yù)測性等特征。21211.3.1 復(fù)雜網(wǎng)絡(luò)的概念4.復(fù)雜網(wǎng)絡(luò) 復(fù)雜網(wǎng)絡(luò)可以看作由一些具有獨立特征的又與其他個體相互連接的節(jié)點的集合，每個個體可視為圖中一個節(jié)點，節(jié)點間的相互連接視為圖中的邊。復(fù)雜網(wǎng)絡(luò)包括兩個層面：作為其連接拓撲結(jié)構(gòu)的圖和作為其狀態(tài)和功能的系統(tǒng)。 錢學森給出了復(fù)雜網(wǎng)絡(luò)的一個較嚴格的定義：具有自組織、自相似、吸引子、小世界、無標度中部分或全部性質(zhì)的網(wǎng)絡(luò)稱為復(fù)雜網(wǎng)絡(luò)。 原則上

16、說，任何包含大量組成單元（或子系統(tǒng)）的復(fù)雜系統(tǒng)，當我們把構(gòu)成單元抽象成節(jié)點，單元之間的相互作用抽象為邊時，都可以當作復(fù)雜網(wǎng)絡(luò)來研究。22221.3.2 復(fù)雜網(wǎng)絡(luò)的特性1.復(fù)雜性 主要表現(xiàn)在以下幾個方面： 網(wǎng)絡(luò)規(guī)模龐大。 連接結(jié)構(gòu)的復(fù)雜性。 節(jié)點的復(fù)雜性。 網(wǎng)絡(luò)時空演化過程復(fù)雜。 部分IP地址連接示意圖 朋友關(guān)系網(wǎng) 網(wǎng)絡(luò)連接的稀疏性。 多重復(fù)雜性融合。23231.3.2 復(fù)雜網(wǎng)絡(luò)的特性2.小世界特性 大多數(shù)網(wǎng)絡(luò)盡管規(guī)模很大，但任意兩個節(jié)點間卻有一條相當短的路徑。3.無標度特性 節(jié)點的度分布具有冪指數(shù)函數(shù)的規(guī)律。因為冪指數(shù)函數(shù)在雙對數(shù)坐標中是一條直線，這個分布與系統(tǒng)特征長度無關(guān)，所以該特性被稱為無

17、標度性質(zhì)。4.超家族特性 盡管網(wǎng)絡(luò)不同，只要組成網(wǎng)絡(luò)的基本單元（最小子圖）相同，它們的拓撲性質(zhì)的重大輪廓外形就可能具有相似性，這種現(xiàn)象被稱為超家族特性。2424返回 目錄1.4 數(shù)理統(tǒng)計基礎(chǔ)1.4.1 概率論基礎(chǔ)1.4.2 數(shù)理統(tǒng)計基礎(chǔ)1.4.3 統(tǒng)計假設(shè)及檢驗1.4.4 一元線性回歸分析25251.4.1 概率論基礎(chǔ)1.隨機試驗 對隨機現(xiàn)象的統(tǒng)計規(guī)律性進行的觀察稱為隨機試驗（簡稱試驗）。 一個隨機試驗有以下特點： 可重復(fù)性。 可觀察性。 隨機性。2.樣本空間、隨機事件 事件也是一個集合，事件間的關(guān)系及運算可以按照集合論中集合之間的關(guān)系及運算來處理。26261.4.1 概率論基礎(chǔ)3.頻率、概率

18、 頻率、概率的定義 概率的性質(zhì)4.古典概型與幾何概型5.條件概率、全概率公式、貝葉斯公式、獨立事件判定6.隨機變量和隨機向量 隨機變量的分布函數(shù) 離散型隨機變量及其概率分布 連續(xù)型隨機變量及其概率密度 隨機向量的聯(lián)合分布函數(shù)與邊緣分布函數(shù) 27271.4.1 概率論基礎(chǔ)7.隨機變量的數(shù)字特征 數(shù)學期望、方差、標準差、協(xié)方差、相關(guān)系數(shù)8.大數(shù)定理、中心極限定理契比雪夫不等式三個著名的大數(shù)定理：契比雪夫大數(shù)定理 伯努利大數(shù)定理 辛欣大數(shù)定理兩個著名的中心極限定理： 列維-林德伯格中心極限定理 棣莫弗-拉普拉斯中心極限定理28281.4.2 數(shù)理統(tǒng)計基礎(chǔ)1.總體、樣本 總體、簡單隨機樣本、抽樣的概念

19、2.統(tǒng)計量 設(shè)X1，X2，Xn是來自總體的一個樣本，g（X1，X2，Xn）是樣本的某一函數(shù)。若g中不含未知參數(shù)，則g（X1，X2，Xn）稱為一個統(tǒng)計量。 常用的統(tǒng)計量有：樣本平均值、樣本方差、樣本標準差、樣本k階原點矩、樣本k階中心矩3.抽樣分布 統(tǒng)計量的分布稱為抽樣分布。 三個常用的抽樣分布：29291.4.2 數(shù)理統(tǒng)計基礎(chǔ) 分布 典型模式 分位點 性質(zhì)t分布 典型模式 分位點 性質(zhì)F分布 典型模式 分位點 性質(zhì)303021.4.3 統(tǒng)計假設(shè)及檢驗1.假設(shè)檢驗的基本思想 假設(shè)檢驗又稱統(tǒng)計假設(shè)檢驗，是一種統(tǒng)計推斷方法?！凹僭O(shè)”是指根據(jù)經(jīng)驗、知識、問題的目的、問題的要求等因素，提出的有關(guān)總體分布

20、的一個命題?！凹僭O(shè)”是否正確或者是否接受，需要根據(jù)試驗樣本進行判斷。利用從該總體中抽取的樣本，用數(shù)理統(tǒng)計的方法判斷假設(shè)是否正確，稱為檢驗。2.假設(shè)檢驗的相關(guān)概念 原假設(shè)H0、對立假設(shè)H1、參數(shù)假設(shè)、非參數(shù)假設(shè)、簡單假設(shè)、復(fù)合假設(shè) 拒絕域S0、接受域S131311.4.3 統(tǒng)計假設(shè)及檢驗 進行一次假設(shè)檢驗一般可以分為以下幾個步驟： 根據(jù)實際情況提出檢驗假設(shè)和備擇假設(shè)； 選擇檢驗統(tǒng)計量g（X1，X2，Xn），并獲知在H0成立時統(tǒng)計量g的分布； 根據(jù)檢測統(tǒng)計量的分布，查出在給定的顯著水平（01）的情況下檢驗H0的臨界值，從而推出H0的拒絕域S0； 根據(jù)樣本值進行最終判斷：當樣本值屬于H0的拒絕域S0

21、時，則拒絕H0，否則接受H0。32321.4.3 統(tǒng)計假設(shè)及檢驗3.假設(shè)檢驗時常見的兩類錯誤 在進行假設(shè)檢驗時，存在著兩類錯誤：以真為假錯誤和以假為真錯誤。當H0為真時，檢驗結(jié)論為拒絕H0，稱為以真為假錯誤或第一類錯誤；當H0為假時，檢驗作出接受H0的推斷，稱為以假為真錯誤或第二類錯誤。犯第一類錯誤的概率是 P拒絕H0H0成立犯第二類錯誤的概率是 P接受H0H0不成立 在樣本容量n和樣本值確定的情況下，當減小時，一般會增大，反之亦然。33331.4.3 統(tǒng)計假設(shè)及檢驗4.t檢驗 t檢驗是一種常用的假設(shè)檢驗方法。所謂t檢驗就是利用滿足t分布的t統(tǒng)計量進行假設(shè)檢驗。 設(shè)X1，X2，Xn是來自服從標

22、準正態(tài)分布 總體的樣本，X1，X2，Xn的平均值為 ，標準差為S，則容易證明統(tǒng)計量 是一個t分布。34342( ,)N X/XtSn1.4.4 一元線性回歸分析1.回歸問題分析 回歸分析是研究相關(guān)關(guān)系的一種數(shù)學工具，它能根據(jù)一個變量的觀察值去估計另一個變量所取得的值。 在回歸分析中，通常有兩個變量，其中x是可觀測、可控制的普通變量，而Y為隨機變量。如何尋找和判定Y與x之間是否存在著顯著的某種相關(guān)關(guān)系呢? 如果存在，如何利用它們的關(guān)系進行預(yù)測和控制呢？ 采用近似方法進行相關(guān)關(guān)系的分析。 回歸分析的任務(wù)就是根據(jù)試驗結(jié)果去估計回歸函數(shù)，討論有關(guān)點估計、區(qū)間估計、假設(shè)檢驗等問題。35351.4.4 一

23、元線性回歸分析 一般地，回歸分析的步驟是： 判斷變量之間是否能夠建立回歸模型； 由分析選擇回歸模型； 根據(jù)數(shù)據(jù)估計回歸方程的各個未知參數(shù)； 進行回歸模型的統(tǒng)計假設(shè)檢驗； 利用回歸模型進行問題的分析及預(yù)測。2.一元線性回歸 一元線性回歸模型 經(jīng)驗回歸函數(shù) 經(jīng)驗回歸方程3636Yabx( )xabxyabx1.4.4 一元線性回歸分析3.一元回歸問題的假設(shè)檢驗 常用的檢測方法有兩種：F檢驗法和t檢驗法。 造成回歸不顯著的原因可能有如下幾種情況： 影響Y取值的因素，除了x外，還有其它不可忽略的因素； Y與x之間的關(guān)系不是線性的，而存在著其它的關(guān)系； Y與x不存在關(guān)系。 因此當回歸效果不顯著時，需要進

24、一步的分析原因，進而分別處理。3737返回 目錄1.5 圖論的基本概念1.5.1 圖的基本概念1.5.2 圖的路和連通性1.5.3 圖的基本運算1.5.4 樹與生成樹1.5.5 圖的矩陣表示38381.5.1 圖的基本概念 網(wǎng)絡(luò)是一個包含了大量個體以及個體之間相互作用的系統(tǒng)，假如把個體視為網(wǎng)絡(luò)的節(jié)點，把個體間的相互作用視為網(wǎng)絡(luò)節(jié)點與節(jié)點之間的連接，那么任意復(fù)雜系統(tǒng)都可以表示為圖的形式。 節(jié)點是圖最基本的、最重要的組成元素。根據(jù)所研究網(wǎng)絡(luò)的不同，圖中節(jié)點具有的含義也不同。 圖是對系統(tǒng)中基本單元（稱為節(jié)點）集合，以及每兩個基本單元之間關(guān)系（邊）集合之間關(guān)系的描述。圖可以定義為一個三元組G（V，E，

25、）。 集合Vv1，v2，vn稱為節(jié)點集 集合Ee1，e2，em稱為邊集 是邊集E到節(jié)點集V的一個映射，稱為關(guān)聯(lián)函數(shù)39391.5.1 圖的基本概念 V中的元素vi稱為節(jié)點或頂點（node或vertex），E中的元素em稱為邊、弧或連線（edge，arc或line），且E中的每條邊em都有V的一對節(jié)點（vi，vj）與之對應(yīng)。 通常將G簡單地表示為二元組G（V，E），其中E就包含了上面提到的E和，即這里E中描述的是節(jié)點對的集合已經(jīng)包含連接關(guān)系。 有些圖可能包含不同類型的節(jié)點和不同權(quán)重的邊。 不同類型的圖的定義：40401.5.1 圖的基本概念無向圖有向圖加權(quán)圖無權(quán)圖無權(quán)圖可以看成每條邊的權(quán)值均為1

26、的等權(quán)圖圖的階NV 圖的邊數(shù)ME有限圖：階和邊數(shù)都有限的圖自環(huán)：兩端點（邊所連接的節(jié)點也稱端點）相同的邊平行邊（或重邊）：有公共起點并且有公共終點的兩 條邊零圖（或無邊圖）：只有節(jié)點沒有邊的圖平凡圖：只有一個節(jié)點的零圖空圖：無邊無節(jié)點的圖41411.5.1 圖的基本概念鄰邊：從同一個節(jié)點伸向其他不同節(jié)點的邊鄰點：同一條邊的兩個端點互稱關(guān)聯(lián)：一條邊上的節(jié)點和該條邊的關(guān)系簡單圖：不存在重邊和自環(huán)的圖復(fù)圖：存在重邊或自環(huán)的圖完全圖：所有節(jié)點對（對于有向圖是指起點終點對） 之間均有一條邊連接的簡單圖N階無向完全圖有N（N1）/2條邊N階有向完全圖有N（N1）條弧42421.5.1 圖的基本概念【例例1

27、.11.1】簡單分析下圖的特點，并寫出三元組G G表示形式（注意連接邊的方向性）和該圖對應(yīng)的無向完全圖。解：圖的階數(shù)N和邊數(shù)M分別為5和6，因此該圖為有限圖。圖中不存在重邊和自環(huán)，因此是簡單圖，其三元組表示形式為G G（V，E，），其中 Vv1，v2，v3，v4，v5 Ee1，e2，e3，e4，e5，e643431.5.1 圖的基本概念（e1）（v2，v1）, （e2）（v1，v5）, （e3）（v2，v5）, （e4）（v5，v4）, （e5）（v5，v3）, （e6）（v4，v3） 若用二元組G G（V，E）表示，則V還是用上式表示，而E表示如下：E（v2，v1），（v1，v5），（v2，

28、v5），（v5，v4），（v5，v3），（v4，v3） 該簡單圖對應(yīng)的完全圖如下圖所示，可以看出該完全圖的邊數(shù)為（54）210。44441.5.2 圖的路和連通性1.路徑、簡單路徑、基本路徑 圖G中的第k條路徑（鏈、途徑）是指由圖中的節(jié)點和邊交替出現(xiàn)而構(gòu)成的有限序列 。 路徑 的起點： 路徑 的終點： 路徑 的內(nèi)點：其余節(jié)點 路徑 長：序列中邊的條數(shù) 由于簡單圖中不存在重邊，所以簡單圖中的第k條路徑可以完全由經(jīng)過的節(jié)點序列表示，所以 可簡記為 。45450 1 1 221()knnnwv ev e vve vkwkwkwkw0vnv(11)ivin kw0 1 21()knnwv v vvv1

29、.5.2 圖的路和連通性簡單路徑（或行跡）：路徑所經(jīng)歷的邊互不相同基本路徑（或軌道）：路徑所經(jīng)歷的節(jié)點互不相同（ 但是起點和終點可以相同）回路：路徑的起點和終點相同簡單回路：閉的簡單路徑基本回路（或圈）：閉的基本路徑k圈：長度為k的圈自環(huán)：長度為1的圈三角形：長度為3的圈Hamilton路：包含每個節(jié)點有且僅有一次的路徑46461.5.2 圖的路和連通性2.連通性連通圖：圖G中任意每對vi、vj節(jié)點之間都有至少一條 路徑存在非連通圖：圖G中至少有一對節(jié)點之間不存在路徑圖G的一個連通分支：若G中的任意兩個節(jié)點屬于且僅 屬于節(jié)點子集Vi時才連通，則稱 圖G中由Vi及其連邊組成的子圖Gi常被用于表示

30、圖G的分支數(shù) =1的圖稱為連通圖 1的圖稱為非連通圖對于任何圖G，節(jié)點數(shù)N、邊數(shù)M和分支數(shù)滿足4747MNw1.5.2 圖的路和連通性 在有向圖中，圖的連通性被分為三種：弱連通、單連通和強連通。有向圖的底圖：將有向圖的所有邊去除方向性所得到 的無向圖弱連通有向圖：底圖是連通圖的有向圖單連通有向圖：在一個有向圖中，任意兩個節(jié)點vi、vj 若只存在vi到vj或者vj到vi路徑強連通有向圖：若vi、vj之間存在可互達的路徑從節(jié)點vi到vj的距離：從vi到vj的路徑中需要經(jīng)歷的最 少邊數(shù)從節(jié)點vi到vj的最短路徑：對應(yīng)的路徑圖G的直徑：所有節(jié)點對的距離中的最大的距離48481.5.2 圖的路和連通性假

31、設(shè)圖G=（V，E）是一個簡單圖， ， 。割點：若去除節(jié)點v，使原來連通的圖變成不連通或分 支數(shù)有增加，即（Gv）（G），這樣的 節(jié)點v割邊（橋）：若去除邊e（但不去除端點）后，使圖G 變?yōu)椴贿B通或使得（Ge）（G）， 這樣的邊e塊：不含割點的連通圖（連通分支）圖G的塊：圖G的不含割點的最大連通分支 上述討論的連通性、割點、割邊及塊的概念均與圖中邊的方向性無關(guān)。在研究這些性質(zhì)時，所有的圖均看作無向圖。4949vVeE1.5.2 圖的路和連通性【例例1.21.2】寫出下圖（a）中起點和終點均為v1的路徑，并簡單分析下面三個圖之間的關(guān)系以及各有什么特點。解：從圖（a）中可以得知從v1到v1的其中兩條

32、路徑為 w1（v1e1v2e3v5e2v1）（v1v2v5v1） w2（v1e2v5e4v4e6v3e5v5e3v2e1v1） （v1v5v4v3v5v2v1） 50501.5.2 圖的路和連通性 在這兩條路徑中，w1和w2的長度分別為3和6。因為路徑w1的邊和節(jié)點均不同，因此它既是簡單路徑又是基本路徑。而路徑w2的邊都不同而節(jié)點有相同的，因此只是簡單路徑。 圖（a）是圖（b）的底圖，且圖（b）為單連通有向圖。圖（a）中包含一個割點為v5，但不存在割邊。圖（c）為圖（a）刪除一條邊后剩余的圖，圖中存在兩條割邊，分別是e4 ， e5。51511.5.3 圖的基本運算 對于圖G（VG，EG）和H（

33、VH，EH），若有VGVH，EGEH，則稱G和H是恒等的，記為GH。 若圖G和圖H之間存在一個保持各節(jié)點連接關(guān)系的一一對應(yīng)，則稱G和H“同構(gòu)”，記為G H，該一一對應(yīng)稱為G和H之間的一個同構(gòu)映射。 圖的同構(gòu)關(guān)系是一種等價關(guān)系，這種等價關(guān)系將圖分為若干等價類，而同構(gòu)的兩個圖屬于同一類。同一類的圖具有相同的結(jié)構(gòu)，其差別僅在于節(jié)點和邊的名稱不同。 常用一個節(jié)點和邊都沒有名稱的圖作為同構(gòu)圖等價類的代表。52521.5.3 圖的基本運算 若VH是VG的子集，EH是EG的子集，則稱H是G的子圖，G是H的母圖。 若H是G的子圖，且VHVG，則稱H為G的生成子圖。 若H是G的子集，且HG，則稱H為G的真子圖。

34、 假設(shè)G1和G2均是圖G的子圖，若G1與G2沒有公共節(jié)點，則稱它們“點不相交”。 假設(shè)G1和G2均是圖G的子圖，若G1與G2沒有公共邊，則稱它們“無重邊”。53531.5.3 圖的基本運算 G1與G2中所有邊構(gòu)成的圖稱為它們的“并”，記為G1G2。 若G1與G2沒有公共邊，則它們的并稱為“直和”，記為G1G2。 若G1與G2有公共邊，G1與G2中的公共邊構(gòu)成的圖稱為它們的“交”，記為G1G2。 若G1和G2有公共邊，則從G1中去掉G2具有的邊，所得到的子圖稱為它們的“差”，記為G1G2。 從圖G1，G2的并中去掉它們的交，得到的子圖稱為它們的“環(huán)和”，記為G1 G2。 從圖G中去掉圖G1的邊得

35、到的子圖稱為圖G1的“補”。54541.5.3 圖的基本運算 把圖G節(jié)點集合V的一個真子集Vr中所有節(jié)點都合為一個，稱為“在圖G中收縮Vr”。 原圖G中所有與Vr中的所有節(jié)點連接的邊變化為與此重合點連接的邊。 如此得到的圖稱為“圖G關(guān)于Vr的收縮圖”，記為GVr。55551.5.4 樹與生成樹1.樹樹：不含圈的連通圖或者說任意兩個節(jié)點間有且只有 一條路徑的圖樹枝：樹中的邊樹葉：樹中度（一個節(jié)點的度指的是與該節(jié)點的鄰邊 數(shù)）為1的節(jié)點分支點：度大于1的節(jié)點林：每個分支都是樹的非連通圖 樹是圖論中最簡單又最重要的一類圖，廣泛應(yīng)用于計算機科學的數(shù)據(jù)結(jié)構(gòu)中，比如二叉樹、堆、Trie 樹以及數(shù)據(jù)壓縮中的

36、霍夫曼樹等。56561.5.4 樹與生成樹 若一個簡單圖G滿足以下相互等價的條件之一，那么G是一棵樹： G是沒有圈的連通圖； G沒有圈，但是在G中任意添加一條邊，就能形成一個回路； G是連通圖，并且3節(jié)點完全圖不是G的子圖； G內(nèi)的任意兩個節(jié)點能被唯一的路所連接； G是連通圖，具有N1條邊且沒有簡單回路的圖（節(jié)點數(shù)為N）； G是連通的，但刪去G的任意一條邊而不刪去與該邊連接的節(jié)點后，所得的圖將不是連通的，即G中的每一條邊均是割邊（橋）。57571.5.4 樹與生成樹2.生成樹 假設(shè)圖H是圖G的生成子圖，并且兩個圖的分支數(shù)相同，若圖H是林，則稱圖H是圖G的生成林；若圖H是樹，則稱圖H是圖G的生成

37、樹。 每個圖G都含有生成林或者生成樹。圖G有生成樹的充要條件是圖G為連通圖。 若從圖G中去除其子圖H包含的邊，剩余的圖稱為H在G中的余圖。若H是G的生成林（樹），則剩余的圖稱為H在G中的余林（樹）。 若H為G的生成樹，則H的邊稱為樹枝，而G中所有非生成樹的邊稱為弦。由弦構(gòu)成的圖就是H的余樹，但余樹并不一定是樹。58581.5.4 樹與生成樹 對于一個連通圖G，有許多方法都能構(gòu)造出它的生成樹，其中最簡單的方法是破圈法。具體方法為：在圖G中任取一個圈，去掉該圈中的一條邊，若剩余圖仍為連通圖，就繼續(xù)尋找下一個圈并同樣去掉其中一條邊，直至得到圖G的一個無圈連通生成子圖，即得到圖G的一棵生成樹。 對于一

38、個非連通圖G，只要求出其各個連通分支的生成樹，就能得到它的生成林。 一個連通圖的生成樹一般不是唯一的，只有當連通圖G本身也是樹時，其生成樹才唯一。59591.5.4 樹與生成樹 假設(shè)H是連通圖G的一棵生成樹，而M和N分別是圖G的邊數(shù)和節(jié)點數(shù)，則樹枝數(shù)為N1，弦數(shù)為MN1。 不妨設(shè) 為弦，設(shè) 是H加 產(chǎn)生的圈，則稱 為對應(yīng)于弦 的基本回路，而稱 為對應(yīng)于生成樹H的基本回路系統(tǒng)。 不同的生成樹將產(chǎn)生不同的基本回路系統(tǒng)，但基本回路系統(tǒng)所含的基本回路的個數(shù)是唯一的，為MN1。 若圖G是一個加權(quán)連通圖，H是G的一棵生成樹，H的每條邊所賦權(quán)值之和稱為生成樹H的權(quán)，記為 。加權(quán)連通圖G的具有最小權(quán)值的生成樹

39、稱為該圖的最小生成樹，一個圖的最小生成樹也一定是唯一的。6060121,MNe ee121,MNC CCHiCie1.5.4 樹與生成樹【例例1.31.3】下面兩個圖分別示出圖G G的無權(quán)和加權(quán)兩種形式，請根據(jù)圖分別回答以下問題。（1）畫出圖（a）的含有共同邊的兩個子圖，并分別畫出它們的交、差、環(huán)和；（2）畫出圖（a）兩個無共同邊的子圖，并畫出它們的直和、各自對于圖G G的補；（3）畫出圖（a）的兩棵生成樹，并畫出各自對應(yīng)的余樹；（4）分別畫出圖（a）收縮真子集v2，v3后的圖；畫出圖（b）的最小生成樹。61611.5.4 樹與生成樹解：（1）圖（a）的有共同邊的兩個子圖G G1，G G2如下

40、圖所示。 由這兩個子圖可得，G G1G G2，G G1G G2，G G2G G1，G G1 G G2的結(jié)果如下圖所示。62621.5.4 樹與生成樹（2）圖（a）的兩個無共同邊的子圖G G3，G G4如下圖所示。 由這兩個子圖可得，G G3G G4，G G3的補，G G4的補的結(jié)果如下圖所示。63631.5.4 樹與生成樹（3）圖（a）的第一個生成樹G G5和其對應(yīng)的余樹，第二個生成樹G G6和其對應(yīng)的余樹如下圖所示。（4）將合并后的節(jié)點用vb表示，則圖（a）收縮真子集v2，v3后的結(jié)果和圖（b）的最小生成樹如下圖所示。64641.5.5 圖的矩陣表示 圖的矩陣表示架起了圖論與矩陣論之間的橋梁

41、，通過這種表示方法就能借助于矩陣的理論和分析方法來研究圖論中的問題。1.鄰接矩陣 鄰接矩陣描述了節(jié)點與節(jié)點之間的鄰接關(guān)系，通常會用一個方陣A來表示，方陣中的元素用 表示。 鄰接矩陣分為有向圖鄰接矩陣和無向圖鄰接矩陣。 一個無權(quán)簡單圖的鄰接矩陣 可以定義為6565ija ijN NAa1,( ,)0,( ,)ijijijv vEav vE1.5.5 圖的矩陣表示 對于一個N階簡單無向圖G，其鄰接矩陣具有以下性質(zhì)： A是一個主對角線上的元素皆為0，其余元素為0或1的對角矩陣，且A的任何一行（列）的元素之和都等于其相應(yīng)節(jié)點的度。 若記 ，則矩陣C的主對角線上的元素為可見對角線元素 恰好為相應(yīng)節(jié)點 的

42、度 。 對于任意非負整數(shù)k， 中的第i行第j列元素表示圖G中連接節(jié)點 和 的長度為k的路徑的數(shù)目。6666 2ijN NCAc2111NNNiiijjiijijijjjca aaakiicivikkAivjv1.5.5 圖的矩陣表示 對于一個N階簡單有向圖G，其鄰接矩陣具有以下性質(zhì)： 第i行元素之和為節(jié)點 的出度 （以節(jié)點 為起點的鄰邊數(shù)），其第j列元素之和為節(jié)點 的入度 （以節(jié)點 為終點的鄰邊數(shù)）。 若記 ，其中 表示矩陣A的轉(zhuǎn)置矩陣，則 表示圖G中的某種節(jié)點個數(shù)，這種節(jié)點的鄰邊中有兩條鄰邊分別以 和 為起點。 若記 ，則 表示圖G中的某種節(jié)點個數(shù)，這種節(jié)點的鄰邊中有兩條鄰邊分別以 和 為終

43、點。6767ivoutikivivinikiv TijN NAACcTA1Nijiljllca aivjv TijN NA AFf1Nijliljlfa aivjv1.5.5 圖的矩陣表示 一個加權(quán)簡單圖的鄰接矩陣 可以定義為其中， 表示邊 上的權(quán)值（即邊權(quán)），在相似權(quán)含義下，兩節(jié)點無連接，權(quán)值為0；而在相異權(quán)含義下，兩節(jié)點無連接，權(quán)值取，它表示一個計算機允許的、大于所有邊上權(quán)值的數(shù)。2.關(guān)聯(lián)矩陣 關(guān)聯(lián)矩陣描述了節(jié)點與邊的關(guān)聯(lián)關(guān)系，圖G的關(guān)聯(lián)矩陣B是一個NM階矩陣。6868 ijN NAa,( ,)0( ,)ijijijijv vEav vE或 ,ij( ,)ijijev v1.5.5 圖的矩

44、陣表示 對于無向網(wǎng)絡(luò)， 的定義如下： 無向圖的關(guān)聯(lián)矩陣具有以下性質(zhì)： 關(guān)聯(lián)矩陣中每列元素之和為2，即G中每條邊都有唯一的兩個端點。 關(guān)聯(lián)矩陣中第i行中1的個數(shù)等于節(jié)點 的度 。 關(guān)聯(lián)矩陣中第i行中1對應(yīng)的邊組成的集合為節(jié)點 的關(guān)聯(lián)集。 關(guān)聯(lián)矩陣中，若兩列相同，則它們對應(yīng)的邊為平行邊。6969 ijN MBb1,0,ijijijvVeEbvVeE與關(guān)聯(lián)與不關(guān)聯(lián)ivikiv1.5.5 圖的矩陣表示 若圖G有（2）個連通分支，則G的關(guān)聯(lián)矩陣B有如下形式：其中， 為第r（r1，2，）個連通分支的關(guān)聯(lián)矩陣。 對于有向網(wǎng)絡(luò)， 的定義如下： 有向圖的關(guān)聯(lián)矩陣具有以下性質(zhì)：70701wBBBrB ijN MB

45、b1,1,0,ijijijvVeEbvVeE 作為起點與關(guān)聯(lián)作為終點與關(guān)聯(lián)其他1.5.5 圖的矩陣表示 關(guān)聯(lián)矩陣的每列元素之和為0，即圖中每條邊關(guān)聯(lián)兩個節(jié)點，一個為起點，一個為終點。 第i行元素絕對值之和等于節(jié)點 的度 ，第i行中1的個數(shù)等于節(jié)點 的出度 ，第i行中1的個數(shù)等于節(jié)點 的入度 。 關(guān)聯(lián)矩陣中所有元素之和為零，且1的個數(shù)與 1的個數(shù)相同都為M。這也說明了關(guān)聯(lián)矩陣中各節(jié)點入度之和等于各節(jié)點出度之和都為M，節(jié)點度總和為2M。 若關(guān)聯(lián)矩陣中兩列相同，說明兩列對應(yīng)的邊有相同的起點和終點，它們是平行邊。7171ivikivoutikivinik1.5.5 圖的矩陣表示3.可達矩陣 對于有向圖G，可達矩陣也可以用來描述圖中節(jié)點之間的鄰接關(guān)系。有向圖的可達矩陣表示為 ，可達矩陣元素 定義為：若存在以 為起點，為終點的邊時，稱 可達 ， 的值為1；否則為不可達，值為0。 可達矩陣具有以下性質(zhì)： 可達矩陣的主對角線元素全為0。 若有向圖是強連通的，則P的全部元素均為1。 若G是具有（2）個連通分支的有向圖，則G的可達矩陣P可表示為：其