機械学習手習い: ソーシャルグラフの分析
「入門 機械学習」手習い、11日目。「11章 ソーシャルグラフの分析」です。
Twitterのソーシャルグラフの可視化をためし、グラフからおススメの友達を推薦するシステムを作ります。
# 前準備 > setwd("11-SNA/")
ローカルコミュニティ構造の可視化
最初の例では、ユーザー johnmyleswhite
のフォロワーが、どのようなコミュニティ構造を持っているかを分析します。
ユーザー johnmyleswhite
とそのユーザーが直接フォローしているユーザーのグラフ(ユーザーを中心とするエゴネットワークと呼びます)を読み込み、
各フォロワー間の距離を算出、これをもとに hclust
で階層的クラスタリングを行います。
# グラフデータの読み込み > user <- 'johnmyleswhite' > user.ego <- read.graph("data/johnmyleswhite/johnmyleswhite_ego.graphml", format='graphml') # ノード間の距離を算出 > user.sp <- shortest.paths(user.ego) # 階層的クラスタリングで、フォロワーのコミュニティ構造を算出 > user.hc <- hclust(dist(user.sp)) # 可視化 > png(paste('../images/', user, '_dendrogram.png', sep=''), width=1680, height=1050) > plot(user.hc) > dev.off()
グラフから、ざっくりと2つの大きなコミュニティがあり、その下にさらに小さなサブコミュニティがある構成になっていることがわかるかと。
グラフデータからおススメの友達を推薦する
「友達の友達」は友達になる確率が高い、の仮定のもと、グラフデータからおススメの友達を推薦してみます。
まずは、グラフデータの読み込み。
# おススメフォロワーを推薦する対象とするユーザー名 > user <- "drewconway" # グラフデータの読み込み > user.graph <- suppressWarnings(read.graph(paste("data/", user, "/", user, "_net.graphml", sep = ""), format = "graphml"))
グラフから、「友達の友達」を友達候補として取り出します。 「多くの友達が友達としている候補は適性が高い」とみなして順位づけして、ソート。
# "drewconway" がフォローしているユーザー(=友達)の一覧を取り出す > friends <- V(user.graph)$name[neighbors(user.graph, user, mode = "out") + 1] [1] "311nyc" "aaronkoblin" "abumuqawama" "acroll" "adamlaiacano" [6] "aeromax" # グラフのエッジの一覧を取り出す > user.el <- get.edgelist(user.graph) > head(user.el) [,1] [,2] [1,] "drewconway" "311nyc" [2,] "drewconway" "aaronkoblin" [3,] "drewconway" "abumuqawama" [4,] "drewconway" "acroll" [5,] "drewconway" "adamlaiacano" [6,] "drewconway" "aeromax" # 友達の友達が2番目の要素(ターゲット)に含まれる行を取り出す。 # ただし、すでにフォロー済み(=友達)になっているユーザーは除く > non.friends <- sapply(1:nrow(user.el), function(i) { ifelse(any(user.el[i,] == user | !user.el[i,1] %in% friends) | user.el[i,2] %in% friends, FALSE, TRUE) }) > non.friends.el <- user.el[which(non.friends == TRUE),] > head(non.friends.el) [,1] [,2] [1,] "000988" "1000timesyes" [2,] "000988" "10ch" [3,] "000988" "1mrankhan" [4,] "000988" "1ndus" [5,] "000988" "500startups" [6,] "000988" "_hoffman" # 友達候補ごとの友達の数を集計 > friends.count <- table(non.friends.el[,2]) > head(friends.count) ___emma __damonwang__ __dave __davidflanagan __iriss 1 1 2 3 1 __neha 1 # データフレームに変換 > friends.followers <- data.frame(list(Twitter.Users = names(friends.count), Friends.Following=as.numeric(friends.count)), stringsAsFactors = FALSE) > head(friends.followers) Twitter.Users Friends.Following 1 ___emma 1 2 __damonwang__ 1 3 __dave 2 4 __davidflanagan 3 5 __iriss 1 6 __neha 1 # 友達候補としての最適度を示す指標として、各友達候補をフォローしている友達比率を計算して使う。 # 多くの友達が友達としている候補は適性が高いとみなす。 > friends.followers$Friends.Norm <- friends.followers$Friends.Following / length(friends) > head(friends.followers) Twitter.Users Friends.Following Friends.Norm 1 ___emma 1 0.003816794 2 __damonwang__ 1 0.003816794 3 __dave 2 0.007633588 4 __davidflanagan 3 0.011450382 5 __iriss 1 0.003816794 6 __neha 1 0.003816794 # お勧め度の指標でソート > friends.followers <- friends.followers[with(friends.followers, order(-Friends.Norm)),]
データができたので、お勧め度順に上位6人を表示してみます。
# 上位6人を取得。 > head(friends.followers) Twitter.Users Friends.Following Friends.Norm 13388 cshirky 80 0.3053435 21403 fredwilson 58 0.2213740 6950 bigdata 57 0.2175573 14062 dangerroom 57 0.2175573 55153 shitmydadsays 55 0.2099237 2025 al3x 54 0.2061069