実例で動かすグラフアルゴリズムとグラフデータベース(Neo4j)、03_グループを見つける

第一回：
https://qiita.com/s_zh/items/3b183e258bcd6506e8cb
第二回：
https://qiita.com/s_zh/items/1b193758965a491e79bc
第三回：
本記事
第四回：
https://qiita.com/s_zh/items/e26625854925acd51190

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

今回は関係の深いユーザグループを見つけてみます

![politician_03_1_louvain_community.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/239303/d6933e5a-e297-3b82-a2d3-4e2ee08a8cca.png)
![politician_03_2_louvain_community.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/239303/2a37cc51-f94a-6da7-0f34-2bcde71e682c.png)


# 準備

まずはdriverを用意します


```python
from neo4j import GraphDatabase
from tqdm.notebook import tqdm
import json

import pandas as pd
```


```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'))
```

# 連結成分

グラフが与えられた時に、互いに関係のないネットワークに分かれている場合があります。その場合はそれぞれのネットワークに対してアルゴリズムを適応することが多いです。そのためのアルゴリズムとしてWeakly Connected Componentsが用意されています。「Weak」と言っているのはこの場合向きを考慮しないからです。

グラフを作ります。政治家とそのフォローしているアカウントのネットワークと政治家だけのアカウントをそれぞれ見てみます。(以前の作業で同じ名前のグラフを作成してある場合エラーになる可能性があります。その時は`call gds.graph.drop('graph-name')`で削除してください。)


```python
with driver.session() as session:
    res = session.run('''
    CALL gds.graph.create('follow-net-all', 'User', 'FOLLOW')
    ''')
```


```python
res = list(res)
[print(r) for r in res]
```

    <Record nodeProjection={'User': {'properties': {}, 'label': 'User'}} relationshipProjection={'FOLLOW': {'orientation': 'NATURAL', 'aggregation': 'DEFAULT', 'type': 'FOLLOW', 'properties': {}}} graphName='follow-net-all' nodeCount=19945 relationshipCount=166491 createMillis=118>





    [None]




```python
with driver.session() as session:
    res = session.run('''
    CALL gds.graph.create.cypher( 
    'follow-net-politicians', 
    'MATCH (g:Group)--(u:User) WITH DISTINCT u as u RETURN id(u) AS id', 
    'MATCH (:Group)--(u:User)-[r:FOLLOW]->(u2:User)--(:Group) WITH DISTINCT r, u, u2 RETURN id(u) AS source, id(u2) AS target')
    ''')
```


```python
res = list(res)
[print(r) for r in res]
```

    <Record nodeQuery='MATCH (g:Group)--(u:User) WITH DISTINCT u as u RETURN id(u) AS id' relationshipQuery='MATCH (:Group)--(u:User)-[r:FOLLOW]->(u2:User)--(:Group) WITH DISTINCT r, u, u2 RETURN id(u) AS source, id(u2) AS target' graphName='follow-net-politicians' nodeCount=346 relationshipCount=13756 createMillis=303>





    [None]



連結しているグラフの数をみてみます。

グラフ全体の場合


```python
with driver.session() as session:
    res = session.run('''
    CALL gds.wcc.stream('follow-net-all')
    YIELD nodeId, componentId
    RETURN count(distinct componentId)
    ''')
```


```python
res = list(res)
pd.DataFrame([r.data() for r in res])
```




<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>count(distinct componentId)</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>0</td>
      <td>1</td>
    </tr>
  </tbody>
</table>
</div>



全部つながっていますね。

次に政治家だけの場合。


```python
with driver.session() as session:
    res = session.run('''
    CALL gds.wcc.stream('follow-net-politicians')
    YIELD nodeId, componentId
    RETURN count(distinct componentId)
    ''')
```


```python
res = list(res)
pd.DataFrame([r.data() for r in res])
```




<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>count(distinct componentId)</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>0</td>
      <td>1</td>
    </tr>
  </tbody>
</table>
</div>



こちらも全部つながっています。

# Louvainアルゴリズム 

Louvainアルゴリズムはイメージとしてグループ内のリンクをできるだけおおくして、グループ間のリンクをできるだけ少なくするようにネットーワークをグループに分割するものです。最適化する指標はModularityと呼ばれるもので、次のような形になっています。

$$
Q = \frac{1}{2m} \sum_{ij} \left( A_{ij} - \frac{k_i k_j}{2m}  \right) \delta(c_i, c_j)
$$

ここでノードiとノードjが同じグループに属すときにだけ$\delta(c_i, c_j)$が１で、それ以外のときに0となります。
$k_i k_j / (2m)$はノードの次数分布を保つ前提でランダムネットーワークを考えるときにノードiとノードjがつながる確率の近似値で、カッコ内の$A_{ij} - k_i k_j / (2m)$はノードiとノードjのリンク度合-繋がりそうな度合=有意なつながり度合いと理解できます。また$\delta(c_i, c_j) \rightarrow \delta(c_i, c_j) - 1/2$とずらしてもQがグループ分布によらない定数分しか異ならないことを考えると、Qは実質的にグループ内の有意な繋がり度合い-グループ間の有意な繋がり度合いになります。

ここでは政治家内で分割してみます。まずグラフを作ります。

次にアルゴリズムを呼び出します。まずはリソースを見てみます


```python
with driver.session() as session:
    res = session.run('''
    CALL gds.louvain.stream.estimate('follow-net-politicians')
    ''')
```


```python
res = list(res)
[print(r.data()) for r in res]
```

    {'requiredMemory': '[26 KiB ... 640 KiB]', 'treeView': 'Memory Estimation: [26 KiB ... 640 KiB]\n|-- algorithm: [26 KiB ... 640 KiB]\n    |-- this.instance: 56 Bytes\n    |-- modularityOptimization(): [23 KiB ... 49 KiB]\n        |-- this.instance: 128 Bytes\n        |-- currentCommunities: 2808 Bytes\n        |-- nextCommunities: 2808 Bytes\n        |-- cumulativeNodeWeights: 2808 Bytes\n        |-- nodeCommunityInfluences: 2808 Bytes\n        |-- communityWeights: 2808 Bytes\n        |-- colorsUsed: 88 Bytes\n        |-- colors: 2808 Bytes\n        |-- reversedSeedCommunityMapping: [0 Bytes ... 2808 Bytes]\n        |-- communityWeightUpdates: 2808 Bytes\n        |-- ModularityOptimizationTask: [4384 Bytes ... 27 KiB]\n            |-- communityInfluences: [1096 Bytes ... 7016 Bytes]\n    |-- subGraph: [1 Bytes ... 563 KiB]\n    |-- dendrograms: [2808 Bytes ... 27 KiB]\n', 'mapView': {'name': 'Memory Estimation', 'components': [{'name': 'algorithm', 'components': [{'name': 'this.instance', 'memoryUsage': '56 Bytes'}, {'name': 'modularityOptimization()', 'components': [{'name': 'this.instance', 'memoryUsage': '128 Bytes'}, {'name': 'currentCommunities', 'memoryUsage': '2808 Bytes'}, {'name': 'nextCommunities', 'memoryUsage': '2808 Bytes'}, {'name': 'cumulativeNodeWeights', 'memoryUsage': '2808 Bytes'}, {'name': 'nodeCommunityInfluences', 'memoryUsage': '2808 Bytes'}, {'name': 'communityWeights', 'memoryUsage': '2808 Bytes'}, {'name': 'colorsUsed', 'memoryUsage': '88 Bytes'}, {'name': 'colors', 'memoryUsage': '2808 Bytes'}, {'name': 'reversedSeedCommunityMapping', 'memoryUsage': '[0 Bytes ... 2808 Bytes]'}, {'name': 'communityWeightUpdates', 'memoryUsage': '2808 Bytes'}, {'name': 'ModularityOptimizationTask', 'components': [{'name': 'communityInfluences', 'memoryUsage': '[1096 Bytes ... 7016 Bytes]'}], 'memoryUsage': '[4384 Bytes ... 27 KiB]'}], 'memoryUsage': '[23 KiB ... 49 KiB]'}, {'name': 'subGraph', 'memoryUsage': '[1 Bytes ... 563 KiB]'}, {'name': 'dendrograms', 'memoryUsage': '[2808 Bytes ... 27 KiB]'}], 'memoryUsage': '[26 KiB ... 640 KiB]'}], 'memoryUsage': '[26 KiB ... 640 KiB]'}, 'bytesMin': 27121, 'bytesMax': 655488, 'nodeCount': 346, 'relationshipCount': 13756, 'heapPercentageMin': 0.1, 'heapPercentageMax': 0.1}





    [None]



実行します


```python
with driver.session() as session:
    res = session.run('''
    CALL gds.louvain.stream('follow-net-politicians')
    YIELD nodeId, communityId
    WITH gds.util.asNode(nodeId) as u, communityId
    RETURN u.name AS name, u.screenName as screen_name, communityId as community_id
    ORDER BY community_id, name ASC
    ''')
```


```python
res_df = pd.DataFrame([r.data() for r in res])
```


```python
res_df.head()
```




<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>screen_name</th>
      <th>community_id</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>0</td>
      <td>菅家　一郎</td>
      <td>kanke_ichirou</td>
      <td>47</td>
    </tr>
    <tr>
      <td>1</td>
      <td>山谷えり子</td>
      <td>yamatanieriko</td>
      <td>48</td>
    </tr>
    <tr>
      <td>2</td>
      <td>akimoto_tsukasa</td>
      <td>akimoto_tsukasa</td>
      <td>62</td>
    </tr>
    <tr>
      <td>3</td>
      <td>【公式】みたに英弘 自民党 衆議院議員／神奈川８区</td>
      <td>mitani_h</td>
      <td>62</td>
    </tr>
    <tr>
      <td>4</td>
      <td>あいさわ一郎</td>
      <td>ichiroaisawa</td>
      <td>62</td>
    </tr>
  </tbody>
</table>
</div>




```python
community_count_df = res_df.community_id.value_counts()
print(community_count_df.shape)
community_count_df.head(10)
```

    (31,)





    62     120
    229    109
    269     35
    120     27
    104     15
    144      9
    134      4
    140      3
    163      2
    345      1
    Name: community_id, dtype: int64



全部で31のグループ、大きく2つのグループが抽出されました。

どのようなグループ分けになっているかについて具体的に調べたいので、ここでは結果をノードのプロパティとして保存しておきます。


```python
with driver.session() as session:
    res = session.run('''
    CALL gds.louvain.write('follow-net-politicians', {writeProperty: 'louvainCommunity'})
    ''')
```

neo4j bloomを使って最も数が多いコニュニティとその他のコニュニティを色分けてみると次のようになります。

![politician_03_1_louvain_community.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/239303/d6933e5a-e297-3b82-a2d3-4e2ee08a8cca.png)
![politician_03_2_louvain_community.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/239303/2a37cc51-f94a-6da7-0f34-2bcde71e682c.png)

おおむね、自民党系、民進党・民主党系、維新系に別れた印象がありますね。具体的に各コニュニティにどのようなグループが紐付いているいるかについて見てみます。


```python
community_group_count = []
with driver.session() as session:
    for communit_id in community_count_df.iloc[:3].index:
        res = session.run('''
        MATCH (u:User)-[r]-(g:Group)
        WHERE u.louvainCommunity = $communit_id
        RETURN DISTINCT g.name as name, COUNT(DISTINCT r) as count
        order by count desc
        ''', communit_id=communit_id)
        df = pd.DataFrame([r.data() for r in res])
        community_group_count.append([communit_id, df])
```


```python
for data in community_group_count:
    print(data[1].head(10))
```

                name  count
    0          自由民主党     92
    1          知事・市長     10
    2            無所属      6
    3  日本のこころを大切にする党      4
    4          日本の政党      3
    5            公明党      2
    6       都知事選2016      2
    7            民進党      2
    8          幸福実現党      2
                  name  count
    0              民進党     49
    1            立憲民主党     26
    2  生活の党と山本太郎となかまたち      9
    3              無所属      8
    4            日本共産党      5
    5            日本の政党      4
    6         都知事選2014      3
    7            社会民主党      3
    8         都知事選2016      2
    9            知事・市長      2
           name  count
    0    日本維新の会     16
    1     知事・市長     12
    2    大阪維新の会      6
    3       民進党      4
    4  都知事選2016      2
    5       無所属      2
    6     日本の政党      2
    7     自由民主党      1
    8       公明党      1


## 向きなしグラフ

louvainアルゴリズムは向きなしグラフとして計算したほうがうまく行くと言われていますので、実際に試してみます。

グラフを作ります。


```python
with driver.session() as session:
    res = session.run('''
    CALL gds.graph.create.cypher( 
    'follow-net-politicians-undirected', 
    'MATCH (g:Group)--(u:User) WITH DISTINCT u as u RETURN id(u) AS id', 
    'MATCH (:Group)--(u:User)-[r:FOLLOW]-(u2:User)--(:Group) WITH DISTINCT r, u, u2 RETURN id(u) AS source, id(u2) AS target')
    ''')
```


```python
res = list(res)
[print(r) for r in res]
```

    <Record nodeQuery='MATCH (g:Group)--(u:User) WITH DISTINCT u as u RETURN id(u) AS id' relationshipQuery='MATCH (:Group)--(u:User)-[r:FOLLOW]-(u2:User)--(:Group) WITH DISTINCT r, u, u2 RETURN id(u) AS source, id(u2) AS target' graphName='follow-net-politicians-undirected' nodeCount=346 relationshipCount=27512 createMillis=152>





    [None]



louvainアルゴリズムを使います。書き込む属性名を`louvainCommunityUndirected`にします。


```python
with driver.session() as session:
    res = session.run('''
    CALL gds.louvain.write('follow-net-politicians-undirected', {writeProperty: 'louvainCommunityUndirected'})
    ''')
```

コニュニティの状況を見てみます。


```python
with driver.session() as session:
    res = session.run('''
    MATCH (u:User)--(:Group)
    RETURN u.louvainCommunityUndirected AS community_id
    ''')
```


```python
res_df = pd.DataFrame([r.data() for r in res])
```


```python
community_count_df = res_df.community_id.value_counts()
print(community_count_df.shape)
community_count_df.head(10)
```

    (5,)





    143    136
    3      109
    267     66
    120     30
    257     23
    Name: community_id, dtype: int64



5のコニュニティに分割されました。向き付の時より多少綺麗になった印象ですね。


```python
community_group_count = []
with driver.session() as session:
    for communit_id in community_count_df.iloc[:3].index:
        res = session.run('''
        MATCH (u:User)-[r]-(g:Group)
        WHERE u.louvainCommunityUndirected = $communit_id
        RETURN DISTINCT g.name as name, COUNT(DISTINCT r) as count
        order by count desc
        ''', communit_id=communit_id)
        df = pd.DataFrame([r.data() for r in res])
        community_group_count.append([communit_id, df])
```


```python
for data in community_group_count:
    print(data[1].head(10))
```

                  name  count
    0              民進党     64
    1            立憲民主党     26
    2              無所属     12
    3  生活の党と山本太郎となかまたち     10
    4            日本の政党      6
    5            日本共産党      6
    6            社会民主党      3
    7            知事・市長      3
    8         都知事選2014      2
    9           日本維新の会      2
                name  count
    0          自由民主党     94
    1  日本のこころを大切にする党      4
    2            無所属      3
    3          日本の政党      3
    4          知事・市長      3
    5       都知事選2016      2
            name  count
    0      知事・市長     20
    1     日本維新の会     18
    2        無所属      6
    3     大阪維新の会      6
    4        民進党      4
    5      自由民主党      3
    6  日本を元気にする会      3
    7   都知事選2014      2
    8      日本の政党      2
    9        公明党      1


より政党ごとに別れた感じがします。

具体的には民進党の例で見てみます。民進党内のコニュニティ分布（向き付）です。自民よりと維新よりが散見されるほか、その他のコニュニティに分類されるものも多かったです。

![politician_03_3_louvain_community_minsin.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/239303/51cb6bb5-6ec2-30d1-730c-c7dd769ed636.png)

向きなしの場合は民主党か維新寄りアカウントだけになりました。

![politician_03_3_louvain_community_minsin_undirected.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/239303/968fa02a-ed04-0429-515d-59549c2fcd15.png)


# 最後に

Louvain以外にLabel Propagationというやりかたもあります。一般的にLabel PropagationはパフォーマンスがLouvainより上で、結果の質がLouvainほどではありません。

どちらの場合でも初期はすべてのノードに異なるIDをアサインして、それらを併合していくことでクラスターを構成します。この処理値を変更することである程度クラスターのコントロールができます。たとえばクラスタリンクの結果が安定しなかったり、思うように行かない場合、予め同じラベルになってほしいものを初期値として指定することで結果の質を高めることができるかもしれません。

ココからさらにコニュニティに限定してもう一度分割したり、コニュニティ内に限定してPageRankを計算すると新しい側面を発見できるかもしれません。