符号付きグラフ

三角形の辺に符号を割り当てる方法は8通りあります。フリッツ・ハイダーの理論によれば、負の符号が奇数個になると三角形は不均衡になります。

数学のグラフ理論の分野において、符号付きグラフとは、各辺に正または負の符号があるグラフのことです。

符号付きグラフは、各サイクルの周囲の辺の符号の積が正であればバランスが取れている。「符号付きグラフ」という名称とバランスの概念は、1953年のフランク・ハラリーの数学的論文で初めて登場した。 ^[1]デネス・ケーニヒは1936年に既に別の用語を用いて同等の概念を研究していたが、符号群の関連性を認識していなかった。^[2]ミシガン大学グループダイナミクス センターにおいて、ドーウィン・カートライトとハラリーは、フリッツ・ハイダーの感情の三角形におけるバランスの心理学理論を、符号付きグラフにおけるバランスの心理学理論へと一般化した。^{[3] [4]}

符号付きグラフは、無関係な多くの分野で自然に現れるため、何度も再発見されてきました。^[5] 例えば、符号付きグラフは、古典的なルートシステムの部分集合の幾何学を記述および分析することを可能にします。位相グラフ理論や群論にも現れます。グラフの奇数サイクルと偶数サイクルに関する質問の自然な文脈となります。非強磁性イジングモデルの基底状態エネルギーの計算にも現れます。この計算では、Σ内の最大のバランスの取れたエッジセットを見つける必要があります。相関クラスタリングにおけるデータ分類にも応用されています。

基本定理

パスの符号は、その辺の符号の積です。したがって、パスが正となるのは、負の辺が偶数個ある場合のみです（0 は偶数です）。Frank Hararyの数学的なバランス理論では、すべてのサイクルが正である場合に、符号付きグラフはバランスが取れています。Harary は、(1) すべてのノードのペアについて、それらの間のすべてのパスが同じ符号を持つ、または (2) 頂点が 2 つの部分集合（空の場合もある）に分割され、各部分集合には正の辺のみが含まれるが、負の辺で接続されている、というときに、符号付きグラフはバランスが取れていることを証明しています。^{[1]これは、すべてのサイクルの長さが偶数である場合に限り、通常の（符号なし）グラフが}二部グラフであるという定理を一般化したものです。

簡単な証明はスイッチング法を用いる。 符号付きグラフのスイッチングとは、頂点部分集合とその補集合間のすべての辺の符号を反転させることを意味する。ハラリーの定理を証明するには、Σがバランスしている場合に限り、Σをすべて正にスイッチングできることを帰納的に証明する。

より弱い定理だが証明はより簡単なもので、符号付き完全グラフの3閉路がすべて正であれば、グラフはバランスが取れているというものである。証明として、任意のノードnを選び、それとnに正のエッジで結ばれたすべてのノードを一方のグループ（A）に、負のエッジで結ばれたすべてのノードをもう一方のグループ（ B）に配置する。これは完全グラフなので、Aのすべての2つのノードは友達でなければならず、 Bのすべての2つのノードも友達でなければならない。そうでなければ、バランスの取れていない3閉路が存在することになる。（これは完全グラフなので、負のエッジが1つあれば、バランスの取れていない3閉路が発生する。）同様に、すべての負のエッジは2つのグループ間を通らなければならない。^[6]

フラストレーション

フラストレーション指数

Σのフラストレーション指数（以前は平衡線指数[7]と呼ばれていた）は、Σが平衡状態になるような辺の最小の数である。この同値性^{の理由は、フラストレーション指数が、} Σが平衡状態になるような辺の最小の数と等しいためである。

フラストレーション指数を表す2つ目の方法は、すべての負の閉路を覆う辺の最小数であるということです。この量は負の閉路被覆数と呼ばれています。

同等の定義がもう 1 つあります (切り替えることで簡単に証明できます)。各頂点に +1 または -1 の値を割り当てます。これをΣ の状態と呼びます。エッジが満たされているとは、エッジが正で両方のエンドポイントが同じ値を持つか、負でエンドポイントが反対の値を持つ場合です。満たされていないエッジは、フラストレーションと呼ばれます。すべての状態におけるフラストレーション エッジの最小数は、フラストレーション インデックスです。この定義は、Abelson と Rosenberg によって、(現在は使用されていない)複雑性という別の表記法で初めて導入されました。^[8] このようなセットの補集合は、最も多くのエッジを持つ Σ のバランスの取れたサブグラフです。

フラストレーション指数を見つけることはNP 困難な問題です。

全負符号グラフのフラストレーション指数が、NP困難であるグラフ理論の 最大カット問題と同じであることを観察すると、NP 困難の複雑性がわかります。

フラストレーション指数は、スピングラスのモデルである混合イジングモデルにおいて重要です。このモデルでは、符号付きグラフは固定されています。状態は、各頂点に「上向き」または「下向き」の「スピン」を与えることで構成されます。上向きスピンを+1、下向きスピンを-1とします。したがって、各状態には複数のフラストレーションエッジがあります。フラストレーションエッジの数が多いほど状態のエネルギーは大きくなります。したがって、基底状態はフラストレーションエネルギーが最も少ない状態です。したがって、Σの基底状態エネルギーを求めるには、フラストレーション指数を求める必要があります。

フラストレーション数

類似の頂点数はフラストレーション数であり、Σから削除することで均衡が保たれる頂点の最小数として定義されます。同様に、Σの均衡誘導部分グラフの最大位数を求めることも重要です。

アルゴリズムの問​​題

符号付きグラフに関する3つの基本的な質問は、次のとおりです。グラフはバランスが取れているか？グラフ内のバランスの取れた辺の最大サイズは？バランスをとるために削除しなければならない頂点の最小数は？最初の質問は多項式時間で簡単に解けます。2番目の質問は、フラストレーション指数または最大バランス部分グラフ問題と呼ばれます。これは、その特殊なケース（グラフのすべての辺が負の場合）がNP困難問題である最大カットであるため、 NP困難です。3番目の質問は、フラストレーション数または最大バランス誘導部分グラフ問題と呼ばれ、これもNP困難です。例えば^{[9]を参照してください。}

マトロイド理論

符号付きグラフには、符号付きグラフィックマトロイド（フレームマトロイド、あるいはバイアスマトロイドとも呼ばれる）とリフトマトロイドと呼ばれる2つのマトロイドが関連付けられています。これらはどちらも、グラフのサイクルマトロイドを一般化したものです。これらは、バイアス付きグラフの同じマトロイドの特殊なケースです。

フレームマトロイド（または符号付きグラフィックマトロイド）M ( G ) は、基底集合としてエッジセットEを持ちます。^[10] 各コンポーネントに円が含まれないか、負の円が 1 つだけ含まれる場合、エッジセットは独立です。 （マトロイド理論では、ハーフエッジは負のループとまったく同じように動作します。）マトロイドの回路は、正の円、または接続する単純なパスを伴う負の円のペアで、2 つの円は互いに素であるか（接続パスは各円と 1 つの端が共通で、それ以外は両方と素）、共通の頂点を 1 つだけ共有します（この場合、接続パスはその単一の頂点です）。エッジセットSのランクはn − bです。ここで、nはGの頂点の数、bはSのバランスの取れたコンポーネントの数で、孤立した頂点もバランスの取れたコンポーネントとしてカウントされます。このマトロイドは、符号付きグラフの接続行列の列マトロイドです。これが、古典的なルート システムのルートの線形依存関係を記述する理由です。

拡張リフトマトロイド L ₀ ( G ) の基底集合は、エッジ集合Eと追加点( e ₀と表記)の和集合E ₀です。リフトマトロイドL ( G ) は、 Eに制限された拡張リフトマトロイドです。追加点は負のループとまったく同じように動作するため、ここではリフトマトロイドについてのみ説明します。エッジ集合は、円がまったく含まれていないか、負の円が 1 つだけ含まれている場合に独立しています (これは、符号付きグラフィックマトロイドの各コンポーネントに個別に適用されるルールと同じです)。マトロイド回路は、正の円、または互いに素であるか共通の頂点のみを持つ負の円のペアです。エッジ集合Sの階数はn − c + εです。ここで、 cは孤立した頂点を数えたSのコンポーネント数、 ε はS がバランスが取れている場合は 0、そうでない場合は 1 です。

その他の種類の「符号付きグラフ」

符号は+1と-1と解釈されることがあります。これは、符号が円周上で乗算され、積の符号が重要な場合の表記法の違いにすぎません。しかし、符号付きグラフ理論に当てはまらないエッジラベルの扱い方には、他に2つの方法があります。

符号付きグラフという用語は、各辺に重みw ( e ) = +1 または -1 が設定されているグラフに適用されることがあります。これらは符号付きグラフとは異なり、重みが制限された重みセットを持つ重み付きグラフです。違いは、重みが乗算されるのではなく加算されることです。問題と手法は全く異なります。

この名前は、符号がエッジ上の色として機能するグラフにも適用されます。色の重要性は、エッジに適用されるさまざまな重みを決定することであり、その符号が本質的に重要であるということではありません。これは結び目理論の場合であり、符号の唯一の重要性は、2要素グループによって交換できることですが、正と負の間に本質的な違いはありません。符号色グラフのマトロイドは、基礎となるグラフのサイクルマトロイドであり、符号付きグラフのフレームマトロイドまたはリフトマトロイドではありません。符号ラベルは、マトロイドを変更する代わりに、マトロイドの要素上の符号になります。

この記事では、厳密な意味での符号付きグラフ理論についてのみ議論します。符号付き色付きグラフについては、色付きマトロイドを参照してください。

符号付き有向グラフ

符号付き有向グラフとは、符号付き弧を持つ有向グラフです。符号付き有向グラフは、有向閉路の符号のみが意味を持つため、符号付きグラフよりもはるかに複雑です。例えば、バランスの定義は複数ありますが、それぞれを特徴づけるのは困難で、符号付き無向グラフの場合とは大きく異なります。

符号付き有向グラフと有向符号付きグラフを混同しないでください。有向グラフは双向グラフであり、有向グラフではありません（すべての符号が正である自明な場合を除く）。

頂点記号

頂点符号グラフ（ vertex -signed graph）は、頂点に符号が与えられたグラフである。円は、頂点の符号の積が正の場合、無矛盾（ただし、これは論理的無矛盾とは無関係）または調和的と呼ばれ、負の場合、無矛盾または不調和的と呼ばれる。調和的頂点符号グラフには、Hararyの平衡定理に類似した単純な特徴づけは存在しない。むしろ、その特徴づけは困難な問題であり、Joglekar、Shah、およびDiwan (2012) によって（より一般的に）最もよく解決された。^[11]

頂点符号理論に大きな変更を加えることなく、辺符号を追加することはしばしば容易である。そのため、頂点符号グラフ（または「マーク付き符号グラフ」）に関する多くの結果は、頂点と辺が符号するグラフにも自然に拡張される。これは、Joglekar、Shah、およびDiwan (2012) による調和の特徴付けにおいて特に顕著である。

マーク付き符号付きグラフと状態関数を持つ符号付きグラフ (§フラストレーションなど) の違いは、前者の頂点符号は基本的な構造の一部であるのに対し、状態関数は符号付きグラフ上の変数関数であるという点です。

「マークされたグラフ」という用語は、ペトリ ネットではまったく異なる意味で広く使用されていることに注意してください。マークされたグラフに関する記事を参照してください。

着色

符号なしグラフと同様に、符号付きグラフの彩色という概念があります。グラフの彩色は頂点集合から自然数への写像であるのに対し、符号付きグラフの彩色は頂点集合から整数への写像です。適切な彩色に関する制約は、符号付きグラフの辺に由来します。2つの頂点に割り当てられた整数は、それらが正の辺で接続されている場合、異なるものでなければなりません。隣接する頂点が負の辺で接続されている場合、それらの頂点のラベルは加法逆であってはなりません。正のループを持つ符号付きグラフには、適切な彩色は存在しません。

頂点ラベルを自然数kの大きさ以下の整数の集合に制限すると、符号付きグラフの真彩色の集合は有限となる。このような真彩色の個数とkの関係はkの多項式であり、これを k で表すと符号付きグラフの彩色多項式と呼ばれる。これは符号なしグラフの彩色多項式に類似している。 ${\displaystyle 2k+1}$

アプリケーション

社会心理学

社会心理学では、符号付きグラフは、人々を表すノード間の友情を表わす正のエッジと敵意を表す負のエッジを持つ社会的状況をモデル化するために使用されてきた。^[3]次に、たとえば、正の3サイクルは、3人の共通の友人、または共通の敵を持つ2人の友人である。一方、負の3サイクルは、3人の共通の敵、または共通の友人を共有する2人の敵である。バランス理論によると、正のサイクルはバランスが取れており、安定した社会的状況であるはずであるのに対し、負のサイクルはバランスが取れておらず、不安定であるはずである。理論によると、共通の敵が3人いる場合、共通の敵を共有することで、 2人の敵が友人になる可能性が高いためである。2人の敵が友人を共有している場合、共有されている友人は、どちらか一方を選び、友情の1つを敵に変える可能性が高い。

アンタル、クラピフスキー、レダーは、社会的ダイナミクスを符号付きグラフのエッジの符号の変化と見なしています。^{[12]離婚するカップルの以前の友人との社会的関係は、社会における符号付きグラフの進化を示すために使用されます。別の例では}、第一次世界大戦前の数十年間におけるヨーロッパ列強間の国際同盟の変化について説明しています。彼らは、ローカルなトライアドダイナミクスと制約付きトライアドダイナミクスを検討しており、後者の場合は、不均衡なトライアドの総数が減少する場合にのみ関係が変化するとしています。シミュレーションでは、変換のためにランダムな不均衡なトライアドが選択された、ランダムな関係を持つ完全グラフを前提としています。このプロセスにおけるN個のノードを持つ符号付きグラフの進化を研究し、友好的なリンクの定常密度を記述するシミュレーションを行います。

バランス理論は、特に大規模システムへの適用において、友好的な関係が社会を結びつける一方で、敵対する二つの陣営に分裂した社会は非常に不安定になるという理論的根拠から、厳しい批判を受けてきた。^[13] 実験的研究もまた、構造バランス理論の予測をわずかに裏付けるにとどまっている。^[14]

スピングラス

物理学では、符号付きグラフは、スピン グラスの研究に適用される非強磁性イジング モデルの自然なコンテキストです。

複雑なシステム

単純な栄養システムを表す3変数の符号付き有向グラフ

符号付き有向グラフは、もともと集団生物学と生態学で開発された分析手法で、現在では多くの科学分野で利用されており、複雑な因果システムの挙動を推論する際に応用されています。^{[15] [16]} このような分析は、システムの特定のレベルでのフィードバック、システムの1つ以上のポイントに摂動を与えた場合の変数の応答の方向、そのような摂動を与えた場合の変数の相関関係、システム全体の分散の分布、および特定の変数のシステム摂動に対する感度または非感度に関する質問に答えます。

データクラスタリング

相関クラスタリングは、類似性に基づいてデータの自然なクラスタリングを探します。データポイントはグラフの頂点として表され、類似する項目を結ぶ正のエッジと、類似しない項目を結ぶ負のエッジを持ちます。

神経科学

脳は、脳領域の活動パターン間の同期と反同期が正負のエッジを決定する符号付きグラフとみなすことができます。この点で、脳ネットワークの安定性とエネルギーを探求することができます。^[17]また、最近では、フラストレーションの概念が脳ネットワーク解析において用いられ、神経接続の非自明な集合体を特定し、脳の調整可能な要素を浮き彫りにしています。^[18]

一般化

符号付きグラフは、ゲイングループの位数が2である特殊なゲイングラフである。符号付きグラフΣによって決定されるペア（ G、B （Σ））は、特殊なバイアス付きグラフである。符号付きグラフは、より大きなゲイングループにはない特殊な性質を持つ。それは、エッジの符号が、平衡閉路の集合B （Σ）によってスイッチングまで決定されるという性質である。^[19]

注記

1. Harary, Frank (1955), "On the notion of balance of a signed graph", Michigan Mathematical Journal , 2 : 143– 146, MR  0067468, 2013-04-15のオリジナルからアーカイブ
2. Kőnig、Dénes (1936)、Akademische Verlagsgesellschaft (編)、Theorie der endlichen und unendlichen Graphen
3. Cartwright, D.; Harary, Frank (1956). 「構造的バランス：ハイダー理論の一般化」（PDF） .心理学評論. 63 (5): 277– 293. doi :10.1037/h0046049. PMID  13359597.
4. スティーブン・ストロガッツ（2010年）「私の敵の敵」ニューヨーク・タイムズ、2010年2月14日
5. ザスラフスキー、トーマス (1998)、「符号付きグラフとゲイングラフおよび関連領域の数学的文献」、Electronic Journal of Combinatorics、5、Dynamic Surveys 8、124 pp.、MR  1744869。
6. ルイス・フォン・アン『ウェブの科学』講義3、28ページ
7. Harary, Frank (1959)「構造的バランスの測定について」Behavioral Science 4, 316–323。
8. Robert P. Abelson、Milton J. Rosenberg (1958)、「象徴的心理論理：態度認知のモデル」、 Behavioral Science 3、1-13。
9. Gülpinar, N.; Gutin, G .; Mitra, G.; Zverovitch, A. (2004). 「符号付きグラフを用いた線形計画法における純粋ネットワーク部分行列の抽出」Discrete Appl. Math. 137 (3): 359– 372. doi :10.1016/S0166-218X(03)00361-5.
10. ザスラフスキー、トーマス（1982）、「符号付きグラフ」、離散応用数学、4（1）：47– 74、doi：10.1016/0166-218X（82）90033-6、hdl：10338.dmlcz / 127957、MR  0676405. 訂正. 離散応用数学, 5 (1983), 248
11. Manas Joglekar、Nisarg Shah、Ajit A. Diwan (2012)、「Balanced group labels graphs」、Discrete Mathematics、vol. 312、no. 9、pp. 1542–1549。
12. T. Antal、PL Krapivsky、S. Redner (2006) ネットワーク上の社会的バランス：友情と敵意のダイナミクス
13. B. アンダーソン著『ソーシャルネットワーク研究の展望』、PW ホランドとS. ラインハート編、ニューヨーク：アカデミック・プレス、1979年。
14. モリセット, ジュリアン・O.; ヤンケ, ジョン・C. (1967). 「構造バランス理論における無関係と強度ゼロの関係」.人間関係. 20 (2): 189– 195. doi :10.1177/001872676702000207. S2CID  143210382.
15. Puccia, Charles J. and Levins, Richard (1986).複雑系の定性モデリング：ループ分析と時間平均化入門. ハーバード大学出版局, Cambridge, MA.
16. Dambacher, Jeffrey M.; Li, Hiram W.; Rossignol, Philippe A. (2002). 「生態学的予測の不確定性を評価する上での群集構造の関連性」. Ecology . 83 (5): 1372– 1385. doi :10.1890/0012-9658(2002)083[1372:rocsia]2.0.co;2. JSTOR  3071950.
17. Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G (2021年1月). 「負のリンクが安静時の脳ネットワークの安定性に及ぼす位相的影響」. Scientific Reports . 11 (1): 2176. Bibcode :2021NatSR..11.2176S. doi :10.1038/s41598-021-81767-7. PMC 7838299. PMID  33500525 . 
18. Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G (2022年10月). 「機能的脳ネットワークにおけるフラストレーション形成パターン」. Network Neuroscience . 6 (4): 1334– 1356. doi : 10.1162/netn_a_00268 . PMC 11117102. PMID  38800463 . 
19. ザスラフスキー、トーマス(1981). 「符号付きグラフの特徴づけ」.グラフ理論ジャーナル. 5 (4): 401– 406. doi :10.1002/jgt.3190050409.

参考文献

• カートライト, D.;ハラリー, F. (1956)「構造的バランス：ハイダー理論の一般化」心理学評論、63 (5): 277– 293、doi :10.1037/h0046049、PMID  13359597。
• Seidel、JJ (1976)、「2 つのグラフの調査」、Colloquio Internazionale sulle Teorie Combinatorie (ローマ、1973)、Tomo I、Atti dei Convegni Lincei、vol. 17、ローマ:国立アカデミー大学、pp.  481–511、MR  0550136。
• Zaslavsky, Thomas (1998)、「符号付きグラフとゲイングラフおよび関連領域の数学的文献」、Electronic Journal of Combinatorics、5、Dynamic Surveys 8、124 pp.、MR  1744869