More than 3 years have passed since last update.

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

Last updated at 2020-09-21Posted at 2020-09-13

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

Colabはこちらです。

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

準備

まずはdriverを用意します

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

import pandas as pd

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

# 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')で削除してください。)

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

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]

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

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]

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

グラフ全体の場合

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

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

	count(distinct componentId)
0	1

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

次に政治家だけの場合。

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

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

	count(distinct componentId)
0	1

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

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は実質的にグループ内の有意な繋がり度合い-グループ間の有意な繋がり度合いになります。

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

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

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

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]

実行します

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

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

res_df.head()

	name	screen_name	community_id
0	菅家　一郎	kanke_ichirou	47
1	山谷えり子	yamatanieriko	48
2	akimoto_tsukasa	akimoto_tsukasa	62
3	【公式】みたに英弘自民党衆議院議員／神奈川８区	mitani_h	62
4	あいさわ一郎	ichiroaisawa	62

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つのグループが抽出されました。

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

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

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

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

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])

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

グラフを作ります。

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

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にします。

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

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

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

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

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のコニュニティに分割されました。向き付の時より多少綺麗になった印象ですね。

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])

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

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

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

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

最後に

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

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

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

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up