부호형 그래프

3. 좌절 (Frustration)

좌절(Frustration^영어)은 부호형 그래프의 불균형 정도를 나타내는 개념이다.

3. 1. 좌절 지수 (Frustration index)

3. 2. 좌절 수 (Frustration number)

4. 알고리즘적 문제

부호형 그래프와 관련된 세 가지 기본적인 문제는 다음과 같다.

• 균형을 이루는가?
• 균형 잡힌 정점 집합의 최대 크기는 얼마인가?
• 균형을 이루기 위해 삭제해야 하는 정점의 최소 개수는 얼마인가?

5. 매트로이드 이론 (Matroid theory)

부호형 그래프는 프레임 매트로이드(부호-그래픽 매트로이드)와 리프트 매트로이드라는 두 가지 매트로이드와 관련된다.^[10] 이들은 그래프의 사이클 매트로이드를 일반화한 것이다.

'''프레임 매트로이드''' ('''부호-그래픽 매트로이드''', '''바이어스 매트로이드'''라고도 함) ''M''(''G'')는 간선 집합 ''E''를 밑집합으로 갖는다.^[10] 각 성분이 원을 포함하지 않거나 음의 원을 하나만 포함하는 경우 간선 집합은 독립적이다. 매트로이드 이론에서 반간선은 음의 루프와 정확히 같은 역할을 한다. 매트로이드의 회로는 양의 사이클, 또는 두 개의 음의 사이클과 연결하는 단순 경로로 구성되는데, 두 사이클은 서로소이거나 (이 경우 연결 경로는 각 사이클과 하나의 끝점을 공유하고 그렇지 않으면 두 사이클과 서로소이다) 단일 공통 정점을 공유한다 (이 경우 연결 경로는 해당 단일 정점이다). 간선 집합 ''S''의 랭크는 ''n'' - ''b''인데, 여기서 ''n''은 ''G''의 정점 수이고 ''b''는 ''S''의 균형 성분 수이며, 고립된 정점도 균형 성분으로 계산한다. 이 매트로이드는 부호형 그래프의 인접 행렬의 열 매트로이드이다.

'''확장된 리프트 매트로이드''' ''L''₀(''G'')는 간선 집합 ''E''와 '''추가 점'''의 결합인 집합 ''E''₀을 밑집합으로 갖는데, 이를 ''e''₀로 나타낸다. '''리프트 매트로이드''' ''L''(''G'')는 ''E''로 제한된 확장된 리프트 매트로이드이다. 추가 점은 음의 루프와 정확히 같은 역할을 하므로, 리프트 매트로이드만 설명한다. 원을 포함하지 않거나 음의 원을 하나만 포함하는 경우 간선 집합은 독립적이다. 이것은 부호-그래픽 매트로이드에서 각 성분에 개별적으로 적용되는 규칙과 동일하다. 매트로이드 회로는 양의 사이클, 또는 서로소이거나 단일 공통 정점을 갖는 두 개의 음의 사이클이다. 간선 집합 ''S''의 랭크는 ''n'' - ''c'' + ε인데, 여기서 ''c''는 ''S''의 성분 수이며, 고립된 정점을 포함하여 계산하고, ε는 ''S''가 균형을 이루면 0이고, 그렇지 않으면 1이다.

6. 다른 종류의 "부호형 그래프"

때로는 부호를 +1과 -1로 간주하기도 한다. 이는 단순히 표기법의 차이일 뿐이며, 원형으로 부호를 곱하고 곱의 부호가 중요한 경우에 해당한다. 그러나 부호형 그래프 이론에 맞지 않는 다른 두 가지 엣지 라벨 처리 방식이 있다.

"부호형 그래프"라는 용어는 각 엣지가 가중치, ''w''(''e'') = +1 또는 -1을 갖는 그래프에 때때로 적용된다. 이는 제한된 가중치 집합을 가진 가중 그래프로, 부호형 그래프와는 다른 종류이다. 가중 그래프에서는 가중치가 더해지는 반면, 부호형 그래프에서는 가중치가 곱해진다는 차이점이 있으며, 문제와 방법 또한 완전히 다르다.

이 이름은 부호가 엣지의 색상으로 기능하는 그래프에도 적용된다. 색상의 중요성은 엣지에 적용되는 다양한 가중치를 결정한다는 것이며, 부호 자체가 본질적으로 중요하다는 의미는 아니다. 이는 매듭 이론의 경우이며, 여기서 부호의 유일한 중요성은 두 개의 원소 그룹에 의해 서로 바뀔 수 있다는 것이며, 양수와 음수 사이에는 본질적인 차이가 없다. 부호 색상 그래프의 매트로이드는 기본 그래프의 사이클 매트로이드이며, 부호형 그래프의 프레임 또는 리프트 매트로이드가 아니다. 부호 라벨은 매트로이드를 변경하는 대신 매트로이드의 요소에 대한 부호가 된다.

6. 1. 부호형 유향 그래프 (Signed digraph)

7. 정점 부호 (Vertex signs)

'''정점 부호 그래프'''는 '''표시된 그래프'''라고도 불리며, 정점에 부호가 주어진 그래프이다. 원의 정점 부호의 곱이 양수이면 '''일치한다''' (하지만 이는 논리적 일관성과는 관련이 없음) 또는 '''조화롭다'''고 하고, 곱이 음수이면 '''불일치''' 또는 '''비조화'''라고 한다. 하라리의 균형 정리와 유사한 조화로운 정점 부호 그래프에 대한 간단한 특징은 없으며, 대신 특징은 어려운 문제였으며, Joglekar, Shah, Diwan (2012)에 의해 (더 일반적으로) 가장 잘 해결되었다.^[11]

정점 부호 이론에 간선 부호를 간편하게 추가할 수 있다. 따라서 정점 부호 그래프("표시된 부호 그래프")에 대한 많은 결과가 정점 및 간선 부호 그래프로 자연스럽게 확장된다. 이는 Joglekar, Shah, Diwan (2012)에 의한 조화의 특징화에 특히 해당된다.

표시된 부호 그래프와 상태 함수가 있는 부호 그래프(§ 좌절 참조)의 차이점은 전자의 정점 부호는 본질적인 구조의 일부인 반면, 상태 함수는 부호 그래프에 대한 변수 함수라는 것이다.

"표시된 그래프"라는 용어는 페트리 그물에서 완전히 다른 의미로 널리 사용된다. 표시된 그래프 문서를 참조하라.

8. 채색 (Coloring)

부호형 그래프의 채색은 정점에 정수를 할당하는 것이다. 양의 변으로 연결된 정점은 서로 다른 정수를, 음의 변으로 연결된 정점은 덧셈 역수가 아닌 정수를 할당해야 한다.

부호형 그래프의 채색은 정점 집합에서 정수로의 매핑이다. 적절한 채색에 대한 제약은 부호형 그래프의 변에서 비롯된다. 두 정점이 양의 변으로 연결되어 있다면, 두 정점에 할당된 정수는 서로 달라야 한다. 인접한 정점에 대한 레이블은 정점이 음의 변으로 연결되어 있다면 덧셈 역수가 아니어야 한다. 양의 루프가 있는 부호형 그래프에는 적절한 채색이 있을 수 없다.

정점 레이블을 자연수 ''k'' 이하의 크기를 가진 정수 집합으로 제한하면, 부호형 그래프의 적절한 채색 집합은 유한하다. 이러한 적절한 채색의 수와 ''k'' 사이의 관계는 ''k''에 대한 다항식이다. $2k+1$로 표현될 때, 이를 부호형 그래프의 '''채색 다항식'''이라고 한다. 이는 무부호 그래프의 채색 다항식과 유사하다.

9. 응용 (Applications)

부호형 그래프는 다양한 분야에서 복잡한 관계를 분석하고 모델링하는 데 사용된다.

• '''사회 심리학''': 사회적 관계에서 친구 관계는 양의 부호로, 적대 관계는 음의 부호로 표현하여 사회적 상황을 모델링한다.^[3] 균형 이론에 따르면, 양의 순환은 안정적인 반면 음의 순환은 불안정한 사회적 상황을 나타낸다.
• '''스핀 글라스''': 물리학에서 부호형 그래프는 비강자성 이징 모형의 맥락에서 스핀 글래스 연구에 활용된다.
• '''복잡계''': 개체군 생물학과 생태학에서 시작된 부호형 그래프 분석 방법은 현재 여러 과학 분야에서 복잡한 인과 시스템의 동작을 추론하는 데 사용된다.^[15][16]
• '''데이터 클러스터링''': 상관 클러스터링에서 데이터 간 유사성은 양의 부호로, 상이성은 음의 부호로 표현하여 데이터의 자연스러운 군집을 찾는다.
• '''신경과학''': 뇌 영역 간 활동 패턴의 동기화 및 비동기화를 각각 양과 음의 부호로 나타내어 뇌 네트워크의 안정성과 에너지를 연구한다.^[17]

9. 1. 사회심리학 (Social psychology)

9. 2. 스핀 글라스 (Spin glasses)

9. 3. 복잡계 (Complex systems)

9. 4. 데이터 클러스터링 (Data clustering)

9. 5. 신경과학 (Neuroscience)

10. 일반화 (Generalizations)

부호형 그래프는 게인 그룹의 차수가 2인 특수한 종류의 게인 그래프이다. 부호형 그래프 Σ에 의해 결정되는 쌍 (''G'', '''''B'''''(Σ))는 특수한 종류의 바이어스 그래프이다. 부호 그룹은 더 큰 게인 그룹에서는 공유되지 않는 특별한 속성을 가지고 있는데, 간선 부호는 균형 잡힌 사이클 집합 '''''B'''''(Σ)에 의해 스위칭까지 결정된다.^[19]

참조

_[1] 간행물 On the notion of balance of a signed graph http://projecteuclid[...]
_[2] 서적 Theorie der endlichen und unendlichen Graphen
_[3] 논문 Structural balance: a generalization of Heider's theory https://snap.stanfor[...]
_[4] 뉴스 The enemy of my enemy http://opinionator.b[...] The New York Times 2010-02-14
_[5] 간행물 A mathematical bibliography of signed and gain graphs and allied areas http://www.combinato[...]
_[6] 웹사이트 Luis Von Ahn Science of the Web Lecture 3 p. 28 http://www.scienceof[...]
_[7] 간행물 On the measurement of structural balance
_[8] 간행물 Symbolic psycho-logic: a model of attitudinal cognition
_[9] 논문 Extracting pure network submatrices in linear programs using signed graphs
_[10] 간행물 Signed graphs
_[11] 간행물 Balanced group labeled graphs
_[12] 웹사이트 Social Balance on Networks: The Dynamics of Friendship and Enmity https://arxiv.org/ab[...]
_[13] 서적 Perspectives on Social Network Research Academic Press, New York
_[14] 논문 No relations and relations of strength zero in the theory of structural balance
_[15] 서적 Qualitative Modeling of Complex Systems: An Introduction to Loop Analysis and Time Averaging http://www.hup.harva[...] Harvard University Press, Cambridge, MA
_[16] 논문 Relevance of community structure in assessing indeterminacy of ecological predictions
_[17] 논문 Topological impact of negative links on the stability of resting-state brain network 2021-01
_[18] 논문 Pattern of frustration formation in the functional brain network 2022-10
_[19] 논문 Characterizations of signed graphs 1981