本文へジャンプ

• English
• お問い合わせ

検索語

Show navigation

• 東芝デジタルソリューションズ株式会社
• ソリューション・サービス
• イベント情報
• ニュース
• 企業情報
• 採用情報
• 事例紹介
• サイトマップ
• お問い合わせ
• ▲ Close

資料 > ホワイトペーパー > SBMによるWeighted Signed Networkのグラフ分割分析

ホワイトペーパー：SBMによるWeighted Signed Networkのグラフ分割分析

概要

SBM (Simulated Bifurcation Machine) によるWeighted Signed Networkのグラフ分割分析の概要を示します。

はじめに

SNSにおけるユーザー同士の関係は、 ユーザーをノードとみなし、ユーザー同士の関係をエッジとみなすとネットワークとして表現することができます。

例えばFacebookでは、ユーザー同士の関係の代表的なものとしてフォローやブロックがあります。 フォローはPositiveな関係の代表で、例えば自分のホーム画面にフォローしている相手の投稿が表示されます。 ブロックはNegativeな関係の代表で、例えば相手から自分へメッセージを送れなくなります。

このように関係にPositive / Negativeの二極を持たせたネットワークのことをSigned Networkと呼び、 さらにPositive / Negativeに程度の大小を持たせたネットワークのことをWeighted Signed Networkと呼びます。 Signed NetworkやWeighted Signed Networkを分析することにより、 ユーザー間の関係性を考慮した高精度なグラフ分割[1]や、 ユーザー間の関係性を考慮した高精度なコミュニティの検出[2]や、 ユーザー間の関係性を考慮した高精度なユーザー推薦[3]ができるようになります。

同様にBitcoin-Alpha取引所ネットワークでも、 特定のユーザーが信頼のおける(Trust)か、そうでない(Distrust)かというユーザー間で評価する仕組みがあります。 Bitcoin-Alpha取引所ネットワークにおいては 信頼のおける(Trust)相手を選ぶことで取引が成立しやすくなる、 そうでない(Distrust)相手を避けることで詐欺や不正送金などに巻き込まれにくくなる といった影響があります。

このペーパーでは、Weighted Signed NetworkからSBMによりグラフ分割分析を行う一連の手順を説明します。 まず、Bitcoin-Alpha取引所ネットワークのデータセット[4]を利用し、 TrustをPositive評価、DistrustをNegative評価としたWeighted Signed Networkを構築します。 次に、ユーザー間の関係性を考慮した高精度なグラフ分割ができるよう、 SBMへの入力となるQUBO行列を構築します[5]。 最後に、SBMを用いてQUBO行列を最小化する解ベクトルを求め、結果を評価します。

参考文献

• [1] Doreian, P., & Mrvar, A. (2009). Partitioning signed social networks. Social Networks, 31(1), 1-11.
  • http://snap.stanford.edu/class/cs224w-readings/doreian09partition.pdf
• [2] Esmailian, P., & Jalili, M. (2015). Community detection in signed networks: the role of negative ties in different scales. Scientific reports, 5(1), 1-17.
  • https://www.nature.com/articles/srep14339
• [3] Tang, J., Aggarwal, C., & Liu, H. (2016, April). Recommendations in signed social networks. In Proceedings of the 25th International Conference on World Wide Web (pp. 31-40).
  • https://dl.acm.org/doi/pdf/10.1145/2872427.2882971
• [4] Kumar, S., Spezzano, F., Subrahmanian, V. S., & Faloutsos, C. (2016, December). Edge weight prediction in weighted signed networks. In 2016 IEEE 16th International Conference on Data Mining (ICDM) (pp. 221-230). IEEE.
  • https://snap.stanford.edu/data/soc-sign-bitcoin-alpha.html
  • https://cs.stanford.edu/~srijan/pubs/wsn-icdm16.pdf
• [5] Lucas, A. (2014). Ising formulations of many NP problems. Frontiers in physics, 5.
  • https://www.frontiersin.org/articles/10.3389/fphy.2014.00005/full

import os
import csv
import gzip
import numpy as np

import requests
import io

Weighted Signed Networkの構築

スタンフォード大学Stanford Network Analysis Projectのサイトから Bitcoin-Alpha取引所ネットワークのデータセットのファイルを入手します。 このファイルはGZ形式で圧縮されたCSVファイルであり、 以下の4列で構成されています。

1. SOURCE: 評価を実施したユーザーのID
2. TARGET: 評価を受けたユーザーのID
3. RATING: 評価の数値（最低評価-10から最高評価+10まで1刻み）
4. TIME: 評価を実施した時刻（UNIX時間）

Raw = []

url = "https://snap.stanford.edu/data/soc-sign-bitcoinalpha.csv.gz"
filename = "soc-sign-bitcoinalpha.csv.gz"

if not os.path.exists(filename):
    with open(filename, mode='wb') as fout:  # wb でバイト型を書き込める
        fout.write(requests.get(url).content)

with gzip.open(filename, "rt") as fin:
    for row in csv.reader(fin, delimiter=","):
        Raw.append(tuple(int(x) for x in row))

Weighted Signed Networkを隣接行列方式で構築します。 隣接行列$Edge$の各要素を以下のように設定します。 グラフ分割においては分割の向きを考慮していないため、対称行列になるよう設定しています。

$$ Edge_{i,j \neq i} = \mathrm{ユーザーiからユーザーjへの評価} + \mathrm{ユーザーjからユーザーiへの評価} $$$$ Edge_{i,i} = 0 $$

id_list = sorted(
    set(src for (src, _, _, _) in Raw) | set(dst for (_, dst, _, _) in Raw))
rev_id = {id: i for (i, id) in enumerate(id_list)}

N = len(id_list)

Edge = np.zeros((N, N), dtype=int)
for (src, dst, rate, _) in Raw:
    i, j = rev_id[src], rev_id[dst]
    Edge[i, j] += rate
    Edge[j, i] += rate

print("固有なユーザーIDの数", N)
print("評価の行われた数", len(Raw))
print("Positive評価の行われた数", len([rate for (_, _, rate, _) in Raw if rate > 0]))
print("Negative評価の行われた数", len([rate for (_, _, rate, _) in Raw if rate < 0]))

固有なユーザーIDの数 3783
評価の行われた数 24186
Positive評価の行われた数 22650
Negative評価の行われた数 1536

SBMへの入力となるQUBO行列の構築

SBMへの入力となるQUBO行列を構築します。 Positiveなエッジをなるべく切断せず、 Negativeなエッジをなるべく切断するようモデル化します。

エッジの重みがすべてプラスの場合は最小カット問題に帰着します。 最小カット問題は多項式時間アルゴリズムがすでに存在しており、 特段にSBMを使う理由はありません。

エッジの重みがすべてマイナスの場合は最大カット問題に帰着します。 最大カット問題は多項式時間アルゴリズムが存在しておらず、 通常の逐次計算よりもSBMを使った方が高速に解ける可能性があります。

エッジの重みにプラスとマイナスが混ざっているWeighted Signed Networkの場合は 最小カット問題と最大カット問題を混ぜたような問題になります。 最大カット問題と同様に多項式時間アルゴリズムが存在しておらず、 通常の逐次計算よりもSBMを使った方が高速に解ける可能性があります。

具体的には解ベクトルを以下のようになるようモデル化します。

• ユーザー$i$がグループ0に属するとき $$ X_{i} = 0 $$
• ユーザー$i$がグループ1に属するとき $$ X_{i} = 1 $$

QUBO行列の各要素を以下のように設定します。

• 対角項 $$ Qubo_{i,i} = \sum_{j \neq i} Edge_{i,j} $$
• 非対角項 $$ Qubo_{i,j \neq i} = - Edge_{i,j} $$

QUBO行列の解釈はユーザーが二人しかいない場合で説明します。

• ユーザー0とユーザー1が同じグループに属するとき $$ \mathrm{評価値} = 0 $$
• ユーザー0とユーザー1が違うグループに属するとき $$ \mathrm{評価値} = \mathrm{ユーザー0からユーザー1への評価} + \mathrm{ユーザー1からユーザー0への評価} $$

となるよう設定しています。

解ベクトルの算出と評価

先ほど設定したQUBO行列を用いてSBMエンジンを呼び出し、QUBO行列を最小化する解ベクトルを求めます。 SBMへの入力はMatrix Market方式を利用します。詳細はSBMのマニュアルを参照ください。

# DIGITを大きくすると、ファイルサイズが大きくなる代わりに、丸め誤差が小さくなる
DIGIT = 8


def triangular(M):
    if isinstance(M, np.ndarray):
        return np.tril(M) + np.triu(M, k=+1).T
    else:
        return M


def writeMM(M):
    MM = triangular(M)
    N = MM.shape[0]
    with io.StringIO() as f:
        f.write('%%MatrixMarket matrix coordinate real symmetric\n')
        f.write(f'{N} {N} {np.sum(MM!=0)}\n')
        for i in range(N):
            for j in range(N):
                if MM[i, j] != 0:
                    f.write(f'{i+1} {j+1} {round(MM[i,j], DIGIT)}\n')
        return f.getvalue()

解ベクトルを求め、評価します。 ユーザー間の評価データのある組合せに限って平均をとった場合、 グループ0同士の評価の平均、および、グループ1同士の評価の平均は0より大きくなっているのに対して、 グループをまたいだ評価の平均は0より小さくなっており、適切にグラフ分割できたことが分かります。

%%time

Qubo = -Edge.copy()
for i in range(N):
    Qubo[i, i] += np.sum(Edge[i, :])

headers = {'content-type': 'application/octet-stream'}

params = {
    "loops": 0,
    "timeout": 10,
}

response = requests.post(f"http://aa.bb.cc.dd:8000/solver/autoising",
                         data=writeMM(Qubo),
                         headers=headers,
                         params=params)

X = np.array(response.json()["result"], dtype=bool)
notX = (1 - X).astype(bool)

print("エネルギー", Qubo @ X @ X)
print("グループ内部の評価の平均",
      (np.sum(Edge[notX, :][:, notX]) + np.sum(Edge[X, :][:, X])) /
      (np.sum(Edge[notX, :][:, notX] != 0) + np.sum(Edge[X, :][:, X] != 0)))
print("グループをまたいだ評価の平均",
      np.sum(Edge[X, :][:, notX]) / np.sum(Edge[X, :][:, notX] != 0))

エネルギー -5445
グループ内部の評価の平均 3.1821155943293347
グループをまたいだ評価の平均 -4.380530973451328
CPU times: total: 3.78 s
Wall time: 14.4 s

数値実験

同じ問題を線形計画法ソルバーでも解き、SBMで解いた場合と処理時間を比較します。 ただし、データセット全体を線形計画法ソルバーで解くのは難しかったので、問題サイズを制限して解きました。 結果は以下のようになり、SBMの方が高速となりました。

• 問題の規模
  • 固有なユーザーIDの数 2403
  • 評価が行われた数 5000

処理時間の評価

	SBM v1.6	Python MIP 1.13.0 / CBC
最適解までの処理時間	0.5 分	12 分

実行環境

	SBM v1.6 (client)	SBM v1.6 (server)	Python MIP 1.13.0 / CBC
CPU	Core-i7 8700 (3.20 GHz, 6 Core)	AWS EC2 p3.2xlarge (vCPU 8)	Core-i7 8700 (3.20 GHz, 6 Core)
GPU	on board	AWS EC2 p3.2xlarge (vCPU 8)	on board
RAM	16 GB	61 GB + 16 GB	16 GB

Temp = [Raw[int(n*len(Raw)/5000)] for n in range(5000)]

id_list = sorted(
    set(src for (src, _, _, _) in Temp) | set(dst for (_, dst, _, _) in Temp))
rev_id = {id: i for (i, id) in enumerate(id_list)}

N = len(id_list)

Edge = np.zeros((N, N), dtype=int)
for (src, dst, rate, _) in Temp:
    i, j = rev_id[src], rev_id[dst]
    Edge[i, j] += rate
    Edge[j, i] += rate

print("固有なユーザーIDの数", N)
print("評価の行われた数", len(Temp))
print("Positive評価の行われた数", len([rate for (_, _, rate, _) in Temp if rate > 0]))
print("Negative評価の行われた数", len([rate for (_, _, rate, _) in Temp if rate < 0]))

固有なユーザーIDの数 2403
評価の行われた数 5000
Positive評価の行われた数 4677
Negative評価の行われた数 323

%%time

Qubo = -Edge.copy()
for i in range(N):
    Qubo[i, i] += np.sum(Edge[i, :])

headers = {'content-type': 'application/octet-stream'}

params = {
    "loops": 0,
    "timeout": 30,
}

response = requests.post(f"http://aa.bb.cc.dd:8000/solver/autoising",
                         data=writeMM(Qubo),
                         headers=headers,
                         params=params)

X = np.array(response.json()["result"], dtype=bool)
notX = (1 - X).astype(bool)

print("エネルギー", Qubo @ X @ X)
print("グループ内部の評価の平均",
      (np.sum(Edge[notX, :][:, notX]) + np.sum(Edge[X, :][:, X])) /
      (np.sum(Edge[notX, :][:, notX] != 0) + np.sum(Edge[X, :][:, X] != 0)))
print("グループをまたいだ評価の平均",
      np.sum(Edge[X, :][:, notX]) / np.sum(Edge[X, :][:, notX] != 0))

エネルギー -1449
グループ内部の評価の平均 2.068932955618508
グループをまたいだ評価の平均 -4.151862464183381
CPU times: total: 1.5 s
Wall time: 32.1 s

%%time

import mip

temp = [(i, j, Qubo[i, j] * 2) for (i, j) in zip(*np.where(Qubo)) if i < j]
M = len(temp)

model = mip.Model()

x = model.add_var_tensor((N, ), 'x', var_type=mip.BINARY)
y = model.add_var_tensor((M, ), 'y', var_type=mip.BINARY)

model.objective = mip.minimize(
    mip.xsum(x * np.diag(Qubo)) + mip.xsum(y[m] * v
                                           for (m,
                                                (i, j, v)) in enumerate(temp)))

for (m, (i, j, v)) in enumerate(temp):
    if v > 0:
        model += (x[i] + x[j] <= y[m] + 1)
    elif v < 0:
        model += (2 * y[m] <= x[i] + x[j])

if model.optimize() == mip.OptimizationStatus.OPTIMAL:
    X = np.array([x[n].x for n in range(N)], dtype=bool)
    notX = (1 - X).astype(bool)

    print("エネルギー", Qubo @ X @ X)
    print(
        "グループ内部の評価の平均",
        (np.sum(Edge[notX, :][:, notX]) + np.sum(Edge[X, :][:, X])) /
        (np.sum(Edge[notX, :][:, notX] != 0) + np.sum(Edge[X, :][:, X] != 0)))
    print("グループをまたいだ評価の平均",
          np.sum(Edge[X, :][:, notX]) / np.sum(Edge[X, :][:, notX] != 0))

エネルギー -1449
グループ内部の評価の平均 2.074810606060606
グループをまたいだ評価の平均 -4.013850415512465
CPU times: total: 11min 57s
Wall time: 11min 58s

このページのトップへ

• 東芝デジタルソリューションズのトップページへ
• 個人情報保護方針
• サイトのご利用条件