【分析】ロミオとジュリエットで学ぶ量子コンピュータのソーシャルネットワーク分析概要


はじめに

こちらはD-WaveのLeapの翻訳です。

1.png


最適化をつかったネットワーク分析

このデモでは、ソーシャルネットワークでの暴力的な行動の出現を予測するための量子コンピューターの使用方法を示します。 不均衡な社会的ネットワークにより暴力を予測できます。不均衡のレベルを判断することは、D-Wave量子コンピュータでよく行われるテクニックです。 ここに示されたテクニックは広範囲の最適化問題に適用されます。


最適化問題

ネットワークを見ること下記のような三種類の分析ができることがわかります。

1、影響を持つインフルエンサーの発見

Minimum Vertex Coverを使うことで影響を持つインフルエンサーを見つけることができます。

1.png

限られたリソースの中で効率的な役割分担をするためにGraph Coloringが使えます。

2.png

人の関係を2つのグループに分けます。グループ内は仲が良くて、グループ間は敵対しています。

3.png

今回は最後の三番目の例を解いてみます。


ロミオとジュリエットから学ぶソーシャルネットワーク

シェイクスピアのロミオとジュリエットからのヴェローナのモンタギューとカプレットを考えてみましょう。ソーシャルネットワークには、敵対的(赤)と友好的(緑)の関係が含まれています。 公正なヴェローナのネットワークをアディジェ川で隔てられた2つのグループに分けましょう。

4.png

物語の始めに、ロミオとジュリエットがまだ会う前に、ヴェローナのネットワークは川の両側それぞれで友好的、川を挟むとすべての関係が敵対的であるように調整することができます。 したがって、このネットワークはバランスが取れています。

5.png


不均衡を導入する

ロミオモンタギューはジュリエットカプレットと出会う。 これで、ロミオとジュリエットを結ぶ新しい友好的なつながりができました。この1つの接続では、ネットワーク内で構造的なバランスを見つけることが不可能になります。

6.png


不均衡が不安定を呼び込む

ジュリエットのロミオに対する新しい愛は、「私の友人の敵は私の敵である」という社会的ルールに違反するつながりのループ(「フラストレーション・ループ」と呼ばれる)を生み出します。この社会的不確実性は将来の暴力の増加と相関を示します。以前安定していた状況は今や不安定です。そして確実に…ロミオとジュリエットの関係は、最終的に悲劇となります。

7.png

8.png

このネットワークはバランスが取れていません。フラストレーションは、友好関係が川の向こう側にあるとき、または敵対関係が川の片側だけに残るときのいずれかに起こります。 フラストレートした関係の数を最小にする区分を見つけることは、困難で重要な問題ですが、この不均衡の測定はD-Wave量子コンピュータにとって最適の問題です。


量子コンピュータへの実装

ソーシャルネットワークを含む最適化の問題では、量子コンピュータをプログラムするために2つの基本的なコントロールを設定するだけで済みます。 2つの変数がどれくらい一致するかを示す程度(量子ビットの結合強度)と、 変数が特定の結果になる傾向がある度合い(量子ビットのバイアス)があります。 D-Wave量子コンピュータに何らかの問題を構築するのには、この2つの設定で十分です。 ロミオとジュリエットの例のように、ソーシャルネットワークをプログラムするには、すべての量子ビットのバイアスを0に設定し、量子ビットの結合強度を+1(敵対的)または-1(友好的)に設定します。 他の最適化問題でも、これら2つの基本的な値を設定するだけで済みます。

9.png


実世界の問題

実世界でもこのような不均衡をプログラミングすることでどこに暴力が生まれるのかをソーシャルネットワーキングの分析によって把握することができ、実際に米国や中東での勢力分布の不均衡の計算にD-Waveが調査で使われてトライされました。実際に上記のように敵対する同士に+1、仲間同士に-1を割り当てます。

計算結果は、下記のようになり、複雑なネットワークを解くことができます。

10.png