Python+NetworkX+ソーシャルデータで最短経路を解いてみる

やったことや目的など

私はTalentBaseというタレントマイニングサービスを開発・運営をしており、膨大なソーシャルデータを解析しています。

そんな中で、人間関係を把握する意味でグラフ解析の一環として「この人とこの人はどれくらいの距離感の関係？」ってことを解析することに。

環境構築

Python, NetworkX
がインストールされていれば、すぐに実装できます。

データの準備

データはSNSの有向グラフデータを使い、人と人の最短経路問題として距離を仮想的に図ってみることにしました。

データがMySQLに保存されていた関係で、mysql-connectorを使ってDBに接続して有向グラフデータを取得して、それをNetworkXで計算するというスキームで実装しました。

実装・計算

main.py

    #!/usr/bin/env python
    # -*- coding: utf-8 -*-

    import networkx as nx
    import mysql.connector

    db_config = {
      'user': 'USERNAME',
      'password': 'PASSWORD',
      'host': 'HOST',
      'database': 'DATABASE',
      'port': 'PORT'
    }

    connect = mysql.connector.connect(**db_config)
    cur=connect.cursor(buffered=True)

    g = nx.DiGraph()

    cur.execute("select FROM_USER_ID,TO_USER_ID,WEIGHT from TABLE_NAME")
    rows = cur.fetchall()

    for row in rows:
      if row[0] == row[1] or row[0] is None or row[1] is None:
        continue
      g.add_node(str(row[0]))
      g.add_node(str(row[1]))
      g.add_edge(str(row[0]),str(row[1]), weight=int(row[2]))

    # ダイクストラ法で最短経路を探す
    print nx.dijkstra_path(g, 'NODE1', 'NODE2') # NODE1からNODE2への最短経路を出力
    #出力例 => ['NODE1','NODE9','NODE3','NODE7','NODE5','NODE2']
    print nx.dijkstra_path_length(g, 'NODE1', 'NODE2') # NODE1からNODE2への最短経路の距離を出力(weightが全て1だったらNODEを渡った数が距離になる)
    #出力例 => 8

考察

大容量のグラフデータを扱い始めると、今回行った計算は結構時間がかかってしまうので、
次回はNeo4jなどを代表するGraphDBを使って解析してみたいと思います。