機械学習手習い: ソーシャルグラフの分析

「入門 機械学習」手習い、11日目。「11章 ソーシャルグラフの分析」です。

www.amazon.co.jp

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