圖論在社交網路的應用

Ⅰ 圖論的應用領域有哪些

圖論的應用領域有很多。凡是涉及排列組合優化問題的都免不了要用到圖論中的各種知識。比如通信編解碼，矩陣運算，任務分配，GPS路徑規劃等等。

至於圖論的經典著作，可以自己去google一下graph theory。

Ⅱ 圖論的實際應用例子

圖論的實際應用例子如下：

什麼是圖形？

大多數人對"圖形"這個術語有著非常廣泛的理解，代表了大多數數學圖形描述。然而，正如人們所期望的那樣，在數學中有一個非常清晰的定義，即圖形是什麼，我們圍繞它們建立有用的規則和計算，使它們對試圖解決的問題有用。

多圖是兩個頂點之間具有有多條邊的圖，通常描繪不同的關系。可以想像一下飛機航線路線圖，每條航線都是航班號。倫敦和紐約之間會有大量的邊（路線）。

偽圖（Pseudographs）是允許將頂點連接到自身的圖形。毋庸置疑，在描繪人際關系的圖表中通常不需要這樣做。但是，例如你需要使用圖表來描繪辦公室中的咖啡訂單以及誰正在購買適合他們的商品時，那麼採用偽圖將非常有用。

在完整的圖形中，沒有更多的邊可以添加到邊集上。所有頂點都相互連接。它可以是一個有用的數學工具來證明圖形是完整的。

樹圖也非常明顯，但它們在數學上被定義為連接且沒有循環的圖形。這意味著任何一對不同的頂點都可以通過一組邊相互連接，但不可能通過一組邊將頂點連接到自身。家譜通常就是這樣的一個例子。例如皇室成員，那麼可以看看西班牙國王查爾斯二世的家譜。

Ⅲ 「社交網路分析」是門怎樣的學科

我們知道每個用戶的活動時間序列，知道用戶之間的聯系，但顯然不能簡單地認為誰粉絲多誰就值錢，因為有些人粉絲質量高。那最簡單的辦法就是咱們來個page rank，至少我能知道誰相對誰更值錢。這樣我至少能在一定程度上量化影響力了，然後再根據其他的feature做一些調整。

但這個方法還是有問題。因為pagerank沒有考慮時間序列。影響力估計的不準。那再進一步，做一個generative model，每個user都以一定的概率（可以簡單的時變）觀看，轉發，點贊他們關注的人的post，為了減少參數，再引入一些隱含變數聲明用戶分多少多少類。做一個agent based model。然後把這個model 放進data 裡面，做參數估計。最後user的粉絲的點贊的期望，可能可以作為影響力的量化。

Ⅳ 2019-05-12

關於漫威英雄的社交網路系列已寫了好幾篇文章，是時候結束它了。作為本系列的最後一篇文章，我們將來研究一下如何在cypher語句映射的虛擬圖上進行中心性計算，我們將使用Neo4j和圖形演算法庫來找出漫威英雄網路中最有影響力的英雄或其他重要的英雄。

關於漫威社交網路的研究已完成的文章有以下幾篇：

在Neo4j中構建漫威社交網路

在Neo4j中對漫威社交網路進行初步分析

Neo4j中基於三角形個數和連通分量的漫威英雄初步社群分析

Neo4j中使用Louvain和標簽傳播演算法對漫威英雄進行客戶群分析

正如我在前面文章中說過的，使用Cypher映射虛擬圖是真的好用，他可以使我們簡單快速的映射一個我們想要的虛擬圖，我們簡稱為「Cypher載入」。為了更好的理解這個神奇的功能，我們需要深入了解它是如何工作。

與直接使用結點標簽和關系類型載入子圖不同，Cypher載入允許我們定義關系的方向，通常是以下三種值「incoming」,"outgoing"或者"both"(雙向/無向)，但是Cypher載入不支持單條無向關系。

這看起來可不太友好，但事實上，Cypher載入允許我們使用Cypher查詢語句映射各種虛擬圖去嘗試執行圖像演算法。我在之前的文章中也使用過，只是沒有詳細的介紹它而已。 

假設我們現在有兩個英雄結點以及在他們之間有一個單向的關系。將此圖載入為無向圖或者有向圖的唯一區別就是：在使用Cypher查詢語句映射時是否指定關系的方向。當我們在查詢時不指定方向，Cypher引擎會為每個關系返回兩個方向的結果，這樣我們映射圖也就是雙向的，你也可以稱他為無向的。

在圖論與網路分析中，中心性是用來表示網路中結點重要性的指標之一。在社交網路中，其用來表明最有影響力的人。在互聯網、城市網路甚至傳染病學中，用來表明關鍵結點。中心性概念最初應用在社交網路中，並且它的很多術語都可以反應出其社會學起源，隨後中心性被推廣到其它類型網路的分析中。[1]

Pagerank是因Google專有的搜索演算法。它通過計算鏈接到頁面的鏈接數量和質量來決定當前頁面的重要性。其基本的假設是，重要的結點肯定會有許多的頁面鏈向它。關於Pagerank更多內容可以看此文(https://neo4j.com/docs/graph-algorithms/3.5/algorithms/page-rank/)

我們使用Cypher載入來漫威網路中最大社群的結點，並且設置關系的weight閾值為100.

美國隊長是Pagerank分數最高的，他位於網路的中心，有24個關系，並且與其他重要英雄如雷神托爾、蜘蛛俠、鋼鐵俠都有聯系。如果我們仔細看一下與美國隊長有聯系的英雄，會發現一個有趣現象，他們因為與美國隊長有聯系，而使得他們的pagerank分也比較高。

接近中心性定義了一個點到所有其他點最短距離的和，換句話說，要計算接近中心性，首先需要計算每對結點之間的最短路徑長度。然後再對每個結點計算其到所有其他結點的最短路徑和。[2]

接近中心性可以理解為信息流到達網路中任一點的所消耗的時間指標。這個接近中心性分數越高，代表信息流從一個結點到另一個結點所花的時間就越長。因此，我們可以認為接近中心性代表著一個結點到達其他結點的潛在能力。關於更多信息可見文檔(https://neo4j.com/docs/graph-algorithms/3.5/algorithms/closeness-centrality/)

我們仍將使用Cypher載入漫威網路中最大社群中的結點並將關系的weight閾值設置為100。對於接近中心性而言，最重要的是需要載入一個獨立社群。

不幸的是，當圖是非連通圖時，接近中心性是無法使用的，因為在非連通圖中，兩個點可能屬於不同的社群，則這兩個點是無法連接的，這樣他們之間的距離就是無窮大。對於這樣的圖中的每一個點，都有屬於另一個社群的點與之無法連接。因此圖中所有頂點的都是沒有用的，而接近中心性的計算也被限制在最大的社群中，其他社群中結點的作用是被忽略的。

上圖中可以看出，美國隊長的位置非常特殊，事實上，在所有類型的中心性上，美國隊長都是排第一。我們可以看到，在較緊密的社群里，其結點的接近中心性的值相對較大，而在邊緣或較少連接的結點上，其接近中心性的值也較小。另外，我們還注意到圖中結點的分布也很重要，一般中間社群結點的接近中心性值要比周邊社群的高。例如，鋼鐵俠和幻視要比蜘蛛俠的接近中心性高。但有意思的是蜘蛛俠的Pagerank值要比較他們大。

從畢達哥拉斯和柏拉圖時代起，人們就知道，和諧就是「諧調和優美的比率」的表述，後來，音樂家用來表達規范音階，建築學家描述建築的完美比例。[4]

社交網路分析是一門快速發展的且跨學科領域，它由社會學、物理學、歷史學、數學、政治等多種學科共同發展而來。可能是由於缺少綜合性研究，造成其中有些方法存在著不足，但已被普遍所接受(Freeman, 1978; Faust & Wasserman, 1992)，而接近中心性在非連通網路的不適用性就是其一。和諧中心性也正是用來在非連通網路中代替接近中心性的。實際情況顯示，在真實環境下，我們解讀的結果發現其與接近中心性指標一致，計算復雜度相同，但最重要的是它可用於非連通網路！[3]

因為和諧中心性是為了幫助接近中心性解決其在非連通圖上的問題，所以，得到的結果也是相似的。 

在圖論中，中介中心性是一種基於最短路徑的中心性指標。在連通圖中，每對點都存在著至少一條最短路徑，對於無權重圖，最短路徑是指路徑所包含的關系數最少，對於權重圖，最短路徑是指路徑所含邊的權重之和最小。而每個點的中介中心性值就是通過這個點的最短路徑的條數。更多描述見(https://neo4j.com/docs/graph-algorithms/current/algorithms/betweenness-centrality/)

我們仍然使用Cypher載入那個最大的社群並設置關系的weight閾值為100

美國隊長仍然排在第一位，但這次野獸排到了第二位，這並不奇怪，因為他產中間和右邊社群的橋梁。蜘蛛俠和浩克扮演著與野獸相同的角色，但不同的是，他們倆所關聯的社群較小，所以，他們的中介中心性值也更低。

[1] https://en.wikipedia.org/wiki/Centrality

[2] http://qualquant.org/wp-content/uploads/networks/2008+1-7-3.pdf

[3] https://infoscience.epfl.ch/record/200525/files/[EN]ASNA09.pdf?

[4] https://arxiv.org/pdf/cond-mat/0008357.pdf

[6] https://en.wikipedia.org/wiki/Betweenness_centrality

Ⅳ 大數據怎麼學

處理大數據需要一個綜合、復雜、多方位的系統，系統中的處理模塊有很多，而數據挖掘技術以一個獨立的身份存在於處理大數據的整個系統之中，與其他模塊之間相輔相成、協調發展。在大數據時代中，數據挖掘技術的地位是無可比擬的。

數據挖掘的基本流程
在正式講數據挖掘知識清單之前，我先和你聊聊數據挖掘的基本流程。

數據挖掘的過程可以分成以下 6 個步驟。

商業理解：數據挖掘不是我們的目的，我們的目的是更好地幫助業務，所以第一步我們要從商業的角度理解項目需求，在這個基礎上，再對數據挖掘的目標進行定義。

數據理解：嘗試收集部分數據，然後對數據進行探索，包括數據描述、數據質量驗證等。這有助於你對收集的數據有個初步的認知。

數據准備：開始收集數據，並對數據進行清洗、數據集成等操作，完成數據挖掘前的准備工作。

模型建立：選擇和應用各種數據挖掘模型，並進行優化，以便得到更好的分類結果。

模型評估：對模型進行評價，並檢查構建模型的每個步驟，確認模型是否實現了預定的商業目標。

上線發布：模型的作用是從數據中找到金礦，也就是我們所說的「知識」，獲得的知識需要轉化成用戶可以使用的方式，呈現的形式可以是一份報告，也可以是實現一個比較復雜的、可重復的數據挖掘過程。數據挖掘結果如果是日常運營的一部分，那麼後續的監控和維護就會變得重要。

數據挖掘的十大演算法
為了進行數據挖掘任務，數據科學家們提出了各種模型，在眾多的數據挖掘模型中，國際權威的學術組織 ICDM （the IEEE International Conference on Data Mining）評選出了十大經典的演算法。

按照不同的目的，我可以將這些演算法分成四類，以便你更好的理解。

l 分類演算法：C4.5，樸素貝葉斯（Naive Bayes），SVM，KNN，Adaboost，CART

l 聚類演算法：K-Means，EM

l 關聯分析：Apriori

l 連接分析：PageRank

1. C4.5

C4.5 演算法是得票最高的演算法，可以說是十大演算法之首。C4.5 是決策樹的演算法，它創造性地在決策樹構造過程中就進行了剪枝，並且可以處理連續的屬性，也能對不完整的數據進行處理。它可以說是決策樹分類中，具有里程碑式意義的演算法。

2. 樸素貝葉斯（Naive Bayes）

樸素貝葉斯模型是基於概率論的原理，它的思想是這樣的：對於給出的未知物體想要進行分類，就需要求解在這個未知物體出現的條件下各個類別出現的概率，哪個最大，就認為這個未知物體屬於哪個分類。

3. SVM

SVM 的中文叫支持向量機，英文是 Support Vector Machine，簡稱 SVM。SVM 在訓練中建立了一個超平面的分類模型。如果你對超平面不理解，沒有關系，我在後面的演算法篇會給你進行介紹。

4. KNN

KNN 也叫 K 最近鄰演算法，英文是 K-Nearest Neighbor。所謂 K 近鄰，就是每個樣本都可以用它最接近的 K 個鄰居來代表。如果一個樣本，它的 K 個最接近的鄰居都屬於分類 A，那麼這個樣本也屬於分類 A。

5. AdaBoost

Adaboost 在訓練中建立了一個聯合的分類模型。boost 在英文中代表提升的意思，所以 Adaboost 是個構建分類器的提升演算法。它可以讓我們多個弱的分類器組成一個強的分類器，所以 Adaboost 也是一個常用的分類演算法。

6. CART

CART 代表分類和回歸樹，英文是 Classification and Regression Trees。像英文一樣，它構建了兩棵樹：一顆是分類樹，另一個是回歸樹。和 C4.5 一樣，它是一個決策樹學習方法。

7. Apriori

Apriori 是一種挖掘關聯規則（association rules）的演算法，它通過挖掘頻繁項集（frequent item sets）來揭示物品之間的關聯關系，被廣泛應用到商業挖掘和網路安全等領域中。頻繁項集是指經常出現在一起的物品的集合，關聯規則暗示著兩種物品之間可能存在很強的關系。

8. K-Means

K-Means 演算法是一個聚類演算法。你可以這么理解，最終我想把物體劃分成 K 類。假設每個類別裡面，都有個「中心點」，即意見領袖，它是這個類別的核心。現在我有一個新點要歸類，這時候就只要計算這個新點與 K 個中心點的距離，距離哪個中心點近，就變成了哪個類別。

9. EM

EM 演算法也叫最大期望演算法，是求參數的最大似然估計的一種方法。原理是這樣的：假設我們想要評估參數 A 和參數 B，在開始狀態下二者都是未知的，並且知道了 A 的信息就可以得到 B 的信息，反過來知道了 B 也就得到了 A。可以考慮首先賦予 A 某個初值，以此得到 B 的估值，然後從 B 的估值出發，重新估計 A 的取值，這個過程一直持續到收斂為止。

EM 演算法經常用於聚類和機器學習領域中。

10. PageRank

PageRank 起源於論文影響力的計算方式，如果一篇文論被引入的次數越多，就代表這篇論文的影響力越強。同樣 PageRank 被 Google 創造性地應用到了網頁權重的計算中：當一個頁面鏈出的頁面越多，說明這個頁面的「參考文獻」越多，當這個頁面被鏈入的頻率越高，說明這個頁面被引用的次數越高。基於這個原理，我們可以得到網站的權重劃分。

演算法可以說是數據挖掘的靈魂，也是最精華的部分。這 10 個經典演算法在整個數據挖掘領域中的得票最高的，後面的一些其他演算法也基本上都是在這個基礎上進行改進和創新。今天你先對十大演算法有一個初步的了解，你只需要做到心中有數就可以了，具體內容不理解沒有關系，後面我會詳細給你進行講解。

數據挖掘的數學原理
我說了這么多數據挖掘中的經典演算法，但是如果你不了解概率論和數理統計，還是很難掌握演算法的本質；如果你不懂線性代數，就很難理解矩陣和向量運作在數據挖掘中的價值；如果你沒有最優化方法的概念，就對迭代收斂理解不深。所以說，想要更深刻地理解數據挖掘的方法，就非常有必要了解它後背的數學原理。

1. 概率論與數理統計

概率論在我們上大學的時候，基本上都學過，不過大學里老師教的內容，偏概率的多一些，統計部分講得比較少。在數據挖掘里使用到概率論的地方就比較多了。比如條件概率、獨立性的概念，以及隨機變數、多維隨機變數的概念。

很多演算法的本質都與概率論相關，所以說概率論與數理統計是數據挖掘的重要數學基礎。

2. 線性代數

向量和矩陣是線性代數中的重要知識點，它被廣泛應用到數據挖掘中，比如我們經常會把對象抽象為矩陣的表示，一幅圖像就可以抽象出來是一個矩陣，我們也經常計算特徵值和特徵向量，用特徵向量來近似代表物體的特徵。這個是大數據降維的基本思路。

基於矩陣的各種運算，以及基於矩陣的理論成熟，可以幫我們解決很多實際問題，比如 PCA 方法、SVD 方法，以及 MF、NMF 方法等在數據挖掘中都有廣泛的應用。

3. 圖論

社交網路的興起，讓圖論的應用也越來越廣。人與人的關系，可以用圖論上的兩個節點來進行連接，節點的度可以理解為一個人的朋友數。我們都聽說過人脈的六度理論，在 Facebook 上被證明平均一個人與另一個人的連接，只需要 3.57 個人。當然圖論對於網路結構的分析非常有效，同時圖論也在關系挖掘和圖像分割中有重要的作用。

4. 最優化方法

最優化方法相當於機器學習中自我學習的過程，當機器知道了目標，訓練後與結果存在偏差就需要迭代調整，那麼最優化就是這個調整的過程。一般來說，這個學習和迭代的過程是漫長、隨機的。最優化方法的提出就是用更短的時間得到收斂，取得更好的效果。

隨著大數據時代的到來，社會對「挖掘」到的數據要求變得更加嚴格，每一個精準的結果都具備獨自的「價值」，這時，大數據時代的新增屬性——「價值」被演繹得有聲有色。數據挖掘（data mining, DM）是一門新興的、匯聚多個學科的交叉性學科，這是一個不平凡的處理過程，即從龐大的數據中，將未知、隱含及具備潛在價值的信息進行提取的過程。1989年8月，在美國底特律市召開的第十一屆人工智慧聯合會議的專題討論會上，知識發現（knowledge discover in database，KDD）初次被科學家們提出，同時，也有人將知識發現稱為數據挖掘，但兩者並不完全等同。1995年，KDD這個術語在加拿大蒙特利爾市召開的第一屆知識發現和數據挖掘國際學術會議上被人們接受，會議分析了數據挖掘的整個流程。實質上，數據挖掘是知識發現的子過程。

數理統計與數據挖掘的區別

更普遍的觀點認為，數據挖掘是數理統計的延伸和發展，如果一定要加以區分，它們又有哪些區別呢？數據挖掘在如下幾個方面與數理統計存在比較明顯的差異。數理統計的基礎之一就是概率論，在對數據進行數理統計分析時，分析人員常常需要對數據分布和變數間的關系作假設，確定用什麼概率函數來描述變數間的關系，以及如何檢驗參數的統計顯著性。但是，在數據挖掘的應用中，分析人員不需要對數據分布做任何假設，數據挖掘中的演算法會自動尋找變數間的關系。因此，相對於海量、雜亂的數據，數據挖掘技術有明顯的應用優勢。