実例で動かすグラフアルゴリズムとグラフデータベース(Neo4j)、01_データ編：PoliticiansNet

Colabは[こちら](https://colab.research.google.com/drive/1aHxW5XDTNrjbOhKVucN15XBsvmDk1qwV?usp=sharing)。

![politician_01_first_see.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/239303/d173aebf-f3a1-c5b9-6e8f-5e1bf4cbe175.png)

追記：今回使った2020年９月６日収集のデータには菅さんと岸田さんが入っていなかったが、９月２１日に収集し直して菅さんと岸田さんを加えたデータはこちらにあります。

https://raw.githubusercontent.com/lightondust/topics_by_jupyter_notebook/master/data/neo4j_graph/politicians_200921.json

# 背景

フォローやフォロワー、ウェブサイトのリンク、ユーザレビュー、取引や接触など、繋がりを持つデータが増え続けています。一方でGoogleのPageRankに代表されるように、これらの繋がりの中にはまだまだ発掘されていない莫大の価値が眠っています。さらに深層学習においても、グラフニューラルネットワークの発展が近年注目を集め、またBERTなどのトランスフォーマー模型もまた本質的には繋がり構造に着目することによって自然言語の理解において飛躍を遂げています。このような状況で、グラフデータを柔軟に扱うことやグラフ構造に着目した解析が今後さらに重要になっていく可能性が高いです。

# 記事について

ここでは具体例を使って、グラフデータベースとグラフアルゴリズムを紹介していきます。

単純にグラフデータの上にグラフアルゴリズムを走らせるだけならば、グラフのためのライブラリで十分です。必ずしもグラフデータベースを使う必要がありません。しかしデータの規模が大きくなり、さらに繋がり方が多様化したことで、一つあるいは少数の視点や手法だけでなく、様々な異なる視点から分析を行うことによって今まで見えなかった世界が広がります。それをするためにはデータを柔軟自在に扱うグラフデータベースを使うと処理や解析の効率が大幅に向上すると考えています。また、意義のある解析ができた次にそれをプロダクトに落とす際もデータベースが必要になってくるので、その時もグラフデータベースを使うのは自然の流れだと思います。

ここでは[Neo4j](https://neo4j.com/)を使います。解析言語はPythonです。

データについては、できるだけグラフデータが身の回りのいたるところにあって、その分析の面白さを体験してもらいたいので、２０２０年９月現在、自民党総裁選とさらにそのあとの選挙が控えている中で、政治家のTwitterアカウントのフォロー関係を使うことにしました。具体的には[Meyou](https://meyou.jp/group/category/politician/)から政治家・議員のアカウントを取得し、そのプロフィールとフォローしているアカウントを取得しました。データは９月６日から７日の間に収集したもので、全体は３５０弱アカウントで、フォローした人数が５０００以上を超えている３０ほどのアカウントについては５０００で足切りしています。データは[こちら](https://github.com/lightondust/topics_by_jupyter_notebook/raw/master/data/neo4j_graph/politicians_200907.json)からダウンロードできます。

# データ読み込み

次のようにデータを読み込みます


```python
import json
import pandas as pd

from dateutil.parser import parse as date_parse
```


```python
data_path = './data/neo4j_graph/politicians_200907.json'
```


```python
with open(data_path, 'r') as f:
    data = json.load(f)
```


```python
# 起点となるユーザのIDがキーで、フォロー対象のユーザIDリストが値、キーは政治アカウントで、対象はその限りではない
following_relationship = data[0]

# 政治アカウントのユーザ情報が入っています
user_information = data[1]

# アカウントが分類されたカテゴリ（政治家・議員のみ）とグループ（「自民党」「民進党」など）
category_information = data[2]
```

# グラフデータ構築

neo4jに関して、おすすめの使い方は以下の２つです。

- ローカルで使うにはこちらの[Neo4j Desktop](https://neo4j.com/download/)が無料で便利な管理ツールが使えます。本格的な開発に向いています。
インストールなど、詳しい情報はこちらの[記事](https://qiita.com/awk256/items/dc528a64ecb380eabb5c)をご参照ください。
- 一時的にやってみるだけならばインストールせずにクラウドから利用できる[Neo4j Sandbox](https://neo4j.com/sandbox/)もあります。Sandboxを作成すると接続情報を取得して外部からプログラムでアクセスすることができます。詳しくは[こちら](https://www.youtube.com/watch?v=rmfgRKPjhl8)ご参照ください。

pythonライブラリに関してはこちらに[ドキュメント](https://neo4j.com/docs/driver-manual/4.0/get-started/)があります。バージョン「4.0.0a4」で動作確認しています。

Neo4jのクエリはCypherという直感的で書きやすいものです（[ドキュメント](https://neo4j.com/docs/cypher-manual/current/)）。

最初から勉強したい場合はこちらの[チュートリアル](https://neo4j.com/graphacademy/online-training/)がわかりやすいです。


```python
from neo4j import GraphDatabase

from tqdm.notebook import tqdm
```


```python
auth_path = './data/neo4j_graph/auth.json'
with open(auth_path, 'r') as f:
    auth = json.load(f)

# ローカルの場合は通常 uri: bolt(or neo4j)://localhost:7687, user: neo4j, pd: 設定したもの
# サンドボックスの場合は作成画面から接続情報が見られます
uri = 'neo4j://localhost:7687'
driver = GraphDatabase.driver(uri=uri, auth=(auth['user'], auth['pd']))
```


```python
# Sandboxの場合はこんな感じ
# uri = 'bolt://54.175.38.249:35275'
# driver = GraphDatabase.driver(uri=uri, auth=('neo4j', 'spray-missile-sizing'))
```

## グラフデータモデル

Neo4jではグラフのノードとエッジ（リレーションシップと呼ばれている）の両方にプロパティをもたせることができます（プロパティグラフという）。そうすることによって様々なデータを柔軟に表現して便利に使うことができます。

データをグラフで表現する（グラフモデリング）方法は様々で、用途に応じて適切なものを採用しますが、ここではまずナイーブにユーザ、カテゴリ、グループノードとその間の関係で表現します。

## ノード作成

ユーザノードは収集した政治家関連のアカウントのみならず、政治家関連アカウントがフォローしているアカウントもノードとして扱います。そうすることで、共通のアカウントをフォローしていることで類似や関連が分かると期待できます。ただそうするとデータ数が膨らみ、データ投入に時間がかかるため、ここではn人以上の政治家にフォローされていることを条件にフィルターをかけます。フィルターする人数を`MIN_FOLLOWED_USER`で指定します。ローカルでは１万程度、Sandboxの場合、数千アカウントまで絞り込むように値を設定するとデータ投入が数分で終わるはずです。

＊実際の開発などの際に大量の初期データを投入したい場合、[Neo4j Import tool](https://neo4j.com/docs/operations-manual/current/tutorial/import-tool/)を使うと速くなります（今回のような数十万程度のデータならすぐに終わります）。こちらについては別記事に説明します。


```python
from collections import Counter
import numpy as np
```


```python
MIN_FOLLOWED_USER = 3
```


```python
def parse_user_feed(user_info):
    user_parse = {}
    for feed in ['id', 
                 'name', 
                 'screen_name', 
                 'location', 
                 'description', 
                 'protected', 
                 'followers_count', 
                 'friends_count', 
                 'listed_count', 
                 'created_at']:
        user_parse[feed] = user_info.get(feed)
        if feed == 'created_at' and user_info.get(feed):
            user_parse[feed] = date_parse(user_parse[feed])
        if 'count' in feed:
            if user_parse[feed]:
                user_parse[feed] = int(user_parse[feed])
    return user_parse
```


```python
user_information_parsed = [parse_user_feed(u) for u in user_information]
```


```python
user_ids = []

for k, v in following_relationship.items():
    user_ids += v
```


```python
user_ids_counter = Counter(user_ids)
user_ids_counter_sort = user_ids_counter.most_common()
```


```python
user_ids_selected = [u[0] for u in user_ids_counter_sort if u[1]>MIN_FOLLOWED_USER]
user_ids_selected +=  [u['id'] for u in user_information_parsed]
user_ids_selected = list(set(user_ids_selected))
# ユーザノード数
print(len(user_ids_selected))

categories = set([c[0] for c in category_information])
groups = set([c[1] for c in category_information])
```

    19945



```python
def create_category_node(tx, category_name):
    tx.run('''
    MERGE (n:Category {name:$category_name})
    ''', category_name=category_name)

def create_group_node(tx, group_name):
    tx.run('''
    MERGE (n:Group {name:$group_name})
    ''', group_name=group_name)

def create_user_node(tx, user_id):
    tx.run('''
    MERGE (u:User {userId: $user_id})
    ''', user_id=user_id)

def set_user_properties(tx, user_property):
    tx.run('''
    MERGE (u:User {userId: $id})
    SET u.name=$name,
    u.screenName=$screen_name,
    u.location=$location,
    u.description=$description,
    u.protected=$protected,
    u.followersCount=$followers_count,
    u.friendsCount=$friends_count,
    u.listedCount=$listed_count,
    u.createdAt=$created_at
    ''', **user_property)
```


```python
# カテゴリノード作成
with driver.session() as session:
    for c in categories:
        session.write_transaction(create_category_node, category_name=c)
```


```python
# グループノード作成 
with driver.session() as session:
    for g in tqdm(groups):
        session.write_transaction(create_group_node, group_name=g)
```


    HBox(children=(IntProgress(value=0, max=17), HTML(value='')))


    



```python
# ユーザノード作成
with driver.session() as session:
    for u in tqdm(user_ids_selected):
        session.write_transaction(create_user_node, user_id=u)
```


    HBox(children=(IntProgress(value=0, max=19945), HTML(value='')))


    



```python
# ユーザ属性登録
with driver.session() as session:
    for u in tqdm(user_information_parsed):
        session.write_transaction(set_user_properties, user_property=u)
```


    HBox(children=(IntProgress(value=0, max=347), HTML(value='')))


    


## リレーションシップ作成

カテゴリとグループの関係


```python
category_group_relationship = set([(c[0], c[1]) for c in category_information])
```


```python
def create_group_category_relationship(tx, relationship):
    tx.run('''
    MATCH (c:Category {name:$category})
    MATCH (g:Group {name:$group})
    MERGE (c)-[:CONTAINED_BY]->(g)
    ''', category=relationship[0], group=relationship[1])
```


```python
with driver.session() as session:
    for rel in tqdm(category_group_relationship):
        session.write_transaction(create_group_category_relationship, relationship=rel)
```


    HBox(children=(IntProgress(value=0, max=17), HTML(value='')))


    


リレーションシップの作成は始点ノードと終点ノードを検索して行うので、必要なフィールドに対してIndexを作っておきます。


```python
with driver.session() as session:
    session.run('CREATE INDEX user_id FOR (u:User) ON (u.userId)')
```


```python
with driver.session() as session:
    session.run('CREATE INDEX user_name FOR (u:User) ON (u.screenName)')
```

政治家とグループのリレーションシップを作ります


```python
group_user_relationship = set([(c[1], c[2]) for c in category_information])
```


```python
def create_politician_group_relationship(tx, relationship):
    tx.run('''
    MATCH (u:User {screenName:$user_name})
    MATCH (g:Group {name:$group})
    MERGE (u)-[:BELONG]->(g)
    ''', group=relationship[0], user_name=relationship[1])
```


```python
with driver.session() as session:
    for rel in tqdm(group_user_relationship):
        session.write_transaction(create_politician_group_relationship, relationship=rel)
```


    HBox(children=(IntProgress(value=0, max=370), HTML(value='')))


    


政治家のフォロー関係を作ります。 


```python
def create_follow_relationship(tx, relationship):
    tx.run('''
    MATCH (u1:User {userId:$follower_id})
    MATCH (u2:User {userId:$follow_id})
    MERGE (u1)-[:FOLLOW]->(u2)
    ''', follower_id=relationship[0], follow_id=relationship[1])
```


```python
user_ids_selected_set = set(user_ids_selected)
with driver.session() as session:
    for k, v in tqdm(following_relationship.items()):
        for u_id in v:
            if u_id in user_ids_selected_set:
                session.write_transaction(create_follow_relationship, (int(k), u_id))
```


    HBox(children=(IntProgress(value=0, max=347), HTML(value='')))


    


# ざっくりデータを見てみる

とりあえずランダムにピックアップして見てみます。

```
MATCH (g:Group)--(u:User) RETURN u LIMIT 25
```

![politician_01_first_see.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/239303/d173aebf-f3a1-c5b9-6e8f-5e1bf4cbe175.png)

いい感じにデータが入っています。次に自由民主党に絞って見てみます。

```
MATCH (g:Group {name:'自由民主党'})--(u:User) RETURN u
```

![politician_01_first_see_jimin.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/239303/8eddd55c-695f-33cf-5feb-5cfa15f03693.png)


Neo4j Browserで実行すると、少し重くなって表示も中々安定しないかもしれません。関係の数が多いためだと思います。では自民党のアカウントの数と党内でのフォロー関係の数を数えてみます


```
MATCH (g:Group {name:'自由民主党'})-- (u:User)-[r:FOLLOW]-(u2)--(g) RETURN COUNT(DISTINCT u), COUNT(r)
```

結果は人数98、関係数2780でした。一人あたり30人程度でほぼ平均党内三分の一の人をフォローしている感じでしょうか。

そして他の党派はどうかというと

```
MATCH (g:Group)--
(u:User)-[r:FOLLOW]-(u2)--(g) RETURN g.name, COUNT(DISTINCT u), COUNT(DISTINCT r)
```

で一覧をみることができます。


```python
with driver.session() as session:
    res = session.run(''' 
    MATCH (g:Group)--
    (u:User)-[r:FOLLOW]-(u2)--(g) 
    RETURN g.name as name, COUNT(DISTINCT u) as account_number , COUNT(DISTINCT r) as relation_number
    ''')
```


```python
res_data = [[r['name'], r['account_number'], r['relation_number']] for r in res]
res_data_df = pd.DataFrame(res_data, columns=['name', 'account_no', 'relation_no'])
res_data_df['ratio'] = res_data_df.relation_no / (res_data_df.account_no * (res_data_df.account_no-1))
```


```python
res_data_df
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>name</th>
      <th>account_no</th>
      <th>relation_no</th>
      <th>ratio</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>0</td>
      <td>自由民主党</td>
      <td>98</td>
      <td>2780</td>
      <td>0.292447</td>
    </tr>
    <tr>
      <td>1</td>
      <td>日本のこころを大切にする党</td>
      <td>4</td>
      <td>6</td>
      <td>0.500000</td>
    </tr>
    <tr>
      <td>2</td>
      <td>日本を元気にする会</td>
      <td>3</td>
      <td>3</td>
      <td>0.500000</td>
    </tr>
    <tr>
      <td>3</td>
      <td>公明党</td>
      <td>29</td>
      <td>635</td>
      <td>0.782020</td>
    </tr>
    <tr>
      <td>4</td>
      <td>都知事選2014</td>
      <td>4</td>
      <td>2</td>
      <td>0.166667</td>
    </tr>
    <tr>
      <td>5</td>
      <td>都知事選2016</td>
      <td>11</td>
      <td>23</td>
      <td>0.209091</td>
    </tr>
    <tr>
      <td>6</td>
      <td>無所属</td>
      <td>18</td>
      <td>74</td>
      <td>0.241830</td>
    </tr>
    <tr>
      <td>7</td>
      <td>民進党</td>
      <td>67</td>
      <td>1383</td>
      <td>0.312754</td>
    </tr>
    <tr>
      <td>8</td>
      <td>日本の政党</td>
      <td>11</td>
      <td>30</td>
      <td>0.272727</td>
    </tr>
    <tr>
      <td>9</td>
      <td>社会民主党</td>
      <td>3</td>
      <td>4</td>
      <td>0.666667</td>
    </tr>
    <tr>
      <td>10</td>
      <td>幸福実現党</td>
      <td>11</td>
      <td>79</td>
      <td>0.718182</td>
    </tr>
    <tr>
      <td>11</td>
      <td>日本共産党</td>
      <td>6</td>
      <td>24</td>
      <td>0.800000</td>
    </tr>
    <tr>
      <td>12</td>
      <td>大阪維新の会</td>
      <td>6</td>
      <td>20</td>
      <td>0.666667</td>
    </tr>
    <tr>
      <td>13</td>
      <td>知事・市長</td>
      <td>25</td>
      <td>151</td>
      <td>0.251667</td>
    </tr>
    <tr>
      <td>14</td>
      <td>立憲民主党</td>
      <td>26</td>
      <td>348</td>
      <td>0.535385</td>
    </tr>
    <tr>
      <td>15</td>
      <td>生活の党と山本太郎となかまたち</td>
      <td>10</td>
      <td>66</td>
      <td>0.733333</td>
    </tr>
    <tr>
      <td>16</td>
      <td>日本維新の会</td>
      <td>20</td>
      <td>168</td>
      <td>0.442105</td>
    </tr>
  </tbody>
</table>
</div>



全員が互いにフォローしあっている時の関係数と実際の関係数の比は「ratio」です。１人が平均党内の何割のアカウントをフォローしているかの目安になります。共産党と公明党は圧倒的に党内仲良しという結果でした。政党が大きくなるにつれて派閥が形成されて、結束が弱まってしまうということでしょうか。いずれにしても政党内では「密」なネットワークが形成されていると言えるだろうかと思います。

最後に自民党内の関係図を見てみます（データ可視化ツールNeo4j Bloomを使っています）。

![politician_01_first_see_jimin_bloom.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/239303/ae223b35-01bc-efc0-5b7c-0e6619c6df1e.png)


次回では重要度の高いノードを見ていきます。
https://qiita.com/s_zh/items/1b193758965a491e79bc