資料分析 R 處理 (2)

基本介紹

教學目標

透過 R 針對 Zachary 空手道俱樂部圖進行分群,再以 Modularity 之 Q 值評估分群成效,最佳值理應為 0.419 。

使用教學

安裝相關函式庫。

1
install.packages("igraph")

載入相關函式庫。

1
library(igraph)

載入 Zachary 空手道俱樂部圖

1
g <- graph.famous("Zachary")

Girvan Newman

  • 有向圖: 支援
  • 權重邊: 支援
  • 執行時間: |V||E|^2 或 N^3 (稀疏矩陣)
1
2
3
4
system.time(ec <- edge.betweenness.community(g))
print(modularity(ec))
print(membership(ec))
write.csv(membership(ec),"ec.csv")

Walktrap

  • 有向圖: 不支援
  • 權重邊: 支援
  • 執行時間: |E||V|^2
1
2
3
4
system.time(wc <- walktrap.community(g))
print(modularity(wc))
print(membership(wc))
write.csv(membership(wc),"wc.csv")

Leading Eigenvector

  • 有向圖: 不支援
  • 權重邊: 不支援
  • 執行時間: c|V|^2 + |E| ~N(N^2)
1
2
3
4
system.time(lec <-leading.eigenvector.community(g))
print(modularity(lec))
print(membership(lec))
write.csv(membership(lec),"lec.csv")

Fast Greedy

  • 有向圖: 不支援
  • 權重邊: 支援
  • 執行時間: |V||E| log |V|
1
2
3
4
system.time(fc <- fastgreedy.community(g))
print(modularity(fc))
print(membership(fc))
write.csv(membership(fc),"fc.csv")

BGLL

  • 有向圖: 不支援
  • 權重邊: 支援
  • 執行時間: |V| 或 |E| (稀疏矩陣)
1
2
3
4
system.time(bgll <- multilevel.community(g))
print(modularity(bgll))
print(membership(bgll))
write.csv(membership(bgll),"bgll.csv")

Label Propagtion

  • 有向圖: 不支援
  • 權重邊: 支援
  • 執行時間: |V| + |E|
1
2
3
4
system.time(lc <- label.propagation.community(g))
print(modularity(lc))
print(membership(lc))
write.csv(membership(lc),"lc.csv")

相關資源