<jupyter_start><jupyter_text>課題5 ネットワーク分析配点- Q1 4P- Q2 4P- Q3 2P<jupyter_code># モジュールのインポート
import networkx as nx
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline<jupyter_output><empty_output><jupyter_text>Q1以下では、networkxモジュールに含まれるデータセット、空手クラブのソーシャルネットワーク、からグラフオブジェクトを作成し、ネットワーク全体を可視化しています。ネットワークは無方向で重みなしです。また自己ループやノード間の多重リンクはありません。<jupyter_code>G = nx.karate_club_graph() # グラフの作成
pos = nx.spring_layout(G) # 可視化のレイアウト
plt.figure(figsize=(10,10)) # 可視化のサイズ
nx.draw(G, pos=pos, with_labels=True) # 可視化<jupyter_output><empty_output><jupyter_text>このネットワークには34のノードと78のリンクが含まれ、各ノードには0から33の数字がふられています。以下ではこの数字をノードのラベルとして用います。<jupyter_code>print(len(G)) # ノード数
print(G.size()) # リンク数<jupyter_output>34
78<jupyter_text>このネットワークの隣接行列`adj_matrix`は、以下の通りです。<jupyter_code>adj_matrix=nx.adjacency_matrix(G).toarray() # 隣接行列の取得
for row in adj_matrix:
    print(row)<jupyter_output>[0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0]
[1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0]
[1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0]
[1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1]
[0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
[1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 0 0 0 0[...]<jupyter_text>Q1.1以下の辞書`adj_list`は、上記のネットワークのノードをキー、そのノードに隣接しているノードのリストを値として持つ辞書です。例えば、キーが31の値のリストを見ることで、ノード31には0, 24, 25, 28, 32, 33のノードが隣接していることがわかります。このような各ノードの隣接ノードリストの辞書を隣接リストと呼びます。隣接行列`adj_matrix`を受け取り、隣接リストとなる辞書`adj_list`を作成して返す`get_adj_list()`関数を実装してください。 ```Pythonadj_list={0: [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 17, 19, 21, 31],                1: [0, 2, 3, 7, 13, 17, 19, 21, 30],                2: [0, 1, 3, 7, 8, 9, 13, 27, 28, 32],                  ...                31: [0, 24, 25, 28, 32, 33],                32: [2, 8, 14, 15, 18, 20, 22, 23, 29, 30, 31, 33],                33: [8, 9, 13, 14, 15, 18, 19, 20, 22, 23, 26, 27, 28, 29, 30, 31, 32]}```<jupyter_code>def get_adj_list(adj_matrix):
    ### 引数：
    # adj_matrix : 隣接行列

    adj_list={} # 隣接リストの辞書
    
    ### 隣接リストの辞書を作成するコード ###
    
    return adj_list<jupyter_output><empty_output><jupyter_text>`get_adj_list`関数が完成したら、以下のセルを実行して、`adj_list[0]`や`adj_list[33]`を表示し、上記に示されている各ノードの隣接ノードリストが作成できているか確認してください。<jupyter_code>adj_list=get_adj_list(adj_matrix)

print(adj_list[0])
print(adj_list[33])
assert adj_list[0] == [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 17, 19, 21, 31]
assert adj_list[33] == [8, 9, 13, 14, 15, 18, 19, 20, 22, 23, 26, 27, 28, 29, 30, 31, 32]<jupyter_output><empty_output><jupyter_text>Q1.2講義資料の幅優先探索のアルゴリズムを参考に、第1引数として隣接リスト、第2引数として始点ノードのラベルを受け取り、始点から各ノードへの距離の辞書`d`を返す以下の`bfs`関数を完成させてください。隣接リストは上記で作成した`adj_list`を用います。`d`は、キーがノードのラベル、値が始点からそのノードへの距離となる辞書です。講義資料の`Q.enqueue`, `Q.dequeue`はそれぞれコード中の`Q.append`, `Q.popleft`に対応します。<jupyter_code>from collections import deque # キューのインポート

def bfs(g, s):
     ### 引数：
    # g: 隣接リスト
    # s: 始点ノードのラベル
    
    Q = deque() # キューの初期化
    visited={} # 訪問済みノード辞書
    d={} # 始点から各ノードへの距離の辞書
    for i in g.keys(): # ネットワークの各ノードiについて
        d[i]=np.inf # 距離の辞書を全て距離無限大に初期化
        visited[i]=False  # 訪問済みノード辞書を全て未訪問（False）に初期化
        
    visited[s]=True # 始点ノードを訪問済みにする
    d[s]=0 # 始点ノード自身への距離は0
    Q.append(s) # 始点ノードをキューに入れる

    while Q: # キューが空でない限り繰り返し
        
        ### 以下の部分のコードを完成させてください ###
        
        i = ### キューからノードiを取り出すコード ###
    
        for ### ノードiに隣接する各ノードjを取り出すコード ###
            if ### ノードjがまだ未訪問であるという条件コード ###              
                ### ノードjを訪問済みに更新するコード ###
                ### 始点からノードjへの距離を(始点からノードiの距離+1)に更新するコード ###
                ### ノードjをキューに入れるコード ###
                
        ### 作成するコードここまで ###
        
    return d # 始点から各ノードへの距離の辞書を返す<jupyter_output><empty_output><jupyter_text>`bfs`関数が完成したら、以下のセルを実行して動作を確認してください。ノード0からノード26への長さは3、ノード11からノード26への長さは4となります。<jupyter_code>d1=bfs(adj_list, 0)
print(d1[26])

d2=bfs(adj_list, 11)
print(d2[26])
assert bfs(adj_list, 0)[26] == 3
assert bfs(adj_list, 11)[26] == 4<jupyter_output><empty_output><jupyter_text>Q2以下では、空手クラブのソーシャルネットワークデータについて各ノードの次数中心性を計算し、次数中心性の上位のノードを表示しています。ノード33が最も次数中心性が高いことがわかります。<jupyter_code>G = nx.karate_club_graph()
plt.figure(figsize=(10,10)) # 可視化のサイズ
nx.draw(G, pos=pos, with_labels=True) # 可視化
# 次数中心性 (次数/最大次数（N-1))
degree=nx.degree_centrality(G)
print(pd.Series(degree).sort_values(ascending=False).head(5))<jupyter_output>33    0.515152
0     0.484848
32    0.363636
2     0.303030
1     0.272727
dtype: float64<jupyter_text>Q2.1近接中心性、媒介中心性、固有ベクトル中心性の各中心性について、上記の次数中心性と同様に各ノードの中心性を計算し、ネットワーク図の各ノードの位置を参照しながらそれぞれの中心性で上位のノードがどのような位置にあるか観察してください。<jupyter_code>closeness= ###  各ノードの近接中心性を計算 ###
### 近接中心性上位のノードを表示 ###

betweenness= ### 各ノードの媒介中心性を計算 ###
### 媒介中心性上位のノードを表示

eigenvector= ### 各ノードの固有ベクトル中心性を計算 ###
### 固有ベクトル中心性上位のノードを表示 ###<jupyter_output><empty_output><jupyter_text>Q2.2以下では各ノードのPageRankを計算する関数を実装します。`pagerank_centrality`関数は、第1引数としてネットワークの隣接行列、第2引数としてダンピング係数（通常移動とテレポート移動の割合を指定）、第3引数としてベキ乗法の繰り返し回数を受け取り、各ノードのPageRankを要素とするベクトルを返します。ベクトルの各要素のインデックスはノードのラベルに対応します。PageRankを更新するための行列$B$はダンピング係数を$\alpha$、推移確率行列を$A$として以下のように定義されます。行列$A$はネットワークの隣接行列について、すべての要素が0の列があればその列のすべての要素を1とした上で、隣接行列の各要素についてその列の和で割ったものです。$B=\alpha A+\frac{1-\alpha}{ノード数}$行列$B$を用いてPageRankのベクトル$x=(x_1,x_2,...,x_n)$は以下のように更新されます。$x=Bx$$x=x/\Sigma_{i=1}^n x_i$<jupyter_code>def pagerank_centrality(adj_matrix, alpha=0.85, t=100):
    ### 引数：
    # adj_matrix: 隣接行列
    # alpha: ダンピング係数（通常移動とテレポート移動の比率を指定）
    # t: ベキ乗法の繰り返し回数
    
    # 推移確率行列Aを作成
    adj_matrix[:, adj_matrix.sum(0)==0]=1 # 出次数が0のノードは隣接行列の対応する列を1で埋める
    
    A = ### 隣接行列の各要素をその列の和（その列に対応するノードの出次数）で割るコード ###

    B = ###  行列B（講義資料参照）を作成するコード　###
    
    x = ### 各ノードのPageRankを要素とするベクトルを初期化するコード。各要素の値は(1/ノード数） ###
    #　ヒント：np.ones()で要素の値が1の配列がつくれる
    
    ### t回以下の計算を繰り返すコード ###
    ### 1. x=(Bとxの内積)
    ### 2.　xのすべての要素の和でxの各要素を割る

    return x<jupyter_output><empty_output><jupyter_text>`pagerank_centrality`関数が完成したら、以下のセルを実行して動作を確認してください。最もPageRankが高いノードは33でそのPageRankは$\simeq0.10$、次にPageRankが高いノードは0でそのPageRankは$\simeq0.09$となります。<jupyter_code>adj_matrix=nx.adjacency_matrix(G).toarray()
pagerank=pagerank_centrality(adj_matrix, 0.85, 100)
# print(pagerank)
print(pd.Series(pagerank).sort_values(ascending=False).head(5))
assert int(pagerank[33]*100) == 10
assert int(pagerank[0]*100) == 9<jupyter_output><empty_output><jupyter_text>NetworkXの`pagerank`関数を使って各ノードのPageRankを計算すると以下のようになります。<jupyter_code>pr=nx.pagerank(G, alpha=0.85, max_iter=100)
print(pd.Series(pr).sort_values(ascending=False).head(5))<jupyter_output>33    0.100918
0     0.097002
32    0.071692
2     0.057078
1     0.052878
dtype: float64<jupyter_text>Q3以下では、空手クラブのソーシャルネットワークデータを用いてコミュニティ抽出を行います。まず、コミュニティ抽出前のネットワークを可視化します。<jupyter_code>G = nx.karate_club_graph()
pos = nx.spring_layout(G)
plt.figure(figsize=(10,10))
nx.draw_networkx(G, pos=pos)
_ = plt.axis('off')<jupyter_output><empty_output><jupyter_text>エッジ媒介中心性を用いたコミュニティ抽出（Girvan-Newman法）を行う以下の`girvan_newman`関数を完成させてください。`girvan_newman`関数は引数としてnetworkxのグラフオブジェクトを受け取り、各コミュニティのノード集合を要素としたリストを返します。<jupyter_code>def find_best_edge(G): # グラフGにおいてエッジ媒介中心性が一番大きいエッジの両端ノードをタプルとして返す関数
    edge_between = nx.edge_betweenness_centrality(G)     
    return max(edge_between, key=edge_between.get)

def girvan_newman(G):
    G = G.copy() # グラフGのエッジを除いていくのでグラフオブジェクトをコピーしておく
    removed_edges=[] # 取り除いたエッジのリスト
    while nx.number_connected_components(G) ==1: # グラフが分割されるまで繰り返す
        
        ### エッジ媒介中心性が一番大きいエッジをGから取り除く以下の処理を完成させてください ###
        
        ### 1. エッジ媒介中心性が一番大きいエッジの両端ノードを探す
        ### 2. そのエッジをGから取り除く（ヒント グラフオブジェクトのremove_edgeメソッド）
        ### 3. 削除したエッジの両端ノードをタプルとしてremoved_edgesに追加
        
        ### 作成するコードここまで ###

    return list(nx.connected_components(G)), removed_edges<jupyter_output><empty_output><jupyter_text>`girvan_newman`関数が完成したら、以下のセルを実行して動作を確認してください。取り除かれるエッジのリスト`removed_edges`は以下になります。```Python [(0, 31), (0, 2), (0, 8), (13, 33), (19, 33), (2, 32), (1, 30), (1, 2), (2, 3), (2, 7), (2, 13)] ```<jupyter_code>communities, removed_edges = girvan_newman(G)
print(removed_edges)
assert set(removed_edges) == set([(0, 31), (0, 2), (0, 8), (13, 33), (19, 33), (2, 32), (1, 30), (1, 2), (2, 3), (2, 7), (2, 13)])<jupyter_output><empty_output><jupyter_text>以下のセルを実行してネットワークを可視化し、先の処理で抽出されたコミュニティを確認してください。取り除かれたエッジは破線で示されています。<jupyter_code>keeped_edges = set(G.edges()) - set(removed_edges)
colors = ['red', 'yellow']

plt.figure(figsize=(10,10))
nx.draw_networkx_edges(G, pos, edgelist=keeped_edges)
nx.draw_networkx_edges(G, pos, edgelist=removed_edges, style='dashed')
for community, color in zip(communities, colors):
    nx.draw_networkx_nodes(G, pos=pos, nodelist=community, node_color=color)
nx.draw_networkx_labels(G, pos=pos)
_ = plt.axis('off')<jupyter_output><empty_output><jupyter_text>参考<jupyter_code># networkx(バージョン2.X以上)のGirvan–Newman法の関数によるコミュニティ抽出
community_generator = nx.community.girvan_newman(G)

# community_generatorはジェネレーターとなっており、for文を繰り返すごとにコミュニティ分割を行う
# 最終的には各ノードが1つのコミュニティの状態となる
for communities in community_generator: 
    print(communities)<jupyter_output>({0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 19, 21}, {2, 8, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33})
({0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 19, 21}, {32, 33, 2, 8, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31}, {9})
({0, 1, 3, 7, 11, 12, 13, 17, 19, 21}, {32, 33, 2, 8, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31}, {4, 5, 6, 10, 16}, {9})
({0, 1, 3, 7, 11, 12, 13, 17, 19, 21}, {2, 24, 25, 27, 28, 31}, {4, 5, 6, 10, 16}, {32, 33, 8, 14, 15, 18, 20, 22, 23, 26, 29, 30}, {9})
({0, 1, 3, 7, 12, 13, 17, 19, 21}, {2, 24, 25, 27, 28, 31}, {4, 5, 6, 10, 16}, {32, 33, 8, 14, 15, 18, 20, 22, 23, 26, 29, 30}, {9}, {11})
({0, 1, 3, 7, 12, 13, 17, 19, 21}, {2, 24, 25, 27, 28, 31}, {4, 5, 6, 10, 16}, {32, 33, 8, 14, 15, 18, 20, 22, 23, 29, 30}, {9}, {11}, {26})
({0, 1, 3, 7, 13, 17, 19, 21}, {2, 24, 25, 27, 28, 31}, {4, 5, 6, 10, 16}, {32, 33, 8, 14, 15, 18, 20, 22, 23, 29, 30}, {9}, {11}, {12}, {26})
({0, 1, 3, 7, 13, 17, 19, 21}, {2, 24, 25[...]
{'fraction_non_alphanumeric': 0.14866760168302945, 'fraction_numerical': 0.1319308087891538, 'mean_word_length': 4.345327336331834, 'pattern_counts': {'":': 0, '<': 68, '<?xml version=': 0, '>': 68, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 104, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '18', 'dir': 'jupyter-structured-clean-dedup', 'id': '427813', 'license': 'MIT', 'n_tokens_mistral': 7683, 'n_tokens_neox': 6448, 'n_words': 1185, 'path': 'ex5/ex5.ipynb', 'repo_name': 'UTDataMining/2020A', 'size': '10695'}