このように関係に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 (PDF形式)(1.13MB)
[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 (PDF形式)(800KB)
[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

Weighted Signed Networkの構築

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

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

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

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

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

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

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

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

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

ユーザーiiがグループ0に属するときXi=0Xi=0
ユーザーiiがグループ1に属するときXi=1Xi=1

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

対角項Quboi,i=∑j≠iEdgei,jQuboi,i=∑j≠iEdgei,j
非対角項Quboi,j≠i=−Edgei,jQuboi,j≠i=−Edgei,j

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

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

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

解ベクトルの算出と評価

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

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

数値実験

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

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