iT邦幫忙

2023 iThome 鐵人賽

DAY 6
0
AI & Data

初探 Network Science系列 第 6

Day-06-Descriptive Network Analysis

  • 分享至 

  • xImage
  •  

Day-06-Descriptive Network Analysis

了解到可以使用哪些資料結構儲存圖之後,接下來的第一步就是了解這個圖的性質。也就是資料分析的第一步,了解你的資料集。

下面提供了幾個常見的 network properties,讓各位在拿到資料集之後,可以先用這些 properties 來了解這個圖的基本資訊。

例如,可以計算圖中的節點數量、邊數量、平均度數等。我的邏輯是先從小到大,從 node 開始,再到 edge,最後到整個 graph 的結構。

Node

Property Description
Node In-Degree 指向該節點的連接數量
Node Out-Degree 節點指向其他節點的連接數量,較高的 Out-Degree 代表該節點在圖中有較多的影響力
Node Degree Distribution 在圖裡面所有節點 Degree 的分佈狀態,顯示出網絡中節點度數的分布模式,例如是否符合 Binomial distribution 等...
Average Node Degree 所有節點的平均 Degree,反映出整個圖裡面所有節點的連接程度
Maximum Node Degree 所有節點中最大的 Degree
Minimum Node Degree 所有節點中最小的 Degree

Path Length & Distance

Diameter(直徑)

Diameter 是指圖中『最長的最短路徑』,也就是圖中兩個節點之間最遠的距離。

Average Path Length

藉由計算途中所有節點之間的最短路徑,並取平均值,來了解整個圖的平均路徑長度。

Clustering Coefficient

Local Clustering Coefficient(單一節點)

https://ithelp.ithome.com.tw/upload/images/20230921/201328379psUoDblSY.png
主要是計算單一個節點與其鄰居節點之間的連接緊密程度。

  • https://chart.googleapis.com/chart?cht=tx&chl=%24E_%7Bi%7D%24 : 節點 https://chart.googleapis.com/chart?cht=tx&chl=%24i%24 的相鄰節點之間的邊數
  • https://chart.googleapis.com/chart?cht=tx&chl=%24n_%7Bi%7D%24 : 節點 https://chart.googleapis.com/chart?cht=tx&chl=%24i%24 的相鄰節點數量
  • 實際公式 : https://chart.googleapis.com/chart?cht=tx&chl=%24C_%7Bi%7D%20%3D%20%5Cfrac%20%7B2E_%7Bi%7D%7D%7Bn_%7Bi%7D(n_%7Bi%7D-1)%7D%24

Global Clustering Coefficient(網絡中形成三角形的機會)

https://ithelp.ithome.com.tw/upload/images/20230921/201328370oZT2hEF8z.png

主要是用來衡量整個網絡中聚集程度的指標。它衡量了網絡中形成三角形的程度,也可以理解成在所有三元組(由三個節點組成,它們之間有兩條連接,triplets)中形成封閉三角形的機會。

  • 實際公式 : https://chart.googleapis.com/chart?cht=tx&chl=%24C%20%3D%20%5Cfrac%20%7B3%5Ctimes%20%5Ctext%7Bnumber%20of%20triangles%7D%7D%7B%5Ctext%7Btnumber%20of%20otal%20triplets%7D%7D%24
  • N1:1, N2:3, N3:1, N4:3, N5:3, N6:0
  • https://chart.googleapis.com/chart?cht=tx&chl=%24C%20%3D%20%5Cfrac%7B3%7D%7B1%2B3%2B1%2B3%2B3%2B0%7D%20%3D%20%5Cfrac%7B3%7D%7B11%7D%20%3D%200.27...%24

Structure

Graph Size

  • 節點的總數量
  • 邊的總數量

Connectedness(連通性)

https://ithelp.ithome.com.tw/upload/images/20230921/20132837MsPtkcIUja.png
描述網絡中是否存在孤立的部分,簡單來說就是圖中的所有節點是否都可以連通

Transitivity

描述網絡中形成三角形結構的程度

Graph Heterogeneity

描述網絡中節點度的異質性,即度分佈的不平均程度

Motifs

描述網絡中常見的小型拓撲結構或模式,例如三角形、四方形等

參考資料


上一篇
Day-05-圖的資料結構
下一篇
Day-07-Network Model--Erdős–Rényi model
系列文
初探 Network Science30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言