Sho Tsugawa's Homepage:情報メディア実験
目次
お知らせ
初回の集合場所は実験開始までに本ページで連絡します。
実験テーマ:ソーシャルネットワーク分析
本実験では、人と人との関係をグラフとして表現したソーシャルネットワークの分析手法を学習します。電子メールや SNS (Social Networking Services) のデータなど、実際の人と人との交流の履歴からソーシャルネットワークを構築し、構築したネットワークを分析します。特にネットワークを特徴付ける指標や、中心的なノードの推定手法について演習を通じて学習します。
中間課題では、データの収集から分析までの流れを一通り行い、レポートにまとめます。
最終課題では、影響最大化問題と呼ばれる、ソーシャルネットワークにおいて影響力の強いノード (の集合) を推定する問題の解法の提案、実装、評価を行い、レポートにまとめます。最後の週には、提案した解法の発表会を予定しています。
概要
- 担当教員: 津川 翔
- 実施学期: 2018年度 秋 ABC
- 実施場所: 第三エリア 3C113
- 受け入れ人数:10 人
スケジュール
以下のスケジュールで実験を進めるが、進捗状況によって、スケジュールを変更する可能性がある。
「*」印の付いた日には、課題に関する補足説明を実施する。
補足資料 (の一部) にアクセスするためのパスワードは実験中に伝える。
日付 | 内容 | 補足資料 | 課題 |
---|---|---|---|
10/5*、10、12 | ガイダンス、ネットワーク生成モデル、ネットワーク可視化 | ガイダンス、生成モデル、生成と可視化 | 課題1 |
10/17、19 | ネットワークの特徴を表す指標:次数分布、平均経路長、クラスタリング係数 | 補足 | 課題2 |
10/24*、10/26 | ノードの特徴を表す指標:中心性 | スライド、中心性の計算 | 課題3 |
10/31、11/7、9、14 | ソーシャルネットワーク分析 | 補足 | 中間課題 |
11/16、20、21、12/5 | ソーシャルネットワーク分析+中間レポート作成 | ||
12/7*、12、14 | 情報拡散モデルと影響最大化問題 | スライド 補足 | 課題5 |
12/19、21、26、1/9、11 | 最終課題 | 最終課題 | |
1/16、17、25、 30 | レポート作成 | ||
2/1 | まとめ |
課題に関する補足
- 「*」印の付いた課題は発展課題である。余力があれば取り組むこと。
- グラフの生成やグラフの指標の計算には、igraph などのライブラリを利用してもよい。ただし、理解を深めるため、余力があれば自分でも実装してみることをすすめる。
- 課題を実施するための補足資料やサンプルプログラムは、本ホームページにおいて公開し、必要に応じて実験中に説明を行う。
課題1
課題 1-1
ER モデル、WS モデル、BA モデルによりグラフを生成せよ。
生成したグラフを可視化し、それぞれの特徴を観察せよ。
課題 1-2
各モデルのパラメータを変更し、グラフを生成せよ。
生成したグラフを可視化し、パラメータによってグラフの構造がどのように変化するかを観察せよ。
課題 1-3*
ER モデル、WS モデル、BA モデル以外の生成モデルについて調査し、そのモデルを用いてグラフを生成せよ。
生成したグラフを可視化し、その特徴を観察せよ。
課題2
課題 2-1
ER モデル、WS モデル、BA モデルにより生成したグラフの次数分布をプロットせよ。
線形、対数の 2 通りの軸でプロットせよ。
課題 2-2
ER モデル、WS モデル、BA モデルにより生成したグラフのクラスタリング係数を求めよ。
課題 2-3
ER モデル、WS モデル、BA モデルにより生成したグラフの平均経路長を求めよ。
課題 2-4
課題 2-1〜2-3 で求めた「次数分布」、「クラスタリング係数」、「平均経路長」を用いて、ER モデル、WS モデル、BA モデルにより生成したグラフがそれぞれどのような特徴を有するかまとめて、メールで報告せよ。メール本文に数行程度の分量で良い。提出期限は、10/24 の実験開始までとする。
課題 2-5*
グラフの構造を特徴付ける指標について調査し、各モデルによって生成したグラフにおけるその指標の値を求めよ。
課題3
課題 3-1
ノードの次数中心性、近接中心性、媒介中心性の定義を理解せよ。
いくつかのグラフにおいて、各ノードの次数中心性、近接中心性、媒介中心性の値を求めよ。
ノードを中心性の値によってランキングし、ランキングの上位のノードが中心性の種類によってどのように異なるかを観察せよ。
用いるモデルは何でもよいが、複数のモデルで試すとよい。
課題 3-2
グラフにおける各ノードの中心性の値を計算し、中心性の値が大きいほどノードのサイズが大きくなるように可視化せよ。
異なる中心性、異なるモデルで生成したグラフでいくつか試してみること。
可視化した結果のうちの 1 つを画像ファイルもしくは PDF ファイルの形式でエクスポートして、メールに添付して提出せよ。提出期限は、10/31 の実験開始までとする。
課題 3-3*
次数中心性、近接中心性、媒介中心性、以外の中心性の定義を調査せよ。
調査した中心性の値をいくつかのグラフで計算し、次数中心性、近接中心性、媒介中心性との違いを考察せよ。
中間課題
課題 4-1
以下の web ページにおいて人と人の関係を表現したソーシャルネットワークのデータが公開されている。(他にも、検索すれば見つかる。「ソーシャル」でないネットワークのデータも含まれている)
これまでに学んだ指標の計算方法や可視化の方法を用いて、ソーシャルネットワークの構造的な特徴について考察せよ。複数のソーシャルネットワーク (少なくとも 2 つ) を分析し、それらの特徴の違いや類似点について論じよ。さらに、モデルで生成したグラフとの違いや類似点について論じよ。
課題 4-2
公開されているデータ以外に、自分でソーシャルネットワークのデータを収集し、分析せよ。例えば、Twitter のデータ (API を利用する)、自分の電子メールのログなどが利用可能である。
課題 4-3
課題 4-1 および 4-2 についてレポートにまとめよ。用いたデータの説明、分析対象のネットワークを可視化した図、分析対象のネットワークの特徴に関する定量的なデータに基づいた考察、を少なくとも含めること。分量については特に指定しない。
- 提出期限:12/6 23:59
- 提出方法:PDF ファイルをメールに添付し、津川のメールアドレスに送る
課題5
課題 5-1
ネットワーク上の情報拡散のモデルである Independent Cascade Model のシミュレーションを実施せよ。
ER モデル、および BA モデルで生成したネットワークを対象に、ランダムに k 個のシードノードを選択した時の、active なノード数を求め、プロットせよ。
横軸 k 、縦軸 active なノード数のグラフを作成せよ。k をどの程度の範囲で変化させるか、ネットワークのサイズなどのパラメータをどのように設定するかは自由に決めてよい。あまり大きなサイズのネットワークではシミュレーションの実行に時間がかかるため注意すること。ある k に対して、シミュレーションを 100 回以上試行し、それぞれの試行での active なノード数の平均を求めること。
課題 5-2
課題 5-1 のシードノードの選択を、次数の高い順に k 個のシードノードを選択するように変更して、同様のシミュレーションを実行せよ。
最終課題
課題6-1
ネットワークにおける k 個のシードノードから Independent Cascade Model で影響伝播を行う。
この時、アクティブなノード数をできるだけ多くするようなシードノードの選び方を考え、実装せよ。
少なくとも、リンク先 の Email のネットワークにおいて、ノード数 k とアクティブなノードの数の関係をプロットせよ。もちろん、他のネットワークでも実験するとなお良い。
次数の高い順にシードノードを選んだ場合、ランダムにシードノードを選んだ場合の結果と比較せよ。
このような問題は、影響最大化 (Influence Maximization) 問題と呼ばれ、現在も活発に研究が行われている。
発表されている論文の手法を実装してもよいし、自分でオリジナルな手法を考案してもよい。
最終発表会では、実装した手法と、その評価結果について発表してもらう。複数の手法を実装してもよい。(既存研究よりも高い性能の手法を考案できれば、論文が書ける)
課題6-2
課題 6-1 について、レポートにまとめよ。分量については特に指定しない。
- 提出期限:2/8 (金) 17:00
- 提出方法:図情支援室学群学務の提出ボックスに所定の表紙を付けて提出する。また、PDF ファイルを津川にメールで送ること。
課題6-3
課題 6-1 について、最終報告会で発表せよ。少なくとも、実装した手法のアイディアと性能評価の結果について発表せよ (日時未定)。