Aidemy Tech Blog

機械学習・ディープラーニング関連技術の活用事例や実装方法をまとめる、株式会社アイデミーの技術ブログです。

HIP HOPでわかるネットワーク分析

自己紹介

みなさん、はじめまして。
Aidemy 研修生の 加藤正義 (加藤正義 (@Kato_Justice) | Twitter) です。昔はテレビ東大生として、時々バラエティ番組とかに出ていました。

〈●〉EYE-CATCH〈●〉

 フィーチャリング関係で繋がった日本語ラッパーのコミュニティをグラフ化すると、以下のような構造をしている。
f:id:kato_justice:20180220153459p:plain
ノードの色は派閥を表し、媒介中心性が大きいほどノードのサイズが大きい。ラッパーの派閥は

  • フリースタイルダンジョン組
  • KGDR + RHYMESTER + 愛国ラッパー達 (韻が固い)
  • 独立したその他ユニット

という具合で分かれた。
媒介中心性の最も高いラッパーはKEN THE 390だった。

ラッパーは好き嫌いが激しい

 突然ですが、僕は日本語ラップが好きです。しかし、当のラッパー同士がお互いのことを無条件で好きかというと、どうやらそうではないようです。ラッパーはしばしば価値観の違いから対立し、ビーフと呼ばれるdisり合いの行動を取ることがあります。
kai-you.net
このようにお互いの好き嫌いが激しいラッパー達なので、彼らの人間関係もいくつかの派閥に分かれていそうだなと思い、ラッパーの派閥構造ネットワーク分析と呼ばれる手法で解析し、可視化してみようと思いました。

feat. で繋がる絆

 ラッパー同士の親しさを客観的に定義する方法のひとつとして、フィーチャリングの関係が利用できると考えました。フィーチャリングとは、ラッパーが楽曲を作製する際に別のラッパーに協力を仰ぐことで、特にラッパーの場合は互いにリスペクトしてる場合のみフィーチャリングが成立すると考えています。よって、フィーチャリングの関係はラッパー同士の絆を表すとよい指標であると考えます。
www.youtube.com
以上を踏まえて、フィーチャリング関係をもとにラッパー派閥の構造を解明していきたいと思います。

やり方

 以下のような流れでやっていきたいと思います。

  1. データを用意する、データの種類は以下の通り。
    • ラッパーと所属グループのリスト
    • 上リスト内のラッパー同士のフィーチャリング関係のリスト
  2. networkxにより、ラッパーをノードフィーチャリング関係をリンクとした無向グラフを構築 (つまり、一度でもfeat. してればダチとみなして、ラッパー達を絆で繋ぐということ)
  3. モジュラリティ指標が最も高いグラフの分割をする (つまり、いつメンで固まること)
  4. 媒介中心性を計算する (媒介中心性:『お前がいなきゃ界隈がまとまらねぇ』という度合いのこと)
  5. 構造がわかりやすいように可視化・要約する

1. データの用意

name.csv - Google スプレッドシート
 name.csvは、今回の分析の対象とするラッパーのリストです。独断と偏見で選んだ57人のラッパー達です。"Name"のカラムにはラッパーの名前が、"Group"のカラムにはそのラッパーが属する代表的なグループが書かれています。所属グループがない場合はラッパー自身の名前で置き換えています。

feat.csv - Google スプレッドシート
 一方、feat.csvにはラッパー同士のフィーチャリング関係が記されています。120行あります。各行について、"name_1"と"name_2"がフィーチャリングで繋がっている事を意味します。フィーチャリング関係をどう調べたかについてですが、YouTubeで『"ラッパー名" feat.』と検索、検索結果を2,3 ページ分スクロールしてリスト内のラッパーがいれば追加、という方法で行いました。正直、ここが一番たいへんでした。ただ、自分でデータを作るので意図しないデータ構造のデータクレンジングで疲労をしなくていいのはよかったのかな?

2. networkxによる無向グラフの構築

 今回は、networkxというpythonのパッケージを使ってグラフを書いていきます。

import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
from community import community_louvain

#グラフの大きさ決める
plt.figure(figsize = (10, 10))
# ラッパーのデータをデータフレーム化
df_name = pd.read_csv("name.csv")
df_ft = pd.read_csv("feat.csv")

#ラッパーの繋がりを格納しておくための辞書
#{"ラッパー名": "フィーチャリングしているラッパー達" , ...} という形で格納
vector = {}
for i in range(len(df_name)):
  vector[df_name.iloc[i,0]] = []

#同じグループで活動しているラッパーについては、無条件で繋げる
for i in range(len(df_name)):
  for j in range(len(df_name)):
    if df_name.iloc[i,1] == df_name.iloc[j,1] and i != j:
      vector[df_name.iloc[i,0]].append(df_name.iloc[j,0])

#フィーチャリングしているラッパーについて、ノードを接続
for i in range(len(df_ft)):
  vector[df_ft.iloc[i,0]].append(df_ft.iloc[i,1])

#vectorをグラフ化する
G = nx.Graph(vector)

この操作により、変数Gにグラフが格納されました。この時点でグラフGを

nx.draw_networkx(G)

によって出力すると、以下のようになります。目を凝らして観察すれば誰が誰と繋がっているのかはわかれど、派閥の存在や、誰が派閥の中心なのかをこのグラフから読み取るのは厳しいですね。
f:id:kato_justice:20180220154518p:plain

3. モジュラリティを最大化するグラフの分割

 さて、単にノード同士を繋いだだけではどういう派閥が存在するのかはわかりません。なので、所属する派閥ごとにグラフを分割したいのですが、どのような基準でグラフを分割をすれば納得感があるでしょうか?このようなシチュエーションで役に立つ概念の一つとして、モジュラリティというものがあります。以下では、モジュラリティについて説明します。
 まずは、ノードがランダムに繋がった(=派閥のない)グラフを見てみましょう。
f:id:kato_justice:20180220220746p:plain
隣接行列には、どのノードがどのノードと繋がっているかの情報が含まれています。隣接行列のij列の値は、ノードiとノードjが繋がっていれば1、そうでなければ0とします。ノード同士をランダムに接続するグラフを作る場合、隣接行列において対角成分を除けば全ての要素の期待値が等しいはずです (対角成分は常に0(自分自身とは繋がれないので(人はいつもほんとうの意味で孤独)))。

 一方で、グラフ内でコミュニティが分化していれば(=グラフ内に派閥構造を持っていれば) グラフおよび隣接行列は以下のようになります。
f:id:kato_justice:20180220225101p:plain
図中の/で示されるコミュニティの内部でのリンクは多く存在するのに対して、コミュニティ間を繋ぐリンクは稀にしか存在しないのがおわかりでしょうか?それに対応するように隣接行列においても、グループ内の繋がりを表す要素には1が多く、グループ間の繋がりを表す要素には0が多いという偏りができています。この偏りを利用して、コミュニティが分化している程度を表そうというのがモジュラリティの考え方です。下の図でモジュラリティの出し方を説明します。ここでは、簡単のために、2分割のみの場合を扱います。
f:id:kato_justice:20180220230632p:plain
モジュラリティQは、所与の分割をした際に各コミュニティ内部でのリンク数から、リンクがランダムであった場合のリンク数期待値を引き、これを総リンク数で割ることで定義されます。つまり、Qはコミュニティ内部にリンクが集中している割合を表す指標というわけです。

 さて、モジュラリティを最大化する分割をどう実装するかなのですが、communityというパッケージの中にモジュラリティが最大になるような分割をしてくれる機能があります。呼び方は簡単で、

partition = community_louvain.best_partition(G)

とすればOKです。値は辞書型で渡され、以下のように数値によってコミュニティが振り分けられます。

{'KEN THE 390': 0, 'TWIGY': 1, 'KREVA': 2, 
... , 'G.K.MARYAN': 1, 'REKKO': 0, 'TAKUMAKI': 0}

グループに関する情報を入れて、Gを再び

nx.draw_networkx(G,node_color=[partition[node] 
for node in G.nodes()], cmap=plt.cm.RdYlBu)

で描写すると、以下のような感じになります。
f:id:kato_justice:20180221180909p:plain
だんだんわかってきましたね。けれど、ネットワークにおいて誰がどれくらい影響力を持っているかはまだわかりません。次は媒介中心性という概念で、誰がラッパーのコミュニティで影響力を持っているのかを明らかにしていきましょう。

4. 媒介中心性を求める ~UZIを例にして

 媒介中心性とは、ネットワーク分析において最もよく使われている中心性の指標で、そのノードを通る最短経路が多いほど媒介中心性は高くなります。詳しい説明するために、以下のような、お互い繋がりあうラッパー達の事を考えてみましょう。このグラフでは、いくつかのノードを経由することにより、全てのノードが互いに辿り着きあえるようになっています。
f:id:kato_justice:20180221230336p:plain
しかし、この界隈に事件が起きて、あるノードが消失したらどうでしょうか?ここでは、UZIが御用となってしまった世界の事を考えてみましょう。
www.excite.co.jp
UZIが塀の中に入ってしまうと、様々な不都合が起きます。フリースタイルダンジョンが放送中止となるだけではなく、これまでUZIを媒介として繋がりあっていたノード同士の繋がりが、断絶されます*1(例: 下図中のKダブとDJ YAS)。また、UZIなしでは連絡をつけるために遠回りをしないといけない場合もあります(例: 下図中のTwiGyと童子-T)。UZIがいなくなってはじめて、UZIがラッパー達の媒介としての役割を担っていたことがわかります。
f:id:kato_justice:20180221231353p:plain
このUZIが果たしていた役割に、スコアをつけることはできないでしょうか?下の図は、YOU THE ROCK★にとっての、UZIの媒介としての価値を示しています。
f:id:kato_justice:20180221234121p:plain
YOU THE ROCK★が最短で各ラッパーに辿り着く経路を考えてみましょう。NORIKIYO、K DUB SHINEにアクセスするには、UZIを通る経路が唯一の最短経路であることがわかります。また、童子-Tにアクセスするには、UZIを経由する経路とDJ-MASTERKEYを経由する経路の2つの最短経路があることがわかります。その他のラッパーにアクセスには、UZIを経由する必要はありません(ほかは全員雷家族のメンバーなので当然そう)。するこのとき、UZIを経由する唯一の最短経路に対してスコア+1最短経路が複数ある場合はUZIを通るものにスコア+1/n(今回は、1/2) を与えます。このスコアの和は、YOU THE ROCK★にとっての、UZIの媒介中心としての価値そのものです。YOU THE ROCKに限らず、全てのノードにとってのUZIのスコアを足し合わせることで、UZIの媒介中心性が表せます*2
 さて、この中心媒介性をnetworkxで求める方法ですが、実際簡単で、

between_cent = nx.communicability_betweenness_centrality(G)

で求めることができます。between_centの中身は辞書型で、

{'KEN THE 390': 0.34846233379185004, 'TWIGY': 0.1644836555192994, 'KREVA': 0.1557333845321839, 
... , 'G.K.MARYAN': 0.15635132015072525, 'ANARCHY': 0.013911874100152521, 'TAKUMAKI': 0.004676026664705854}

のような形になっています。

5. 可視化・要約

 さて、今までの作業でラッパーのfeat. 関係グラフに関する、モジュラリティ最大化媒介中心性を求めました。折角なので、これをわかりやすく可視化していきたいです。
グラフ分割についての可視化は先ほどやったのですが、ここでは、媒介中心性の程度もわかるように、媒介中心性が大きいほどノードも大きくなるグラフを書きたいと思います。以下のようなコードで実現できます。

#モジュラリティが最大になるような分割をする
partition = community_louvain.best_partition(G)
#中心媒介性を出す
between_cent = nx.communicability_betweenness_centrality(G)
#中心媒介性をもとにノードの大きさを決める
#そのままじゃ小さすぎるで雑に5000くらいかける
node_size = [5000 * size for size in list(between_cent.values())]
#いい感じにグラフのレイアウトをやる
pos = nx.spring_layout(G)
#グラフを出力。派閥ごとに色分けし、
#中心媒介性の大きいノードほど大きく表示
nx.draw_networkx(G,pos, node_color=[partition[node]
for node in G.nodes()],node_size=node_size, cmap=plt.cm.RdYlBu)

これで、アイキャッチで出てきたような、わかりやすいグラフが出力されます。ノードの色は派閥を表し、大きさは媒介中心性を表します。
f:id:kato_justice:20180220153459p:plain
これでちゃんとわかりやすいので、よかったですね。

 しかし、このグラフだけでは詳しい事までは読み取れないので、今回得られたデータを要約してみましょう。まず、各派閥ごとの属性を見てみます。「だいたいこんな感じ」というやつなので、全員に当てはまるわけではありません。

派閥 属性
0 フリースタイルダンジョン組
1 KAMINARI-KAZOKU.
2 KGDR + RHYMESTER + その他愛国的ラッパー、韻が固い
3 30~40歳くらい? ゼロ年代中盤くらいにヒットしたラッパーたちで、古参である派閥2よりは若い
4 濃水 SOUL SCREAM
5 BUDDHA BRAND

自明なこととして、所属ユニットが派閥に強く影響しているようです*3。少しだけ自明でない事としては、派閥0が示す通りユニットを組んでいなくてもフリースタイルダンジョン組の結びつきは強いことや、派閥2が示すように活動時期や価値観が似たラッパー達の結びつきは強い事が挙げられます。

 媒介中心性のランキングは以下のようになりました。このランキングが高いほどラッパー界での影響力が高いことになります(なるのか?) みんな有名なラッパーたちばっかですね。

ランク 名前 媒介中心性
1位 KEN THE 390 0.35
2位 Zeebra 0.34
3位 UZI 0.31
4位 DJ MASTERKEY 0.28
5位 般若 0.24
6位 Mummy-D 0.24
7位 R-指定 0.17
8位 NORIKIYO 0.17
9位 TwiGy 0.16
10位 SKY-HI 0.16

おわりに

  • 怠け者の僕にしてはけっこう頑張りました、分析そのものより、データ集めやブログ執筆のためのポンチ絵作りに手間がかかりました。ポンチ絵を作るのは楽しい。
  • この記事がきっかけで、ネットワーク分析というよりかは日本語ラップに興味を持つ人が増えてくれればいいなと思っています。
  • ラッパーのfeat. 関係ですが、手作業で集めたので漏れなどがあると思います。間違いを指摘してくれるとうれしいです。
  • B-BOYになりたい(写真は、B-BOYだった頃のぼくです、成り格好は一丁前だがまだスキルがない)

f:id:kato_justice:20180222122326j:plain

コード全文

 コピペして使えるようにまとめておきます。

import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
from community import community_louvain

#グラフの大きさ決める
plt.figure(figsize=(10, 10))
# ラッパーのデータをデータフレーム化
df_name=pd.read_csv("name.csv")
df_ft=pd.read_csv("feat.csv")

vector={}
for i in range(len(df_name)):
  vector[df_name.iloc[i,0]] = []
    
#同じグループで活動しているラッパーについては、無条件で繋げる
for i  in range(len(df_name)):
  for j in range(len(df_name)):
    if df_name.iloc[i,1]==df_name.iloc[j,1] and i!=j:
      vector[df_name.iloc[i,0]].append(df_name.iloc[j,0])

#フィーチャリングしているラッパーについて、ノードを接続
for i  in range(len(df_ft)):
  vector[df_ft.iloc[i,0]].append(df_ft.iloc[i,1])

G= nx.Graph(vector) 

# モジュラリティ最大の分割
partition = community_louvain.best_partition(G)
#媒介中心性を求める
between_cent = nx.communicability_betweenness_centrality(G)
node_size = [5000 * size for size in list(between_cent.values())]
#形を整えて、出力
pos = nx.spring_layout(G)
nx.draw_networkx(G,pos, node_color=[partition[node] for node in G.nodes()],node_size=node_size, cmap=plt.cm.RdYlBu)

*1:もちろん、実際はUZIなしでも連絡を取り合えると思うのですが、話を簡単にするためにそうさせてください

*2:実際は、この値を、UZIを通らない頂点対の数(N個の頂点のグラフなら、(N-1)*(N-2)/2 )で割ります

*3:同じグループ内のラッパーは全てリンクさせたのでそれはそう