대수연결성

Algebraic connectivity
6개의 꼭지점, 직경 3, 연결성 1, 대수 연결성 0.722인 예제 그래프

그래프 G의 대수적 연결성(Fiedler 값 또는 Fiedler 고유값이라고도 함)은 G의 라플라시안 행렬 중 두 번째로 작은 고유값(다중 고유값을 별도로 계산함)이다.[1]이 고유값은 G가 연결된 그래프인 경우에만 0보다 크다.이는 라플라시안에서 고유값으로 나타나는 횟수 0이 그래프에서 연결된 성분의 수라는 사실에 대한 귀착이다.이 값의 크기는 전체 그래프가 얼마나 잘 연결되어 있는지를 반영한다.네트워크의 강건성과 동기화성을 분석하는 데 이용되어 왔다.

특성.

잘린 이코사헤드론이나 벅민스터풀레렌 그래프는 전통적인 연결성이 3이고 대수적 연결성이 0.243이다.

음이 아닌 가중치를 가진비방향 그래프의 대수적 연결성, ( G)inequality 0 [\ 0 G가 연결된 경우에만 불평등이 엄격하다.단, G가 연결된 그래프라 하더라도 일반 지시 그래프의 경우 대수적 연결성이 음수일 수 있다.[2]게다가, 대수적 연결의 가치 above 그래프의 전통적인(정점)연결, 대수적 연결 ≤ 연결{\displaystyle{\text{대수 연결}}\leq{\text{연결}}}.[3]만약 실수가 음이 아닌 에지 역기를 들고 한 지도자 없는 연결된 그래프의 vertices의 수가 n은으로 제한됩니다.d직경은 D, 대수적 연결 또한 ≥ 6노드와 그래프를 들어 1nD{\displaystyle{\text{대수 연결}}\geq{\frac{1}{nD}}},[4]고 사실 4nD{\displaystyle{\frac{4}{nD}에 의해(결과 브렌던 매케이 때문에)}}.[5]을 보여 주는 아래에 대수적 연결을 경계로 한 것으로 알려져 위에서(n.=6,D=3) 이 바운드 평균, 4/18 = 0.18 ≤ 대수 연결 0.722 ≤ 연결 1.

전통적인 연결성과 달리 대수적 연결성은 정점들이 연결되는 방식뿐만 아니라 정점의 수에 따라 달라진다.랜덤 그래프에서 대수적 연결성은 정점의 수에 따라 감소하고, 평균 정도에 따라 증가한다.[6]

대수적 연결성의 정확한 정의는 사용되는 라플라시아어의 유형에 따라 달라진다.판충은 정점 수에 대한 의존을 없애면서 라플라크의 리스케일 버전을 이용한 광범위한 이론을 전개해 그 한계가 다소 다르다.[7]

쿠라모토 모델과 같은 네트워크상의 동기화 모델에서는 라플라시안 매트릭스가 자연적으로 발생하기 때문에 대수적 연결성은 네트워크가 얼마나 쉽게 동기화될 것인지에 대한 지표를 준다.[8]평균 거리(성격 경로 길이)와 같은 다른 측도 사용할 수 있으며,[9] 사실 대수적 연결성은 (의 평균 거리)와 밀접한 관계가 있다.[5]

대수적 연결성은 또한 대수적 연결성의 절반으로 아래 경계를 이루는 등측수와 같은 다른 연결 속성과도 관련이 있다.[10]

피들러 벡터

대수적 연결성과 관련된 원래의 이론은 미로슬라프 피들러가 만들었다.[11][12]그를 기리기 위해 대수적 연결성과 관련된 고유 벡터는 피들러 벡터로 명명되었다.피들러 벡터는 그래프를 분할하는 데 사용될 수 있다.

피들러 벡터를 사용하여 그래프 분할

연결된 두 개의 그래프로 분할.

소개 섹션의 예시 그래프의 경우, 피들러 벡터는(0.0.0.- .- .221- )이다음수 값은 잘 연결되지 않은 꼭지점 6 및 인접 관절점 정점 4와 연관되어 있는 반면 양의 값은 다른 정점과 연관되어 있다.The signs of the values in the Fiedler vector can therefore be used to partition this graph into two components: . Alternatively, the value of 0.069 (which is close to zero) can be placed in a class of its own, partitioning the graph into three components: { ,} { ,6 또는 그림과 같이 다른 파티션으로 이동했다.피들러 벡터의 성분의 제곱 값은 벡터가 정규화된 이후 최대 1까지 합한 값으로 부호 기반 파티션에 할당될 해당 데이터 포인트의 확률로 해석할 수 있다.

참고 항목

참조

  1. ^ 와이스슈타인, 에릭 W. "알제브라틱 커넥티비티"Wolfram Web Resource에서 온.
  2. ^ Wu, Chai Wai (2005). "Algebraic connectivity of directed graphs". Linear and Multilinear algebra. Taylor and Francis. 53 (3): 203–223. doi:10.1080/03081080500054810. Even if G is quasi-strongly connected, which is equivalent to G containing a directed spanning tree, a(G) can still be nonpositive as the exploding star and Theorem 1 indicate.
  3. ^ J.L. 그로스와 J. 옐런.Graph 이론 핸드북, CRC Press, 2004, 314페이지.
  4. ^ J.L. 그로스와 J. 옐런.Graph 이론 핸드북, CRC Press, 2004, 페이지 571.
  5. ^ a b Bojan Mohar, The Laplacian Spectrum of Graphes, Graph 이론, 콤비네이터ics 및 Applications, Vol. 2, Ed.Y. Alavi, G. Chartrand, O. R. Oellermann, A. J. Schwenk, Wiley, 1991, 페이지 871–898.
  6. ^ 이산 복합 시스템의 동기화 및 연결, Michael Holroid, 국제 복합 시스템 회의, 2006.
  7. ^ F. 정.스펙트럼 그래프 이론, 프로비던스, RI: 아머수학. Soc, 1997.[1]
  8. ^ Tiago Pereira, Complex Networks에서 동기화된 동작의 안정성, arXiv:1112.2297v1, 2011.
  9. ^ D. 와트, 6도: The Science of a Connected Age, Vintage, 2003.
  10. ^ 노먼 빅스.대수 그래프 이론, 제2편, 캠브리지 대학 출판부, 1993, 페이지 28 & 58.
  11. ^ M. 피들러."그래프의 Algebraic connectivity of Graphs", 체코슬로바키아 수학 저널 23(98)(1973), 298–305.
  12. ^ M. 피들러."그래프와 대수적 연결성의 래플라시안", 조합론과 그래프 이론(Warsaw, 1987), 바나흐 센터 출판물 25(1)(1989), 57–70.