Sho Tsugawa's Homepage:情報メディア実験

ER モデル、WS モデル、BA モデルによりグラフを生成せよ。
生成したグラフを可視化し、それぞれの特徴を観察せよ。

各モデルのパラメータを変更し、グラフを生成せよ。
生成したグラフを可視化し、パラメータによってグラフの構造がどのように変化するかを観察せよ。

ER モデル、WS モデル、BA モデル以外の生成モデルについて調査し、そのモデルを用いてグラフを生成せよ。
生成したグラフを可視化し、その特徴を観察せよ。

ER モデル、WS モデル、BA モデルにより生成したグラフの次数分布をプロットせよ。
線形、対数の 2 通りの軸でプロットせよ。

ER モデル、WS モデル、BA モデルにより生成したグラフのクラスタリング係数を求めよ。

ER モデル、WS モデル、BA モデルにより生成したグラフの平均経路長を求めよ。

課題 2-1〜2-3 で求めた「次数分布」、「クラスタリング係数」、「平均経路長」を用いて、ER モデル、WS モデル、BA モデルにより生成したグラフがそれぞれどのような特徴を有するかまとめて、メールで報告せよ。メール本文に数行程度の分量で良い。提出期限は、10/24 の実験開始までとする。

グラフの構造を特徴付ける指標について調査し、各モデルによって生成したグラフにおけるその指標の値を求めよ。

ノードの次数中心性、近接中心性、媒介中心性の定義を理解せよ。
いくつかのグラフにおいて、各ノードの次数中心性、近接中心性、媒介中心性の値を求めよ。
ノードを中心性の値によってランキングし、ランキングの上位のノードが中心性の種類によってどのように異なるかを観察せよ。
用いるモデルは何でもよいが、複数のモデルで試すとよい。

グラフにおける各ノードの中心性の値を計算し、中心性の値が大きいほどノードのサイズが大きくなるように可視化せよ。
異なる中心性、異なるモデルで生成したグラフでいくつか試してみること。
可視化した結果のうちの 1 つを画像ファイルもしくは PDF ファイルの形式でエクスポートして、メールに添付して提出せよ。提出期限は、10/31 の実験開始までとする。

次数中心性、近接中心性、媒介中心性、以外の中心性の定義を調査せよ。
調査した中心性の値をいくつかのグラフで計算し、次数中心性、近接中心性、媒介中心性との違いを考察せよ。

以下の web ページにおいて人と人の関係を表現したソーシャルネットワークのデータが公開されている。(他にも、検索すれば見つかる。「ソーシャル」でないネットワークのデータも含まれている)

• Stanford Large Network Dataset Collection
• Mark Newman 先生のホームページ

これまでに学んだ指標の計算方法や可視化の方法を用いて、ソーシャルネットワークの構造的な特徴について考察せよ。複数のソーシャルネットワーク (少なくとも 2 つ) を分析し、それらの特徴の違いや類似点について論じよ。さらに、モデルで生成したグラフとの違いや類似点について論じよ。

公開されているデータ以外に、自分でソーシャルネットワークのデータを収集し、分析せよ。例えば、Twitter のデータ (API を利用する)、自分の電子メールのログなどが利用可能である。

課題 4-1 および 4-2 についてレポートにまとめよ。用いたデータの説明、分析対象のネットワークを可視化した図、分析対象のネットワークの特徴に関する定量的なデータに基づいた考察、を少なくとも含めること。分量については特に指定しない。

• 提出期限：12/6 23:59
• 提出方法：PDF ファイルをメールに添付し、津川のメールアドレスに送る

ネットワーク上の情報拡散のモデルである Independent Cascade Model のシミュレーションを実施せよ。
ER モデル、および BA モデルで生成したネットワークを対象に、ランダムに k 個のシードノードを選択した時の、active なノード数を求め、プロットせよ。
横軸 k 、縦軸 active なノード数のグラフを作成せよ。k をどの程度の範囲で変化させるか、ネットワークのサイズなどのパラメータをどのように設定するかは自由に決めてよい。あまり大きなサイズのネットワークではシミュレーションの実行に時間がかかるため注意すること。ある k に対して、シミュレーションを 100 回以上試行し、それぞれの試行での active なノード数の平均を求めること。

課題 5-1 のシードノードの選択を、次数の高い順に k 個のシードノードを選択するように変更して、同様のシミュレーションを実行せよ。

ネットワークにおける k 個のシードノードから Independent Cascade Model で影響伝播を行う。
この時、アクティブなノード数をできるだけ多くするようなシードノードの選び方を考え、実装せよ。
少なくとも、リンク先 の Email のネットワークにおいて、ノード数 k とアクティブなノードの数の関係をプロットせよ。もちろん、他のネットワークでも実験するとなお良い。
次数の高い順にシードノードを選んだ場合、ランダムにシードノードを選んだ場合の結果と比較せよ。

このような問題は、影響最大化 (Influence Maximization) 問題と呼ばれ、現在も活発に研究が行われている。
発表されている論文の手法を実装してもよいし、自分でオリジナルな手法を考案してもよい。
最終発表会では、実装した手法と、その評価結果について発表してもらう。複数の手法を実装してもよい。(既存研究よりも高い性能の手法を考案できれば、論文が書ける)

課題 6-1 について、レポートにまとめよ。分量については特に指定しない。

• 提出期限：2/8 (金) 17:00
• 提出方法：図情支援室学群学務の提出ボックスに所定の表紙を付けて提出する。また、PDF ファイルを津川にメールで送ること。

課題 6-1 について、最終報告会で発表せよ。少なくとも、実装した手法のアイディアと性能評価の結果について発表せよ (日時未定)。