情報理学１ 筆記問題




※作成に際しての注意


計算問題にあたっては、計算過程をできるだけ詳しく、わかりやすく書いてください。
図示するにあたっては、横軸、縦軸がなにであるかちゃんと記してください。
最後の問題は、ちゃんと情報源を書いてください。ＵＲＬもお願いします。

※提出に際しての注意


解答を記述する方法は可読であればなんでもいいです。(手書きでもワープロでも）
但し、紙で提出してください。



前書きのWSモデルの作り方を見ながら、以下の問いに答えなさい。
なお、前書きと同じく、全ノード数はＮ、１ノードあたりのリンク数はｋとする。

    ＷＳモデルは、ｐ＝０のときは規則格子状のネットワークとなり、ｐ＝１のときはランダムなネットワークとなり、ｐ〜０．０１のときはスモールワールドネットワークとなります。
    以下では、それぞれの場合の、平均距離Ｌ、平均クラスター係数Ｃを求め、前書きに示されているような大小関係になることを確かめます。
    但し、Ｎはとても大きいとします。


    まずはじめにｐ＝０のときを考えます。


  1. このときの平均クラスター係数Cを求めなさい。


  2. このときの平均距離が≒Ｎ／２ｋとなることを示しなさい。このとき、ｋ＜＜Ｎとする。


    次にｐ＝１のときを考えます。ｐ＝１のときのネットワークとして、全リンク数／ノードのペアの総数であるｋ／Ｎ−１≒ｋ／Ｎを確率として
    ノード間にリンクを張っていったランダムネットワークを考えることにします。

  3. このときの平均クラスター係数Ｃを求めなさい。


    4. ちなみに、このときの平均距離Ｌは∝ｌｏｇＮとなります。


    最後に、ｐ〜０．０１のときを考えます。

  4. 平均クラスター係数Ｃを求めよ。
    このときのＣは、
    Ｃ＝（ｐ＝０のときのクラスターがｐ〜０．０１のときに壊れずに残っている割合）＊（ｐ＝０のときのＣ）で近似して考えてください。
    ちなみに、クラスターとは、クラスター係数のときに考えている隣接ノード同士をリンクで結んで出来る三角形のことです。



  5. ｐ≠０，１のときの平均距離Ｌはおおよそ


    と計算で求めることが出来る。
    上のＬ式を用いて



    を示してください。


  6. Ｌ（ｐ）／Ｌ（０）をＮｋｐ／２を変数として以下の指定通り図示してください。






    7. 以上求めたＣ，Ｌを用いて、Ｃ，Ｌの大小関係が、前書きどおりになっていることを確かめてみてください。（書く必要はありません）


    次の問題は、必修ではありません。しかし、やってくれた方には加算したいと思います

  7. ネットワークの性質を表す指標には、Ｃ，Ｌ以外にも、次数がｋであるノードの数の全ノード数に対する割合を示す次数分布がある。
    実際のネットワークにおいて、次数分布がべき乗になることが多くあることが知られている。そのようなネットワークをスケールフリーネットワークという。
    実際にスケールフリーネットワークになっているネットワークを調べてきて、何のネットワークか、そのべき指数はいくらか、
    次数分布がべき乗であることからわかるそのネットワークの特徴を書いてください。なお、参考にしたものを挙げておいてください（ＵＲＬも）