실행 불가능한 정확함 vs 실행 가능한 근사: 빅데이터 그래프의 선택

마케팅 데이터가 커지면 어느 순간 이런 생각이 든다.

“이 알고리즘, **이제는 너무 느린데… 바꿀 수 없을까?”

이번 글은 네트워크 중심성(중요 고객 찾기) 예시를 가지고 아래 3가지 개념을 이해할 수 있도록 정리해 보려고 한다.

  • 언제 Exact 알고리즘(정확하지만 느린 방식) 을 쓰고
  • 언제 Proxy/Sampling 알고리즘(근사지만 빠른 방식) 으로 바꾸는 게 좋은지
  • 그리고 어떻게 검증해볼 수 있는지

1. 문제 상황: 고객 네트워크에서 “핵심 허브”를 찾고 싶을 때

요즘 마케팅 데이터는 점점 관계형이다.

  • 누가 누구에게 송금/결제를 했는지
  • 누가 누구를 추천했는지
  • 어떤 채널·인플루언서를 통해 고객이 유입되었는지

이런 데이터가 쌓이면 자연스럽게 그래프가 된다.

  • 노드(node) = 고객, 계정, 지갑, 채널
  • 간선(edge) = 추천, 거래, 클릭, 전환 등
  • 가중치(weight) = 거래 금액, 횟수, 전환 수

이때 자주 하는 질문은 이렇다.

  • “이 네트워크에서 가장 영향력 큰 고객은 누구일까?”
  • “어디를 막으면 전체 흐름이 크게 줄어들까?”
  • “어디를 타겟팅하면 파급력이 가장 클까?”

그래프 이론에서는 이런 질문에 답하기 위해 중심성(centrality) 지표를 사용한다. 이를 위해 다음 2가지 “그래프에서 중심을 찾는 계산법”을 이해해야 한다.

항목Exact Closeness Centrality (정확 계산)Degree Proxy (근사 계산)
핵심 아이디어모든 노드까지의 평균 최단거리가 짧을수록 중심이다연결 강도(가중 in/out degree)가 높을수록 중심이다
계산 방식각 노드에서 출발해 전체 그래프 최단거리 탐색각 노드의 가중 in/out degree를 한 번씩만 집계한다
계산 복잡도O(N²) 수준 (≈ O(N × (V+E)))O(N) 수준 (O(V+E), 그래프 한 번 스캔)
작은 그래프(Small, < 1만)1분 미만 → 빠름0.1초 미만 → 매우 빠름
중간 그래프(Medium, 5만)30분 ~ 1시간 → “좀 오래 걸린다”1초 미만 → “바로 끝난다”
대형 그래프(Large, 20만)수일 ~ 수주 (사실상 실행 불가)3~5초 내외 → 실행 가능
Massive (100만+)이론상 수십 년, 현실적으로 불가능분 단위 → 여전히 실무 범위 내
장점이론적으로 가장 정확한 전역 중심성매우 빠르고, 상위 핵심 노드 순위가 잘 보존되는 편이다
단점빅데이터에서는 시간·리소스 비용이 너무 크다거리 정보를 직접 보지 않아 근사값에 불과하다
이런 경우에 적합소규모 그래프, 연구용 정밀 분석대형/빅데이터 그래프, 운영 배치·실시간 분석


2. Exact Closeness vs Degree Proxy – 개념 비교

2.1 Exact Closeness (정확 알고리즘)

Closeness Centrality의 아이디어는 단순하다.

“이 노드는 시스템 전체 관점에서 전역적으로 중요한 허브인가?”를
알려주는 지표이다.

예시 그래프를 보자.

import networkx as nx

G = nx.Graph()
G.add_edges_from([
    ("U1", "U2"),
    ("U1", "U3"),
    ("U2", "U4"),
    ("U3", "U4"),
    ("U3", "U5"),
])

closeness = nx.closeness_centrality(G)
print(closeness)

U3처럼 여러 노드와 짧은 경로로 연결된 노드는 Closeness 값이 높게 나온다. 마케팅 관점에서는 “신호를 한 번 줬을 때, 네트워크 전체로 빠르게 퍼질 가능성이 높은 고객”이다.문제는 이 알고리즘이 많이 느리다는 점이다. 모든 노드 쌍에 대한 최단 거리를 계산해야 해서, 노드 수가 커지면 계산량이 폭발한다.

2.2 Degree Proxy (근사 알고리즘)

Degree Proxy는 훨씬 직관적이다.

“이 노드는 주변 이웃들과 어떤 관계 패턴을 가지는가?”에

초점을 둔 지표이다.

방법은 간단하다.

import networkx as nx
import numpy as np

G = nx.DiGraph()
edges = [
    ("U1", "U2", 100),
    ("U3", "U1", 50),
    ("U3", "U2", 300),
]
for s, t, w in edges:
    G.add_edge(s, t, weight=w)

in_deg = dict(G.in_degree(weight="weight"))
out_deg = dict(G.out_degree(weight="weight"))

max_in = max(in_deg.values()) or 1
max_out = max(out_deg.values()) or 1

proxy = {}
for n in G.nodes():
    ni = in_deg.get(n, 0) / max_in
    no = out_deg.get(n, 0) / max_out
    proxy[n] = (ni + no) / 2

print(proxy)

여기서 Degree Proxy는 각 노드에 대해 들어오는 금액(in-degree 가중 합) 과 나가는 금액(out-degree 가중 합) 을 구한 뒤, 이를 0~1 사이로 정규화해서 평균 낸 점수이다.

즉, 이 지표는

“이 주소가 **바로 연결된 상대(1-hop 이웃)**들과
얼마나 많이, 얼마나 자주 거래하는지”

를 숫자로 표현한 것이다.

이때 계산에 사용하는 정보는 오직 1-hop(직접 연결) 까지이다. 반대로 Exact Closeness는 이 노드에서 그래프 모든 노드까지의 최단 거리를 다 쓰기 때문에, 2-hop, 3-hop… 전체 hop 구조를 반영한다. 그래서 Degree Proxy는 1-hop 연결 강도를 기준으로 한 간단한 중심성이고, 속도와 단순함을 얻는 대신, Exact Closeness처럼 그래프 전체 거리 구조를 세밀하게 보지는 못하는 근사치라고 이해하는 것이 맞다.

3. 빅데이터에서 중요한 건 “복잡도(계산량)”이다

이제 실제로 두 중심을 찾는 계산법이 그래프 규모별로 어떤 차이를 만드는지를 보자.

3.1 체감 속도 비교 표

가정:

  • Exact 알고리즘: O(N²) (Closeness 계열)
  • Proxy/Sampling: O(N) (Degree 위주)

시간은 대략적인 체감 수준이다.

그래프 규모 (노드 수 N)Exact 알고리즘 (O(N²))Proxy/Sampling (O(N))체감 차이비고
Small (1만 미만)1분 미만0.1초 미만미미함둘 다 순식간에 끝나서 차이를 못 느낀다.
Medium (5만)30분 ~ 1시간1초 미만느껴짐“어? 좀 걸리네?” vs “지금 끝났네?”
Large (20만)수일 ~ 수주 (사실상 Timeout)3~5초극단적실행 불가 vs 실행 가능의 차이로 바뀐다.
Massive (100만+)이론상 수십 년 (현실적 불가능)분 단위불가능 수준슈퍼컴퓨터가 아니면 Exact는 선택지에서 사라진다.

핵심은 Large, Massive 데이터 구간이다.

3.2 왜 이렇게까지 차이가 나는가?

Exact Closeness

Exact Closeness는 그래프 전체 거리 구조를 끝까지 계산하는 방식이다.
그래서 전역 구조를 가장 충실하게 반영하지만, 그만큼 계산량이 폭발한다.

  • 노드가 2배 늘어나면 계산량은 4배(≈ O(N²)) 늘어난다.
  • 노드가 10배 늘어나면 계산량은 100배가 된다.

간단한 숫자로 보면:

  • (10{,}000^2 = 100{,}000{,}000) → 1억 번 연산
  • (200{,}000^2 = 40{,}000{,}000{,}000) → 400억 번 연산

이 정도 규모가 되면,
일반적인 시스템에서는 사실상 돌리기 어려워진다.

장점:

  • 전역 구조를 가장 정확하게 반영하는 중심성이다.
  • “정확한 이론적 기준점(ground truth)”으로 쓰기에는 최적이다.

단점:

  • 빅데이터에서는 “이론적으로는 좋지만, 실무에서는 못 돌리는 알고리즘” 이 된다.

Degree Proxy

Degree Proxy는 발상을 바꾼다.

“그래프 전체 최단 거리를 다 계산하는 대신,
각 노드의 **1-hop 연결 강도(가중 in/out degree)**로 대략적인 중심성을 대신 보자.”

  • 노드가 2배 늘어나면 계산량도 **딱 2배(≈ O(N))**만 늘어난다.
  • 간선 기준으로 봐도 **그래프 한 번 스캔 수준(O(V+E))**이다.

예를 들어 노드 20만 개라면:

  • 계산량은 대략 20만 번 + 간선 수 스캔
  • 현대 CPU 입장에서는 “일도 아닌” 수준이다.

그 대신 감수하는 부분이 있다.

  • Degree Proxy는 직접 연결된 1-hop 이웃과의 거래 강도만 보기 때문에,
    Exact Closeness처럼 전체 hop 구조와 전역 거리 패턴을 그대로 반영하지는 못한다.
  • 즉, 속도와 실행 가능성을 얻는 대신, 전역 구조 관점에서의 정확성을 일부 포기한 근사 중심성이다.

정리하면

  • Exact Closeness
    • ✅ 가장 정확한 전역 중심성
    • ❌ 대형 그래프에서는 시간·리소스 비용이 너무 커서 “실행 불가”에 가깝다.
  • Degree Proxy
    • ✅ 수십만 노드도 몇 초 안에 처리 가능한 속도 (O(N))
    • ❌ 1-hop 정보만 쓰다 보니, 전역 거리 구조를 반영하는 정밀도는 내려간 근사값이다.

그래서 현실적으로 빅데이터(대형 그래프)를 다룰 때는 “완벽한 정확성(Exact Closeness)” vs “실제로 돌아가는 근사(Degree Proxy)” 중에서 후자를 선택하고, 그 근사가 내 데이터에서 어디까지 유효한지를 별도 검증으로 확인하는 전략이 더 현실적이다. 또는 전역 허브를 찾는 과제가 아니라, 1~3 hop 기반의 군집 분석이 목적이라면 오히려 Degree Proxy가 더할 나위 없이 유리한 선택이 될 수 있다.

4. 언제 “이 알고리즘(Proxy)”을 쓰는 게 좋은가?

실무에서 알고리즘을 교체할 기준을 몇 가지로 정리해보겠다.

4.1 이런 상황이면 Degree Proxy를 고려할 만하다

  1. 그래프 규모가 커졌을 때 (노드 50K 이상)
    • Closeness 한 번 돌리는 데 30분~1시간 이상 걸리기 시작한다.
    • 파이프라인이 매일/매시간 돌아야 하면 부담이 커진다.
  2. 배치/리포트 마감 시간이 빡빡할 때
    • 예: 새벽 배치 2시간 안에
      • ETL + 피쳐 엔지니어링 + 모델링 + 레포트 생성이 모두 끝나야 하는 경우
    • 여기서 Closeness 하나가 1시간을 잡아먹으면 다음 단계가 밀리기 시작한다.
  3. 정확한 값보다 “순위/우선순위”가 중요할 때
    • 핵심 고객 Top 1%, 영향력 높은 채널 Top 100을 찾는 것이 목적일 때 0.12345 vs 0.12346 같은 미세한 차이는 의미가 줄어든다.
    • “누가 상위 그룹에 들어오느냐”가 더 중요하다.

이런 조건이 맞으면, Exact → Proxy로 전환을 적극적으로 고려할 수 있다.

4.2 하이브리드 전략: 작은 건 Exact, 큰 건 Proxy

완전히 갈아타는 대신 혼합 전략도 좋다.

  • 노드 수 < 50K인 작은 그래프 → 그대로 Closeness(Exact) 사용
  • 노드 수 ≥ 50K인 대형 그래프 → Degree Proxy 사용

이렇게 하면:

  • 작은 세그먼트/캠페인 분석에서는 여전히 정교한 전역 중심성을 쓰고,
  • 대형 전체 네트워크 분석에서는 “실제로 돌아가는” 알고리즘을 쓸 수 있다.

빅데이터 환경에서는 이런 스케일 기반 스위칭 전략이 현실적인 해답이 되는 경우가 많다.

5. “이렇게 바꿔서 실행해볼 수 있다” – 코드 레벨 감각

실제 파이프라인에서라면 로직은 대략 이렇게 갈 수 있다 (의사 코드 수준).

import networkx as nx

def compute_centrality(G, use_proxy_threshold=50000):
    n_nodes = G.number_of_nodes()
    
    # 1) 항상 계산하는 값 (ex. degree 기반)
    in_deg = dict(G.in_degree(weight="weight"))
    out_deg = dict(G.out_degree(weight="weight"))
    
    max_in = max(in_deg.values()) or 1
    max_out = max(out_deg.values()) or 1
    
    degree_proxy = {
        n: (in_deg.get(n, 0)/max_in + out_deg.get(n, 0)/max_out) / 2
        for n in G.nodes()
    }
    
    # 2) 그래프가 작으면 Exact Closeness도 계산
    if n_nodes < use_proxy_threshold:
        closeness = nx.closeness_centrality(G, distance="distance")
    else:
        closeness = degree_proxy  # 큰 그래프에서는 Proxy로 대체
    
    return {
        "degree_proxy": degree_proxy,
        "closeness_like": closeness,
    }

실제 구현에서는 더 많은 요소가 있겠지만, “노드 수 기준으로 Exact vs Proxy를 분기한다” 라는 구조는이 정도로 단순하게도 잡을 수 있다.

6. “이건 이렇게 검증해볼 수도 있다” – 최소 검증 프로세스

알고리즘을 바꿀 때 중요한 건 “느려서 못 돌리던 걸 빠르게 만들었다”가 아니라, “결과가 과연 얼마나 달라지는가?”를 숫자로 확인하는 일이다. 복잡한 실험이 아니라, 딱 필요한 것만 체크하는 프로세스로 정리해보면 아래와 같다.

단계/지표목적어떻게 하는지해석/비고
① 샘플 노드 추출전체 대신 일부만 뽑아 빠르게 검증한다대형 그래프에서 노드 1,000~5,000개를 무작위 샘플링한다샘플만으로도 경향과 관계성은 충분히 확인 가능하다
② Exact Closeness 계산Proxy와 비교할 “정답 값”을 만든다그래프 전체로 Closeness를 돌린 뒤, 샘플 노드 값만 꺼낸다느리지만 샘플 수가 적어서 한 번 정도는 계산 가능하다
③ Degree Proxy 매칭같은 노드의 근사값을 옆에 붙인다샘플 node_id 기준으로 미리 계산해둔 degree_proxy를 조인closeness_exact vs degree_proxy를 1:1로 비교할 준비 단계이다
④ Spearman 상관 (필수)순위 구조가 비슷한지 본다두 컬럼으로 spearmanr(Exact, Proxy)를 계산한다ρ가 높을수록 순위 구조가 잘 보존된 것이다
⑤ Top-k Overlap (필수)상위 핵심 그룹이 유지되는지 확인한다Exact/Proxy 상위 1% 노드 집합의 Jaccard Overlap을 계산한다비율이 높을수록 “핵심 허브 집합”이 잘 보존된다
⑥ Scatter Plot (선택)관계를 직관적으로 보여준다X=degree_proxy, Y=closeness_exact로 산점도를 그린다우상향 패턴이면 “Proxy가 경향을 잘 따른다”이다
⑦ 추가 검증 (선택)상위 구간·k별 정밀도를 더 세분화한다상위 10~20% Spearman, Precision@k 등을 본다데이터 특성상 Proxy가 잘 안 맞는 경우를 찾아낸다

6.1 샘플링으로 Exact vs Proxy 비교

대형 그래프(예: 노드 20만 개)에서는 모든 노드에 대해 Exact Closeness를 계산하기가 현실적으로 어렵다. 그래서 “일부 노드만 뽑아서 맛보기로 비교해보는 방식”을 쓴다.

작업의 흐름은 다음과 같다.

  1. 샘플 노드 뽑기
    • 전체 노드(예: 200,000개) 중에서
      1,000~5,000개 정도를 무작위로 샘플링한다.
    • 이게 오늘 검증할 “검사 대상 고객 리스트”이다.
  2. 샘플에 대해 Exact Closeness 계산
    • 그래프는 전체를 그대로 둔 상태에서 Closeness를 한 번 계산하고,
      그 결과 중 샘플 노드에 해당하는 값만 꺼낸다.
    • 이렇게 해서 closeness_exact 컬럼이 생긴다.
  3. 같은 노드에 대해 Degree Proxy 값 붙이기
    • Degree Proxy는 이미 전체 노드에 대해 계산해둔 상태라고 가정한다.샘플 노드 리스트를 기준으로, Proxy 값을 node_id로 조인해서 옆에 붙인다.
    예를 들어 샘플 테이블은 대략 이런 형태가 된다. node_id closeness_exact degree_proxy ------------------------------------------ U000123 0.213 0.81 U004567 0.075 0.24 U012345 0.180 0.72 ... 이제 각 노드에 대해 정확 값(Exact) 과 근사 값(Proxy)이 한 줄에 나란히 있는 상태가 된다.
  4. 무엇을 비교할 것인가 – 기본적으로는 두 가지만 본다
    • (1) 순위 구조가 비슷한가?
      Exact로 정렬했을 때 1등, 2등, 3등이 Proxy로 정렬했을 때도 비슷하게 상위에 오는지 본다.
    • (2) 상위 그룹(Top-k)이 비슷한가?
      예를 들어 상위 1% 핵심 고객 리스트가 Exact와 Proxy에서 얼마나 겹치는지 본다.

이 두 지표가 충분히 높다면,
“완벽하게 같지는 않아도 실무에서 쓸 만한 정도로는 잘 따른다”라고 판단할 수 있다.

다만 데이터 특성에 따라 이 두 지표가 생각보다 낮게 나오는 경우도 있다. 특히 크립토 온체인 데이터처럼 허브 구조가 극단적으로 치우친 네트워크에서는 Degree 기반 Proxy가 Closeness를 잘 대변하지 못할 수 있다. 그래서 아래에서 설명하는 추가 검증(상위 구간 Spearman, Precision@k)까지 함께 보는 것을 권장한다.

Okamoto, K., Chen, W., & Li, X.-Y. (2008). Ranking of Closeness Centrality for Large-Scale Social Networks. Frontiers in Algorithmics (FAW 2008), LNCS 5059.
→ closeness 값을 전부 정확히 구하는 것보다, 대규모 그래프에서 closeness 상위 노드의 랭킹을 빠르게 찾는 문제에 집중하며, 랭킹/상위 노드 보존을 실용적인 목표로 삼는 논문이다.

Saxena, A., Gera, R., & Iyengar, S. R. S. (2017). A Faster Method to Estimate Closeness Centrality Ranking. arXiv:1706.02083.
→ 전통적인 정확 계산 대신 closeness 랭킹을 빠르게 근사하는 방법을 제안하고, 평가에서도 절대값보다는 랭킹 및 랭킹 오차를 중심 지표로 사용하는 논문이다.

6.2 지표 ① Spearman Rank Correlation (순위 구조 유지 여부)

첫 번째 검증 포인트는 **“순위 구조가 얼마나 비슷한지”**이다.
점수 자체(0.123 vs 0.124)의 차이보다,
누가 더 중요하다고 랭크되는지가 더 중요하다.

그래서 스피어만 순위 상관계수(Spearman Rank Correlation) 를 쓴다.

from scipy.stats import spearmanr

rho, p = spearmanr(df["closeness_exact"], df["degree_proxy"])
print("Spearman rho:", rho)
  • rho 값이 1에 가까울수록
    → 두 점수의 순위가 거의 동일하다는 뜻이다.
  • 0에 가까울수록
    → “누가 상위인지”가 거의 랜덤에 가깝다는 뜻이다.

실무 기준으로는 대략

  • ρ ≈ 0.7 이상이면
    → “순위 구조가 꽤 잘 유지된다”
  • ρ ≈ 0.5 전후면
    → “일부 구간은 맞지만, 전체적으로는 많이 섞인다”

정도로 해석할 수 있다.
(구체 기준은 도메인/데이터에 따라 보수적으로 조정하면 된다.)

6.3 지표 ② Top-k Overlap (핵심 상위 그룹 유지 여부)

두 번째 검증 포인트는 **“정말 중요한 상위 그룹이 유지되느냐”**이다.
실무에서는 결국 상위 몇 % 고객을 타겟팅하는 경우가 많기 때문이다.

검증 과정은 다음과 같다.

  1. Exact Closeness 기준 상위 1% 노드 집합을 구한다.
    • 예: top_exact
  2. Degree Proxy 기준 상위 1% 노드 집합을 구한다.
    • 예: top_proxy
  3. 이 두 집합이 얼마나 겹치는지를 계산한다.
def jaccard_overlap(s1, s2):
    s1, s2 = set(s1), set(s2)
    return len(s1 & s2) / len(s1 | s2) if s1 or s2 else 0.0
  • 이 값이 0.7~0.8 이상이면,
    “실제로 챙겨야 할 핵심 허브 집합은 잘 유지된다”라고 볼 수 있다.
  • 예를 들어 상위 100명을 뽑는다고 했을 때
    그중 70~80명 이상이 Exact와 Proxy에서 공통으로 뽑힌다는 뜻이다.

다만, 크립토 네트워크처럼 극단적으로 허브가 많은 그래프에서는 이 값이 20~30% 수준으로 낮게 나올 수도 있다. 이 경우에는 단순히 “Proxy를 쓰면 충분하다”고 말하기보다는, 다음 섹션의 추가 검증 지표까지 함께 보고 Proxy의 역할을 “보조 스코어” 정도로 위치시키는 것이 안전하다.

6.4 추가 검증 ① 상위 구간별 Spearman

전체 구간에서 Spearman r을 한 번만 계산하면 “대충은 알겠지만 어디에서 깨지는지”는 잘 보이지 않는다. 그래서 상위 구간별로 잘리는 Spearman을 한 번 더 본다.

예시:

  1. Exact 기준으로 내림차순 정렬
  2. 상위 20%, 10%, 5%, 1% 구간을 각각 자른다.
  3. 각 구간에서 다시 spearmanr(exact, proxy)를 계산한다.

해석은 단순하다.

  • 상위 10%/5%에서 r이 확 올라간다면
    → “진짜 최상위 구간에서는 Proxy가 순위를 꽤 잘 맞춘다”
  • 상위 구간에서도 r이 낮게 유지되면
    → “이 데이터 구조에서는 Degree Proxy가 Closeness를 잘 설명하지 못한다”

같은 Ethereum 스테이블코인 네트워크처럼 허브 구조가 강한 크립토 데이터에서는 “전체 r은 0.5 수준인데, 상위 5%에서도 크게 오르지 않는” 케이스가 나올 수 있다. 이때는 Proxy를 보조 지표로만 쓰는 것이 맞다.

6.5 추가 검증 ② Precision@k (k별 상위 정확도)

Top-1% Overlap은 한 지점(1%)만 찍어보는 지표이다.
조금 더 입체적으로 보려면 k를 바꿔가며 Precision@k를 그려볼 수 있다.

  • X축: k (예: 100, 200, 500, 1,000, …, 5,000)
  • Y축: Precision@k = |Top-k_exact ∩ Top-k_proxy| / k

해석 예시:

  • k=100에서 Precision@k = 0.60
    → 최상위 100명 중 60명은 Exact와 Proxy가 동일하게 뽑는다.
  • k=1,000에서 Precision@k = 0.30
    → k가 커질수록 Proxy의 분별력이 떨어진다.

이 그래프 하나만 있어도,

  • “Proxy를 Top-100 후보 발굴용으로는 쓸 만하다”
  • “Top-2000 이상을 다루는 정밀 분석에는 적합하지 않다”

같은 식으로 실무적인 cut-off를 설정할 수 있다.

정리

  • 최소 검증으로는 Spearman r, Top-k Overlap, 두 개면 충분하다.
  • 다만 크립토 온체인 데이터처럼 구조가 특이한 네트워크에서는 이 두 지표가 기대보다 낮게 나올 수 있다.
    • 예를 들어 다음과 같은 이유 때문이다.
      • 극단적인 허브 + 긴 꼬리 구조 몇 개 주소(거래소, 브리지, 컨트랙트)에 거래가 과도하게 몰려 있고, 나머지 대부분 주소는 소량·단발 거래만 가진다. 이 경우 Degree Proxy는 “허브 vs 나머지”만 강하게 구분하고, 그 밖의 노드들은 거의 비슷한 점수(거의 0)에 몰리기 때문에 Closeness처럼 미세한 순위 차이를 섬세하게 표현하지 못한다.
      • 지역 허브(Local Hub)가 많은 구조 온체인에서는 특정 프로토콜·체인·커뮤니티 내부에서만 활발한 “동네 허브”들이 많다. 이 노드들은 degree는 크지만, 전체 네트워크 기준으로는 다른 커뮤니티와의 연결성(전역 거리 구조)가 좋지 않아서 Closeness와 Degree가 서로 다른 방향을 가리키는 경우가 많다.
      • 단기·일회성 플로우가 많음 에어드랍, 이벤트, MEV, 봇 거래처럼 짧은 기간에 폭발적으로 발생했다가 사라지는 플로우가 많다. 이런 노드들은 degree는 높아도 네트워크의 “지속적인 중심”이라고 보기는 어렵기 때문에 Degree Proxy가 일시적 노이즈를 과대평가할 수 있다.
    • 이런 이유로 크립토 온체인 네트워크에서는 Spearman, Top-k Overlap만으로는 Proxy의 한계를 다 보기 어렵다. 이때는 상위 구간별 Spearman, Precision@k 같은 추가 검증까지 함께 보면서 “Proxy를 어디까지 믿을 것인지”를 데이터셋별로 다시 결정하는 편이 안전하다.

7. 마무리: 빅데이터를 다룰 때 Degree Proxy 알고리즘을 추천하는 이유

정리해보면, 빅데이터 환경에서 이 알고리즘(Weighted Degree Proxy)을 추천할 수 있는 이유는 세 가지이다.

  1. 속도
    • Exact Closeness: (O(N^2)) → 대형 그래프에서 사실상 실행 불가
    • Degree Proxy: (O(N)) → 수십만 노드도 몇 초 안에 처리 가능
  2. 실무 목적 적합성
    • 마케팅 의사결정에서는 “정확한 거리 값”보다 “누가 상위 그룹에 들어오는가(순위)”가 더 중요하다.
    • Degree Proxy는 이 순위를 충분히 잘 근사한다.
  3. 검증 가능성
    • 샘플링 + Spearman + Top-k Overlap으로 Proxy의 타당성을 빠르게 검증할 수 있다.
    • 검증만 통과하면, 이후에는 안심하고 대형 그래프에 적용할 수 있다.

태그