2014-01-11

'13のあれこれ（論文採択と出版かなぁ）

去年の成果といえるもののまとめ。

2013年4月にPLOS ONEに論文が採択された。

PLOS ONE: Suicide Ideation of Individuals in Online Social Networks

縁あって、TokyoWebMiningという勉強会で上記の論文の発表をした。
そのときの資料は以下。

Suicide ideation of individuals in online social networks tokyo webmining from Hiroko Onari

SNS上で自殺傾向にある人のソーシャルネットワーク（人間関係）はどうなっているのか調査した論文です。

あと、3月に岡山で開催されて日本行動計量学会でこの論文の発表した。

2013年8月に『データサイエンティスト養成読本』って本の一部を書いて出版。

データサイエンティスト養成読本 [ビッグデータ時代のビジネスを支えるデータ分析力が身につく! ] (Software Design plus)

作者: 佐藤洋行,原田博植,下田倫大,大成弘子,奥野晃裕,中川帝人,橋本武彦,里洋平,和田計也,早川敦士,倉橋一成
出版社/メーカー: 技術評論社
発売日: 2013/08/08
メディア: 大型本
この商品を含むブログ (11件) を見る

特集2 マーケティング分析本格入門の「第3章：ソーシャルメディアネットワーク分析」を書いた。

この本は主にエンジニア向けではあるものの、私の書いた章は出版社からの依頼で、マーケター向けの内容にしている。ソーシャルネットワークのデータを使って、どうやってマーケティングするか、売上につなげるのかという視点で、架空のECサイトを例にネットワーク分析の例を書いている。

あとは仕事が忙しかった。エンジニア向けの問題を結構な量を作った気がする。

体の9割くらいが仕事でできているに違いない。そして、めでたくMHP賞をいただいた。
※MHP賞とは、Most働きすぎパーソンに送られる賞らしいです。

2012-09-09

Girvan-Newmanのコミュニティー分割アルゴリズムをNetworkXでやってみた

Pythonの複雑ネットワーク解析ライブラリーであるnetworkXを使って、Girvan-Newman algorithmのコミュニティー分割をしてみました。

分割されていく様子をgifアニメーションにしています。

f:id:millionsmile:20120909114250g:plain

Girvan-Newman algorithmは、あるコミュニティーの中で媒介中心性の高いエッジ（リンク、繋がり）を検出し、そのエッジを切ることで、そのコミュニティーを分割していくアルゴリズムです。

原論文はこちら（PDFをリンクしています）。

Girvan, M., Newman, M. E. J., Community structure in social and biological networks", Proceedings of the National Academy of Science of the United States of America, Vol. 99, pp. 7821-7826 (2002)

データはZachary's karate club（ある海外の大学で空手クラブで２人のリーダーが仲間割れしたときの内部の人間関係ネットワーク）を使っています。データ・ソースは、Network dataから取得できます。

ノードID = 33 (空手クラブの主将)とノードID = 1 (パートタイムのインストラクター)が空手クラブの経営問題を巡って対立した時の中心メンバー34人の友人関係です。

f:id:millionsmile:20120909150437p:plain

ここでは媒介中心性の高いエッジを切っていくわけなので、主将派とインストラクター派をつなぐ役割を果たしているエッジが最初に切られます。さらに分割されたコミュニティー内で媒介中心性の高いエッジを切っていく、というのを繰り返していきます。

最終的には空手クラブのネットワークは、70回分割にかけたところで、きれいに分割されました。

媒介中心性の計算式はこちら。

$b_{i}\equiv \frac{ \sum_{i_{s}=1;i_{s}\neq{i}}^{N} \sum_{i_{t}=1;i_{t}\neq{i}}^{i_{s}-1} \frac{g_{i}^{(i_{s}i_{t})}}{N_{i_{s}i_{t}}} } {(N-1)(N-2)/2}$

$g_{i}^{(i_{s}i_{t})}$ は、ある頂点 $v_{i_{s}}$ から別の頂点 $v_{i_{t}}$ へ行く最短経路の中で $v_{i}$ を通る数で、 $N_{i_{s}i_{t}}}$ は $v_{i_{s}}$ から $v_{i_{t}}$ へ行く最短路の総数である。分子は頂点 $v_{i}$ が他の点を結ぶ最短路上にあると得点が入る。分母は規格化定数である。

コードはこちら。

今回は媒介中心性を使いましたが、この手法でコミュニティ分割する場合、計算量が大きいとか、どこまで分割するべきなのかといった数値を予め設定しなければいけないなどの欠点があり、アルゴリズムの改良が進んでいます。最近では、媒介中心性ではなく、モジュラリティQというコミュニティ分割結果の良さの指標というのが考えだされています。モジュラリティQに関してはまた別の機会に試してみます。

※元ネタは2008年に書かれた「tsubosakaの日記」の記事より。今のPythonのバージョンだとライブラリの階層が変更になっていたりして動かないのでそこを改良しています。

※参考文献『複雑ネットワーク -基礎から応用まで-』増田直紀、今野紀雄著