graph_tool.stats

Sylen·2025년 1월 4일

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 vertex_hist() 함수를 이용하여, 그래프의 정점에 대한 다양한 특성(차수나 다른 속성)에 대한 히스토그램을 효율적으로 계산하고 시각화하는 방법을 단계별로 설명합니다. 초보자를 위해 파이썬 코드 예시, 상세한 한글 주석, 개념적 배경을 친절하고 정성스럽게 풀어보겠습니다.

1. `vertex_hist()`란?

1.1 기본 개념

목적: 특정 정점 속성(예: in-degree, out-degree, total degree, 또는 임의의 vertex property)을 구간(bin)별로 세어서 히스토그램을 만들어줌.
시그니처:
```
counts, bins = graph_tool.stats.vertex_hist(
    g,
    deg, 
    bins=[0, 1], 
    float_count=True
)
```
- deg: "in", "out", "total" 또는 VertexPropertyMap (수치형).
- bins: 히스토그램 구간 정의.
  - 예) [0,1] 형태면, 실제 히스토그램 구간을 자동 설정(간격=1).
  - 임의의 리스트 (ex: [0, 5, 10, 20])를 주면 직접 구간을 명시.
- float_count: bin에 대한 카운트를 부동소수(float)로 반환할지, 정수(int)로 반환할지.

1.2 동작 방식

그래프의 모든 정점을 순회하면서, deg가 가리키는 값(차수 또는 property) 확인 → 적절한 bin에 카운팅.
결과:
- counts: 각 bin별 카운트(기본 float, float_count=False면 int).
- bins: bin 구간의 끝점 리스트.

1.3 시간 복잡도

문서에서 O(V) (정점 수만큼) 시간이 걸린다고 명시. 실제로, 정점을 한 번씩 스캔하면 충분한 간단한 알고리즘.

2. 튜토리얼 예시 코드

다음 코드는 임의 그래프를 만든 뒤, “정점의 out-degree”에 대한 히스토그램을 구하고 시각화하는 예시입니다.

# vertex_hist_tutorial.py

import graph_tool.all as gt
import numpy as np
import matplotlib.pyplot as plt

def main():
    # 1) 그래프 생성: random_graph()로 예시
    #    - 정점 1000개, 포아송(lambda=5) 분포 기반 차수
    g = gt.random_graph(1000, lambda:  np.random.poisson(5),directed=False)  
    # => 무방향, average degree ~10 근방 기대
    
    print("Number of vertices:", g.num_vertices())
    print("Number of edges:", g.num_edges())

    # 2) vertex_hist: out-degree(무방향 그래프이므로 out=total 과 동일)
    #    bins=[0,1] => 자동으로 (max_deg+1)까지 간격 1로
    counts, bin_edges = gt.vertex_hist(g, "out", bins=[0,1], float_count=True)

    # 3) 결과 확인
    print("Counts:", counts)
    print("Bin edges:", bin_edges)

    # 4) 시각화: 막대그래프
    #    bin_edges는 bin 개수+1 길이이므로, 막대의 x좌표를 중간값으로 설정
    bin_centers = 0.5*(bin_edges[:-1] + bin_edges[1:])
    
    plt.figure(figsize=(8,4))
    plt.bar(bin_centers, counts, width=0.8, align='center', alpha=0.7)
    plt.title("Histogram of vertex out-degree")
    plt.xlabel("Degree")
    plt.ylabel("Count")
    plt.grid(True)
    plt.show()

if __name__=="__main__":
    main()

코드 해설

gt.random_graph(1000, lambda: (poisson(5), poisson(5))):
- 노드 1000개, 각 노드 차수를 포아송(5) 근사로. 대략 평균 차수 ~10. 무방향.
vertex_hist(g, "out", bins=[0,1]):
- out-degree에 대해, 히스토그램 bin을 [0,1]로 주면, 자동으로 0부터 최대값까지 폭=1인 구간 설정.
반환:
- counts: 각 bin별 수(부동소수).
- bin_edges: bin 경계값(ex. [0,1,2,...,K]).
시각화:
- bin 중심점 = (bin_edges[i] + bin_edges[i+1])/2
- plt.bar(...).

3. 파라미터 상세

3.1 deg

"in", "out", "total":
- 유향 그래프에서 in-degree, out-degree, 무방향 그래프면 "out"="in"="total" 의미.
VertexPropertyMap:
- 예: node별 “population”등 사용자 정의 실수 값.
- 히스토그램 구할 때 bins 구간에 매핑.

3.2 bins

[a,b] 길이가 2인 리스트:
- 자동으로 a, a+b, a+2b, ... 형태 bin 에지 생성
- 예) [0,1] => [0,1,2,3,..., up to max_value+1].
임의 길이>2 리스트: 명시적 bin 경계.

3.3 float_count

True(기본): counts를 float로 반환(확장성).
False: 정수 count.

4. 다른 예시: 정점 속성 히스토그램

아래는 정점 속성(예: vprop = g.new_vertex_property("float"))에 대한 히스토그램 예:

vprop = g.new_vertex_property("float")
# 임의로 값 지정
for v in g.vertices():
    vprop[v] = np.random.uniform(0, 100)

counts, bins = gt.vertex_hist(g, vprop, bins=[0,10], float_count=False)
# => 0부터 최대값 까지, 폭=10 구간

5. 결과 활용

counts와 bins를 이용해 바로 matplotlib 막대그래프, 누적분포, 로그스케일 등 원하는 식으로 그림.
빅데이터(수십만 노드)에도 빠르게 계산(Parallel(OpenMP) 지원) → 정점 속성 분포 파악, degree distribution 분석 등에 사용.

6. 정리

vertex_hist(): 그래프 정점에 대해, 차수 혹은 임의 속성값의 히스토그램을 쉽게 구할 수 있는 함수.

사용법:

counts, bins = gt.vertex_hist(g, deg="out", bins=[0,1], float_count=True)

장점:
- 병렬(OpenMP) 가능 → 대규모 그래프 처리에 효율적.
- bin 설정 단순, 혹은 커스텀 가능.
- degree뿐 아니라 property map에도 적용 OK.
활용: degree distribution 시각화, 속성 분포 파악, 이상치(예: 매우 큰 차수) 확인.

이상으로 vertex_hist 함수에 대한 자세한 설명과 예시 코드를 마쳤습니다. 도시·교통 등 정점 중심 빅데이터에서 각 노드의 속성(차수·인구·종류 등)의 분포를 쉽게 그려볼 수 있고, 수 분할(히스토그램) 기반의 탐색 분석이 가능해집니다.

아래 튜토리얼은 graph-tool 라이브러리의 edge_hist() 함수를 이용해 그래프에서 특정 간선(edge) 속성의 분포(히스토그램)를 손쉽게 구하고 시각화하는 방법을 설명합니다. 함수 호출 시, 원하는 속성을 bin 단위로 세어, numpy.ndarray 형태의 결과(카운트, bins)로 반환하므로, 간선 속성 분석에 유용합니다.

1. `edge_hist()` 개요

counts, bins = graph_tool.stats.edge_hist(
    g,
    eprop,
    bins=[0, 1],
    float_count=True
)

g: 그래프(Graph).
eprop: EdgePropertyMap(실수형 혹은 정수형) — ex) 어떤 간선 가중치, 용량, 길이 등.
bins: 히스토그램 구간(“엣지”라곤 하지만 여기서 bin edges 의미).
- 기본 [0,1] → 자동으로 최대값까지 간격=1씩 구간.
- 혹은 [0,0.1,0.2,0.3, ...] 등 임의 리스트로 세밀하게 지정 가능.
- 2개 값일 때 (예: [0, 1]), 내부적으로 “최댓값”까지 step=1씩 bins 생성.
float_count: bin에 대한 카운트가 float(True) 또는 int(False)로 반환 여부.

반환:

counts: 각 bin별 카운트(기본 float)
bins: bin 경계값(길이 = bin 개수+1)

1.1 알고리즘 성능

문서에 따르면, 시간복잡도는 (O(E)). 즉, 간선 수만큼 한 번씩 속성 읽고 bin 분류.

2. 간단 튜토리얼 예시 코드

아래 예시는 무작위 그래프를 생성하고, 각 간선에 난수(0~1)를 할당한 뒤, 해당 속성의 히스토그램을 그려보는 코드입니다.

# edge_hist_tutorial.py

import graph_tool.all as gt
import numpy as np
import matplotlib.pyplot as plt

def main():
    # 1) 무작위 그래프 생성 (1000 노드, 각 노드 차수=5 근사)
    #    => graph_tool.random_graph()를 사용
    g = gt.random_graph(1000, lambda: np.random.poisson(5), directed=False)
    
    print("Number of vertices:", g.num_vertices())  # 1000
    print("Number of edges:", g.num_edges())        # 대략 ~2500정도 (정규5 -> average deg=10/2=5?)

    # 2) edge property 생성 (double type)
    eprop = g.new_edge_property("double")
    
    # 3) 임의 난수(0..1) 할당
    arr = eprop.get_array()
    arr[:] = np.random.random(g.num_edges())
    # 이제 eprop[e] 는 [0..1) 범위 랜덤 값
    
    # 4) edge_hist: bins => 예) 0..1 구간을 10등분
    bins_input = np.linspace(0, 1, 11)  # [0., 0.1, 0.2,...1.0]
    counts, bin_edges = gt.edge_hist(g, eprop, bins=bins_input, float_count=True)

    # 5) 결과 확인
    print("Counts:", counts)
    print("Bin edges:", bin_edges)

    # 6) 시각화: 막대그래프
    bin_centers = 0.5*(bin_edges[:-1] + bin_edges[1:])
    width = bin_edges[1] - bin_edges[0]
    
    plt.figure(figsize=(8,4))
    plt.bar(bin_centers, counts, width=width, align='center', alpha=0.7)
    plt.title("Histogram of edge property (random 0..1) in the graph")
    plt.xlabel("Edge property value")
    plt.ylabel("Count")
    plt.grid(True)
    plt.show()

if __name__ == "__main__":
    main()

코드 해설

그래프 생성: random_graph(1000, lambda: (5,5))로 1000개 노드를 가진 그래프, 평균 차수 ~5인 무방향 그래프.
간선 property: eprop = g.new_edge_property("double")
난수 할당: np.random.random(...)으로 [0,1) 범위.
edge_hist(...): bins=np.linspace(0,1,11) => 구간 [0~0.1), [0.1~0.2), ..., [0.9~1.0]
counts, bin_edges 반환.
plt.bar(...)로 막대그래프 시각화.

3. bins 설정 옵션

[a, b] 길이가 2인 리스트: 자동으로 a, a+b, a+2b, ... 형태로 bin edges 생성.
직접 리스트나 np.linspace 등 → bin 경계 수동 지정.
ex) [0,5,10,20] => bin 3개: [0..5), [5..10), [10..20).

4. `float_count=True/False` 차이

True(기본): 결과 counts가 float. ex) [ 123. 456. ...]
False: int 카운트. ex) [123 456 ...]

실질적 차이는 “정밀도”가 아니라, bin count를 부동소수로 합산할 필요가 있을 때(예: 확률 가중 등) 유용.

5. 성능과 병렬화

“If enabled during compilation, this algorithm will run in parallel using OpenMP.”
- 빌드 시 OpenMP 활성화하면, 큰 그래프(edge 수가 수백만)에서도 병렬 계산 가능.

6. 다른 예: 특정 가중치(길이, capacity) 등

가령 “도로 네트워크”에서 간선 길이, 속도, 용량이 “EdgePropertyMap”
edge_hist로 히스토그램 => 길이 분포, 속도 분포, 용량 분포 등 분석 가능.

road_length = g.new_edge_property("double")
# ... 값 할당 ...
counts, bins = gt.edge_hist(g, road_length, bins=[0,10], float_count=False)
# => 0..최댓값까지 폭=10씩 bin

7. 요약

edge_hist(): 그래프 간선에 대해, 특정 속성의 히스토그램(bin 단위 카운트) 계산

사용법:

counts, bins = gt.edge_hist(g, eprop, bins=[start, step], float_count=True)

or 커스텀 bin.

성능: (O(E)), 병렬(OpenMP) 지원. 대규모 그래프에도 효율적.
활용: 가중치/속성분포 시각화, threshold-based 분석, 이상치(특이값) 검출.

이상으로 edge_hist() 함수에 대한 구체적 설명과 예시 코드를 마쳤습니다. 도시·교통 네트워크에서 “도로별 속성(길이, 용량, 혼잡도 등)의 분포”를 빠르고 간단히 파악해보는 데 유용하게 쓸 수 있습니다.

아래 튜토리얼은 graph-tool 라이브러리의 vertex_average() 함수를 사용하여, 그래프의 정점에 대해 특정 속성(차수나 임의 프로퍼티) 의 평균과 표준편차를 효율적으로 계산하고 활용하는 과정을 자세히 설명합니다. 초보자를 위해 파이썬 코드 예시, 상세한 한글 주석, 추가 팁을 포함했습니다.

1. `vertex_average()`의 기본 개념

avg, std = graph_tool.stats.vertex_average(g, deg)

입력:
- g: Graph 객체.
- deg: 문자열 "in", "out", "total" (정점 차수) 혹은 VertexPropertyMap (정점 프로퍼티).
출력:
- avg: float, 해당 속성(혹은 차수)의 전체 정점 평균.
- std: float, 그 평균의 표준편차(표본 표준편차).

1.1 차수(degree) vs. 사용자 정의 프로퍼티

"in", "out", "total":
- 유향 그래프일 때 in-/out-degree, 무방향 그래프면 "out"="total", "in"="total" 같은 의미.
만약 deg가 VertexPropertyMap이라면, 임의의 실수형 값(예: 인구, 수요, 점수 등)을 가질 수 있음.

2. 기본 사용 예시

아래는 무방향 예시 그래프를 만들고, "total" 차수에 대해 평균과 표준편차를 구하는 예입니다.

# vertex_average_tutorial.py

import graph_tool.all as gt
import numpy as np

def main():
    # 1) 무작위 그래프 생성
    #    - 500개 노드, 포아송(λ=5) 근사 차수
    g = gt.random_graph(500, lambda: (np.random.poisson(5),
                                      np.random.poisson(5)),
                        directed=False)

    print("Number of vertices:", g.num_vertices())
    print("Number of edges:", g.num_edges())

    # 2) vertex_average: total degree
    avg, std = gt.vertex_average(g, deg="total")
    print("Average degree (total):", avg)
    print("Std dev of degree:", std)

if __name__=="__main__":
    main()

코드 해설

gt.random_graph(500, lambda: (poisson(5), poisson(5)), directed=False):
- 노드 500개, 평균 차수 ~10 근방(무방향이므로 λ=5 => in+out=10).
vertex_average(g, deg="total"):
- 무방향 => "total" 차수가 곧 각 노드가 가진 “degree”.
결과로 평균 차수와 표준편차를 출력.

3. 사용자 정의 정점 프로퍼티에 대한 평균 계산

차수 대신, 정점 속성을 직접 만들어서 그 평균·표준편차를 구할 수도 있습니다.

# vertex_property_example.py

import graph_tool.all as gt
import numpy as np

def main():
    # 1) 그래프 생성
    g = gt.Graph()
    g.add_vertex(5)  # 5개 노드

    # 간단히 연결 (예: 0->1, 1->2,...)
    g.add_edge(0,1)
    g.add_edge(1,2)
    g.add_edge(2,3)
    g.add_edge(3,4)

    # 2) 정점 프로퍼티(예: node_value) 생성
    node_val = g.new_vertex_property("float")
    
    # 3) 임의 값 할당
    for v in g.vertices():
        node_val[v] = np.random.uniform(10, 50)  # 10~50 범위 임의

    # 4) vertex_average
    avg, std = gt.vertex_average(g, deg=node_val)  # 'deg' 인자에 property
    print("Node property average:", avg)
    print("Node property std dev:", std)

if __name__=="__main__":
    main()

해설

node_val이라는 VertexPropertyMap("float")에 임의의 실수를 할당.
vertex_average(g, deg=node_val)로 평균, 표준편차 계산.

출력 예)

Node property average: 29.8123
Node property std dev: 10.564

4. 표준편차 계산 방식

vertex_average()가 반환하는 std는 모집단 표준편차가 아닌, 샘플 표준편차(sample standard deviation, Bessel’s correction) 여부는 문서에서 명확히 언급되지 않았지만, 보통 sqrt( (Σ(x-avg)^2)/N ) 형태로 추정됩니다.
대규모 그래프면 차이는 미미.

5. 성능 및 병렬화

O(V): 정점을 한 번씩 스캔해 deg(또는 property) 합계와 제곱합계, 그리고 N(=|V|)로부터 평균·분산·표준편차를 계산.
OpenMP 병렬 지원 가능(빌드시 옵션) → 수십억 노드급 그래프까지 빠르게 처리할 수 있음.

6. 시각화 등 추가 활용

평균이나 표준편차 자체는 숫자 2개이지만,

히스토그램: vertex_hist() (함께 사용)
박스 플롯: 간단히 matplotlib에서 plt.boxplot([node_val[v] for v in g.vertices()]) 등.
이상값 탐지: mean ± 2*std 등을 임계로 삼아 outlier 검사.

7. 정리

vertex_average()는 그래프의 정점 기반 속성(차수나 임의 프로퍼티)의 평균과 표준편차를 단 한 번에 쉽게 구해줌.
호출 예)
```
avg, std = gt.vertex_average(g, "out")
```
결과: (avg, std)
장점:
- 짧고 직관적인 API
- 병렬화 지원 → 대규모 그래프에도 효율적
확장: vertex property map에 임의의 실수값(교통량, 인구, 점수 등)을 담아 평균·편차 계산 가능.

이상으로 vertex_average()의 사용법, 예시 코드, 응용 아이디어를 살펴보았습니다. 도시·교통·네트워크 분석에서 정점별 속성(차수·가중·특성 값)에 대한 전역 통계량(평균, 표준편차)을 빠르고 간단히 구해볼 때 매우 유용합니다.

아래 튜토리얼은 graph-tool 라이브러리의 edge_average() 함수를 이용해서, 그래프의 간선(edge)에 대해 특정 속성(Property) 값의 전체 평균과 표준편차를 간단히 계산하는 방법을 설명합니다. 초보자를 위해 파이썬 코드 예시, 상세한 한글 주석, 응용 팁을 포함했습니다.

1. `edge_average()`란?

avg, std = graph_tool.stats.edge_average(g, eprop)

입력:
- g: Graph 객체
- eprop: EdgePropertyMap, 간선별로 저장된 실수(double) 형태 속성 (예: 길이, 가중치, 비용 등).
출력:
- avg: 주어진 간선 속성값들의 전체 평균(부동소수점)
- std: 그 평균에 대한 표준편차

1.1 동작 방식

모든 간선을 순회하면서, eprop[e](속성값)를 더하여 평균을 구하고, 분산(표준편차)도 함께 계산.
결과로 (평균, 표준편차) 튜플 반환.

1.2 시간 복잡도 및 병렬화

(O(E)): 간선 수만큼 한 번씩 속성을 읽는 단순 알고리즘.
빌드시 OpenMP 옵션이 활성화되었다면, 대규모 그래프에서도 병렬적으로 빠르게 처리.

2. 간단 예시 코드

다음 코드는 무작위 그래프를 만들고, 각 간선에 난수(0..1)를 할당한 뒤 edge_average()로 평균과 표준편차를 계산하는 예입니다.

# edge_average_tutorial.py

import graph_tool.all as gt
import numpy as np

def main():
    # 1) 그래프 생성: 1000개 노드, 각 노드는 차수=5 근사 (무방향)
    g = gt.random_graph(1000, lambda: (5, 5), directed=False)
    
    print("Number of vertices:", g.num_vertices())  # 1000
    print("Number of edges:", g.num_edges())        # 대략 2500 정도

    # 2) edge property 생성 (double type)
    eprop = g.new_edge_property("double")

    # 3) 임의 난수 할당: 0..1 범위
    arr = eprop.get_array()
    arr[:] = np.random.random(g.num_edges())

    # 4) edge_average: (평균, 표준편차) 반환
    avg, std = gt.edge_average(g, eprop)
    
    print("Edge property average:", avg)
    print("Edge property std:", std)

if __name__=="__main__":
    main()

코드 해설

그래프 생성: random_graph(1000, lambda: (5,5))로 1000개 노드, 각 노드 차수는 평균 5(무방향이면 이웃 합=10?). 실제 간선 수는 무작위로 약 2500 근방.
EdgePropertyMap 만들기: eprop = g.new_edge_property("double").
임의 값 할당: arr[:] = np.random.random(g.num_edges()) → [0..1) 범위.
edge_average(g, eprop): 모든 간선에 대한 속성값의 평균과 표준편차 계산.

출력 예 (예시):

Edge property average: 0.4982
Edge property std: 0.00298

3. 다른 예시: 실제 가중치나 길이 등

아래는 도시 도로망에서 간선에 길이를 저장했다고 가정:

# edge_length_example.py

import graph_tool.all as gt

def main():
    # 예: g는 이미 로드된 도로망 그래프
    #     각 간선에 "length"라는 double property가 있다고 가정
    length_prop = g.edge_properties["length"]

    avg_len, std_len = gt.edge_average(g, length_prop)
    print("Average road length:", avg_len)
    print("Std dev:", std_len)

이처럼 실제 분석 시, 도로 길이, 비용, 혼잡도 등등 “간선”에 대응되는 어떤 값이든 평균·표준편차를 한 번에 구할 수 있습니다.

4. 표준편차(`std`) 계산 의미

반환되는 std는 (모집단) 표준편차인지, (샘플) 표준편차인지는 문서에 명시X이나, 보통
[
\sigma = \sqrt{\frac{\sum_i (x_i - \bar{x})^2}{N}}
]
형태로 추정됩니다. (Bessel 보정전 or 후 여부는 크게 차이 안 남)

5. 시각화 / 후처리

edge_average()는 숫자 2개(평균, 표준편차)만 반환. 히스토그램은 edge_hist() 참고.
예) "평균 ± 2*표준편차" 범위로 이상치(Outlier)를 찾는 등 다양한 응용 가능.

6. 요약

edge_average(): 그래프의 간선별 속성(실수)에 대해 전체 평균, 표준편차를 손쉽게 얻는 함수.
인수:
- g: Graph 객체
- eprop: EdgePropertyMap("double")
반환: (average: float, std: float)
복잡도: O(E), 병렬화 지원 (OpenMP).
활용: 간선 가중치(길이, 비용, 속도, 수요 등) 통계 요약, 이상치 탐색 등에 유용.

이상으로 edge_average() 함수에 대한 친절한 튜토리얼을 마쳤습니다. 도시·교통·네트워크 빅데이터에서 간선 중심 속성(도로 길이, 혼잡도, 비용 등)에 대한 요약 통계를 구하고 싶을 때 간단히 활용할 수 있습니다.

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 distance_histogram() 함수를 이용해, 그래프 상에서 두 정점 사이의 최단거리(shortest path distance) 분포를 효율적으로 계산하고 시각화하는 방법을 설명합니다. 초보자를 위해 파이썬 예시 코드, 친절한 한글 주석, 사용 팁을 포함했습니다.

1. `distance_histogram()` 개요

counts, bins = graph_tool.stats.distance_histogram(
    g,
    weight=None,
    bins=[0, 1],
    samples=None,
    float_count=True
)

입력:
- g: Graph 객체
- weight: (선택) EdgePropertyMap (간선 가중치) – 없으면 비가중 최단거리
- bins: 히스토그램 구간. [0,1] 형식이면 0부터 최대 거리까지 폭=1씩 자동 생성
- samples: (선택) 샘플링 개수. (None이면 전체 정점 쌍, 정수면 특정 수의 소스 정점을 무작위 선택해 최단거리)
- float_count: True면 bin 카운트를 float, False면 int
출력:
- counts: 각 bin별 최단거리 개수(기본 float)
- bins: bin 경계값(길이=bin 개수+1)

1.1 최단거리의 의미

비가중 그래프라면 정수로 (ex. 1,2,3...), 유향/무향에 따라 다를 수 있음.
가중치가 있으면 Dijkstra 등으로 거리를 구해, 그 값을 bin에 할당.

1.2 시간 복잡도

무가중이고 samples=None일 때, Floyd-Warshall가 아니라 각 정점을 소스 삼아 BFS (이론상 (O(V \times (V+E))))를 병렬화. 실제 graph-tool 구현 세부 방식에 따라 최적화되어 있음.
가중치 있으면 O(V \times E \log V), 샘플링(s>0) 시는 O(s \times (V+E)) or O(s \times E \log V).

2. 기본 사용 예시

다음은 무방향 그래프(무가중)에 대해 모든 정점 쌍의 최단거리 분포(=distance histogram)를 계산하는 예시 코드입니다.

# distance_histogram_tutorial.py

import graph_tool.all as gt
import numpy as np
import matplotlib.pyplot as plt

def main():
    # 1) 예시 그래프 생성 (랜덤 그래프)
    #    - 100개의 노드, 각 노드 차수 ~3 근사
    g = gt.random_graph(100, lambda: (3,3), directed=False)
    
    print("Num vertices:", g.num_vertices())
    print("Num edges:", g.num_edges())

    # 2) distance_histogram: 무가중 => weight=None
    #    bins=[0,1] => 0부터 최대거리까지 폭=1씩 bin 생성
    counts, bin_edges = gt.distance_histogram(
        g,
        weight=None,
        bins=[0,1],
        samples=None,      # 모든 소스 (전체 정점) 사용
        float_count=True
    )
    
    # 3) 결과 확인
    print("Counts:", counts)
    print("Bin edges:", bin_edges)

    # 4) 시각화 (막대 그래프)
    bin_centers = 0.5*(bin_edges[:-1] + bin_edges[1:])
    
    plt.figure()
    plt.bar(bin_centers, counts, width=1.0, align='center', alpha=0.7)
    plt.title("Distance histogram (unweighted) of the graph")
    plt.xlabel("Distance")
    plt.ylabel("Count")
    plt.grid(True)
    plt.show()

if __name__=="__main__":
    main()

코드 해설

gt.random_graph(100, lambda: (3,3), directed=False)로 100개 노드, 평균 차수 ~3인 무작위 그래프.
distance_histogram(g, weight=None, bins=[0,1]):
- 모든 정점 쌍에 대해 최단거리를 구해 0..maxDistance까지 1씩 bin 구성.
counts: 각 거리값이 bin에 얼마나 속했는지(실제로는 0인 bin은 “자기 자신”=0, 일반적 의미에서 count=0 or 별도 처리).
시각화 → x축=거리, y축=count. BFS 기반이므로 (O(V(V+E))) 시간(병렬화 가능).

3. 샘플링(`samples`)을 활용한 최단거리 분포 추정

전체 정점 쌍이 아주 많으면(수십만 노드 이상) 계산이 부담될 수 있으므로, samples로 소스 정점 수 제한 → 무작위 s개 소스에서만 BFS (또는 Dijkstra) 실행 후, 나머지 노드까지 거리 측정.

counts_s, bins_s = gt.distance_histogram(
    g,
    weight=None,
    bins=[0,1],
    samples=10,     # 10개 정점만 소스로 사용
    float_count=True
)

예) 10개의 소스 정점만 택 → 약 (10 \times (V+E)) 로 계산량 대폭 줄임.
얻어진 counts_s, bins_s는 실제 전역 분포의 근사치.

4. 가중치(weight) 있는 그래프

EdgePropertyMap("double") 형태의 가중치(예: 거리, 비용, 시간 등) → Dijkstra류 알고리즘으로 최단거리.
distance_histogram(g, weight=weight_prop, ...) 식으로 호출.
빅그래프라면 이 경우 (O(V \times E \log V)) or 샘플링 시 (O(s \times E \log V)).

5. 주의사항 및 팁

bin 0: 문서 예시에서, counts[0]이 0 (혹은 특정 값)일 수 있음. 보통 “자기 자신에게 거리=0”이 V번 있겠으나, graph-tool에서 이 부분(자기 자신)은 보정할 수도 있으니 결과 해석 시 주의.
그래프가 연결 안 됐을 때: BFS 시 도달 불가능한 쌍도 있을 수 있음. 이러한 쌍의 거리는 ∞로 취급 → histogram에 포함 안 되거나, maxDistance보다 큰 값.
병렬화: OpenMP로 병렬화 가능. 그래프가 클수록 컴파일 옵션 확인 필요.

6. 시각화 아이디어

“distance vs. count” 형태로 막대그래프.
누적(CDF)으로 볼 수도 있음(예: cumulative sum).

예시 (cumulative 형태):

cum_counts = np.cumsum(counts / counts.sum())
plt.plot(bin_centers, cum_counts, marker='o')

7. 정리

distance_histogram(): 그래프에서 모든(혹은 샘플링된) 정점 쌍의 최단거리 분포를 bin 단위로 세어 줌.

사용법:

counts, bins = gt.distance_histogram(g, weight=..., bins=[0,1], samples=None)

시간복잡도:
- 무가중, samples=None → (O(V(V+E)))
- 가중치, samples=None → (O(V \times E \log V))
- 샘플링 s개 → (O(s(V+E))) or (O(sE\log V))
활용:
- 네트워크 지름(최대 거리), 평균 거리, 분포 등 확인
- 빅그래프에서는 samples로 근사.

이상으로 distance_histogram()의 기능, 예시 코드, 활용을 살펴보았습니다. 도시·교통 네트워크에서 최단 경로분포(ex. 평균 이동 거리, 페어와이즈 접근성, 커뮤니티 분리 정도 등)를 평가할 때 매우 유용합니다.

Sylen

AI가 재밌는 걸

이전 포스트

graph_tool.spectral Operator objects

다음 포스트

graph_tool.stats

1. vertex_hist()란?

1.1 기본 개념

1.2 동작 방식

1.3 시간 복잡도

2. 튜토리얼 예시 코드

코드 해설

3. 파라미터 상세

3.1 deg

3.2 bins

3.3 float_count

4. 다른 예시: 정점 속성 히스토그램

5. 결과 활용

6. 정리

1. edge_hist() 개요

1.1 알고리즘 성능

2. 간단 튜토리얼 예시 코드

코드 해설

3. bins 설정 옵션

4. float_count=True/False 차이

5. 성능과 병렬화

6. 다른 예: 특정 가중치(길이, capacity) 등

7. 요약

1. vertex_average()의 기본 개념

1.1 차수(degree) vs. 사용자 정의 프로퍼티

2. 기본 사용 예시

코드 해설

3. 사용자 정의 정점 프로퍼티에 대한 평균 계산

해설

4. 표준편차 계산 방식

5. 성능 및 병렬화

6. 시각화 등 추가 활용

7. 정리

1. edge_average()란?

1.1 동작 방식

1.2 시간 복잡도 및 병렬화

2. 간단 예시 코드

코드 해설

3. 다른 예시: 실제 가중치나 길이 등

4. 표준편차(std) 계산 의미

5. 시각화 / 후처리

6. 요약

1. distance_histogram() 개요

1.1 최단거리의 의미

1.2 시간 복잡도

2. 기본 사용 예시

코드 해설

3. 샘플링(samples)을 활용한 최단거리 분포 추정

4. 가중치(weight) 있는 그래프

5. 주의사항 및 팁

6. 시각화 아이디어

7. 정리

graph_tool.spectral Operator objects

graph_tool.topology 1

0개의 댓글

1. `vertex_hist()`란?

1. `edge_hist()` 개요

4. `float_count=True/False` 차이

1. `vertex_average()`의 기본 개념

1. `edge_average()`란?

4. 표준편차(`std`) 계산 의미

1. `distance_histogram()` 개요

3. 샘플링(`samples`)을 활용한 최단거리 분포 추정