網絡，數學上稱為圖，最早研究始於1736年歐拉的哥尼斯堡七橋問題，但是之後關於圖的研究發展緩慢，直到1936年，才有了第壹本關於圖論研究的著作。
1960年，數學家Erdos和Renyi建立了隨機圖理論，為構造網絡提供了壹種新的方法。在這種方法中，兩個節點之間是否有邊連接不再是確定的事情，而是根據壹個概率決定，這樣生成的網絡稱作隨機網絡。隨機圖的思想主宰復雜網絡研究長達四十年之久，然而，直到近幾年，科學家們對大量的現實網絡的實際數據進行計算研究後得到的許多結果，絕大多數的實際網絡並不是完全隨機的，既不是規則網絡，也不是隨機網絡，而是具有與前兩者皆不同的統計特征的網絡。這樣的壹?些網絡稱為復雜網絡，對於復雜網絡的研究標誌著網絡研究的第三階段的到來。
1998年，Watts及其導師Strogatz在Nature上的文章《Collective Dynamics of Small-world Networks》，刻畫了現實世界中的網絡所具有的大的凝聚系數和短的平均路徑長度的小世界特性。隨後，1999年，Barabasi及其博士生Albert在Science上的文章《Emergence of Scaling in Random Networks》提出無尺度網絡模型(度分布為冪律分布)，，刻畫了實際網絡中普遍存在的“富者更富”的現象，從此開啟了復雜網絡研究的新紀元。
隨著研究的深入，越來越多關於復雜網絡的性質被發掘出來，其中很重要的壹項研究是2002年Girvan和Newman在PNAS上的壹篇文章《Community structure in social and biological networks》，指出復雜網絡中普遍存在著聚類特性，每壹個類稱之為壹個社團(community)，並提出了壹個發現這些社團的算法。從此，熱門對復雜網絡中的社團發現問題進行了大量研究，產生了大量的算法。
許多復雜系統都可以建模成壹種復雜網絡進行分析，比如常見的電力網絡、航空網絡、交通網絡、計算機網絡以及社交網絡等等。復雜網絡不僅是壹種數據的表現形式，它同樣也是壹種科學研究的手段。
復雜網絡的定義
錢學森對於復雜網絡給出了壹種嚴格的定義：
復雜網絡具有網絡平均路徑長度較小、聚類系數較大、節點度分度服從冪律分布等相同特性
言外之意，復雜網絡就是指壹種呈現高度復雜性的網絡，其特點主要具體體現在如下幾個方面：
小世界特性（Small world theory）又被稱之為是六度空間理論或者是六度分割理論（Six degrees of separation）。小世界特性指出：社交網絡中的任何壹個成員和任何壹個陌生人之間所間隔的人不會超過六個。
在考慮網絡特征的時候，通常使用兩個特征來衡量網絡：
對於規則網絡，任意兩個點（個體）之間的特征路徑長度長（通過多少個體聯系在壹起），但聚合系數高（妳是朋友的朋友的朋友的幾率高）。對於隨機網絡，任意兩個點之間的特征路徑長度短，但聚合系數低。而小世界網絡，點之間特征路徑長度小，接近隨機網絡，而聚合系數依舊相當高，接近規則網絡。
復雜網絡的小世界特性跟網絡中的信息傳播有著密切的聯系。實際的社會、生態、等網絡都是小世界網絡，在這樣的系統裏，信息傳遞速度快，並且少量改變幾個連接，就可以劇烈地改變網絡的性能，如對已存在的網絡進行調整，如蜂窩電話網，改動很少幾條線路，就可以顯著提高性能。
現實世界的網絡大部分都不是隨機網絡，少數的節點往往擁有大量的連接，而大部分節點卻很少，節點的度數分布符合冪率分布，而這就被稱為是網絡的無標度特性（Scale-free）。將度分布符合冪律分布的復雜網絡稱為無標度網絡。
例如，知乎中用戶的fellow數的分布情況：
無標度特性反映了復雜網絡具有嚴重的異質性，其各節點之間的連接狀況（度數）具有嚴重的不均勻分布性：網絡中少數稱之為Hub點的節點擁有極其多的連接，而大多數節點只有很少量的連接。少數Hub點對無標度網絡的運行起著主導的作用。從廣義上說，無標度網絡的無標度性是描述大量復雜系統整體上嚴重不均勻分布的壹種內在性質。
其實復雜網絡的無標度特性與網絡的魯棒性分析具有密切的關系。無標度網絡中冪律分布特性的存在極大地提高了高度數節點存在的可能性，因此，無標度網絡同時顯現出針對隨機故障的魯棒性和針對蓄意攻擊的脆弱性。這種魯棒且脆弱性對網絡容錯和抗攻擊能力有很大影響。
研究表明，無標度網絡具有很強的容錯性，但是對基於節點度值的選擇性攻擊而言，其抗攻擊能力相當差，高度數節點的存在極大地削弱了網絡的魯棒性，壹個惡意攻擊者只需選擇攻擊網絡很少的壹部分高度數節點，就能使網絡迅速癱瘓。
人以類聚，物以群分。復雜網絡中的節點往往也呈現出集群特性。例如，社會網絡中總是存在熟人圈或朋友圈，其中每個成員都認識其他成員。集群程度的意義是網絡集團化的程度；這是壹種網絡的內聚傾向。連通集團概念反映的是壹個大網絡中各集聚的小網絡分布和相互聯系的狀況。例如，它可以反映這個朋友圈與另壹個朋友圈的相互關系。
下圖為網絡聚集現象的壹種描述：
真實網絡所表現出來的小世界特性、無尺度冪律分布或高聚集度等現象促使人們從理論上構造出多樣的網絡模型，以解釋這些統計特性，探索形成這些網絡的演化機制。本節介紹了幾個經典網絡模型的原理和構造方法，包括ER隨機網絡模型、BA無尺度網絡模型和小世界模型。
ErdOs-Renyi隨機網絡模型(簡稱ER隨機網絡模型)是匈牙利數學家Erdos和Renyi提出的壹種網絡模型。1959年，為了描述通信和生命科學中的網絡，Erdos和Renyi提出，通過在網絡節點間隨機地布置連接，就可以有效地模擬出這類系統。這種方法及相關定理的簡明扼要，導致了圖論研究的復興，數學界也因此出現了研究隨機網絡的新領域。ER隨機網絡模型在計算機科學、統計物理、生命科學、通信工程等領域都得到了廣泛應用。
ER隨機網絡模型是個機會均等的網絡模型。在該網絡模型中，給定壹定數目的個體(節點)，它和其他任意壹個個體(節點)之間有相互關系(連接)的概率相同，記為戶。因為壹個節點連接k個其他節點的概率，會隨著k值的增大而呈指數遞減。這樣，如果定義是為每個個體所連接的其他個體的數目，可以知道連接概率p(k)服從鐘形的泊松(Poisson)分布，有時隨機網絡也稱作指數網絡。
隨機網絡理論有壹項重要預測：盡管連接是隨機安置的，但由此形成的網絡卻是高度民主的，也就是說，絕大部分節點的連接數目會大致相同。實際上，隨機網絡中連接數目比平均數高許多或低許多的節點，都十分罕見。
在過去40多年裏，科學家習慣於將所有復雜網絡都看作是隨機網絡。在1998年研究描繪萬維網(以網頁為節點、以超級鏈接為邊)的項目時，學者們原以為會發現壹個隨機網絡：人們會根據自己的興趣，來決定將網絡文件鏈接到哪些網站，而個人興趣是多種多樣的，可選擇的網頁數量也極其龐大，因而最終的鏈接模式將呈現出相當隨機的結果。
然而，事實並非如此。因為在萬維網上，並非所有的節點都是平等的。在選擇將網頁鏈接到何處時，人們可以從數十億個網站中進行選擇。然而，我們中的大部分人只熟悉整個萬維網的壹小部分，這壹小部分中往往包含那些擁有較多鏈接的站點，因為這樣的站點更容易為人所知。只要鏈接到這些站點，就等於造就或加強了對它們的偏好。這種“擇優連接(Preferential Attachment)”的過程，也發生在其他網絡中。在Internet上，那些具有較多連接的路由器通常也擁有更大的帶寬，因而新用戶就更傾向於連接到這些路由器上。在美國的生物技術產業內，某些知名公司更容易吸引到同盟者，而這又進壹步加強了它在未來合作中的吸引力。類似地，在論文引用網絡(論文為節點，引用關系為邊)中，被引用次數較多的科學文獻，會吸引更多的研究者去閱讀並引用它。針對這些網絡的“擇優連接”的新特性，學者提出了BA無尺度網絡模型。
無尺度網絡的發現，使人類對於復雜網絡的認識進入了壹個新的天地。無尺度網絡的最主要特征是節點的度分布服從冪次定律。BA模型是無尺度網絡(Scale-free Network)的第壹個抽象模型。由於考慮了系統的成長性(Growth)和擇優連接性，BA模型給我們帶來了很多啟發，並且可以應用於多種實際網絡。但是BA模型的兩個基本假定，對於解釋許多現實中的現象來說過於簡單，與現實的網絡還有較大的距離。
有學者試圖對BA模型進行擴展，即根據現實中的網絡，增添某些假定，以便進壹步探索復雜網絡系統的規律。對BA模型的擴充可以考慮三個因素：擇優選擇的成本、邊的重新連接、網絡的初始狀態。擴充的BA模型可以更好地模擬現實世界中的網絡現象。
1999年，丸Barabasi和兄Albert在對互聯網的研究中發現了無尺度網絡，使人類對於復雜網絡系統有了全新的認識。過去，人們習慣於將所有復雜網絡看作是隨機網絡，但Barabasi和Albert發現互聯網實際上是由少數高連接性的頁面組織起來的，80％以上頁面的鏈接數不到4個。只占節點總數不到萬分之壹的極少數節點，卻有1000個以上的鏈接。這種網頁的鏈接分布遵循所謂的“冪次定律”：任何壹個節點擁有是條連接的概率，與1／k成正比。它不像鐘形曲線那樣具有壹個集中度很高的峰值，而是壹條連續遞減的曲線。如果取雙對數坐標系來描述冪次定律，得到的是壹條直線。
Scale-free網絡指的是節點的度分布符合冪律分布的網絡，由於其缺乏壹個描述問題的特征尺度而被稱為無尺度網絡。其後的幾年中，研究者們在許多不同的領域中都發現了無尺度網絡。從生態系統到人際關系，從食物鏈到代謝系統，處處可以看到無尺度網絡。
為什麽隨機模型與實際不相符合呢?Barabasi和Albert在深入分析了ER模型之後，發現問題在於ER模型討論的網絡是壹個既定規模的，不會繼續擴展的網絡。正是由於現實當中的網絡往往具有不斷成長的特性，早進入的節點(老節點)獲得連接的概率就更大。當網絡擴張到壹定規模以後，這些老節點很容易成為擁有大量連接的集散節點。這就是網絡的“成長性”。
其次，ER模型中每個節點與其他節點連接時，建立連接的概率是相同的。也就是說，網絡當中所有的節點都是平等的。這壹情況與實際也不相符。例如，新成立的網站選擇與其他網站鏈接時，自然是在人們所熟知的網站中選擇壹個進行鏈接，新的個人主頁上的超文本鏈接更有可能指向新浪、雅虎等著名的站點。由此，那些熟知的網站將獲得更多的鏈接，這種特性稱為“擇優連接”。這種現象也稱為“馬太效應(Matthew Effect)”或“富者更富(Rich Get Richer)”。
“成長性”和“擇優連接”這兩種機制解釋了網絡當中集散節點的存在。
BA無尺度模型的關鍵在於，它把實際復雜網絡的無尺度特性歸結為增長和優先連接這兩個非常簡單的機制。當然，這也不可避免地使得BA無尺度網絡模型和真實網絡相比存在壹些明顯的限制。比如，壹些實際網絡的局域特性對網絡演化結果的影響、外界對網絡節點及其連接邊刪除的影響等。
壹般自然的或者人造的現實網絡與外界之間有節點交換，節點間連接也在不斷變化，網絡自身具有壹定的自組織能力，會對自身或者外界的變化作出相應的反應。因此，在BA模型基礎上，可以把模型的動力學過程進行推廣，包括對網絡中已有節點或者連接的隨機刪除及其相應的連接補償機制。
對每壹個時間步長，考慮如下三種假設：
復雜網絡研究中壹個重要的發現是絕大多數大規模真實網絡的平均路徑長度比想象的小得多，稱之為“小世界現象”，或稱“六度分離(Six Degrees of Separation)”。
所謂小世界現象，是來自社會網絡(Social Networks)中的基本現象，即每個人只需要很少的中間人(平均6個)就可以和全世界的人建立起聯系。在這壹理論中，每個人可看作是網絡的壹個節點，並有大量路徑連接著他們，相連接的節點表示互相認識的人。
1998年，Watts和Strogatz引入了壹個介於規則網絡和完全隨機網絡之間的單參數小世界網絡模型，稱為WS小世界模型，該模型較好地體現了社會網絡的小平均路徑長度和大聚類系數兩種現象。
WS小世界模型的構造方法如下：
在WS小世界模型中，p＝0對應於規則網絡，p＝l則對應於完全隨機網絡，通過調節聲的值就可以控制從規則網絡到完全隨機圖的過渡。因此，WS小世界網絡是介於規則網絡和隨機網絡之間的壹種網絡。
WS小世界模型構造算法中的隨機化過程有可能破壞網絡的連通性。因此，Newman和Watts稍後提出了NW小世界模型。NW小世界模型的構造方法如下：
NW模型只是將WS小世界模型構造中的“隨機化重連”改為“隨機化加邊”。
NW模型不同於WS模型之處在於它不切斷規則網絡中的原始邊，而是以概率p重新連接壹對節點。這樣構造出來的網絡同時具有大的聚類數和小的平均距離。NW模型的優點在於其簡化了理論分析，因為WS模型可能存在孤立節點，但NW模型不會。當戶足夠小和N足夠大時，NW小世界模型本質上就等同於WS小世界模型。
小世界網絡模型反映了實際網絡所具有的壹些特性，例如朋友關系網，大部分人的朋友都是和他們住在同壹個地方，其地理位置不是很遠，或只在同壹單位工作或學習的同事和同學。另壹方面，也有些人住得較遠的，甚至是遠在異國他鄉的朋友，這種情形好比WS小世界模型中通過重新連線或在NW小世界模型中通過加入連線產生的遠程連接。
小世界網絡模型的主要特征之壹是節點之間的平均距離隨遠程連接的個數而指數下降。對於規則網絡，平均距離L可估計為L正比於N；而對於小世界網絡模型，L正比於ln(N)／1n(K)。例如，對於壹個千萬人口的城市，人與人的平均接觸距離是6左右，這使得生活人群之間的距離大大縮短。該模型由壹個規則的環組成，通常是壹個壹維的幾乎具有周期性邊界條件的環(即環中每個節點幾乎都連接到壹固定數目的鄰近節點)和少量的隨機選取節點連接成的“捷徑” (重新連接現存的邊)。小世界網絡同時具有“高網絡聚集度”和“低平均路徑”的特性。
從小世界網絡模型中可以看到，只要改變很少的幾個連接，就可以劇烈的改變網絡的性能。這樣的性質也可以應用其他網絡，尤其是對已有網絡的調整方面。例如，蜂窩電話網，改動很少幾條線路(低成本、低工作量)的連接，就可以顯著提高性能。也可以應用到互聯網的主幹路由器上，以改變流量和提高傳輸速度。同樣的思路也可以應用到電子郵件的快速傳遞、特定Web站點的定位等。
如果學習復雜網絡，目前認為最好的視頻教程：
社交計算與社會網絡分析Network Analysis
1） 復雜網絡中聚類算法總結
2） Network Analysis復雜網絡分析總結
3） 復雜網絡和社會網絡