각 노드의 연결 수를 무작위로 생성하는 그래프 기반 연결 수

Question

나는 내가 가진 일부 데이터를 기반으로 그래프를 생성하려고 노력하고 있습니다.

이 그래프는 각 노드가있는 가장자리 수가 난수의 숫자 인 N와 같는 P(k) 노드를 가져야합니다. 여기서 k는 노드의 "인덱스"(대부분 임의)입니다.

내 질문은 실제로이 작업을 수행하는 방법이 있습니까?나는 더 많은 데이터가 밀도 또는 다른 접속도를 결정하는 더 많은 데이터가 필요하다고 생각하고있다 (n1-> n2-> n3). 나는 완전히 확신이 아니다.

Answer 1

기본적으로 어느 정도의 수준의 시퀀스가있는 그래프를 생성하고 싶습니다 (무작위로되기 원하는 것은 아니지만 관련이 없습니다). 이것은 그래프 실현 문제점 해결 된 Havel-hakimi 알고리즘 알고리즘이 돌아올 것입니다. 가능한 경우 원하는 정도의 시퀀스를 갖는 (간단한) 그래프 (그러한 서열을 그래픽 라고 함)로한다. $ \ mathbb n $ 을 통한 모든 유한 시퀀스는 예를 들어 그래픽입니다. 홀수 숫자에 대한 회원들이 멤버 합계가 핸드 셰이크 lemma 에 의해 그래픽 일 수 없습니다. 그래프의 모든 °의 합은 그래프의 가장자리 수의 2 배와 짝수로서). 또한 솔루션은 일반적으로 고유하지 않을 것입니다 : 학위 순서 $ (2, 2, 2, 2, 2, 2) $ 은 다음과 같이 실현할 수 있습니다 사이클 그래프 $ C_6 $ $ 6 $ 또는 disjoint union $ C_3 \ MATHOP {\ DOT \ CUP} C_3 $ 두주기 그래프의 $ C_3 $ 의 크기 $ 3 $ 각각.

프로그래밍 언어에 대한 많은 그래프 라이브러리는이 문제에 대한 알고리즘의 구현, 예를 들어 Python 라이브러리 networkx .