\documentclass[a4paper]{jarticle}
\usepackage[dvipdfm]{graphicx}
\usepackage{tani_resume}%スタイルファイルの読み込み

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

%jpは日本語
%eは英語
%titleとauthorは自分用に書き換えてください。

\jptitle{伝播速度限定モデルにおけるScale Free Network上の情報拡散Dynamics}
\etitle{}
\jpauthor{小幡 正博}
\eauthor{Masahiro Obata}
\course{谷　研究室}
\year{23}
\abstract{%概要(2009メンバーは書いています。)
%ここから
有限ネットワーク上において，頂点が大きな次数であればあるほど，相応の影響力を有すると思われる．ネットワーク上で，情報を効率よく伝達するには，意図的に小さな次数の頂点を優先して選択する方法が優れていると主張する研究が行われている．その研究では，確率計算を行う際に近似を行っている．その近似が妥当かどうかを検証するため，修正版BAモデルでScale Freeネットワークを生成し伝達時間を計測する計算機実験を行った．
%ここまで概要
}


\begin{document}%ドキュメントの始め

\maketitle

\begin{multicols}{2}%文章を2段落に分ける＆文章の始め

\section{はじめに}
%背景・動機・先行研究・目的・今回やること　をこの下に。
社会には様々なネットワークが存在する．例えば，学校のクラス内における友人関係やインターネット網，交通網等，多種多様である．グラフ理論では，ネットワークを頂点と辺で表す．グラフ理論の歴史は17世紀のケーニヒスベルクの橋の問題が始まりとされる[1，2]．そして，1998年ダンカン・ワッツとスティーヴン・ストロガッツのSmallWorldに関する論文[3]により，ネットワーク理論が注目されていくこととなった．社会には様々な問題が存在する．例えば，ウイルス伝播予防問題，災害時緊急情報伝達問題，交通網に関する問題等である．これらはグラフを用いることでモデル化できる．

これらの問題を考える上で，ネットワーク上を物事が伝播する様子を解明していく事は重要である．伝播させたくない対象に対しては伝播しにくいように対策を講じる．一方，伝播させたい対象に対しては伝播しやすくするように対策を講じることが期待できるからである．

ネットワーク上の情報拡散の研究のひとつとして，Toyoizumi and Taniが，ある仮定に基づき，次数の逆数に比例した確率分布に従い情報を伝達する頂点を選択する方法が，情報がネットワーク全体に行き渡るまでの平均時間が最小になることを証明した[4]．
本研究では，その仮定が妥当か，また，証明された結果が妥当かを検証するため，Scale Free Networkを生成し計算機実験を行う．

%ここから下は数式を入れたことによって変化する。後で変更する.
2節では，本研究で用いたネットワークの性質であるScale Free性について述べる．3節では，修正版BAモデルについて述べる．4節では，ネットワーク上での伝播規則について述べる．5節については，本研究で行ったシミュレーションについて述べる．6節では，今後の課題について述べる．

\section{Scale Free Network}
%そのための準備（読む人／聞く人のため）　をこの下に
この節では，本研究で扱ったネットワークの性質であるScale Free NetworkのScale Free性について述べる．
\subsection{Scale Free性}
既に述べたように社会には様々なネットワークが存在する．ネットワーク上において頂点が保有する辺の総数をその頂点の次数と呼ぶが，世の中の多くのネットワークの次数分布は，ある性質を有していることが確認されている．それは，ネットワーク上の次数分布がベキ分布であるということだ．そのようなネットワークをScale Free性を有するといい，そのネットワークをScale Free Networkと呼ぶ．Scale Free性は次のように定義される．
$p(k)$が，ネットワーク上における頂点次数$k$である確率とするとき，
\[ P(k) \propto k^{-\gamma}, (\gamma>0)  \]
を満たしている確率分布となる.
$γ$をベキ指数と呼ぶ．この変数によりベキ分布の形状が決定する．
%図を挿入する.ここで,スケールフリーのベキ乗を視覚化する

直感的説明では，Scale Free性を持つとは，一部の頂点が大きな次数を有するが，大部分の頂点は小さな次数を有している状態である．例えば，一部の大富豪達が巨万の富を持つ一方で，多くの人は，平均よりも少ない富を持つ状態である．また，容易に想像できることと思うが，一部の人には多くの友人がいる．他方，大部分の人には，少数の友人のみといった具合である．

\section{修正版BAモデル}
この節では，本研究で採用したモデルについて述べる．
\subsection{Scale Free Network}
Scale Free 性を持つネットワークモデルとして，BAモデルが存在する．BAモデルは，1999年にバラバシとアルバートによって提案されたモデルである[5]．
このモデルは作成ネットワーク作成課程において成長と優先的選択という２つのルールを用いることで，ベキ分布を実現する．
\subsection{成長と優先的選択}
成長とは，既存のネットワークに対して，新たな頂点をさらに加えることを指す．
優先的選択とは，新たに加える頂点が有するリンクの端点を既存の頂点に連結させる際，その端点の選択は，既存の頂点の各次数に比例する確率で行われる．

\subsection{修正版BAモデル生成方法}
%修正版BAモデルの生成について記載する。
修正版BAモデルの生成方法は，文献[6]に従った．

\begin{enumerate}
\item 最初に1本の辺も無い１つの頂点だけが存在する.
\item １回のステップで１つの頂点を増やす(成長)．その頂点は辺を１本のみ有する．
\item その１本のリンクは，既に存在するネットワーク上の頂点を選択するが，それは各頂点の次数に比例した確率で行われる(優先的選択)．
\item (2)と(3)を作成したい頂点数のネットワークになるまで繰り返す．
\end{enumerate}

つまり，$n-1$回のステップで，$n-1$個の頂点と$n-1$本の辺が増加する．その結果，全頂点数は$n$個のネットワークが生成される．この生成法では，ベキ指数3のベキ分布に収束する[6]．


\begin{center}
\includegraphics[bb=0 0 553 325,width=7cm]{ko.jpg}\\
\figurename{1:ベキ分布の様子$\gamma=2,3,4$}
\end{center}
 

\section{伝播規則}
この節では，ネットワーク上における伝播規則について述べる．
\subsection{伝播規則についての用語}
\paragraph{ソースノード}ネットワーク上において伝播させる情報を持っている頂点のことを指す．
\paragraph{ターゲットノード}ネットワーク上においてソースノードが次に伝播させる頂点として選択する頂点のこと．
\subsection{伝播規則について}
伝播規則は，論文[4]と同様である．まず初めにネットワークからランダムにソースノードを選択する．その後，１ステップで全ソースノードが1つのターゲットノードに情報伝達する．その際に，１度選択した頂点も重複して選ばれることを許している．ターゲットノードを選択する際の規則として，論文[4]と同様のNo controlとInverse controlを用いる．
\subsection{ターゲットノードの選択方法を考える}
ターゲットノードの選択方法として，２つの方法がある．

\begin{enumerate}
\item No control:すべての頂点の重みを１とする．
\item Inverse control：重みを各隣接頂点の次数の逆数とする．
\end{enumerate}

次の図2，3では，ソースノードの次数が$k$でれば，そのソースノードに対して，隣接頂点が$k$個存在する．それらを $b_i (1\le i \le k)$
とする．
\begin{center}
\includegraphics[bb=0 0 430 310,width=5cm]{no_control.jpg}\\
\figurename{2:No control}
\end{center}
この図2では，色の頂点はソースノードを表している．
ソースノードに隣接している頂点に添えられている分数は，ターゲットノードとして選択される各隣接頂点の確率である．

\begin{center}
\includegraphics[bb=0 0 432 303,width=5cm]{inverse_control.jpg}\\
\figurename{3:Inverse control}
\end{center}

図3も，表記方法は図2と同様．意図的に確率を約分せず表示．
 
%数式の練習をする
%No controlの図を入れる
%Inverse controlの図を入れる
%\begin{description}
%\item n:ネットワーク上の全頂点数
%\item $n_k$：次数がkである頂点の総数
%\item P\{ K=k \}= $n_k$/n :次数分布
%\item $K_e$ :ソースノードと辺eを介して隣接しているノードの次数
%\[ \left( \frac{kP}{EK}\]
%\end{description}
\section{シミュレーション}
この節では，実際に計算機実験を行ったことについて述べる．シミュレーションは以下の内容で行った．
\paragraph{ネットワークサイズ} 10,000頂点
\paragraph{ネットワークモデル} 修正版BAモデル
\paragraph{作成ネットワーク数} 100個
\paragraph{シミュレーション回数} 1つのネットワークに対して50回
\paragraph{使用言語}C++

ランダム選択を行う際にrand関数を用いたが，乱数生成の種は次のように揃えた．シミュレーションは１つのネットワークに対して，50回のシミュレーションを行う．その時の乱数生成の種はシミュレーションが１回終わるまでは同じものを使った．つまり，１つのグラフに対して，50個の異なる乱数生成の種を準備した．50回シミュレーションを行った後，用意しておいた別のネットワークに対して，50回シミュレーションを行なっていく．そうすることで，時間を乱数生成の種に用いるよりも，異なるネットワークで行ったシミュレーションと比較しやすくなると考えたからだ．
\subsection{シミュレーションアルゴリズム}
\begin{enumerate}
\item ネットワーク上からランダムにソースノードを１つ選択する．
\item 各ソースノードが情報を伝えるターゲットノードをそれぞれ１つ選択し，情報を伝達する．全ソースノードが同時に行う．この回数を1ステップとする．
\item ネットワーク上のすべての頂点がソースノードとなると，シミュレーションを終える．
\end{enumerate}
\subsection{実行結果}
%図を挿入
シミュレーションを行った結果次の２つの図4，5を得た．No controlの方が情報伝播が速い結果が得られた．
現在シミュレーションのプログラムの実装が適切かどうかの確認は行われていない．プログラムの実装が適切な場合は，次のようなことが言える．『１つ目は，修正版BAモデルでは成り立たないということ．２つ目は，[4]の中で行われている近似は妥当ではないということ．３つ目は，計算機実験で用いた計算機自体に問題があるということ．これら３つが考えられる．』
\begin{center}
\includegraphics[bb=0 0 599 364,width=7cm]{graph2.jpg}\\

\figurename{4:Inverse controlのシミュレーション}
\end{center}

この図4は本来の定義とは異なる方法でInverse controlを実装したプログラムによる１０回分のシミュレーションである．

次の図5は，No controlとInverse controlのシミュレーション結果を1000stepまでを示したグラフである.
\begin{center}
\includegraphics[bb=0 0 481 290,width=7cm]{graph3.jpg}\\

\figurename{5:1000stepまでのグラフ}
\end{center}

%この図5はNo controlとInverse controlのシミュレーション結果の，1000stepまでを示したグラフである．

\section{今後の課題}
今回の実験では，シミュレーションを行う際，逆数の重みを扱う部分をうまく実装することができなかった．この部分を実装する必要がある．また，本実験で用いたプログラムの実装が適切であったかどうか確認する．
%\section{付録}
%\section{用語一覧}
%\begin{itemize}
%\item ケーニヒスベルクの橋の問題:
%\item
%\item ノード:ネットワークにおける頂点のことを指す.
%\item リンク:ネットワークにおける頂点間を連結する辺を指す.
%\item 次数:ノードが有するリンクの総数のことを指す.
%\item スケールフリー性:ネットワークの次数分布がベキ分布となっている場合のこと.kを次数,p(k)を次数分布,γをベキ指数とする
%\[
%p(k)∝k^{-γ},(γ>0)
%\]
%\includegraphics[width=5cm]{scale_free.jpg}
%\item Scale Free Network:Scale Free性を有するネットワークのこと.
%\item BAモデル:成長と優先的選択によりスケールフリー性を実現したモデル.
%\item 修正版BAモデル:BAモデルを簡略化したが,スケールフリー性を実現しているモデル.
%\item ソースノード:ネットワーク上において情報伝達源となっている頂点のこと.
%\item ターゲットノード:ソースノードが伝達する際の相手の頂点のこと.
%\item No Control:ソースノードがターゲットノードを選ぶ際に何の制御も考えない方法.
%\item Inverse Control:No Controlとは違い,ターゲットノードを選ぶ際に,ソースノードの隣接頂点の次数の逆数に比例する確率で選択する方法
%\end{itemize}
%ここまで　やったこと

\end{multicols}%2段落の文章の終わり

\begin{thebibliography}{6}%参考文献({2}：2つ参考文献があるという意味)
\bibitem{a}Leonard Euler's Solution to the Konigsberg Bridge Problem 

http://mathdl.maa.org/mathDL/46/?pa=content{\&}sa=viewDocument{\&}nodeId=1310{\&}bodyId=1452
\bibitem{b}The Euler Archive, commentary on publication, and original text, in Latin. http://www.math.dartmouth.edu/~euler/docs/originals/E053.pdf
\bibitem{c}Duncan J. Watts \& Steven H. Strogatz, Collective dynamics of 'small-world' networks, http://www.nature.com/nature/journal/v393/n6684/abs/393440a0.html
\bibitem{e}Hiroshi Toyoizumi, Seiichi Tani, Optimal Spread over Finite-Size Statistical Network
\bibitem{d}A.-L. Barabasi and R. Albert. Emergence of scaling in random networks.
Sciende,286:509-512, 1999. http://www.sciencemag.org/content/286/5439/509.short
\bibitem{f}今野紀雄 , 井手 勇介  複雑ネットワーク入門 (KS理工学専門書) 2008/05/13.


\end{thebibliography}%参考文献終わり

\end{document}%ドキュメントの終わり
