%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%	卒業研究報告書（平成22年度）
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% platex sotuken.tex
\documentclass[a4paper]{jarticle}

\usepackage{tani_resume}
\usepackage{subfigure}
\usepackage{pifont}

\alignbeforeskip -5mm
\alignafterskip -5mm
\eqnarraybeforeskip -5mm
\eqnarrayafterskip -5mm

\setcounter{page}{3}
\jptitle{ネットワーク解析のためのTwitterAPIの試用}
\etitle{}
\jpauthor{岡田　沙季}
\eauthor{}
\course{谷　研究室}
\year{22}
\abstract{%
Twitterネットワークの相関関係を解析する準備として，TwitterAPIを用いたアプリケーションを２つ試作した．}

% 最終更新時刻の挿入
%\compheading

\setlength{\headheight}{15pt}
\begin{document}

% タイトルを表示させる
\maketitle

\begin{multicols}{2}
\section{はじめに}
近年，ブログやSNS(Social Network Service)をはじめとするソーシャルメディアサービスが大変注目を集めている．ソーシャルメディアとは，一般のユーザが情報を作り出し, 発信していくメディアのことであり，その中でも特にTwitterが世界的に急成長を遂げている．現在Twitterのユーザ数は１億４５００万に達し，大変多くの人々に支持されていることが分かる．\par
Twitterに限らず，近年ウェブの発展により，ネットワークが数理科学の研究の対象となっており，様々な性質が発見されている．その１つとして，スケールフリー性を持つネットワーク構造などが至るところで発見されている(例えば\cite{complex}を参照) ．\\
\fbox{定義}\\
あるネットワークの頂点の次数分布$P(k)$がある定数$γ$によるべき分布に従うとき，このネットワークはスケールフリーであるという．\\
ここで，次数分布がべき分布であるとは，\\
\[P(k) \propto k^{-\gamma}\,\left({\gamma}>0\right)\]
を満たしていることである．\\
\\
スケールフリーの性質としては，一部のノードが他のたくさんのノードとエッジで繋がっており，大きな次数を持っている一方で、大多数のノードはごくわずかなノードとしか繋がっておらず，次数は小さいという点が挙げられる(図１を参照)．\par
Twitter のフォローの関係も一種のネットワークと見なせる．それらを可視的，定量的に捉えることが，本研究の動機である．本研究では，その準備として，Twitter API(Application Program Interface) を利用し，Twitter ネットワーク間の相関をネットワークグラフにより視覚的に表現するアプリケーションを開発した．

\begin{center}
\includegraphics[bb=0 0 462 347,width=5cm]{scale.png}\\
\figurename{１ スケールフリーネットワーク}
\end{center}

\section{ソーシャルメディアについて}

\subsection{ソーシャルメディア}
ソーシャルメディアとは、ユーザが情報を発信し，形成していくメディアのことで，以下の３つの特徴を持つ(\cite{media})．\\
\begin{enumerate}
\item ユーザのコミュニケーションがコンテンツの主役である．
\item 登録制により，ユーザの同一性が保たれている．
\item ソーシャルグラフを持っている．
\end{enumerate}
\subsection{ソーシャルグラフ}
ソーシャルグラフとは，ウェブ上における人間の相関関係，SNSでいえばユーザ同士のつながりの情報を図式化したものを言う(\cite{socialgraph})．ソーシャルグラフは，構成要素のノード(個人)と関係性のエッジ(つながり)で説明される(図２を参照)．

\begin{center}
\includegraphics[bb=0 0 408 276,width=5cm]{social.png}\\
\figurename{２ ソーシャルグラフ}
\end{center}

\section{Twitterについて}

\subsection{Twitter}
Twitterとは，近年最も注目を集めているソーシャルメディアの一つで，個々のユーザが「ツイート」と呼称される短文を投稿し，閲覧できるコミュニケーションサービスである．Twitterはソーシャルメディアの中でも，特にミニブログというカテゴリーに括られており，ブログ・SNSとチャットの中間のようなシステムを持つ．\\

\subsection{TwitterAPI}
API(Application Program Interface)とは，OSやアプリケーションソフト，あるいはウェブアプリケーションが，自ら持つ機能の一部を外部のアプリケーション(ソフトやウェブサービス)から簡単に利用できるようにするインターフェースのことである．APIが提供されている機能は独自に開発する必要がないため，プログラムの開発を効率的に行うことが可能になる．
つまり，Twitter APIはTwitterを操作するためのAPIである．\par
Twitter APIには実行制限があり，制限は認証により異なるがOAuth認証では，取得系APIの場合は1時間あたり350回，送信系APIの場合は3時間あたり125回の制限が設けられている．認証の必要なものはユーザID単位で，認証の不要なものはIPアドレス単位で，実行回数のカウントを行なう．本研究では，このTwitterAPIを用いてネットワーク解析のための情報を取得する．\\

\section{作成したアプリケーション}
\subsection{ツイートメール送信アプリケーション}
TwitterAPIに慣れるための試作として，タイムライン(投稿が時系列順に表示される画面)にて表示されたツイートに，キーワードと一致する単語があった場合，メールを送信するアプリケーションを作成した．ここでは，タイムラインを取得するために，statuses/home\Pisymbol{psy}{"5F}timelineというAPIを用いた．statuses/home\Pisymbol{psy}{"5F}timelineは，タイムラインの中から直前のステータス(TwitterAPIにおけるツイートの情報)のうち２０を返すAPIである．APIから返って来るデータはいくつかの形式を指定できるが，本研究ではXML形式を指定した．ステータスには，ツイートしたユーザの情報なども含まれるが，ここでは，statuses/home\Pisymbol{psy}{"5F}timelineにより取得したステータスのうち，ツイート内容のデータを用いた．その内，キーワードとして指定した単語と一致するものがあった場合，一致した単語を配列に格納しておく．配列が空でなかった場合，ツイートされた日時，ツイートしたユーザのスクリーンネーム，ツイートの文章をキューに貯めていく．キューが空でなかった場合メールを送信する．受信されたメールは図３のようになる．\par
また，調べたツイートのIDをファイルに保存しておき，次にプログラムを実行する際に，そのIDよりも大きいもののみ調べるように指定し，重複しないようにした．

\begin{center}
\includegraphics[bb=0 0 620 258,width=7cm]{mail.png}\\
\figurename{３ 受信メール}
\end{center}

\subsection{ソーシャルグラフ可視化}
Twitterにおけるソーシャルグラフの解析のために，ソーシャルグラフの可視化をするアプリケーションを作成した．ここでは，指定したユーザのフォローを取得するために，friends/idsというAPIを利用し，また指定したユーザのフォロワーを取得するために，followers/idsというAPIを利用した．friends/idsは指定したユーザがフォローしている全てのユーザのID値を配列で返し，followers/idsは，指定したユーザをフォローしているユーザのID値全て配列で返すAPIである．それぞれXML形式でデータを取得した．\par
取得したデータは，Followテーブルに格納した．テーブル定義は以下の通りである．\\
\begin{center}
\begin{tabular}[b]{|c|c|}
\hline
Field&Type \\ \hline
id&bigint(20) \\ \hline
rootId&int(11) \\ \hline
user&varchar(30) \\ \hline
follow&varchar(30) \\ \hline
inserttime&timestamp \\
\hline
\end{tabular}
\end{center}\par
Twitterのフォロー関係をデータベースに格納するにあたり，幅優先探索を用いた．\par
幅優先探索とは，始点から隣接した全てのノードを訪問し，それらの隣接頂点のうち，未訪問のものを訪問，同様のことを繰り返して探索していく方法である．\\
アルゴリズムは以下の通りになる．
\begin{enumerate}
\item 始点をキューに入れる．
\item 訪問時にキューから取り出し，次に行くことが出来る未訪問の頂点を全てキューに入れる．
\item キューが空になるまで２を繰り返す．
\end{enumerate}
しかし純粋な幅優先探索すると，Twitterのネットワークにおいて，相互フォローしているユーザが存在した場合ループしてしまう．\\
そのため本研究で用いた実際の探索方法としては，Followテーブルに，root(起点となるユーザ)を１人指定し，rootのフォロー，フォロワー，rootがフォローしているユーザのフォロー，フォロワーといった要領でデータベースにデータを格納していく方法である．\par
一度調べたユーザは調べないようにするため，Checkedテーブルを用意し，既にフォロー，フォロワーを調べたユーザを格納していった．
またQテーブルという，Followテーブルに格納されたユーザで，Checkedテーブルに存在しないユーザを格納していくテーブルを用意した．rootのフォロー，フォロワーを格納し終わったのち，Qテーブルから１番若いIDのものを取り出す．同様の方法で格納していき，Qが空になるまで探索を続けFollowテーブルにデータを格納していく．
以上のような方法でデータを格納したデータベースから，任意のユーザ，取得したいネットワークの深さを指定し，可視化を行う．\par
また，JavaScriptによるグラフの描画には，JavaScriptライブラリのcanvasXpressのネットワークグラフ描画の機能を使用した(\cite{canvas})．このライブラリを用いると，ノードとエッジのデータを引数に指定することで，ネットワークグラフを描画することができる．
下記の画像は岡田のTwitterIDからフォロー，フォロワーを取得し，深さ1までのネットワークを描画したものである(図４を参照)．

\begin{center}
\includegraphics[bb=0 0 824 613,width=7cm]{graph1.png}\\
\figurename{４ 深さ1のネットワークグラフ}
\end{center}
\section{今後の課題}
実際に可視化してみたものの，ブラウザに表示出来るデータの数には限界があり，Twitterのような大規模ネットワークの解析には，数値的に検証する必要があると分かった．\par
数値的に解析する方法の一つとして，Twitterのネットワークにおける同類選択性について解析することを考えた．
\subsection{同類選択性}
Twitterのフォローの仕方には大きく分けて以下の2つが挙げられる(\cite{dourui})．
\begin{enumerate}
\item 友人，同業者，同じ趣味の人など比較的似た相手を見つけてフォローする．
\item 有名人，ニュース関係，企業の公式アカウントなど自分と異なる優れた，または小まめに情報を提供してくれる相手を見つけてフォローする．
\end{enumerate}
以上の2つのフォローの仕方で，Twitterのネットワーク上では，どちらの方が優勢であるか検証する．\\

\subsection{次数総相関係数}
同類選択性を検証するにあたってネットワークの次数相関係数を求める必要がある(\cite{zisuu})．
\[r = \frac{\sum_{i}j_{i}k_{i} - M^{-1}\sum_{i}j_{i}\sum_{i'}k_{i'}}{\sqrt{\left[\sum_{i}j^{2}_{i} - M^{-1}\left(\sum_{i}j_{i}\right)^{2}\right]\left[\sum_{i}k^{2}_{i} - M^{-1}\left(\sum_{i}k_{i}\right)^{2}\right]}}\]
この式において，$j_{i}$は入次数，$k_{i}$は出次数，Mはノードの総数である．\par
rの値が正であると，同程度の次数の頂点同士が結ばれているようなネットワークとなり，同類選択性は高い．またrの値が負であると，大きい次数の頂点と小さい次数の頂点が結ばれているようなネットワークとなり，同類選択性は低くなる．\par
以上の検証方法でTwitterネットワークを解析することが今後の課題である．

\begin{thebibliography}{9}
\bibitem{complex}
複雑ネットワーク入門　今野紀雄，井手勇介著

\bibitem{media}
ハチヨンdialog\\
http://84dialog.blogspot.com/

\bibitem{socialgraph}
kotobank\\
http://kotobank.jp/

\bibitem{canvas}
canvasXpress\\
http://canvasxpress.org/

\bibitem{dourui}
cafebabe\\
http://d.hatena.ne.jp/cafebabe/20090930/1254341275

\bibitem{zisuu}
Mixing patterns in networks\\
http://arxiv.org/PS\_cache/cond-mat/pdf/0209/0209450v2.pdf

\bibitem{prog}
Twitter APIプログラミング　辻村浩著\\

\bibitem{refe}
Twitter APIリファレンスガイドブック　池田成樹著\\

\end{thebibliography}

\end{multicols}

\end{document}
