Step 5. 링크 생성 알고리즘

이 문서에서 다루는 내용: 필터링된 키워드 노드들 사이에 두 종류의 엣지(직접 연관 엣지, 동시출현 엣지)를 생성하고, 각 엣지에 정규화된 연결 강도(strength)를 부여하여 최종 GraphData를 완성합니다.

1. 요구사항

PM 김도연:

"이준혁 님, 지난 단계에서 노드 필터링과 그룹 할당까지 끝났잖아요. 그런데 지금 상태로는 키워드들이 그냥 점으로만 있는 거고, 점과 점 사이에 선이 없으니까 그래프가 안 되는 거죠?"

"마케팅팀에서 원하는 건 '이 키워드와 저 키워드가 얼마나 관련 있는지'를 선의 굵기로 보고 싶다는 거예요. 연결 방식은 두 가지가 필요합니다. 첫째, 시드 키워드에서 직접 연관된 키워드로 이어지는 선. 둘째, 서로 다른 시드에서 공통으로 등장하는 키워드끼리도 연결이 되면 좋겠어요. 예를 들어 '감자빵'을 검색해서 나온 키워드랑 '강황'을 검색해서 나온 키워드 중에 겹치는 게 있으면, 그것도 하나의 관계라고 볼 수 있으니까요."

"그리고 선마다 연결 강도 숫자가 있으면, 나중에 그래프에서 굵기를 다르게 표현할 수 있을 것 같습니다. 강하게 연결된 키워드 쌍은 굵은 선, 약하게 연결된 건 가는 선 -- 이런 식으로요."

2. 시니어의 접근 방식

시니어 이준혁 (8년차):

"자, Phase 3까지 끝나서 지금 손에 뭐가 있는지 정리해보자. filteredNodeIds라는 Set이 있고, nodeMap에 각 노드의 상세 정보가 있고, seedToRelated에 시드별 연관 키워드 목록이 있고, keywordToSeeds에 각 키워드가 어느 시드 파일들에 등장했는지가 들어 있어. 재료는 다 준비됐어."

"이제 이것들을 가지고 **링크(엣지)**를 만들 건데, 그래프 이론에서 노드만 있고 엣지가 없으면 뭐겠어? 그냥 점 뿌려놓은 거지. 엣지가 있어야 비로소 '관계'가 보이기 시작해."

"링크를 두 종류로 나눌 거야."

"(a) 직접 연관 엣지 -- 시드 키워드와 그 연관 키워드를 잇는 선이야. '감자빵'을 검색했더니 '감자빵 레시피'가 나왔으면, '감자빵'에서 '감자빵 레시피'로 선을 긋는 거지. 이건 직관적이야."

"(b) 동시출현(co-occurrence) 엣지 -- 이건 좀 더 재밌어. '감자빵 레시피'라는 키워드가 '감자빵' 파일에도 있고 '감자칩' 파일에도 있다고 해봐. 그러면 '감자빵 레시피'와 '감자칩'은 직접적인 연관은 아니지만, 같은 맥락에서 자주 등장한다는 뜻이야. 이런 간접 관계까지 잡아주면 그래프가 훨씬 풍부해져."

"여기서 질문 하나. 두 키워드 사이에 엣지를 만들 때, A에서 B로 잇는 것과 B에서 A로 잇는 걸 다르게 봐야 할까? 우리 그래프에서 방향성이 의미가 있을까?"

"답은 '아니다'야. 우리 그래프는 **무방향 그래프(undirected graph)**야. '감자빵'과 '감자빵 레시피' 사이의 연관은 양쪽에서 다 성립하니까. 그래서 A-B와 B-A를 같은 엣지로 취급해야 해. 이걸 어떻게 구현하느냐가 이번 Phase의 첫 번째 포인트야."

"두 번째 포인트는 strength 정규화야. 엣지마다 '이 연결이 얼마나 강한가'를 0에서 1 사이의 숫자로 매기는 건데, (a)와 (b)에서 계산 방식이 달라. 각각 왜 다른 공식을 쓰는지, 그 의미가 뭔지를 이해하는 게 중요해."

"세 번째 포인트는 복잡도야. (b) 동시출현 엣지를 만들 때 이중 루프를 돌거든. 노드가 100개면 약 5,000번 비교, 1,000개면 약 500,000번 비교. 이게 감당 가능한 수준인지 머릿속으로 계산하는 습관을 들여야 해."

"코드로 가자."

3. 구현

3.1 Phase 4 전체 코드

먼저 Phase 4의 전체 코드를 보고, 이후 각 부분을 상세히 분석합니다.

// src/lib/buildGraph.ts (Phase 4: 링크 생성, lines 99-161)
 
  // ── Phase 4: 링크 생성 ──
  const maxSeedCount = Math.max(...[...nodeMap.values()].map(n => n.seedCount));
  const links: KeywordLink[] = [];
  const linkSet = new Set<string>();
 
  // (a) seed → 연관 키워드 엣지
  for (const [seedKeyword, relateds] of seedToRelated) {
    if (!filteredNodeIds.has(seedKeyword)) continue;
 
    for (const rel of relateds) {
      if (rel === seedKeyword) continue;
      if (!filteredNodeIds.has(rel)) continue;
 
      const key = [seedKeyword, rel].sort().join('||');
      if (linkSet.has(key)) continue;
      linkSet.add(key);
 
      const targetNode = nodeMap.get(rel)!;
      links.push({
        source: seedKeyword,
        target: rel,
        strength: targetNode.seedCount / maxSeedCount,
      });
    }
  }
 
  // (b) 동시출현 엣지 (2개 이상 파일에서 함께 등장한 쌍만)
  const filteredIds = [...filteredNodeIds];
  const totalSeeds = seedKeywords.length;
 
  for (let i = 0; i < filteredIds.length; i++) {
    const seedsA = keywordToSeeds.get(filteredIds[i]);
    if (!seedsA) continue;
 
    for (let j = i + 1; j < filteredIds.length; j++) {
      const key = [filteredIds[i], filteredIds[j]].sort().join('||');
      if (linkSet.has(key)) continue;
 
      const seedsB = keywordToSeeds.get(filteredIds[j]);
      if (!seedsB) continue;
 
      // 교집합 크기 계산
      let overlap = 0;
      for (const s of seedsA) {
        if (seedsB.has(s)) overlap++;
      }
 
      if (overlap >= 2) {
        linkSet.add(key);
        links.push({
          source: filteredIds[i],
          target: filteredIds[j],
          strength: overlap / totalSeeds,
        });
      }
    }
  }
 
  // 필터된 노드 수집
  const nodes = filteredIds.map(id => nodeMap.get(id)!);
 
  return { nodes, links };
}

이 코드는 크게 네 부분으로 나뉩니다: (1) 사전 준비, (2) 직접 연관 엣지 생성, (3) 동시출현 엣지 생성, (4) 최종 반환. 하나씩 뜯어봅시다.

3.2 사전 준비 -- maxSeedCount와 linkSet

// src/lib/buildGraph.ts (lines 100-102)
 
const maxSeedCount = Math.max(...[...nodeMap.values()].map(n => n.seedCount));
const links: KeywordLink[] = [];
const linkSet = new Set<string>();

이준혁: "세 줄인데 각각 역할이 뚜렷해."

maxSeedCount -- 정규화를 위한 기준값

nodeMap에 있는 모든 노드의 seedCount 중 최댓값을 구합니다. 이 값은 나중에 (a) 직접 연관 엣지의 strength를 계산할 때 분모로 쓰입니다.

동작을 추적해봅시다. 시드 파일이 "감자빵", "강황", "마라탕" 세 개라고 가정합니다:

nodeMap의 상태:
  "감자빵"       → seedCount: 3 (세 파일 모두에서 등장)
  "감자빵 레시피" → seedCount: 2 (감자빵, 강황 파일에서 등장)
  "강황 효능"    → seedCount: 1 (강황 파일에서만 등장)
 
maxSeedCount = Math.max(3, 2, 1) = 3

이준혁: "왜 최댓값으로 나누느냐고? 가장 많은 시드에서 등장한 키워드의 strength를 1.0(최대)으로 만들기 위해서야. 나머지는 그에 비례한 값이 되는 거지. 이걸 min-max 정규화라고 해."

links -- 결과를 담을 배열

KeywordLink[] 타입의 빈 배열입니다. Step 1에서 설계한 타입 그대로입니다:

// src/types/graph.ts
export interface KeywordLink {
  source: string;   // 출발 노드 id
  target: string;   // 도착 노드 id
  strength: number; // 연결 강도 (0~1)
}

linkSet -- 중복 엣지 방지를 위한 Set

이 Set이 Phase 4 전체를 관통하는 핵심 장치입니다. 이미 만든 엣지인지를 빠르게 확인(O(1))하는 용도입니다.

3.3 (a) 직접 연관 엣지 생성

// src/lib/buildGraph.ts (lines 104-123)
 
// (a) seed → 연관 키워드 엣지
for (const [seedKeyword, relateds] of seedToRelated) {
  if (!filteredNodeIds.has(seedKeyword)) continue;
 
  for (const rel of relateds) {
    if (rel === seedKeyword) continue;
    if (!filteredNodeIds.has(rel)) continue;
 
    const key = [seedKeyword, rel].sort().join('||');
    if (linkSet.has(key)) continue;
    linkSet.add(key);
 
    const targetNode = nodeMap.get(rel)!;
    links.push({
      source: seedKeyword,
      target: rel,
      strength: targetNode.seedCount / maxSeedCount,
    });
  }
}

단계별로 분석합니다.

1단계: 외부 루프 -- 시드별 순회

for (const [seedKeyword, relateds] of seedToRelated) {
  if (!filteredNodeIds.has(seedKeyword)) continue;

seedToRelated는 Map<string, string[]> 타입으로, 각 시드 키워드와 그 연관 키워드 목록을 담고 있습니다 (Phase 1에서 구축). 시드 자체가 필터링에서 탈락했다면 건너뜁니다.

2단계: 내부 루프 -- 연관 키워드별 순회 + 가드 조건

for (const rel of relateds) {
  if (rel === seedKeyword) continue;       // 자기 자신과의 엣지 방지
  if (!filteredNodeIds.has(rel)) continue;  // 필터링 탈락 노드 제외

이준혁: "가드 조건이 두 개야. 첫 번째는 자기 자신을 가리키는 '셀프 루프'를 막는 거고, 두 번째는 검색량 필터를 통과한 노드만 연결하겠다는 거야. Phase 2에서 열심히 필터링해놨는데 여기서 필터 안 된 노드를 다시 끌어오면 안 되니까."

3단계: 중복 키 생성 -- [a, b].sort().join('||')

const key = [seedKeyword, rel].sort().join('||');
if (linkSet.has(key)) continue;
linkSet.add(key);

이준혁: "여기가 이번 Phase의 가장 핵심적인 트릭이야. 왜 sort()를 하는 걸까?"

무방향 그래프에서 "감자빵 -> 감자칩" 엣지와 "감자칩 -> 감자빵" 엣지는 같은 엣지입니다. 그런데 단순히 seedKeyword + '||' + rel로 키를 만들면:

"감자빵" + "||" + "감자칩" = "감자빵||감자칩"
"감자칩" + "||" + "감자빵" = "감자칩||감자빵"

두 키가 달라서 같은 엣지를 두 번 만들게 됩니다. sort()를 거치면:

["감자빵", "감자칩"].sort() → ["감자빵", "감자칩"] → "감자빵||감자칩"
["감자칩", "감자빵"].sort() → ["감자빵", "감자칩"] → "감자빵||감자칩"

순서와 상관없이 항상 같은 키가 나옵니다. 이렇게 하면 linkSet에서 한 번 체크하는 것만으로 중복을 완벽하게 걸러낼 수 있습니다.

이준혁: "구분자로 ||를 쓴 이유도 있어. 키워드 안에 -나 _는 있을 수 있지만, ||가 들어갈 일은 없거든. 충돌이 없는 구분자를 고르는 게 포인트야."

4단계: 엣지 생성 + strength 계산

const targetNode = nodeMap.get(rel)!;
links.push({
  source: seedKeyword,
  target: rel,
  strength: targetNode.seedCount / maxSeedCount,
});

strength 계산을 구체적으로 추적해봅시다:

시드 파일: "감자빵", "강황", "마라탕" (3개)
maxSeedCount = 3
 
"감자빵 레시피" → seedCount: 2 (감자빵, 강황 파일에서 등장)
  → strength = 2 / 3 = 0.667
 
"강황 효능" → seedCount: 1 (강황 파일에서만 등장)
  → strength = 1 / 3 = 0.333
 
"감자빵" → seedCount: 3 (모든 파일에서 등장)
  → strength = 3 / 3 = 1.0

이준혁: "이 공식의 의미를 생각해봐. 여러 시드 파일에서 공통으로 등장하는 키워드일수록 strength가 높아지는 거야. 왜? 여러 검색어의 연관으로 반복 등장한다는 건 그만큼 범용적이고 중요한 키워드라는 뜻이거든. 반면 딱 하나의 시드에서만 나온 키워드는 그 시드에 종속적인 키워드야."

3.4 (b) 동시출현(co-occurrence) 엣지 생성

// src/lib/buildGraph.ts (lines 125-155)
 
// (b) 동시출현 엣지 (2개 이상 파일에서 함께 등장한 쌍만)
const filteredIds = [...filteredNodeIds];
const totalSeeds = seedKeywords.length;
 
for (let i = 0; i < filteredIds.length; i++) {
  const seedsA = keywordToSeeds.get(filteredIds[i]);
  if (!seedsA) continue;
 
  for (let j = i + 1; j < filteredIds.length; j++) {
    const key = [filteredIds[i], filteredIds[j]].sort().join('||');
    if (linkSet.has(key)) continue;
 
    const seedsB = keywordToSeeds.get(filteredIds[j]);
    if (!seedsB) continue;
 
    // 교집합 크기 계산
    let overlap = 0;
    for (const s of seedsA) {
      if (seedsB.has(s)) overlap++;
    }
 
    if (overlap >= 2) {
      linkSet.add(key);
      links.push({
        source: filteredIds[i],
        target: filteredIds[j],
        strength: overlap / totalSeeds,
      });
    }
  }
}

(a)와 다르게 이번에는 모든 노드 쌍을 검사합니다. 시드-연관 관계가 아니라, 필터링된 노드끼리의 간접적인 관계를 찾는 것이기 때문입니다.

1단계: 이중 루프 -- j = i + 1의 의미

for (let i = 0; i < filteredIds.length; i++) {
  for (let j = i + 1; j < filteredIds.length; j++) {

이준혁: "j가 0이 아니라 i + 1부터 시작하는 거 보여? 이것도 무방향 그래프이기 때문이야. (A, B) 쌍과 (B, A) 쌍을 둘 다 검사할 필요가 없잖아. i < j인 쌍만 검사하면 모든 조합을 한 번씩 커버할 수 있어. 비교 횟수가 n^2에서 n(n-1)/2로 절반이 되는 거지."

노드가 100개일 때의 비교 횟수를 계산해보면:

전체 조합: 100 * 99 / 2 = 4,950번
노드 500개: 500 * 499 / 2 = 124,750번
노드 1,000개: 1,000 * 999 / 2 = 499,500번

이준혁: "이게 O(n^2) 복잡도야. 노드가 500개 이하면 문제없어. 근데 수만 개가 되면 느려질 수 있거든. 지금 우리 프로젝트에서는 키워드 데이터가 수백 개 수준이라 충분히 괜찮은데, 만약 규모가 커지면 역 인덱스(inverted index)나 해시 기반 접근으로 최적화해야 해. 이건 나중에 필요할 때 고민해도 돼."

2단계: linkSet으로 (a)에서 이미 생성된 엣지 건너뛰기

const key = [filteredIds[i], filteredIds[j]].sort().join('||');
if (linkSet.has(key)) continue;

(a)에서 직접 연관 엣지를 만들 때 이미 linkSet에 키를 넣어뒀습니다. 여기서 같은 키가 발견되면 이미 직접 연관으로 연결된 쌍이라는 뜻이므로, 동시출현 엣지를 중복으로 만들지 않습니다.

이준혁: "이게 linkSet을 (a)와 (b) 사이에서 공유하는 이유야. 하나의 Set으로 두 종류의 엣지 모두에서 중복을 관리하는 거지."

3단계: Set 교집합 계산

const seedsA = keywordToSeeds.get(filteredIds[i]);  // Set<string>
const seedsB = keywordToSeeds.get(filteredIds[j]);  // Set<string>
 
let overlap = 0;
for (const s of seedsA) {
  if (seedsB.has(s)) overlap++;
}

keywordToSeeds는 Phase 1에서 만들어둔 Map<string, Set<string>>입니다. 각 키워드가 어느 시드 파일들에 등장했는지를 담고 있습니다.

교집합 계산을 구체적으로 추적해봅시다:

시드 파일: "감자빵", "강황", "마라탕", "떡볶이" (4개)
 
키워드 A = "감자칩"
  → seedsA = {"감자빵", "강황", "마라탕"}  (3개 파일에서 등장)
 
키워드 B = "고구마칩"
  → seedsB = {"감자빵", "마라탕"}  (2개 파일에서 등장)
 
교집합 계산:
  "감자빵" ∈ seedsB? → Yes → overlap = 1
  "강황"   ∈ seedsB? → No
  "마라탕" ∈ seedsB? → Yes → overlap = 2
 
overlap = 2 → 임계값(2) 이상이므로 엣지 생성!

이준혁: "교집합 계산의 시간 복잡도가 뭘까? seedsA를 순회하면서 seedsB.has()를 호출해. Set의 has()는 O(1)이니까, 전체는 O(|seedsA|) -- 즉 seedsA의 크기에 비례해. 시드 파일이 보통 수십 개 이하니까 이 부분은 매우 빠르게 동작해."

4단계: 임계값 overlap >= 2와 strength 계산

if (overlap >= 2) {
  linkSet.add(key);
  links.push({
    source: filteredIds[i],
    target: filteredIds[j],
    strength: overlap / totalSeeds,
  });
}

이준혁: "왜 overlap >= 1이 아니라 >= 2일까? 생각해봐."

"시드 파일이 '감자빵', '강황', '마라탕', '떡볶이' 네 개라고 하자. 키워드 A와 키워드 B가 딱 하나의 파일에서만 같이 나왔어. 그 파일이 '감자빵' 파일이라면, A와 B가 정말 연관 있는 건지 아니면 그냥 '감자빵'이라는 주제에서 우연히 같이 나온 건지 구분이 안 돼."

"그런데 2개 이상의 파일에서 함께 등장했다면? '감자빵' 파일에서도 같이 나오고 '마라탕' 파일에서도 같이 나왔다는 거잖아. 서로 다른 맥락에서 반복적으로 동시 등장했다는 건, 우연이 아니라 실제로 관련이 있을 가능성이 높다는 뜻이야. 이게 임계값 2의 의미야."

strength 계산을 추적해봅시다:

totalSeeds = 4 (시드 파일 4개)
 
키워드 A와 B의 overlap = 2
  → strength = 2 / 4 = 0.5
 
키워드 C와 D의 overlap = 3
  → strength = 3 / 4 = 0.75
 
키워드 E와 F의 overlap = 4
  → strength = 4 / 4 = 1.0 (모든 시드에서 동시 등장)

이준혁: "(a) 직접 연관 엣지의 strength가 seedCount / maxSeedCount이고, (b) 동시출현 엣지의 strength가 overlap / totalSeeds야. 공식이 다른 이유를 알겠어? (a)는 개별 노드의 중요도를 반영하는 거고, (b)는 두 노드 사이의 공유도를 반영하는 거야. (b)의 공식은 Jaccard 유사도와 비슷한 개념이야 -- '전체 시드 중에서 이 둘이 함께 나타난 비율이 얼마냐'를 재는 거지."

3.5 최종 반환 -- GraphData 완성

// src/lib/buildGraph.ts (lines 157-160)
 
// 필터된 노드 수집
const nodes = filteredIds.map(id => nodeMap.get(id)!);
 
return { nodes, links };

filteredIds 배열의 각 id를 nodeMap에서 찾아 KeywordNode 객체 배열로 변환합니다. nodeMap.get(id)!에서 !(non-null assertion)을 쓰는 이유는, filteredIds 자체가 filteredNodeIds에서 나왔고, filteredNodeIds에 넣을 때 nodeMap에 있는 것만 넣었기 때문에 undefined가 될 수 없기 때문입니다.

최종 반환값은 GraphData 타입을 충족합니다:

// src/types/graph.ts
export interface GraphData {
  nodes: KeywordNode[];  // 필터링 + 그룹 할당 완료된 노드 배열
  links: KeywordLink[];  // 직접 연관 + 동시출현 엣지 배열
}

이준혁: "Phase 1에서 데이터를 읽고, Phase 2에서 필터링하고, Phase 3에서 그룹 매기고, Phase 4에서 엣지를 만들어서, 최종적으로 { nodes, links } 하나로 합쳐서 반환하는 거야. buildGraph() 함수 하나가 이 네 단계를 전부 품고 있는 셈이지. 이 GraphData가 나중에 react-force-graph-2d 컴포넌트에 그대로 넘어가게 돼."

4. 핵심 포인트 정리

• 두 종류의 엣지가 그래프의 관계를 풍부하게 만든다. (a) 직접 연관 엣지는 시드와 연관 키워드의 명시적 관계를, (b) 동시출현 엣지는 여러 시드에서 공통으로 나타나는 키워드 간의 암묵적 관계를 포착한다.

• [a, b].sort().join('||')은 무방향 그래프에서 중복 엣지를 방지하는 정석 패턴이다. 두 노드를 사전순으로 정렬한 뒤 결합하면, 순서에 관계없이 항상 같은 키가 생성된다. linkSet(Set)에 이 키를 저장해서 O(1)로 중복 검사를 수행한다.

• strength 정규화 전략이 엣지 유형에 따라 다르다. 직접 연관은 seedCount / maxSeedCount로 개별 노드의 범용성을 반영하고, 동시출현은 overlap / totalSeeds로 두 노드 간의 공유 비율(Jaccard-like 유사도)을 반영한다. 둘 다 0~1 범위로 정규화되어 시각화 시 일관된 굵기 매핑이 가능하다.

• 동시출현 임계값 overlap >= 2는 우연한 동시 등장을 걸러낸다. 단 하나의 파일에서만 함께 나타난 키워드 쌍은 실제 연관이 아닌 우연의 일치일 수 있다. 2개 이상의 서로 다른 맥락(시드 파일)에서 반복 등장해야 의미 있는 관계로 인정한다.

• 동시출현 엣지의 이중 루프는 O(n^2) 복잡도를 가진다. j = i + 1로 시작해서 비교 횟수를 n(n-1)/2로 줄이지만, 본질적으로 모든 노드 쌍을 검사한다. 현재 규모(수백 개 노드)에서는 문제없으나, 대규모 데이터에서는 역 인덱스 등의 최적화가 필요할 수 있다.

• Set의 has() 메서드(O(1))를 활용한 교집합 계산은 간결하면서도 효율적이다. seedsA를 순회하며 seedsB.has()를 호출하는 패턴은 O(|seedsA|) 시간에 교집합 크기를 구한다. JavaScript의 Set에 교집합 메서드가 없기 때문에 이렇게 직접 구현하는 것이 일반적인 방법이다.

5. 다음 Step 예고

Step 6: API Route와 인메모리 캐싱

buildGraph() 함수가 완성되었으니, 이제 이 함수를 Next.js API Route에서 호출하여 클라이언트에 GraphData를 제공하는 엔드포인트를 만듭니다. 그래프 빌드는 파일 I/O와 연산이 수반되므로, 매 요청마다 재계산하지 않도록 인메모리 캐싱 전략을 적용하는 방법을 다룹니다.