情報工学領域実習 B

グラフ上のランダムウォーク

実習の流れ・チーム分けの方針・態度目標

2024-09-25 と同じ。

https://lsnl.jp/~ohsaki/lecture/training/2024/#8-1

内容目標

- グラフ上のランダムウォークとは何かを理解し、他人に説明できるようになる。

- グラフ上のランダムウォークのシミュレーションを実行できるようになる。

課題

課題 1

以下のグラフにおいて、 ノード 1 から移動を開始したエージェント (単純ランダムウォーク (SRW) のエージェント) が、 ノード 6 に到達するまでの時間 (初回到着時間) を実験で求めよ。 実験には、 紙、 筆記用具、 サイコロ (または同等品) のみを使用せよ。

   1           5
  / \         /
 /   \       /
2 --- 3 --- 4----6

課題 2

計算機を用いたシミュレーションにより、 課題 1 の初回到着時間を 100 回計測することにより、 平均初回到着時間を求めよ。

課題 3

課題 2 と同じ。 ただし、 エージェントの移動モデルは、 単純ランダムウォーク (SRW) ではなく、 直前に訪問したノードへの再訪を可能な限り回避する、 不可逆ランダムウォーク (NBRW) とせよ。

課題 4

課題 2 と同じ。 ただし、エージェントの移動モデルは、 平均初回到着時間が短かくなりそうなランダムウォークを自分で考案せよ。

略解

課題 1

省略

課題 2

> sudo pip3 install -U perlcompat tbdump graph-tools py-stats
> git clone https://github.com/h-ohsaki/randwalk.git
> cd randwalk
> wget https://lsnl.jp/~ohsaki/lecture/training/2024/priv/6-srw
> chmod +x 6-srw

※ 上記の 6-srw では、(2, 3) のリンクが不足しているので、(2, 3) のリンクを追加する必要がある。

1 回だけ実行する場合:
> ./6-srw

100 回の平均を計算する場合:
> for i in (seq 100)
  ./6-srw | tail -1 | awk '{ print $1 }' | sed 's/t=//'
end | stats -v

課題 3

20 行目の SRW を NBRW に書き替えればよい。

課題 4

省略

レポート課題 2024-11-27

2024-09-25 のものと同じ。

https://lsnl.jp/~ohsaki/lecture/training/2024/#8-6