2022-10-04 Naver boostcamp 일일노트 [그래프 추가학습]

in Study

다양한 그래프 패턴

  • 에르되스-레니 랜덤 그래프
    • n개의 정점, 임의 정점 사이에 간선이 존재할 확률은 p
  • 작은 세상 효과
    • 경로 : 정점들의 순열. 시작점과 끝점 존재
    • 지름 : 정점 간 거리의 최댓값. 그래프의 모든 경로 중 최댓값.
    • 메신저, 우편 실험 60년대 -> 정점 간의 평균 거리가 6-7로 생각모다 매우 작다. –> 작은 세상 효과
    • 작은 세상 효과는 그래프에서도 존재하나, 체인 / 사이클 그래프 / 격자 그래프 에서는 그 기하학적 특징으로 인해 작은 세상 효과가 존재하지 않는다.
  • 정점의 연결성
    • 연결성 : 간선의 수
      • 나가는 연결성 (Out Degree) - 정점에서 나가는 간선 수
      • 들어오는 연결성 (In Degree) - 정점으로 들어오는 간선의 수
    • 그래프 중에는 연결성이 매우 높은 (간선이 매우 많은) Hub 정점이 존재한다.
    • 랜덤 그래프의 연결성 분포는 높은 확률로 정규 분포와 유사하다.

  • 군집 구조

    • 군집 : 연결성이 높은 (간선이 많은) 정점들의 집합
    • 지역적 군집 계수 - 한 정점에서 군집의 형성 정도를 측정 정점 i의 이웃쌍 중 간선으로 직접 연결된 것의 비율로 측정. 어떤 정점의 이웃 정점들이 서로 얼마나 연결되어 있는지 표현함.
    • 지역적 군집 계수가 높을수록 그 정점과 이웃들은 높은 확률로 군집을 형성하게 됨
    • 동질성
    • 전이성 예) 친구끼리 서로 소개시켜주는 것
    • 반면 랜덤 그래프에서는 지역적 혹은 전역 군집 계수가 높지 않음 -> 간선 연결이 독립적이기 때문

검색 엔진에서 활용하는 그래프

  • 구글 이전의 검색 엔진

    1. 웹을 거대한 디렉토리로 정의하려는 예전의 시도 - 저장과 검색에 어려움 (너무 카테고리가 많고 모호해진다)

    2. 웹페이지에 포함된 키워드에 의존한 검색 엔진 키워드만 갖고 전혀 연관성 없는 사이트 (예 : 축구 단어가 많이 나오는 음란사이트) 등 악의적 게시물에 취약함.

  • 페이지랭크

    • 핵심 아이디어 : 투표

    • 들어오는 간선이 많을 수록 신뢰한다

    • 간선을 억지로 늘리는 (팔로워 수 구매) 악용을 막으려면? 가중 투표 - 관련성 높고 신뢰할 수 있는 웹사이트의 투표를 더 중요히 간주함.

    • 페이지랭크 점수 \(r_j = \sum_{i \in N_{in} (j)} {r_i \over d_{out}(i)}\) 들어오는 이웃들이 보내는 투표의 가중치 합

    • 임의 보행 관점

      웹서퍼가 t번째 방문한 웹페이지가 웹페이지 i일 확률을 $p_i(t)$라고 할 때,
      $p(t)$ 웹페이지 수 길이의 확률분포 벡터가 됨.

      t가 무한히 커지면, p(t) = p(t+1) = p가 성립하게 됨. 결국, 투표 관점에서 정의한 페이지 랭크 점수 (1) 은 임의 보행 관점에서의 정상 분포 p 와 동일하다.

    • 페이지랭크의 계산

      • 반복곱 (power iteration)
        • 반복곱을 통해 페이지랭크 계산 가능 (계산 과정 복잡. 추후 필요할 시 학습!)
        • 페이지랭크 점수가 항상 특정값으로 수렴하진 않는다. 원인 1. 스파이더 트랩 (Spider Trap) - 들어오는 간선은 있지만 나가는 간선은 없는 정점들의 집합 (계속 왔다갔다만 함) 원인 2. 막다른 정점 (Dead End) : 들어오는 간선은 있지만 나가는 간선은 없는 정점
        • 문제의 해결법 - 순간이동 (Teleport)
          • 막다른 정점에 다다랐다면, 임의의 웹페이지로 순간이동한다. .. 이후 과정들이 이어져 있는 일련의 순간이동 알고리즘!
          • 순간이동을 도입한 반복곱 - (1)의 항에 추가적인 항 하나를 덧붙임.

그래프를 통한 전파

정보 / 행동 / 질병 등이 전파됨. 이러한 전파의 원리 및 모형에 대해 공부한다.

  • 의사결정 기반의 전파 모형
    • 주변 사람들의 의사결정이 본인의 의사결정에 영향을 미친다 예) 라인, 카카오톡 중 친구들이 라인을 많이 쓰는 경우
  • 선형 임계치 모형
    • 행복이 최대화되는 선택을 한다고 가정 p 비율의 이웃이 A를 선택했다고 할 때 (1-p 비율의 이웃이 B를 선택함) 이웃을 둔 자기자신은 언제 A를 선택할까? $ ap > b(1-p) $ 일 때 A를 선택하게 됨. 즉 $ p > {b \over a + b}$ 일 때. 여기서 임계치 $ q = {b \over a + b}$ 라고 한다. 이 모형을 선형 임계치 모형이라 함.
    • 그러면 얼리어답터 노드가 다른 행동 A를 선택했을 때, 그 행동이 어떻게 전파되는지를 모형으로 판단할 수 있음. 주변 이웃들의 변화로 임계치에 변화가 생겨, 노드들의 행동 변화를 이끌어냄.

© 2023. All rights reserved.