① 一文帶你認識30個重要的數據結構和演算法
數組是最簡單也是最常見的數據結構。它們的特點是可以通過索引（位置）輕松訪問元素。
它們是做什麼用的？
想像一下有一排劇院椅。每把椅子都分配了一個位置（從左到右），因此每個觀眾都會從他將要坐的椅子上分配一個號碼。這是一個數組。將問題擴展到整個劇院（椅子的行和列），您將擁有一個二維數組（矩陣）。
特性
鏈表是線性數據結構，就像數組一樣。鏈表和數組的主要區別在於鏈表的元素不存儲在連續的內存位置。它由節點組成——實體存儲當前元素的值和下一個元素的地址引用。這樣，元素通過指針鏈接。
它們是做什麼用的？
鏈表的一個相關應用是瀏覽器的上一頁和下一頁的實現。雙鏈表是存儲用戶搜索顯示的頁面的完美數據結構。
特性
堆棧是一種抽象數據類型，它形式化了受限訪問集合的概念。該限制遵循 LIFO（後進先出）規則。因此，添加到堆棧中的最後一個元素是您從中刪除的第一個元素。
堆棧可以使用數組或鏈表來實現。
它們是做什麼用的？
現實生活中最常見的例子是在食堂中將盤子疊放在一起。位於頂部的板首先被移除。放置在最底部的盤子是在堆棧中保留時間最長的盤子。
堆棧最有用的一種情況是您需要獲取給定元素的相反順序。只需將它們全部推入堆棧，然後彈出它們。
另一個有趣的應用是有效括弧問題。給定一串括弧，您可以使用堆棧檢查它們是否匹配。
特性
隊列是受限訪問集合中的另一種數據類型，就像前面討論的堆棧一樣。主要區別在於隊列是按照FIFO（先進先出）模型組織的：隊列中第一個插入的元素是第一個被移除的元素。隊列可以使用固定長度的數組、循環數組或鏈表來實現。
它們是做什麼用的？
這種抽象數據類型 (ADT) 的最佳用途當然是模擬現實生活中的隊列。例如，在呼叫中心應用程序中，隊列用於保存等待從顧問那裡獲得幫助的客戶——這些客戶應該按照他們呼叫的順序獲得幫助。
一種特殊且非常重要的隊列類型是優先順序隊列。元素根據與它們關聯的「優先順序」被引入隊列：具有最高優先順序的元素首先被引入隊列。這個 ADT 在許多圖演算法（Dijkstra 演算法、BFS、Prim 演算法、霍夫曼編碼 ）中是必不可少的。它是使用堆實現的。
另一種特殊類型的隊列是deque 隊列（雙關語它的發音是「deck」）。可以從隊列的兩端插入/刪除元素。
特性
Maps （dictionaries）是包含鍵集合和值集合的抽象數據類型。每個鍵都有一個與之關聯的值。
哈希表是一種特殊類型的映射。它使用散列函數生成一個散列碼，放入一個桶或槽數組：鍵被散列，結果散列指示值的存儲位置。
最常見的散列函數（在眾多散列函數中）是模常數函數。例如，如果常量是 6，則鍵 x 的值是x%6。
理想情況下，散列函數會將每個鍵分配給一個唯一的桶，但他們的大多數設計都採用了不完善的函數，這可能會導致具有相同生成值的鍵之間發生沖突。這種碰撞總是以某種方式適應的。
它們是做什麼用的？
Maps 最著名的應用是語言詞典。語言中的每個詞都為其指定了定義。它是使用有序映射實現的（其鍵按字母順序排列）。
通訊錄也是一張Map。每個名字都有一個分配給它的電話號碼。
另一個有用的應用是值的標准化。假設我們要為一天中的每一分鍾（24 小時 = 1440 分鍾）分配一個從 0 到 1439 的索引。哈希函數將為h(x) = x.小時*60+x.分鍾。
特性
術語：
因為maps 是使用自平衡紅黑樹實現的（文章後面會解釋），所以所有操作都在 O(log n) 內完成；所有哈希表操作都是常量。
圖是表示一對兩個集合的非線性數據結構：G={V, E}，其中 V 是頂點（節點）的集合，而 E 是邊（箭頭）的集合。節點是由邊互連的值 - 描述兩個節點之間的依賴關系（有時與成本/距離相關聯）的線。
圖有兩種主要類型：有向圖和無向圖。在無向圖中，邊(x, y)在兩個方向上都可用：(x, y)和(y, x)。在有向圖中，邊(x, y)稱為箭頭，方向由其名稱中頂點的順序給出：箭頭(x, y)與箭頭(y, x) 不同。
它們是做什麼用的？
特性
圖論是一個廣闊的領域，但我們將重點介紹一些最知名的概念：
一棵樹是一個無向圖，在連通性方面最小（如果我們消除一條邊，圖將不再連接）和在無環方面最大（如果我們添加一條邊，圖將不再是無環的）。所以任何無環連通無向圖都是一棵樹，但為了簡單起見，我們將有根樹稱為樹。
根是一個固定節點，它確定樹中邊的方向，所以這就是一切「開始」的地方。葉子是樹的終端節點——這就是一切「結束」的地方。
一個頂點的孩子是它下面的事件頂點。一個頂點可以有多個子節點。一個頂點的父節點是它上面的事件頂點——它是唯一的。
它們是做什麼用的？
我們在任何需要描繪層次結構的時候都使用樹。我們自己的家譜樹就是一個完美的例子。你最古老的祖先是樹的根。最年輕的一代代表葉子的集合。
樹也可以代表你工作的公司中的上下級關系。這樣您就可以找出誰是您的上級以及您應該管理誰。
特性
二叉樹是一種特殊類型的樹：每個頂點最多可以有兩個子節點。在嚴格二叉樹中，除了葉子之外，每個節點都有兩個孩子。具有 n 層的完整二叉樹具有所有2ⁿ-1 個可能的節點。
二叉搜索樹是一棵二叉樹，其中節點的值屬於一個完全有序的集合——任何任意選擇的節點的值都大於左子樹中的所有值，而小於右子樹中的所有值。
它們是做什麼用的？
BT 的一項重要應用是邏輯表達式的表示和評估。每個表達式都可以分解為變數/常量和運算符。這種表達式書寫方法稱為逆波蘭表示法 (RPN)。這樣，它們就可以形成一個二叉樹，其中內部節點是運算符，葉子是變數/常量——它被稱為抽象語法樹（AST）。
BST 經常使用，因為它們可以快速搜索鍵屬性。AVL 樹、紅黑樹、有序集和映射是使用 BST 實現的。
特性
BST 有三種類型的 DFS 遍歷：
所有這些類型的樹都是自平衡二叉搜索樹。不同之處在於它們以對數時間平衡高度的方式。
AVL 樹在每次插入/刪除後都是自平衡的，因為節點的左子樹和右子樹的高度之間的模塊差異最大為 1。 AVL 以其發明者的名字命名：Adelson-Velsky 和 Landis。
在紅黑樹中，每個節點存儲一個額外的代表顏色的位，用於確保每次插入/刪除操作後的平衡。
在 Splay 樹中，最近訪問的節點可以快速再次訪問，因此任何操作的攤銷時間復雜度仍然是 O(log n)。
它們是做什麼用的？
AVL 似乎是資料庫理論中最好的數據結構。
RBT（紅黑樹） 用於組織可比較的數據片段，例如文本片段或數字。在 Java 8 版本中，HashMap 是使用 RBT 實現的。計算幾何和函數式編程中的數據結構也是用 RBT 構建的。
在 Windows NT 中（在虛擬內存、網路和文件系統代碼中），Splay 樹用於緩存、內存分配器、垃圾收集器、數據壓縮、繩索（替換用於長文本字元串的字元串）。
特性
最小堆是一棵二叉樹，其中每個節點的值都大於或等於其父節點的值：val[par[x]]
② 啟發式搜索全局擇優搜索和局部擇優搜索的區別是什麼
根據問題的實際情況不斷尋找可利用的知識，從而構造成一條代價較少的推理路線，使問題得到圓滿解決的過程稱為搜索。
尋找問題的解的一種可靠的方法是首先列出所有候選解，然後依次檢查每一個解，即可以找到所需要的問題的答案。這是一種「萬能」的方法，理論上，當候選解的數量可以窮盡並且通過檢查所有或部分候選解能夠得到所需解時，問題就能得到解決。
但是，在實際應用中，因為候選解的數量通常都非常大（比如指數級），並且計算機的速度和內存都有限制，因此對問題不加分析的窮盡演算法通常只能解決規模很小的問題。
在實際運用中常採用回溯和分枝定界法對問題進行求解。按照這兩種方法對候選解進行系統檢查通常會使問題的求解時間大大減少（無論對於最壞情形還是對於一般情形）。這二種方法由於都是按規定的路線進行，基本沒有使用與問題有關的啟發性信息，屬於盲目搜索策略。在涉及人工職能的有些問題如博弈問題時，還會用到啟發是搜索策略，如A*演算法等。
一、回溯法和分枝限界法
問題的表示
狀態空間表示法是表示問題及其搜索過程的一種形式表示方法。可以用解空間樹來表示問題的結構。 對於一棵樹，樹中的每一個結點確定所求問題的一個問題狀態，由根結點到其它結點的所有路徑確定了這個問題的狀態空間。解狀態是一些問題狀態S，對於這些問題狀態，由根到S的那條路徑確定了這解空間的一個元組。答案狀態則是由解狀態到根的路徑。
對於一種狀態空間樹，可以先系統地生成問題的狀態，接著確定問題狀態的解狀態，最後確定那些解狀態是答案狀態從而將這些問題解出。
從根結點開始解問題，如果已經生成一個結點而它的所有兒子結點還沒有全部生成，則這個結點叫做活結點。當前正在生成其兒子的活結點叫E結點，不再進一步擴展或者其兒子結點已經全部生成的生成結點就是死結點。
回溯演算法使用深度優先方法搜索樹結構，而分枝定界一般用寬度優先方法來搜索這些樹。
回溯方法的步驟如下：
1) 定義一個解空間，它包含問題的解。
2) 用適於搜索的方式組織該空間。
3) 用深度優先法搜索該空間，利用限界函數避免移動到不可能產生解的子空間。
回溯演算法的特性是在搜索執行的同時產生解空間。在搜索期間的任何時刻，僅保留從開始節點到當前E -節點的路徑。因此，回溯演算法的空間需求為O（從開始節點起最長路徑的長度）。
分枝限界法的步驟和回溯的唯一區別是採用了寬度優先的方法來搜索樹，因此分枝法消耗的空間比回溯法要多。
這二種搜索策略從本質上來講都是屬於窮盡法的搜索，由於在搜索路徑上的不同也造成這二種方法各自都有其優缺點、適用的求解問題也就不同。
寬度優先佔有優勢的問題：
九宮重排問題
九宮重排問題是一個可以回溯法和分枝法都能解決的問題。但是，對於這個問題運用分枝法是有利的。
九宮重排問題，在3*3的方格棋盤上放置標由數字1、2、3、4、5、6、7、8共8個棋子，初始狀態為S 0 ，目標狀態為Sg ，當找到一個解時結束搜索。
從根結點到葉子結點的路徑即為解，演算法為空格左移，空格上移，空格右移，空格下移。
S0
Sg
2
8
3
1
2
3
1
4
8
4
7
6
5
7
6
5
用寬度優先搜索，如下圖：
f'(x) = g(x) + h(x)
2 8 3
14
7 6 5
2 8 3
1 4
7 6 5
23
1 8 4
7 6 5
3 8 2
1 6 4
75
3 8 2
1 4
7 6 5
8 3
2 1 4
7 6 5
3 8 2
14
7 6 5
82
2 1 4
7 6 5
2 3 4
1 8
7 6 5
1 2 3
8 4
7 6 5
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
3 8 2
14
7 6 5
2 8 3
1 6
7 5 4
2 8 3
6 4
1 7 5
2 8 3
1 4 5
76
28
1 4 3
7 6 5
2 8 3
1 4 5
7 6
28
1 4 3
7 6 5
2 8 3
7 1 4
6 5
2 8 3
74
6 1 5
8 1 3
24
7 6 5
8 3 2
2 1 4
7 6 5
1 2 3
84
7 6 5
16
26
9
8
7
6
2
1
S0
4
3
5
Sg
圖示解的路徑是 S0-3-8-16-26(Sg)
寬度優先搜索的盲目性較大，當目標結點距離初始結點較遠時將會產生許多無用結點，空間浪費較大，搜索效率低，但是只要問題有解，用寬度優先搜索總可以得到解，而且得到的路徑最短的解。
用深度優先策略搜索，如下圖：
2 8 3
14
7 6 5
2 8 3
1 4
7 6 5
23
1 8 4
7 6 5
3 8 2
1 6 4
7 5
3 8 2
1 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
2 8 3
1 6
7 5 4
1
S0
2
2 8
1 6 3
7 5 4
2 8 1 6 3
7 5 4
2 8
1 6 3
7 5 4
3
4
5
6
在深度優先搜索中，搜索一旦進入某個分枝，就將沿著該分枝一直向下搜索，如果該節點恰好在此分支上，則可較快地得到解。但是，如果目標節電不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。
顯然該問題用寬度優先搜索的策略是較好的。
經典的N皇後問題
N皇後問題要求求出N個皇後在棋盤上的所有擺法，（該問題很多書籍上都有詳細介紹，這兒圖表省略），該問題是適合用回溯法來描述和解決的問題，通過深度優先搜索至多需要檢索N!個元組，而如果用分枝法，因為要生成所有問題的解，則必須儲存檢索過程中的E結點，造成儲存空間的極度膨脹，這類問題明顯是用回溯法佔優勢的。
回溯法和分枝法是基本的搜索策略，大多數情況下如果找不到更好的解決方案，總是可以用這二種方法嘗試。
但是它們有一個很大的缺陷就是都是在一個給定的狀態空間中窮舉。這在狀態空間不大的情況下是很合適的演算法，可是當狀態空間十分大，且不預測的情況下就不可取了。它的效率實在太低，甚至不可完成。
二、啟發式搜索演算法
通常在搜索中能直接運用回溯、分枝法的問題並不多，回溯和分枝的過程中，施加一定的條件，對搜索過程中出現的結點進行判斷，可以提高效率。
啟發式搜索就是在狀態空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。這樣可以省略大量無畏的搜索路徑，提到了效率。在啟發式搜索中，對位置的估價是關鍵。採用了不同的估價可以有不同的效果。
啟發式搜索有很多的演算法，如：局部擇優搜索法、最好優先搜索法等等。A*也是。這些演算法都使用了啟發函數，但在具體的選取最佳搜索節點時的策略不同。
局部擇優搜索法，就是在搜索的過程中選取「最佳節點」後舍棄其他的兄弟節點，父親節點，而一直得搜索下去。這種搜索的結果很明顯，由於舍棄了其他的節點，可能也把最好的節點都舍棄了，因為求解的最佳節點只是在該階段的最佳並不一定是全局的最佳。
局部擇優搜索法它是對深度優先搜索方法的一種改進。
全局擇優搜索是 局部擇優搜索的一種改進，試圖克服局部擇優搜索的的局限性。再搜索時，每次總是從全體的活結點中選取一個估價值最小的節點，
在搜索過程中，啟發式搜索的關鍵是要確定下一個要考察的節點，用於估價節點重要性的函數稱為估價函數
f'(x) = g(x) + h(x)
其中g(x)為從初始節點So到節點X已經實際付出的代價；h(x)是從節點X到節點Sg的最優路徑的估計代價。h(x)稱為啟發函數。
九宮重排
當用全局擇優搜索求解該問題時，可以設估價函數為 f'(x) = d(x) + h(x)
d(x)表示節點x的深度，h(x)表示節點x的棋局與目標節點棋局位置不相同的棋子數。
2 8 3
14
7 6 5
2 8 3
1 4
7 6 5
23
1 8 4
7 6 5
3 8 2
1 6 4
75
3 8 2
1 4
7 6 5
8 3
2 1 4
7 6 5
3 8 2
14
7 6 5
1 2 3
8 4
7 6 5
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
1 2 3
84
7 6 5
4
6
4
6
6
4
1
S0
4
4
5
Sg
1 2 3
7 8 4
6 5
5
5
S3
S2
S1
圖中節點旁標明的數字是該節點的估價函數值。
該問題的解路徑為： So-S1-S2-S3-Sg
以上論述一些樹型問題基本的搜索的策略，當問題的狀態空間是有向圖時，節點的重復將導致大量冗餘的搜索，甚至時搜索過程陷入無效的循環而無法找到解，這時就需要對估價函數進行限制，A*演算法就是針對圖的有序搜索的演算法。
問題的求解可以有很多方法，而如何建立數學模型，選擇問題的求解方式是十分重要的，方法的好壞是面向一個具體的問題的，需要具體問題具體分析
③ 基於社區發現演算法和圖分析Neo4j解讀《權力的游戲》下篇
其中的分析和可視化是用Gephi做的，Gephi是非常流行的圖分析工具。但作者覺得使用Neo4j來實現更有趣。
節點中心度
節點中心度給出網路中節點的重要性的相對度量。有許多不同的方式來度量中心度，每種方式都代表不同類型的「重要性」。
度中心性(Degree Centrality)
度中心性是最簡單度量，即為某個節點在網路中的聯結數。在《權力的游戲》的圖中，某個角色的度中心性是指該角色接觸的其他角色數。作者使用Cypher計算度中心性：
MATCH (c:Character)-[:INTERACTS]- RETURN c.name AS character, count(*) AS degree ORDER BY degree DESC
character
degree
Tyrion
36
Jon
26
Sansa
26
Robb
25
Jaime
24
Tywin
22
Cersei
20
Arya
19
Joffrey
18
Robert
18
從上面可以發現，在《權力的游戲》網路中提利昂·蘭尼斯特（Tyrion）和最多的角色有接觸。鑒於他的心計，我們覺得這是有道理的。
加權度中心性（Weighted Degree Centrality）
作者存儲一對角色接觸的次數作為 INTERACTS 關系的 weight 屬性。對該角色的 INTERACTS 關系的所有 weight 相加得到加權度中心性。作者使用Cypher計算所有角色的這個度量：
MATCH (c:Character)-[r:INTERACTS]- RETURN c.name AS character, sum(r.weight) AS weightedDegree ORDER BY weightedDegree DESC
character
weightedDegree
Tyrion
551
Jon
442
Sansa
383
Jaime
372
Bran
344
Robb
342
Samwell
282
Arya
269
Joffrey
255
Daenerys
232
介數中心性（Betweenness Centrality）
介數中心性：在網路中，一個節點的介數中心性是指其它兩個節點的所有最短路徑都經過這個節點，則這些所有最短路徑數即為此節點的介數中心性。介數中心性是一種重要的度量，因為它可以鑒別出網路中的「信息中間人」或者網路聚類後的聯結點。
圖6中紅色節點是具有高的介數中心性，網路聚類的聯結點。
為了計算介數中心性，作者使用Neo4j 3.x或者apoc庫。安裝apoc後能用Cypher調用其170+的程序：
MATCH (c:Character) WITH collect(c) AS charactersCALL apoc.algo.betweenness(['INTERACTS'], characters, 'BOTH') YIELD node, scoreSET node.betweenness = scoreRETURN node.name AS name, score ORDER BY score DESC
name
score
Jon
1279.7533534055322
Robert
1165.6025171231624
Tyrion
1101.3849724234349
Daenerys
874.8372110508583
Robb
706.5572832464792
Sansa
705.1985623519137
Stannis
571.5247305125714
Jaime
556.1852522889822
Arya
443.01358430043337
Tywin
364.7212195528086
緊度中心性（Closeness centrality）
緊度中心性是指到網路中所有其他角色的平均距離的倒數。在圖中，具有高緊度中心性的節點在聚類社區之間被高度聯結，但在社區之外不一定是高度聯結的。
圖7 ：網路中具有高緊度中心性的節點被其它節點高度聯結
MATCH (c:Character) WITH collect(c) AS charactersCALL apoc.algo.closeness(['INTERACTS'], characters, 'BOTH') YIELD node, scoreRETURN node.name AS name, score ORDER BY score DESC
name
score
Tyrion
0.004830917874396135
Sansa
0.004807692307692308
Robert
0.0047169811320754715
Robb
0.004608294930875576
Arya
0.0045871559633027525
Jaime
0.004524886877828055
Stannis
0.004524886877828055
Jon
0.004524886877828055
Tywin
0.004424778761061947
Eddard
0.004347826086956522
使用python-igraph
Neo4j與其它工具（比如，R和Python數據科學工具）完美結合。我們繼續使用apoc運行 PageRank和社區發現（community detection）演算法。這里接著使用python-igraph計算分析。Python-igraph移植自R的igraph圖形分析庫。 使用 pip install python-igraph 安裝它。
從Neo4j構建一個igraph實例
為了在《權力的游戲》的數據的圖分析中使用igraph，首先需要從Neo4j拉取數據，用Python建立igraph實例。作者使用 Neo4j 的Python驅動庫py2neo。我們能直接傳入Py2neo查詢結果對象到igraph的 TupleList 構造器，創建igraph實例：
from py2neo import Graphfrom igraph import Graph as IGraph graph = Graph query = ''' MATCH (c1:Character)-[r:INTERACTS]->(c2:Character) RETURN c1.name, c2.name, r.weight AS weight '''ig = IGraph.TupleList(graph.run(query), weights=True)
現在有了igraph對象，可以運行igraph實現的各種圖演算法來。
PageRank
作者使用igraph運行的第一個演算法是PageRank。PageRank演算法源自Google的網頁排名。它是一種特徵向量中心性(eigenvector centrality)演算法。
在igraph實例中運行PageRank演算法，然後把結果寫回Neo4j，在角色節點創建一個pagerank屬性存儲igraph計算的值：
pg = ig.pagerank pgvs = for p in zip(ig.vs, pg): print(p) pgvs.append({"name": p[0]["name"], "pg": p[1]}) pgvs write_clusters_query = ''' UNWIND {nodes} AS n MATCH (c:Character) WHERE c.name = n.name SET c.pagerank = n.pg '''graph.run(write_clusters_query, nodes=pgvs)
現在可以在Neo4j的圖中查詢最高PageRank值的節點：
MATCH (n:Character) RETURN n.name AS name, n.pagerank AS pagerank ORDER BY pagerank DESC LIMIT 10
name
pagerank
Tyrion
0.042884981999963316
Jon
0.03582869669163558
Robb
0.03017114665594764
Sansa
0.030009716660108578
Daenerys
0.02881425425830273
Jaime
0.028727587587471206
Tywin
0.02570016262642541
Robert
0.022292016521362864
Cersei
0.022287327589773507
Arya
0.022050209663844467
社區發現（Community detection）
圖8
社區發現演算法用來找出圖中的社區聚類。作者使用igraph實現的隨機遊走演算法（ walktrap）來找到在社區中頻繁有接觸的角色社區，在社區之外角色不怎麼接觸。
在igraph中運行隨機遊走的社區發現演算法，然後把社區發現的結果導入Neo4j，其中每個角色所屬的社區用一個整數來表示：
clusters = IGraph.community_walktrap(ig, weights="weight").as_clustering nodes = [{"name": node["name"]} for node in ig.vs]for node in nodes: idx = ig.vs.find(name=node["name"]).index node["community"] = clusters.membership[idx] write_clusters_query = ''' UNWIND {nodes} AS n MATCH (c:Character) WHERE c.name = n.name SET c.community = toInt(n.community) '''graph.run(write_clusters_query, nodes=nodes)
我們能在Neo4j中查詢有多少個社區以及每個社區的成員數：
MATCH (c:Character) WITH c.community AS cluster, collect(c.name) AS members RETURN cluster, members ORDER BY cluster ASC
cluster
members
0
[Aemon, Alliser, Craster, Eddison, Gilly, Janos, Jon, Mance, Rattleshirt, Samwell, Val, Ygritte, Grenn, Karl, Bowen, Dalla, Orell, Qhorin, Styr]
1
[Aerys, Amory, Balon, Brienne, Bronn, Cersei, Gregor, Jaime, Joffrey, Jon Arryn, Kevan, Loras, Lysa, Meryn, Myrcella, Oberyn, Podrick, Renly, Robert, Robert Arryn, Sansa, Shae, Tommen, Tyrion, Tywin, Varys, Walton, Petyr, Elia, Ilyn, Pycelle, Qyburn, Margaery, Olenna, Marillion, Ellaria, Mace, Chataya, Doran]
2
[Arya, Beric, Eddard, Gendry, Sandor, Anguy, Thoros]
3
[Brynden, Catelyn, Edmure, Hoster, Lothar, Rickard, Robb, Roose, Walder, Jeyne, Roslin, Ramsay]
4
[Bran, Hodor, Jojen, Luwin, Meera, Rickon, Nan, Theon]
5
[Belwas, Daario, Daenerys, Irri, Jorah, Missandei, Rhaegar, Viserys, Barristan, Illyrio, Drogo, Aegon, Kraznys, Rakharo, Worm]
6
[Davos, Melisandre, Shireen, Stannis, Cressen, Salladhor]
7
[Lancel]
角色「大合影」
《權力的游戲》的權力圖。節點的大小正比於介數中心性，顏色表示社區（由隨機遊走演算法獲得），邊的厚度正比於兩節點接觸的次數。現在已經計算好這些圖的分析數據，讓我們對其進行可視化，讓數據看起來更有意義。
Neo4j自帶瀏覽器可以對Cypher查詢的結果進行很好的可視化，但如果我們想把可視化好的圖嵌入到其它應用中，可以使用Javascript可視化庫Vis.js。從Neo4j拉取數據，用Vis.js的neovis.js構建可視化圖。Neovis.js提供簡單的API配置，例如：
var config = { container_id: "viz", server_url: "localhost", labels: { "Character": "name" }, label_size: { "Character": "betweenness" }, relationships: { "INTERACTS": }, relationship_thickness: { "INTERACTS": "weight" }, cluster_labels: { "Character": "community" } }; var viz = new NeoVis(config); viz.render;
其中：
節點帶有標簽Character，屬性name；
節點的大小正比於betweenness屬性；
可視化中包括INTERACTS關系；
關系的厚度正比於weight屬性；
節點的顏色是根據網路中社區community屬性決定；
從本地伺服器localhost拉取Neo4j的數據；
在一個id為viz的DOM元素中展示可視化。
④ 論文整理(1)社交網路影響力
社會網路分析理論：
在社會網路[63]由人類學家Barnes最早提出的概念，他在社會網路的分析基礎上統地研究挪威一個小漁村的跨親緣與階級的關系。在社會網路分析中，存在一些經典的理論。這些理論主要包括:六度分割理論、弱關系理論、150法則、小世界網路理論、馬太效應等。基於社會網路有關的研究方向和內容，在不同的領域著發揮著各自的作用，例如，社會影響力分析，社區發現，信息傳播模型，鏈接預測，基於社會網路的推薦。
150法則是指一個人能保持穩定社交關系的人數上限通常為150人。1929年由英國羅賓•鄧巴教授(Robin Dunbar)提出了經典的」150定律」理論，該定律同時也被稱為「鄧巴數字」[64]。這個定律在我們的實際日常生活中的應用是相當普遍的，SIM卡中只能存儲150個聯系人的電話，微軟的MSN中也只可以最多把150位聯系人的信息添加到自己的名單中[64]等等。
小世界網路是一種具有特殊結構的復雜網路，在這種網路中大部份的節點是不相鄰的，但絕大部份節點之間是連通的且距離很短。六度分割理論也是小世界網路理論的一種體現。在多數現實世界的社會網路中，盡管網路中的節點數量巨大，網路中相鄰的節點相對較少，但每兩個節點間往往只需要很短的距離便能連通。
六度分割就是指一個人與其他任何一個人之間建立起聯系，最多都只需要經過六個人。所以，即便鄧巴數字告訴我們，我們是能力上維持一個特別大的社交圈的，但是六度分割理論卻可以告訴我們，通過我們現有的社交人脈圈以及網路可以無限擴張我們的人脈圈，在需要的時候都能夠和地球中想要聯系的任何人取得聯系。
弱關系理論弱關系(Weak Tie)是指需要較少或不需要情感聯系的人們之間的社會聯系，這種聯系幾乎不需要耗費個人的時間或精力來維系，但這種聯系卻很有作用。美國社會學家Mark Granovetter在研宄人們在求職過程中如何獲取工作信息時發現[65]，由家人、好友等構成的強關系在獲取工作信息過程中起到的作用很有限，而那些關系較疏遠的同學、前同事等反而能夠提供更加有用的求職信息。
馬太效應可以理解為達爾文進化論中適者生存的理念。在社交網路的發展過程如同生物進化的過程，存在強者越強、弱者越弱的現象。也就是說，在社交網路中越是處於網路核心的節點很大可能會變來越核心，而那些處於社交網路中邊緣地帶的節點或許會越來越不重要甚至直至消失。那些在社交網路中相比其他節點擁有更大影響力的節點，其帶給該網路的影響也要比那些擁有弱影響力的節點所帶來的影響要強。
從不同角度探索節點影響力挖掘演算法：
1.基於鄰節點中心性的方法。這類方法最簡單最直觀，它根據節點在網路中的位置來評估節點的影響力。度中心性[13]考察網路中節點的直接鄰居數目，半局部中心性[14]考察網路中節點四層鄰居的信息，ClusterRank[15]同時考慮了網路中節點的度和聚類系數。
2.基於路徑中心性的方法。這類方法考察了節點在控制信息流方面的能力，並刻畫節點的重要性。這類方法包括子圖中心性[16]、數中心性[17]（一些演化演算法包括：路由介數中心性[18]，流介數中心性[19]，連通介數中心性[20]，隨機遊走介數中心性[21]等）及其他基於路徑的挖掘方法。
3.迭代尋優排序方法。這類方法不僅考慮了網路中節點鄰居的數量，並且考慮鄰居質量對節點重要性的影響，包括了特徵向量中心性[13]，累積提名[22]，PageRank演算法[23]及其變種[24-32]。
4.基於節點位置的排序演算法。這類方法最顯著的特點是，演算法並沒有給出一個計算節點重要性的定義，而是通過確定節點在網路中的位置，以此來確定節點的重要程度。在網路核心位置的節點，其重要性就相對較高，相反的，若節點處於網路邊緣，那麼它的重要性就會比較低。基於節點位置的以及不同應用場景的推薦演算法具有重要的研究意義[34-37]。
節點影響力評估方法：
在社交網路節點影響力的評估方法主要可以分為三類，基於靜態統計量的評估方法、基於鏈接分析演算法的評估方法，基於概率模型的評估方法。
眾學者在靜態統計量的方法上，結合不同社交網路中相關信息，借鑒鏈接分析法以及建立概率模型來評估節點影響力，對社交網路節點影響力可以做到更有效的評估[66]。
1)基於靜態統計量度量方法
主要是通過網路中節點的一些靜態屬性特徵來簡單直接地體現節點的影響力，但面對社交網路中復雜信息以及不同平台，並不能有效地度量不同社交網路中節點影響力。如度中心性，主觀認為節點的重要性取決於與其他節點連接數決定，即認為一個節點的鄰居節點越多，影響力越大。在有向網路中，根據邊的方向，分為入度和出度，在有權網路中，節點的度可以看作強度，即邊的權重之和。度中心性刻畫了節點的直接影響力，度中心性指標的特點是簡單、直觀、計算復雜度低，也具有一定合理性。
但針對不同平台的網路結構中，度中心性的影響力效果未必能達到目標效果，而且社交網路中用戶間關系的建立具有一定的偶然性，而且不同的用戶間的關系強度也不同。度中心性沒有考慮了節點的最局部信息，雖然對影響力進行了直接描述，但是沒有考慮周圍節點處所位置以及更高階鄰居。眾學者在靜態統計量的方法上，結合不同社交網路中相關信息，借鑒鏈接分析法以及建立概率模型來評估節點影響力，對社交網路節點影響力可以做到更有效的評估[66-67]。
2)基於鏈接分析演算法的方法
鏈接分析演算法(Link Analysis)主要應用在萬維網中用來評估網頁的流行性。通過超鏈接，萬維網中的網頁連接成一個網路，同時這個網路也具備了小世界網路的特徵，且微博平台中的關注和粉絲關系與網頁的鏈入與鏈出十分相似，因此鏈接分析法的思想也被應用在了微博社交網路中節點影響力的評估中。經典的演算法是PageRank[68]和HITS演算法[69](Hyperlink-Inced Topic Search)。
PageRank演算法模型，是Google在搜索引擎結果中對網站排名的核心演算法，核心思想通過計算頁面鏈接的數量和質量，來確定網站的重要性的粗略估計，即節點的得分取決於指向它的節點的數量和這些節點的本身得分。即有越多的優質節點指向某節點時它的得分越高。
HITS演算法是由Jon Kleinberg於1997年提出的。HITS演算法模型中，有兩類節點，權威(Authority)節點，和樞紐(Hub)節點。權威節點在網路中具有高權威性，樞紐節點具有很個指向邊的節點。通過計算網路中每個節點的Authority權威值和Hub樞紐值來尋找高權威性的節點。即求值過程是在迭代中計算Authority和Hub值，直到收斂狀態。Hub值和Authority值計算公式。
通過多數研究者發現，將鏈接分析法結合社交網路特性可以更好的對用戶影響力進行評估，由於技術的快速發展，社交網路的多變性，因此如何將社交網路中的復雜數據和用戶行為與相關演算法進行結合，仍是需要我們繼續研究的方向。
3)基於概率模型的方法
主要是建立概率模型對節點影響力進行預測。這么多學者將用戶影響力作為參數對社交網路中的節點用戶行為建立概率模型，並根據社交網路中已有的用戶數據求解概率模型，得出用戶影響力。
文獻[70]認為用戶間影響力越大、被影響用戶的活躍度和轉發意願越高，則其轉發另一個用戶的信息的概率越大，所以利用用戶影響力、轉發意願和活躍度等構建轉發概率模型。通過用戶發布的tweet數量、轉發的tweet數和用戶的歷史轉發行為數據，計算出用戶活躍度、轉發意願和轉發概率，進而社交網路中用戶影響力。
文獻[71]在度量影響力時融合了用戶發布信息的主題生成過程，認為興趣相似或經常聯系的用戶間影響力較強，用戶的行為受其朋友的影響也受其個人興趣的影響。基於這些假設，結合文本信息和網路結構對LDA模型進行擴展，在用戶發布信息的基礎上建立模型，通過解模型計算得出用戶間基於主題的影響力。
文獻[72]認為轉發概率同樣可以體現用戶間的影響力，根據用戶間的關注關系。歷史轉發記錄，利用貝葉斯模型預測用戶間的轉發概率。
文獻[73]考慮了用戶建立關注關系的原因，用戶被關注可能是與關注者興趣投，也可能受用戶的影響力影響。將基於用戶的主題建模和基於主題的影響力評估相結合，並在同一個生成模型中進行計算，提出基於LDA演算法模型的擴展演算法模型FLDA模型(Followship-LDA)。
[13] P. Bonacich. Factoring and weighting approaches to status scores and clique identification[J]. Journal of Mathematical Sociology, 1972, 2(1): 113-120
[14]D.Chen,L.Lü,M.S.Shang,etal.[J]. Physica A, 2012, 391(4): 1777-1787
[15] D. B. Chen, H. Gao, L. Lü, et al. Identifying influential nodes in large-scale directed networks: The role of clustering[J]. PLoS One, 2013, 8(10): e77455
[16]E.Estrada, J.A. Rodriguez-Velazquez.[J].Physical Review E, 2005, 71(5): 122-133
[17]L.C.Freeman.[J].Sociometry,1977, 40(1): 35-41
[18] S. Dolev, Y. Elovici, R. Puzis. Routing betweenness centrality[J].Journal of the ACM, 2010, 57(4): 710-710
[19] Y. Gang,Z.Tao, H. Bo,etal. [J].PhysicalReviewE, 2005, 73(4): 46108
[20] E. Estrada, D. J. Higham, N. Hatano. Communicability betweenness in complex networks[J]. Physica A, 2009, 388(5): 764-774
[21]M.E.J.Newman.[J].Social networks, 2005, 27(1): 39-54
[22]R.Poulin,M.C.Boily,B.R.Masse. networks[J]. Social networks, 2000, 22(3): 187-200
[23] B. S. Brin, L. Page. The anatomy of a large scale hypertextual Web search engine[J]. Computer Networks & ISDN Systems, 1998, 30: 107-117
[24] P. Jomsri, S. Sanguansintukul, W. Choochaiwattana. CiteRank: combination similarity and static ranking with research paper searching[J]. International Journal of Internet Technology & Secured Transactions, 2011, 3(2): 161-177
[13][25]H.S.Bhat,B.Sims.[D].California: University of California. 2012
[26] J. Weng, E. P. Lim, J. Jiang, et al. Twitterrank: finding topic-sensitive influential twitterers[C]. Third International Conference on Web Search & Web Data Mining, ACM, 2010, 261-270
[27]Y.B.Zhou,L.Lu,M.Li.: [J].NewJournalofPhysics,2012,14(14): 33033-33049
[28] J. Xuan, H. Jiang, Z.Ren, et al. Developer prioritization in bug repositories[C]. International Conference on Software Engineering, 2012, 25-35
[29]Q.Li,T.Zhou,L.Lü,etal.[J]. Physica A, 2013, 404(24)47-55
[30] L. Lü, Y. C. Zhang, C H Yeung, et al.Leaders in social networks, the delicious case[J]. PLoS One, 2011, 6(6): e21202
[31]J.M.Kleinberg.[J].Authoritative sources in a hyperlinked environmen, 1999, 46(5): 604-632
[32]R.Lempel,S.Moran.Thestochasticapproachforlink-structureanalysis(SALSA)andthe TKC effect[J]. Computer Networks, 2000, 33(2): 387-401
[33]T.Martin,X.Zhang,M.E.J.Newman.[J].Physical Review E, 2014, 90(5): 052808
[34] A. Banerjee, A. G. Chandrasekhar, E. Duflo, et al. Gossip: Identifying central indivials in a social network[R]. National Bureau of Economic Research, 2014.
[35]S.Ji,L.Lu,C.H.Yeung,etal. percolation in social networks[J]. arXiv preprint arXiv:1508.04294, 2015.
[36] S. Y. Tan, J. Wu, L. Lü, et al. Efficient network disintegration under incomplete information: the comic effect of link prediction[J]. Scientific Reports, 2016, 6.
[37]任曉龍,呂琳媛.網路重要節點排序方法綜述[J].科學通報, 2014,59(13): 1175-1197
[63]貝克,曉冬.社會資本制勝:如何挖掘個人與企業網路中的隱性資源[M].上海交通大學出版社,2002.
[64]天涯.六度分隔理論和150法則[EB/OL].http://blog.sina.com.cn/s/blog_62bae1640100|5f3.html.[2010-07-14].
[65]Granovetter M S.The Strength of Weak Ties[J]. American journal of sociology, 1973: 1360-1380.
[66]王梓.社交網路中節點影響力評估演算法研究[D].北京郵電大學, 2014.
[67] Meeyoung Cha, Hamed Haddadi,Fabricio Benevenutoets. Measuring User Influence in Twitter: The Million Follower Fallacy[C]. Proceedings of the 4th International AAAI Conference on Weblogs and Social Media (ICWSM),2010:10-17
[3][68] Page, Lawrence, Brin, et al. The PageRank citation ranking[C]// BringingOrder to the Web. Stanford InfoLab. 1998: 1-14.
[4][69]Kleinberg J M. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM, 1999, 46(5): 604-632.
[70]Zibin Yin, Ya Zhang. Measuring Pair-Wise Social Influence inMicroblog[C], 2012 ASE/IEEE International Conference on SocialComputing and 2012 ASE/IEEE International Conference on Privacy,Security, Risk and Trust, 2012: 502-507.
[71]Lu Liu, Jie Tang, Jiawei Han, Meng Jiang, Shiqiang Yang. Mining topic-level influence in heterogeneous networks[C]. Proceedings of the 19th ACMinternational conference on information and knowledge management, 2010: 199-208.
[72] Qianni Deng, Yunjing Dai. How Your Friends Influence You: Quantifying Pairwise Influences on Twitter[C], International Conference on Cloud and Service Computing, 2012:185-192.
[73] Bi, Bin, et al. Scalable Topic-Specific Influence Analysis on Microblogs[C], Proceedings of the 7th ACM international conference on Web search and data mining,2014: 513-522.
⑤ 數據結構和演算法為什麼這么重要
演算法都是從生活里得到的，生活里用的很自如，應用到程序里一樣會很方便。
比如最簡單的，中國有那麼多省，每個省有那麼多市，每個市有那麼多區縣之類的，看到一個小地方，怎麼才能知道它在哪，很明顯，去看它在哪個區，哪個市，哪個省。
這就是樹的作用，從子節點通過父節點去確定它的位置。這個同樣應用在文件管理，還有特殊的比如要求設計個資料庫，能夠體現部門，小組的包含關系，很簡單，在小組裡面加個父節點的欄位就可以了。
再比如查字典，給了一個字，怎麼才能查到它？通過讀音，知道它的首字母，就很容易的去從首字母找到它。如果字典是亂的，就完全無從下手，這就是hash演算法的東西，通過能夠區分出來的特徵，縮小查找范圍，加快查找效率。
同樣的很多，都是可以用到程序里的，很容易理解
⑥ 圖的節點特徵
我的微信公眾號是「黃泓圖計算分享」，很多朋友反映公眾號上看文章不方便，就在上同步一份
圖包含兩大要素：節點和邊。節點和邊上都可以有屬性，邊既可以有方向也可以無向。對於圖的建模，可以包含結構上的特徵和聚集的特徵。特徵表徵的粒度，可以是節點，邊，子圖等等。
本文先從最常見的情況講起：以節點為粒度的結構特徵。以節點為粒度的結構特徵，往往同時會作為圖嵌入（Graph Embedding）演算法的輸入，從而得到描述節點所在的局部結構的向量。例如度以及三角形的個數，可以作為Role2vec[5]或者GraphSage[6]的輸入。這些後面再詳談。
以節點為粒度的結構特徵，最簡單的是度（degree），也就是一個節點關聯的鄰居節點的個數。在很多應用中，想必大家都有意無意用過這個特徵。
節點的重要性
描述節點重要性的特徵，一般有兩類：一類是基於一定的定義直接描述的特徵，如度，介數中心性和緊密中心性等等。另外一類是源於互聯網鏈接分析的演算法，如HITS演算法和PageRank演算法。
根據定義直接描述的節點重要性
介數中心性（betweeness） 描述的是一個節點作為樞紐節點的重要程度。描述一個節點作為樞紐的重要程度還有別的方法（如HITS，下面會提到），介數中心性採用的是最粗暴的定義方法：一個節點的介數中心性是經過這個節點的最短路徑條數與所有最短路徑條數的比值。因為定義簡單粗暴，所以計算起來也比較麻煩。如果要進行分布式計算的話需要設計特殊的演算法。比較好的一個實現來自sparkling graph：
https://github.com/sparkling-graph/sparkling-graph/tree/master/operators/src/main/scala/ml/sparkling/graph/operators/measures/vertex/betweenness
這里betweeness使用了兩個實現，分別是Edmonds[1]和Hua[2]。親測Hua的實現效率更加高一些，奈何話題太冷，論文沒什麼人引用。
緊密中心性（closeness centrality） 描述一個節點到圖中其他節點的難易程度。取的是這個節點到圖中其他節點的距離平均數的倒數。如果這個值比較大，那麼說明這個節點到其他節點大部分都是經過很少的幾步就行，整個圖結構比較緊密。對於這個指標，sparkling graph也有比較好的實現。
三角形計數（triangle count） 是用來描述一個圖中的頂點之間聚集密集程度的系數。節點所在的局部結構越密集，三角形個數越多。對於這個指標，spark graphx有比較好的實現。
基於鏈接分析的節點重要性特徵
HITS演算法和PageRank演算法最初的提出都是用於衡量Web圖模型中頁面的重要程度。他們基於不同的假設。
用戶瀏覽網頁的隨機遊走模型(Random Surfer Model)
用戶瀏覽網頁的隨機遊走模型(Random Surfer Model)假設用戶隨機遊走網頁由兩部分構成：
（1）直接跳轉：用戶進入一個網頁a，並且以等概率訪問這個網頁的鏈接（假設這個網頁有d個鏈接，則為1/d）
（2）遠程跳轉（teleporting）：用戶瀏覽到某個程度之後決定不再繼續深入，而是輸入另外一個網址重新瀏覽。
PageRank演算法
假設：
（1） 數量假設： 一個頁面節點接收到的入鏈數量越多，他就越重要
（2） 質量假設： 如果指向一個頁面節點的頁面節點重要，這個頁面就越重要
基於這樣的假設以及random surfer model可以得到PageRank的迭代公式。首先一個頁面節點a可能以兩者方式受到訪問：一種是遠程跳轉，一種是直接跳轉。
假設圖中有N個節點，用戶有概率1-p會進行遠程跳轉，則遠程跳轉的概率是：
進入遠程跳轉的概率 x 選中這個節點的概率=(1-p)x(1/N)
第二種方式是有其他節點等概率跳轉而來。假設節點a的一個鄰居b，b自己有degree(b)個鄰居，b自己的page rank分數為PR(b)，則b能夠給a的分數為PR(b)/degree(b)。a的所有鄰居能分給a的page rank分數加起來，再乘以用戶進入直接跳轉的概率p，就是在直接跳轉這種方式下節點a能夠得到的page rank分數。
遠程跳轉和直接跳轉兩部分分數結合起來，也就是大家一般在博客里看到的page rank迭代公式。
HITS演算法
HITS演算法認為節點有兩個特性：一是節點本身的重要程度，即權威度（Authority）。二是節點作為引向重要節點的樞紐節點的重要程度，即樞紐度（Hub）。
假設：
（1）一個Authority值高的節點應該有很多Hub值高的節點指向
（2）一個Hub值高的節點應該指向很多Authority值高的節點
HITS的迭代方式就是這樣Authority值和Hub值迭代相互增強：
（1）一個節點的Authority值是指向他的節點的hub值之和（對應假設1）
（2）一個節點的Hub值是他指向的節點的Authority值之和（對應假設2）
執行1，2直到收斂
如果沒有種子集合，HITS的初始值可以所有節點的authority和hub值都設置為1。如果有種子集合，則構圖方式為對種子集合進行擴充，凡是和種子集合裡面的節點有直接指向關系的節點都擴充進來，然後使用上述的迭代步驟。
應用場景
PageRank可以用於僅僅依靠鏈接指向判斷圖中的重要節點。HITS和page rank值本身也可以作為節點特徵輸入分類模型。例如對於企業違約風險的預測當中，[3]提到基於企業之間的擔保關系可以構建一個有向圖。這個論文使用了不同的圖特徵作為輸入，發現HITS得到的authority和hub值的特徵權重比較大。作者對此的解釋是：風險大的企業，需要找很多公司擔保，從而authority值高，最後違約率高。風險低，穩健的企業，傾向於擔保很多企業，Hub值就會很高。其實單純從這個角度來講，直接用節點的出度和入度做特徵也是可以的。HITS得到的好處在於可以實現Hub和Authority分值的相互增強。
HITS與PageRank在應用場景上的一個重要區別是HITS可以從一個有標注的種子集合向外擴充得到其他同樣相關的節點中的重要節點。[4]使用HITS從一個專家標注的與「時尚」有關的網頁地址的種子集合進行擴充，自動對外部關聯的網頁與「時尚」的相關性進行排序。重要的一點是作者提到PageRank和HITS在使用場景上的重要區別：
（1）PageRank在你有比較完整的鏈接信息的時候才有效，而HITS可以在鏈接信息不完整的時候也發揮作用
（2）HITS可以利用人工標注的樣本進行挖掘，PageRank不行（除非personalized page rank，不過那是另一個故事了）
引用
[1]Edmonds N , Hoefler T , Lumsdaine A . A space-efficient parallel algorithm for computing betweenness centrality in distributed memory[C]// 2010 International Conference on High Performance Computing, HiPC 2010, Dona Paula, Goa, India, December 19-22, 2010. IEEE, 2010.
[2] Hua Q S , Fan H , Ai M , et al. Nearly Optimal Distributed Algorithm for Computing Betweenness Centrality[C]// IEEE International Conference on Distributed Computing Systems. IEEE, 2016.
[3] Niu Z, Cheng D, Yan J,et al. A hybrid approach for riskassessment of loan guarantee network[J]. Papers, 2017.
[4]https://www.confluent.io/blog/ranking-websites-real-time-apache-kafkas-streams-api/
[5]Ahmed N K , Rossi R , Lee J B , et al. Learning Role-based Graph Embeddings[J]. 2018.
[6]Hamilton W L , Ying R , Leskovec J . Inctive Representation Learning on Large Graphs[J]. 2017.
⑦ 網路中關鍵節點的識別
最近半年一直在嘗試從復雜的關系網路中，挖掘可能從事某種惡意的團伙，比如在交易數據中挖掘潛在可疑交易的詐騙團伙等。在對全網的復雜網路分團後，面臨一個問題，就是需要識別可疑惡意團伙的核心節點，或者關鍵節點。
從調研的情況來看，主要有如下衡量節點重要性的手段：
這是一種最簡單也最直觀的衡量方式，計算網路中每個節點的度數，根據度數大小衡量重要性。度數越大，說明與該節點連接的節點越多，即該節點越重要。典型的案例，如微博的大V，因為其分數多，度數高，因此根據度衡量，大V們往往會被計算為團中的關鍵節點。
優點：計算簡單，成本低，是一種考慮節點近鄰的排序方式。
存在的問題：缺乏全局的考慮，因為其僅考慮了1度關聯的節點數，甚至沒有考慮關聯節點的重要性。如果某個大V購買了很多僵死粉，也會被計算為關鍵節點，雖然這個「大V」對其他正常用戶的影響力很小。
某個節點的介數，是指網路中所有的最短路徑中經過該節點的路徑數。介數越高，說明網路中任意兩個人的關系與這個節點的關系越大，即這個節點在全局中的影響力越大，也就越重要越關鍵。
優點：相比度，介數考慮節點在整個網路中的重要程度，是一種基於路徑的衡量，或叫排序方式。
存在的問題：計算時間復雜度較大，尤其在節點較多的網路中，在實際應用中需要進行優化。
核度也是一種基於近鄰度量的計算方式。對網路從外圍一層一層剝離直到沒有節點，節點的核度是指該節點處於被剝離的位置。如度為1的節點為最外層，也就是核度為1的層，剝離這些節點後，會再次出現度為1的節點，重復剝離。值得注意的是，並不是度越大的節點，核度越大，越最後被剝離。
如果一個節點的核度越大，越是最後被剝離，說明它越處於網路中的中心位置，也就越重要。
優點：相比度的局限性，核度考慮了節點在整個網路的重要程度，並且計算復雜度沒有明顯增大。
存在的不足：劃分力度太粗，導致很多看起來並不屬於同一層級的節點，被劃分為相同的重要層級，即每一次剝離的節點很多。
除了上述3個指標，還有很多其他衡量節點的方式，如H指數等。綜合來看，挖掘和識別網路中的重要節點，目前存在如下的問題：
1、無法找到一種適合所有網路結果的衡量方式，也就是說，不同網路結果的節點重要性衡量是不一樣的。
2、即使在明確的衡量公式下，不同參數也會導致結果不同。
3、眾多的分析演算法都是對單個點的重要性衡量，而不是節點集，重要的節點集，並不是單個節點的集合，而是對復雜網路的一種抽取。