都道府県間のネットワーク図と隣接距離の計測

　こういうやつの作り方です。各自治体の名前をノードとし、隣接行列（どことどこが接しているか）をもとにネットワークを作成します。この記事を作るにあたって実装した手法ですが、この記事ではアルゴリズムとかソースコードとかを主体に書いていきます。

データ収集

　自治体と人口のデータを総務省から取得してます。異なる集計区分が同一の列にある、郡と自治体名が分かれていないなど、あまり綺麗なデータではないですが（河野太郎、なんとかしてくれー！）最低限整形してcsvに書き出します。これを元に、自治体名と人口についてそれぞれリストを作成します。

import pandas as pd
import numpy as np

df = pd.read_csv('data.csv') # 自前で用意した整形データ

prefecture = '青森県'

cities = []
pops = []

for c in df[df['都道府県名'] == prefecture]['市区町村名']:
    if c is np.nan:
        continue
    p = df[df['市区町村名'] == c]['計']
    if len(p) > 1:
        pop = pop.iloc[0]
    p = int(p)
    p = np.log2(p)-9 #サイズ感の調整
    cities.append(c)
    pops.append(p)

print(cities)
print(pops)

result

['青森市', '弘前市', '八戸市', ...
[9.224411558184599, 8.494972742467962, 8.894640162224299, ...

　次に、netoworkxモジュールを使ってネットワーク図を作成します。隣接関係をこのページから取得し、正規表現によって解析可能なデータとします。解析する度にスクレイピングをしかけていてはお互いに不幸な感じになるので、一回解析したらローカルファイルにpickleとして保存しておくのがおすすめです。

import re
import requests
import networkx as nx
import pickle

get = requests.get("https://uub.jp/cpf/rinsetsu.html")
get.encoding = get.apparent_encoding
text = get.text

with open('text.pickle', 'wb') as f:
    pickle.dump(text,f)

# with open("text.pickle", mode="rb") as f:
#     text = pickle.load(f) # 2回目以降はこれだけで一瞬で済む

G = nx.Graph()

for c, p in zip(cities, pops):
    G.add_node(c, count=p)

pattern = r'<tr class="al bw">(.*)</td></tr>'
result = re.findall(pattern, text)

print(result)

result

['<td class="ac">1</td><td>札幌市</td><td class="ac"></td><td class="ar">11</td><td><nobr>小樽市</nobr> <nobr>江別市</nobr> <nobr>千歳市</nobr>  ...

　隣接関係を元にグラフノード間のエッジを作っていき、ネットワーク図を出力します。

import matplotlib.pyplot as plt

for r in result:
    pattern = r'</td><td>(.*?)</td>'
    new_result = re.findall(pattern, r)
    now_city = new_result[0]
    pattern = r'<nobr>(.*?)</nobr>'
    next_cities = re.findall(pattern, r)
    for next_city in next_cities:
        c1 = now_city
        c2 = next_city
        if not G.has_node(c1) or not G.has_node(c2):
            continue
        G.add_edge(c1, c2)


plt.figure(figsize=(10, 10))
pos = nx.spring_layout(G, 0.1)
node_size = [np.power(2, d['count'])
             for (n, d) in G.nodes(data=True)]
nx.draw_networkx_nodes(G, pos, node_size=node_size,
                       node_color='b', alpha=0.2)
nx.draw_networkx_labels(G, pos, font_family='Yu Mincho',
                        font_size=10)  # 游明朝で日本語化
nx.draw_networkx_edges(G, pos, alpha=0.4, edge_color='r',
                       width=1)


plt.axis('off')
plt.show()

　冒頭のようなネットワーク図が表示されるはずです。エッジの追加と、ネットワーク図の図示についてはPythonでQiitaタグのネットワークを可視化するを全面的に参考にさせていただきました。ありがとうございます。参照先で課題となっていた日本語化については、Windowsでは游明朝を指定することで解決できるはずなので、上のコードではそうしています。

隣接距離の計算

　グラフが構成されれば、隣接距離（ノード間の最短ステップ数）を計測することができます。色々方法はあると思いますが、古典的なBFS（幅優先探索）で行いました。

from collections import deque

dist = {}

to = {}
pattern = r'<tr class="al bw">(.*)</td></tr>'
result = re.findall(pattern, text)

for c in cities:
    dist[c] = 10000 #十分に大きい値
    to[c] = []

for r in result:
    pattern = r'</td><td>(.*?)</td>'
    result = re.findall(pattern, r)
    now_city = result[0]
    pattern = r'<nobr>(.*?)</nobr>'
    next_cities = re.findall(pattern, r)
    for next_city in next_cities:
        c1 = now_city
        c2 = next_city
        if c1 not in cities or c2 not in cities:
            continue
        to[c1].append(c2)
        to[c2].append(c1)

capital = "青森市"

q = deque()
q.append(capital)
dist[capital] = 0

while len(q) > 0:
    now_city = q.popleft()
    for next_city in to[now_city]:
        if dist[now_city] + 1 >= dist[next_city]:
            continue
        q.append(next_city)
        dist[next_city] = dist[now_city] + 1

near = []
for i in cities:
    near.append([])

for d in dist:
    near[dist[d]].append(d)

for i, n in enumerate(near):
    if len(n) == 0:
        break
    print("隣接距離{}の自治体：{}".format(i, n))

result

隣接距離0の自治体：['青森市']
隣接距離1の自治体：['黒石市', '五所川原市', '十和田市', '平川市', '平内町', '蓬田村', '藤崎町', '板柳町', '七戸町']
隣接距離2の自治体：['弘前市', 'つがる市', '今別町', '外ヶ浜町', '大鰐町', '田舎館村', '鶴田町', '中泊町', '野辺地町', '六戸町', '東北町', '五戸町', '新郷村']
隣接距離3の自治体：['八戸市', '三沢市', '鰺ヶ沢町', '西目屋村', '横浜町', '六ヶ所村', 'おいらせ町', '三戸町', '南部町']
隣接距離4の自治体：['むつ市', '深浦町', '東通村', '田子町', '階上町']
隣接距離5の自治体：['大間町', '風間浦村', '佐井村']