山本担当分 レポート課題#
締め切り: 2025年7月31日（木）23:59
提出先: 学務情報システム
提出形式
指定したテンプレートファイル（Wordファイル）を用いて解答を作成すること
提出時にはWordファイルをPDFファイルに変換すること
留意事項: 問3で用いるデータをダウンロードするためのパスワードは，別途学務情報システム経由でお知らせします
問1: ノードの媒介中心性（20点）#
以下はあるソーシャルネットワークグラフ\(G_{social}\)である． グラフ\(G_{social}\)中におけるノードA，B，およびCの媒介中心性を計算過程を示しながら求めなさい． なお，本課題のノード\(n\)の媒介中心性の計算において，ノードから別ノードへの最短経路が\(n\)を経由するもの以外にも存在する場合，\(n\)を経由する最短経路のみを計算対象としなさい．
問2: PageRank（合計40点）#
問2-(1): シンプルなPageRank（20点）#
以下のグラフ上のノードの重要度について，下記手順（単純なPageRankアルゴリズム）で計算したい．
すべてのノードの重要度を\(\frac{1}{N}\)で初期化
ノード\(x\)の重要度\(p(x)\)を右式で更新: \(p(x)=\sum_{y \in link\_to(x)} \frac{1}{deg_{out}(y)}p(y)\)
ステップ2をスコアが収束するまで繰り返す
ただし，\(N\)はノード数，\(link\_to(x)\)はノード\(x\)にエッジを張っているノードの集合，\(deg_{out}(y)\)はノード\(y\)の出次数とする．
ステップ2を3回繰り返したときの各ノードの重要度の値を計算しなさい． また，ステップ2を3回繰り返した際の値の変化傾向から，ステップ2を無限に繰り返した際に得られるノードの重要度の収束値を予想しなさい． なお，重要度の計算を手計算で行う場合はその過程を，プログラミングで行う場合はコードを解答とともに示しなさい．
問2-(2): PageRankの解釈（20点）#
グラフ\(G\)に含まれるノード数を\(N\)，ノード\(x\)にエッジを張っているノード集合を\(link\_to(x)\)，ノード\(y\)の出次数を\(deg_{out}(y)\)，\(\alpha\)を0以上1以下の実数とするとき，\(G\)に含まれるノード\(x\)のPageRank値\(p(x)\)は，以下の式によって再帰的に計算される．
グラフ\(G\)の各ノードのPageRank値を上の式に従って計算したとき，どのノードのPageRank値も少なくとも\(\frac{1-\alpha}{N}\)以上になることを示しなさい． また，\(\alpha\)が0に近づくにつれて，各ノードのPageRank値がどのような値になるか，ノード間のPageRank値の違いがどのような意味合いを持つのか述べなさい．
問3: 社会ネットワーク分析（合計40点）#
以下のグラフ\(G_{edo}\)は，人文学オープンデータ共同利用センターが公開しているデータベース江戸買物案内をもとに，「江戸買物独案内」で登場する商人の交流関係の一部をグラフ化したものである（データベースからの課題用データ抽出，およびグラフ化は山本が実施）． グラフ中のノードは江戸買物案内に2回以上登場する商人，エッジは同じ区域（居所（歴史地名大系））で商売を営んでいたことを意味する．
グラフ\(G_{edo}\)のデータは，レポート課題用にコチラからダウンロードが可能である（パスワードは講義中に伝えます）．
また，ダウンロードしたデータは，以下のコードでNetworkX形式のグラフとして読み込める（データはdata/edo_merchantディレクトリにedo_merchant.graphmlという名前で保存したとする）．
G_edo = nx.read_graphml(path="data/edo_merchant/edo_merchant.graphml")
# # グラフG_edoのノードから10件を表示
# list(G_edo.nodes)[:10]
# # 玉屋市郎兵衛の隣接ノード（同じ商売区域で商売を営んでいた人）を表示
# for neighbor in G_edo.neighbors('玉屋市郎兵衛'):
# print(neighbor)
問3-(1): 影響力のある商人（15点）#
グラフ\(G_{edo}\)をもとに，データ中に含まれる商人のうち「最も影響力のあった商人」の上位10名を求めなさい． 解答においては，上位10名を求める過程や検討の際に用いたプログラミングコードも合わせて提示すること． なお，「影響力」の定義は解答者が定めればよいが，その定義を必ず解答の中で宣言すること．
問3-(2): 商売区域をつなぐ重要な商人（15点）#
可視化されたグラフが示しているように，グラフ\(G_{edo}\)においてノード（商人）は商売区域ごとにコミュニティを形成しているように見える． 現代においてもそうであるように，ある地域から別の地域，しかも大きな区域に進出をする際には，商売区域をつなぐような人物は重宝されたと考えられる．
グラフ\(G_{edo}\)をもとに，データ中に含まれる商人のうち「コミュニティの橋渡し役として重要であったと考えられる商人」の上位10名を求めなさい． 解答においては，上位10名を求める過程や検討の際に用いたプログラミングコードも合わせて提示すること． なお，「橋渡し役としての重要度」の定義は解答者が定めればよいが，その定義を必ず解答の中で宣言すること．
問3-(3): 鰹節・塩干肴問屋業界で影響力のある商人（10点）#
コチラからダウンロードできるデータには，グラフ\(G_{edo}\)に含まれる商人のうち，「鰹節・塩干肴問屋」を営んでいた商人の名前が収められている． グラフ\(G_{edo}\)をもとに，「鰹節・塩干肴問屋」を営む商人の界隈で影響力のあった商人の上位5名を求めなさい． 解答においては，上位5名を求める過程や検討の際に用いたプログラミングコードも合わせて提示すること． なお，「影響力」の定義は解答者が定めればよいが，その定義を必ず解答の中で宣言すること．