轉：https://www.cnblogs.com/maybe2030/p/4665847.html
對複雜網絡總結比較好，對與想要快速了解複雜網絡的夥伴們可以好好看看。
閱讀目錄
- 1. 複雜網絡的特點
- 2. 社群檢測
- 3. 結構平衡
- 4. 影響最大化
- 5. 網絡傳播
- 6. 補充
- 7. 參考文獻
在我們的現實生活中，許多複雜系統都可以模組化成一種複雜網絡進行分析，比如常見的電力網絡、航空網絡、交通網絡、計算機網絡以及社交網絡等等。複雜網絡不僅是一種資料的表現形式，它同樣也是一種科學研究的手段。複雜網絡方面的研究目前受到了廣泛的關注和研究，尤其是随着各種線上社交平台的蓬勃發展，各領域對于線上社交網絡的研究也越來越火。研究所學生期間，本人的研究方向也是一直與複雜網絡打交道，現在馬上就要畢業了，寫一篇博文簡單介紹一下複雜網絡特點以及一些有關複雜網絡研究内容的介紹，希望感興趣的博友可以一起讨論，一起學習。
下圖分别是一個航空網絡（上圖）和Facebook網絡全球友誼圖（下圖）。
回到頂部
1. 複雜網絡的特點
錢學森對于複雜網絡給出了一種嚴格的定義：具有自組織、自相似、吸引子、小世界、無标度中部分或全部性質的網絡稱之為複雜網絡。言外之意，複雜網絡就是指一種呈現高度複雜性的網絡，其特點主要具體展現在如下幾個方面：
1.1 小世界特性
小世界特性（Small world theory）又被稱之為是六度空間理論或者是六度分割理論（Six degrees of separation）。小世界特性指出：社交網絡中的任何一個成員和任何一個陌生人之間所間隔的人不會超過六個，如下圖所示：
在考慮網絡特征的時候，通常使用兩個特征來衡量網絡：
特征路徑長度（characteristic path length）：在網絡中，任選兩個節點，連通這兩個節點的最少邊數，定義為這兩個節點的路徑長度，網絡中所有節點對的路徑長度的平均值，定義為網絡的特征路徑長度。這是網絡的全局特征。
聚合系數(clustering coefficient)：假設某個節點有kk條邊，則這kk條邊連接配接的節點（kk個）之間最多可能存在的邊的條數為k(k−1)/2k(k−1)/2，用實際存在的邊數除以最多可能存在的邊數得到的分數值，定義為這個節點的聚合系數。所有節點的聚合系數的均值定義為網絡的聚合系數。聚合系數是網絡的局部特征，反映了相鄰兩個人之間朋友圈子的重合度，即該節點的朋友之間也是朋友的程度。
對于規則網絡，任意兩個點（個體）之間的特征路徑長度長（通過多少個體聯系在一起），但聚合系數高（你是朋友的朋友的朋友的幾率高）。對于随機網絡，任意兩個點之間的特征路徑長度短，但聚合系數低。而小世界網絡，點之間特征路徑長度小，接近随機網絡，而聚合系數依舊相當高，接近規則網絡。
複雜網絡的小世界特性跟網絡中的資訊傳播有着密切的聯系。實際的社會、生态、等網絡都是小世界網絡，在這樣的系統裡，資訊傳遞速度快，并且少量改變幾個連接配接，就可以劇烈地改變網絡的性能，如對已存在的網絡進行調整，如蜂窩電話網，改動很少幾條線路，就可以顯著提高性能。
1.2 無标度特性
現實世界的網絡大部分都不是随機網絡，少數的節點往往擁有大量的連接配接，而大部分節點卻很少，節點的度數分布符合幂率分布，而這就被稱為是網絡的無标度特性（Scale-free）。将度分布符合幂律分布的複雜網絡稱為無标度網絡。
下圖為一個具有10萬個節點的BA無标度網絡的度數分布示意圖：
無标度特性反映了複雜網絡具有嚴重的異質性，其各節點之間的連接配接狀況（度數）具有嚴重的不均勻分布性：網絡中少數稱之為Hub點的節點擁有極其多的連接配接，而大多數節點隻有很少量的連接配接。少數Hub點對無标度網絡的運作起着主導的作用。從廣義上說，無标度網絡的無标度性是描述大量複雜系統整體上嚴重不均勻分布的一種内在性質。
其實複雜網絡的無标度特性與網絡的魯棒性分析具有密切的關系。無标度網絡中幂律分布特性的存在極大地提高了高度數節點存在的可能性，是以，無标度網絡同時顯現出針對随機故障的魯棒性和針對蓄意攻擊的脆弱性。這種魯棒且脆弱性對網絡容錯和抗攻擊能力有很大影響。研究表明，無标度網絡具有很強的容錯性，但是對基于節點度值的選擇性攻擊而言，其抗攻擊能力相當差，高度數節點的存在極大地削弱了網絡的魯棒性，一個惡意攻擊者隻需選擇攻擊網絡很少的一部分高度數節點，就能使網絡迅速癱瘓。
1.3 社群結構特性
人以類聚，物以群分。複雜網絡中的節點往往也呈現出叢集特性。例如，社會網絡中總是存在熟人圈或朋友圈，其中每個成員都認識其他成員。叢集程度的意義是網絡集團化的程度；這是一種網絡的内聚傾向。連通集團概念反映的是一個大網絡中各集聚的小網絡分布和互相聯系的狀況。例如，它可以反映這個朋友圈與另一個朋友圈的互相關系。
下圖為網絡聚集現象的一種描述：
回到頂部
2. 社群檢測
社群檢測（community detection）又被稱為是社群發現，它是用來揭示網絡聚集行為的一種技術。社群檢測實際就是一種網絡聚類的方法，這裡的“社群”在文獻中并沒有一種嚴格的定義，我們可以将其了解為一類具有相同特性的節點的集合。近年來，社群檢測得到了快速的發展，這主要是由于複雜網絡領域中的大牛Newman提出了一種子產品度（modularity）的概念，進而使得網絡社群劃分的優劣可以有一個明确的評價名額來衡量。一個網絡不通情況下的社群劃分對應不同的子產品度，子產品度越大，對應的社群劃分也就越合理；如果子產品度越小，則對應的網絡社群劃分也就越模糊。
下圖描述了網絡中的社群結構：
Newman提出的子產品度計算公式如下:
Q=1/(2m)∑ij(Aij−kikj/(2m))δ(Ci,Cj)Q=1/(2m)∑ij(Aij−kikj/(2m))δ(Ci,Cj)
其中mm為網絡中總的邊數，AA是網絡對應的鄰接矩陣，Aij=1Aij=1代表節點ii和節點jj之間存在連邊，否則不存在連邊。kiki為節點ii的度數，CiCi為節點ii屬于某個社群的标号，而δ(Ci,Cj)=1δ(Ci,Cj)=1當且僅當Ci=CjCi=Cj。
上述的子產品度定義其實很好了解，我們可以根據一個網絡的空模型去進行了解。網絡的空模型可以了解為隻有節點的而沒有連邊，這時候一個節點可以和圖中的任意其他節點相連，并且節點ii和jj相連的機率可以通過計算得到。随機選擇一個節點與節點ii相連的機率為kj/2mkj/2m，随機選擇一個節點與節點jj相連的機率為kj/2mkj/2m，那麼節點ii和節點jj相連的機率為pipj=kikj/(4m2)pipj=kikj/(4m2)，邊數的期望值Pij=2mpipj=kikj/(2m)Pij=2mpipj=kikj/(2m)。是以子產品度其實就是指一個網絡在某種社群劃分下與随機網絡的差異，因為随機網絡并不具有社群結構，對應的差異越大說明該社群劃分越好。
Newman提出的子產品度具有兩方面的意義：
（1）子產品度的提出成為了社群檢測評價一種常用名額，它是度量網絡社群劃分優劣的量化名額；
（2）子產品度的提出極大地促進了各種優化算法應用于社群檢測領域的發展。在子產品度的基礎之上，許多優化算法以子產品度為優化的目标方程進行優化，進而使得目标函數達到最大時得到不錯的社群劃分結果。
當然，子產品度的概念不是絕對合理的，它也有弊端，比如分辨率限制問題等，後期國内學者在子產品度的基礎上提出了子產品度密度的概念，可以很好的解決子產品度的弊端，這裡就不詳細介紹了。
常用的社群檢測方法主要有如下幾種：
（1）基于圖分割的方法，如Kernighan-Lin算法，譜平分法等；
（2）基于層次聚類的方法，如GN算法、Newman快速算法等；
（3）基于子產品度優化的方法，如貪婪算法、模拟退火算法、Memetic算法、PSO算法、進化多目标優化算法等。
回到頂部
3. 結構平衡
結構平衡（Structural Balance）主要是針對社交網絡的研究而被提出的，它最早源于社會心理學家Heider提出的一個結構平衡理論。
3.1 網絡平衡的發展
網絡平衡有時也稱社會平衡（Social Balance），就網絡平衡的發展來說，我們可以将其分為三個發展階段。
3.1.1 網絡平衡理論的提出
“網絡平衡”一詞最早是由Heider基于對社會心理學的研究而提出的，Heider在1946年的文章Attitudes and cognitive organization[1]中針對網絡平衡的概念提出了最早的平衡理論：
（1）朋友的朋友是朋友；
（2）朋友的敵人是敵人；
（3）敵人的朋友是敵人；
（4）敵人的敵人是朋友。
用常見的三元組合來表示上述的Heider理論如下：
上述的平衡理論是有關網絡平衡提出的最早的理論，它後來也被稱為是強平衡理論。
1956年，Cartwright和Harary對Heider的平衡理論進行了推廣，并将其用在了圖理論中（STRUCTURAL BALANCE: A GENERALIZATION OF HEIDER'S THEORY[2]）。Cartwright和Harary指出對于一個符号網絡而言，網絡平衡的充要條件是網絡中的所有三元組都是平衡的，該結論也可以陳述為一個符号網絡平衡的充要條件是它所包含的所有回路（cycles）都是平衡的（“-”号的個數為整數個）。而且，在這篇文章中，他們還提出了著名的結構平衡理論：如果一個符号網絡是平衡的，那麼這個網絡就可以分為兩部分子網絡，其中每個子網絡内部中節點的連接配接都是正連接配接，網絡之間的連接配接均為負連接配接。
在這各階段網絡平衡的發展的重心主要在于建構網絡平衡的心理學和社會學模型。
3.1.2 網絡平衡的數學模型
在有了Heider等人的奠基工作後，有關網絡平衡的發展主要是建構其數學模型，比如網絡的動态表現，一個網絡連接配接如何随時間的變化而變化，網絡中節點之間的朋友或者敵人的關系如何演化等等。
3.1.3 網絡平衡的應用
最新關于網絡平衡方面的研究大都是研究一些線上網絡，比如對某個網站使用者屬性的分析等等。而且，目前我們身處大資料時代，我們所要研究的網絡規模也變為了大型甚至可以說是超大型網絡，這這個背景下，如何計算一個網絡是否平衡便成為該領域的主要熱點問題。
3.2 網絡平衡的基本理論
(1) Heider理論（強平衡理論SBT）。
(2) 結構平衡理論（Structural Balance Theroem）：在完全符号網絡中，網絡平衡的充要條件是其所有的三元組（回路）都平衡。
結構平衡的推論：一個完全符号網絡平衡的充要條件是它可以被分為兩部分X和Y，X和Y内部的節點連接配接均為正連接配接，X和Y之間的連接配接均為負連接配接。
(3) 弱平衡理論（A weaker form of structural balance，WSBT）：如果完全符号網絡中不存在這樣的三元組：兩個邊為正，一邊為負，則該網絡稱為是弱平衡網絡。
對于弱平衡理論而言，上圖的三元組中，三邊均為負連接配接的三元組也屬于平衡三元組，也就是三元組的四種情況有三種屬于平衡狀态，一個屬于不平衡狀态（兩邊為正，一邊為負）。
弱平衡網絡推論：如果一個網絡為弱平衡理論，那麼它可以分為多個部分，每部分内的連接配接為正，部分之間的連接配接為負。
(4) 對任意網絡平衡的定義.
1) 對于一個任意網絡而言，如果我們可以将它所缺失的邊填充使它成為一個平衡的完全符号網絡，那麼原網絡就是平衡網絡；
2) 對于一個任意網絡而言，如果我們可以将它分為兩部分，使得每個部分内的連接配接均為實線，部分之間的連接配接均為虛線。
以上的兩種定義是等價的。
一個符号網絡平衡的充要條件是它不包括含有奇數個負連接配接的回路。
(5) 近似平衡網絡（略）。
3.3 網絡平衡的計算（A spectral algorithm for computing social balance）
命題1：節點i參與的三元組數目
A為鄰接矩陣，元素取值可能為：1，-1,0；
G為鄰接矩陣，元素取值可能為：0,1.
命題2：對于節點i而言，bi為其參與的平衡三元組數目，ui為其參與的不平衡三元組數目，則
理論1：對于完全符号圖而言，
平衡三元組所占的比例為
理論2：對于任意符号網絡，平衡三元組所占的比例為
注：以上兩個計算網絡平衡的公式中，特征值可以随大到小選擇前幾個比較大的，就像PCA那樣，這樣可以使得計算的複雜度大大減小。
回到頂部
4. 影響最大化
随着各種線上社交平台的發展，社交平台（比如QQ、微網誌、朋友圈等）已經不僅僅是一種使用者進行溝通的社交平台，它們更是社會資訊産生和傳播的一種主要的媒介。影響最大化（Influence Maximization）同結構平衡一樣，也是針對社會網絡的研究而被提出的，它來源于經濟學的市場營銷。2001年，影響最大化被Domins首次以一種算法問題的形式被提出。而影響最大化受到廣泛的關注是在2003年Kempe等人在當年的KDD會議上發表的一篇有關影響最大化的論文之後，随後各種影響最大化算法被迅速提出，最近的十幾年裡，影響最大化的相關文章達到了上千篇，可見這個問題還是很值得關注的。
影響最大化問題可以這樣來描述：一個商家或者企業利用一種社交平台（比如為新浪微網誌）為自己的新産品或者新服務進行推廣，如何在資金有限的情況下雇傭微網誌達人來做推廣可以使得推廣範圍達到最大？
我們再給出影響最大化的一般定義：
給定一個網絡GG和一個整數KK（一般小于50），如何在GG中找出KK個節點，使得這KK的節點組成的節點集合SS的影響傳播範圍σ(S)σ(S)達到最大。
根據上述影響最大化的定義我們很容易可以知道，影響最大化本身屬于一種組合優化問題。常用的影響最大化傳播模型有獨立級聯傳播模型（ICM）和線性門檻值傳播模型（LTM）。
影響最大化方面的主要算法可以分為如下幾類：
（1）基于網絡中心性的啟發式方法：比如最大度方法、最短平均距離方法、PageRank方法等；
（2）基于子子產品性的貪婪方法：比如最經典的Greedy算法，CELF算法以及後來的NewGreedy和CELF++等；
（3）基于社群結構的方法：比如CGA算法、CIM算法等；
（4）基于目标函數優化的方法：比如模拟退火算法等。
回到頂部
5. 網絡傳播
網絡傳播領域涉及很多方面，比如網絡節點重要性排序、網絡魯棒性分析、網絡資訊爆發門檻值優化等。這些領域都很有意思，感興趣的博友可以好好深入研究一下。
回到頂部
6. 補充
6.1 網絡可視化工具
首先在這裡推薦兩款我常用的網絡可視化工具：Pajek (點選進入官方網站)、Gephi（點選進入官方網站）。
下邊為pajek可視化視窗下的一個網絡拓撲結構圖：
這是Gephi的一個可視化效果：
6.2 網絡資料集
常用的一些公開資料集整理：
Pajek（可視化工具）資料集：http://vladowiki.fmf.uni-lj.si/doku.php?id=pajek:data:index；
Newman（複雜網絡科學領域大牛）個人資料集：http://www-personal.umich.edu/~mejn/netdata/
Stanford大學大規模網絡資料集：http://snap.stanford.edu/data/
複旦大學網絡資料集整理：http://gdm.fudan.edu.cn/GDMWiki/Wiki.jsp?page=Network%20DataSet
KONECT資料集整理：http://konect.uni-koblenz.de/
回到頂部
7. 參考文獻
[1] Grivan and Newman. Community structure in social and biological networks. PNAS, 2002.
[2] Newman and Grivan. Finding and evaluating community structure in networks. PRE, 2004.
[3] Newman. Networks: an introduction. 2010.
[4] Cartwright and Harary. Structural balance: a generalization of Heider's theory. 1956.
[5] Facchetti et al. Computing global structural balance in large-scale signed social networks. 2011.
[6] Kempe et al. Maximizing the spread of influence through a social network. 2003.
[7] Chen et al. Efficient influence maximization in social networks. 2009.
[8] 任曉龍，呂琳媛. 網絡重要節點排序方法綜述. 2014.