Chapter 3. Mapping Networks

• 네트워크를 시각화하는 과정을 introduce!

Introduction

• 네트워크 분석에서 시각화는 오래 전부터 중요한 역할을 해왔음.
• 예전엔 손으로 다 그렸지만 요즘엔 자동화됨. 그래도 여전히 challenges 존재 for at least 2 main reasons.
  • 동일한 시스템을 여러가지 방식으로 나타낼 수 있음
  • 2D 화면에 효과적으로 표현하기 쉽지 않음
• 시각화 단계는 크게 다음 세 가지로 구분됨.
  

  

  • collection of data from a system of interest
  • creation of network graph representation from the data
  • rendering of the representation in the form of a visual image

---

Collecting Relational Network Data

• 연구 분야마다 tools and techniques for collection, quality and quantity of data expected to collect 다르지만,
  공통적인 aspects and issues 위주로 다뤄보고자 함.

measurement of system elements and interactions

• 어떤 element을 선택할 것인지
  • e.g. 인터넷 네트워크 분석에서 element를 개별 사용자로 정의할 것인지, 개별 기기로 정의할 것인지, 네트워크 관리 단위로 정의할 것인지에 따라 다른 네트워크가 구축됨
• 어떤 interaction을 선택할 것인지
  • e.g. 인터넷 네트워크 분석에서 실제 기기와 케이블 연결을 나타내는 물리적 연결에 중점을 둘 것인지, 사용자들이 데이터를 주고받는 패턴을 기반으로 하는 논리적 연결에 중점을 둘 것인지에 따라 다른 네트워크가 구축됨
• 어떤 measurement를 선택할 것인지
  • binary: 특정 관계가 존재하는지 여부
  • counts: 특정 상호작용이 발생한 횟수
  • continuous: 상호작용 강도를 수치로 표현한 것

Enumerated, Partial, and Sampled Data

• 데이터 수집에는 한계가 있기에, population을 완벽하게 수집하는 것은 현실적으로 어려움. 따라서 네트워크 데이터는 크게 세 유형으로 구분됨. 물론 현실에서는 이 구분이 혼합된 경우도 많음!
• enumerated data
  • 그냥 full population에서 collect in an exhaustive fashion
• partial data
  • full enumeration of 특정 subset of population
  • 한계: 네트워크 밖 요인의 영향이 분석에서 제외될 수 있음
    spatial data analysis에서 boundary effect와 유사: 연구 대상의 경계 설정할 때, 그 밖에서 일어나는 현상이 분석에 영향 미칠 수도 있는 문제
• sampled data
  • population에서 some random mechanism으로 선택
  • sampling design은 분석 결과에 큰 영향 줄 수 있음

---

Constructing Network Graph Representations

• construct network graph할 때 vertex와 edge 개수를 적절히 조절하는 것이 중요함
  너무 많은 vertex를 포함하면 공간 부족과 해상도 낮음의 문제가 발생하고, 너무 많은 edge를 포함하면 그래프가 엉켜 ball of yarn 해석이 어려울 수 있음
  • 이를 해결하기 위해
  • spatial aggregation: vertex와 edge를 적절하게 합침
  • vertex annotation and grouping: vertex에 있는 부가 정보를 활용해 subgraph들로 분할
  • edge pruning and thresholding: 일정한 기준에 따라 edge 몇 개 제거
  • egocentric network visualization: 특정 vertex와 그와 직접 연결된 neighbors 및 그들의 관계만 표현
  • fish-eye view: 특정 vertex를 중심으로 가까운 부분은 상세하게, 먼 부분은 덜 상세하게 표현

---

Visualizing Network Graphs

Elements of Graph Visualizations

• 핵심 과제는 combinational structure을 geometric representation으로 만드는 것.
• drawing conventions, constraints 만족하면서 aesthetics 최대한 반영하도록 최적화하는 것이 중요
  • drawing conventions: 반드시 따라야 하는 규칙
  • constraints: 그래프 전체가 아니라 subgraph에 적용되는 규칙
  • aesthetics: 반드시 만족할 필요는 없지만, 만족하면 좋은 사항

Methods of Graph Visualization

• 그래프 시각화 방법은 매우 다양하지만 대부분 두 가지 접근 방식으로 분류 가능
• drawing graphs with special structure
  • planar graphs
    • two common techniques for the layout
      • use orthogonal paths: edge가 90도 각도로만 꺾이도록 함
      • use k-sided convex polygon: k개의 edge로 이루어진 cycle이 있을 때 k각형을 만듦
    • 그래프를 시각적으로 배치하는 데에 필요한 연산량 O(|V|)
  • trees
    • planar graph의 한 유형이지만 독특한 구조적 특징이 있어 별도의 시각화 방법 개발됨
      

      

    • 그래프를 시각적으로 배치하는 데에 필요한 연산량 O(|V|)
• drawing graphs based on physical analogies
  • spring embedder
    • vertex를 ball로, edge를 spring으로 가정함. 시스템이 힘의 균형을 이루도록 spring을 늘리거나 줄이면서 네트워크를 안정된 상태로 배치함.
    • 그래프를 시각적으로 배치하는 데에 필요한 연산량, 한 번의 반복에 O(|V|^2)
  • energy placement
    • 시스템에서 최소 에너지를 가질 때 가장 안정적인 상태가 된다는 원리 활용. vertex의 위치를 수학적으로 최적화하여 전체 네트워크 에너지를 최소화.
    • 일반적으로 그래프를 시각적으로 배치하는 데에 필요한 연산량 O(|V|^2), 일부 알고리즘은 O(|V|)에 근접

---

Case Studies

Mapping Science

• measurement
  • 학술지를 기본 분석 단위로 설정하여 학문 분야 간의 관계를 연구하고자 함
  • citation data를 통해 각 학술지의 inter-citation frequency를 파악, 그 내용을 바탕으로 interaction 정의
• network graph construction
  • vertex: 각 학술지
  • edge
    • 처음엔 i가 j를 인용한 횟수 Cij와 j가 i를 인용한 횟수 Cji의 합이 0보다 큰 경우 두 학술지 간 edge 생성
    • 하지만 validate 해봤을 때, expected clustering 결과와 일치하지 않았음
    • 따라서 Jaccard Coefficient 적용! 조금 더 정확
      

      

• visualization of the backbone of science
  • methods for automatic display와 human interpretation and annotation을 결합
    • 처음엔 우선 VxOrd 활용해 시각화 진행
    • 형성된 clusters에 적절한 label을 assign + 가독성을 높이기 위해 간선 제거
      

      

    • cluster를 하나의 vertex로 변환하고, 해당 cluster 크기에 비례하게 크기 조정
      + citation percentage가 75% 이상인 경우, directed edge 추가
      + citation percentage 높을수록 edge 진한 색으로
      + vertex 또한 self-citation percentage에 따라 색 부여, 더 어두운 색은 independent discipline을 더 밝은 색은 dependent discipline을 의미하도록
      

      

Mapping the Internet

• physical Internet이 아닌 logical Internet을 대상으로
  • packet: 데이터는 작은 조각으로 나뉘어 전달됨, 출발지 source와 도착지 destination에 대한 정보 포함
  • router: 데이터를 destination까지 전달하는 중계 장치
  • logical Internet은 실제로 사용되는 path만 포함하므로, physically linked 되어 있어도 traffic 흐르지 않는다면 map에 포함되지 않음
• measurement
  • logical Internet은 직접적 database 존재하지 않기 때문에, traffic flow를 기반으로 간접적으로 분석해야 함, 이때 활용하는 도구가 traceroute
    
    • 원리
      

      

      
      
      • packet에는 time to live TTL이라는 integer 정보가 포함됨
      • packet이 router 통과할 때마다 TTL은 1씩 감소함
      • TTL=0 되면 packet drop하고 source에게 해당 router 주소를 전달함
      • 즉, traceroute는 TTL 값 증가시키며 연속적으로 packet 전송해 packet이 통과하는 모든 router 주소 확보하는 것
    • 한계
      • sampling bias: source와 destination 선택 방식이 데이터 수집 결과에 영향을 미침
      • security issue: 방화벽 firewall이 있는 네트워크에서는 traceroute 방법으로 데이터 수집 불가, 또 일부 router 소유자는 불필요한 traffic 줄이기 위해 raceroute 응답 기능 비활성화 해두기도
• network graph construction
  • 많은 destination에 대해 traceroute 시행하면 출발지를 중심으로 tree같은 구조 만들 수 있음, 하지만 문제는
    • A에서 B로 가는 path ≠ B에서 A로 가는 path 일수도
    • Internet path는 동적, 계속 바뀌기 때문에 며칠동안 데이터를 모으면 false link 생김
    • router는 보통 여러 개의 IP주소 갖기 때문에 같은 router가 여러 개처럼 인식될 수도
• visualization of the router-level Internet
  

  

  
  
  • 대부분 다른 층 shell과 연결됨 (i.e. 같은 층 shell 내에서의 연결은 적음)
  • 외곽으로 갈수록 shell 두꺼워짐 (i.e. 중심 shell은 직접적으로 연결할 수 있는 router가 제한적)

---

Mapping Dynamic Networks

• 앞서 다뤘던 Internet과 같이 계속 변하는 네트워크도 있기 때문에 dynamic map도 필요
  • static map: 특정한 순간의 네트워크, 한 장의 그림으로 표현하는 느낌
  • dynamic map: 시간이 지나면서 네트워크 어떻게 변하는지 담음
• 만약 네트워크가 바뀔 때마다 자동으로 완전히 다른 새 map을 만든다면, 구축부터 해석까지 번거로워질 것
• 이전 map과 너무 다르지 않게 구현할 수 있도록 조절할 수 있다면 좋을 것!
  • 기존 node와 edge는 아예 움직이지 않음 (i.e. 그냥 삭제하거나 삽입하는 정도), 네트워크가 많이 변하면 엉킬 수 있음
  • 새로운 node 근처 작은 부분만 조정
  • 그래프 간 거리를 계산해 비슷한 모양을 유지할 수 있도록 함
  • 수학적 확률 모델 활용해 네트워크 변화를 부드럽게 표현 (e.g. exponential smoothing)
    

    

---

Additional Related Topics and Readings

• network mapping은 꼭 현실 그대로 반영하는 게 최선이 아닐 수도!
  지하철 노선도처럼 더 유용한 형태로 왜곡해 표현하는 게 더 효과적일 수도 있음