Top

그래프 알고리즘 [스파크와 Neo4j로 이해하는 알고리즘과 그래프 분석]

  • 원서명Graph Algorithms: Practical Examples in Apache Spark and Neo4j (ISBN 9781492047681)
  • 지은이마크 니덤(Mark Needham), 에이미 호들러(Amy E. Hodler)
  • 옮긴이테크 트랜스 그룹 T4
  • ISBN : 9791161755427
  • 33,000원
  • 2021년 07월 22일 펴냄
  • 페이퍼백 | 348쪽 | 188*235mm
  • 시리즈 : 데이터 과학

책 소개

요약

그래프 분석과 알고리즘, 이론에 대한 소개로 시작해서 그래프 알고리즘에 초점을 맞춘 경로 찾기, 중심성, 커뮤니티 감지 등을 간략하게 설명한다. 알고리즘의 기능 설명을 확인할 수 있고, 알고리즘에 대한 사용 사례와 자세한 내용을 볼 수 있다. 또한 스파크, Neo4j에서 알고리즘 사용 방법을 제공하는 구체적인 예제 코드를 통해 이론의 활용이 가능하다. 그래프 분석으로 모든 조직의 복잡한 시스템과 대규모 네트워크의 동작을 파악할 수 있으며, 그래프 분석을 더 잘 활용해서 새로운 발견을 하고 지능형 솔루션을 더 빠르게 개발할 수 있을 것이다.

이 책에 쏟아진 찬사

"기초 알고리즘의 기본 개념에서 시작해 프로세싱 플랫폼과 실제 사용 예제에 이르기까지 멋진 그래프 세계로 인도할 유익한 가이드를 제공한다."

— 커크 본(Kirk Borne) 박사, 부즈 앨런 해밀턴(Booz Allen Hamilton)의 수석 데이터 과학자 겸 수석 고문

“그래프 알고리즘으로 패턴과 구조를 검출해 연결된 데이터를 살펴볼 수 있는 실용적이고 유익한 가이드다. 그래프 데이터베이스 작업 개발자가 반드시 읽어야 한다.”

— 루앤 미스퀴타(Luanne Misquitta), GraphAware 엔지니어링 부사장

추천의 글

마케팅 속성 분석, 자금 세탁 방지(AML, Anti-Money Laundering) 분석, 고객 여정 모델링, 안전사고 원인 분석, 문헌 기반 발견, 사기 네트워크 감지, 인터넷 검색 노드 분석, 지도 애플리케이션 생성, 질병 클러스터 분석에서 공통점은 그래프를 사용한다는 것이다.
위에 나열된 모든 예에는 직접/간접(전이) 관계를 포함해 엔티티와 엔티티 간의 관계가 포함된다. 엔티티는 그래프의 노드며 사람, 이벤트, 개체, 개념, 장소가 될 수 있다. 노드 간의 관계는 그래프의 에지(edge)가 된다.
그래프 알고리즘과 그래프 데이터베이스를 그토록 흥미롭고 강력하게 만드는 것은 A가 B와 관련된 두 개체 간에 단순한 관계만 있기 때문은 아니다. 결국 데이터베이스의 표준 관계형 모델은 수십 년 전에 엔티티 관계 다이어그램(ERD)에서 이러한 타입의 관계를 인스턴스화했다. 그래프에서 중요한 것은 방향 관계와 전이 관계다. 방향 관계에서 A는 B를 유발할 수 있지만 그 반대는 안 된다. 전이 관계에서 A는 B와 직접 관련되고 B는 C와 직접 관련되며 A는 C와 직접적으로는 관련되지 않았지만 결과적으로 보면 A는 C와 전이적으로 관련된다.
이러한 전이 관계(특히 관계와 네트워크 패턴이 가능한 한 많고 엔티티 간 일정한 분리 정도를 가지면서 엔티티들이 많고 다양할 때가 해당됨)를 통해 그래프 모델은 연결이 끊어지거나 관련이 없는 것처럼 보일 수 있고 관계형 데이터베이스에 의해 감지되지 않는 엔티티 간의 관계가 존재할 수 있다. 따라서 그래프 모델은 많은 네트워크 분석 사용 사례에서 생산적이며 효과적으로 적용할 수 있다.
인터넷 검색에서 주요 검색 엔진은 하이퍼링크 네트워크(그래프 기반) 알고리즘을 사용해 주어진 검색 단어 집합에 대해 전체 인터넷에서 신뢰할 수 있는 중앙 노드를 찾는다. 네트워크의 권위 있는 노드는 다른 많은 노드가 가리키는 노드이기 때문에 이 경우 에지의 방향성은 매우 중요한 역할을 한다.
그래프 알고리즘을 통한 모든 네트워크 분석 예를 사용해 앞서 언급한 다른 사용 사례에서도 유사한 그래프 작성 능력을 설명할 수 있다. 각 사례는 엔티티(사람, 개체, 이벤트, 행동, 개념, 장소)와 그 관계(접촉점, 인과(casual) 관계, 단순(simple) 연결 모두)와 깊이 관련된다.
그래프가 가진 힘을 고려할 때 실제 사용 사례에서 활용될 수 있는 그래프 모델의 가장 강력한 노드는 ‘콘텍스트(context)’일 수 있다는 점을 염두에 둬야 한다. 콘텍스트에는 시간, 위치, 관련 이벤트, 주변 엔티티 등이 포함될 수 있다. 콘텍스트를 그래프(노드 및 에지)에 통합하면 인상적인 예측(predictive) 분석과 규범적(prescriptive) 분석 기능을 얻을 수 있다.
마크 니덤(Mark Needham)과 에이미 호들러(Amy E. Hodler)의 이 책은 알고리즘, 개념, 알고리즘의 실제 머신러닝 애플리케이션을 포함해 이러한 중요한 타입의 그래프 분석에 대한 지식과 기능을 확장하는 것을 목표로 한다. 기본 개념에서 기본 알고리즘, 처리 플랫폼, 실제 사용 사례에 이르기까지 멋진 그래프 세계에 대한 유익한 가이드다.
— 커크 본 박사, 부즈 앨런 해밀턴의 수석 데이터 과학자 및 수석 고문

이 책에서 다루는 내용

■ 오늘날의 데이터에서 그래프 분석으로 더 많은 예측 요소를 나타낼 수 있는 방법
■ 인기 있는 그래프 알고리즘의 작동 방식과 적용 방식
■ 20개 이상의 그래프 알고리즘 예제의 샘플 코드와 팁
■ 다양한 유형의 상황에서 어떤 알고리즘을 사용할지 알아보기
■ 스파크와 Neo4j용 작업 코드, 샘플 데이터 세트를 포함한 예제
■ Neo4j와 스파크를 결합해 링크 예측을 할 수 있는 ML 워크플로 작성

이 책의 구성

처음 두 개 장에서는 그래프 분석, 알고리즘과 이론에 대한 소개를 제공한다. 세 번째 장에서는 고전적인 그래프 알고리즘(경로 찾기, 중심성, 커뮤니티 감지)에 초점을 맞춘 세 가지 내용을 상세히 살펴보기 전에 사용된 플랫폼을 간략하게 설명한다. 워크플로 내에서 그래프 알고리즘이 사용되는 방식을 보여주는 두 개의 장으로 책을 마무리한다. 하나는 일반 분석용이고 다른 하나는 머신러닝용이다.

이 책의 대상 독자

아파치 스파크™ 또는 Neo4j를 사용해본 경험이 있는 개발자와 데이터 과학자가 그래프 알고리즘을 시작할 수 있도록 돕는 실용적인 가이드다. 알고리즘 예제는 스파크와 Neo4j 플랫폼을 활용하지만 선택한 그래프 기술에 관계없이 좀 더 일반적인 그래프 개념을 이해하는 데도 도움이 될 수 있다.

저자/역자 소개

지은이의 말

세계의 금융과 커뮤니케이션 시스템에서 사회적 프로세스와 생물학적 프로세스에 이르기까지 연결(connections)이 주도하고 있다. 이러한 연결의 의미를 찾는 작업은 사기 조직을 식별하고, 각 그룹의 강점을 평가하고 연속적인 실패를 예측하기 위한 권장 사항을 최적화하는 등 산업 전반의 혁신을 주도한다.
연결성이 계속 가속화됨에 따라 그래프 알고리즘에 대한 관심이 폭발적으로 증가한 것은 데이터 간의 관계에서 인사이트를 얻고자 명확하게 수학을 기반으로 하기 때문이다. 그래프 분석으로 모든 조직의 복잡한 시스템과 대규모 네트워크의 작동을 파악할 수 있다.
그래프 분석의 유용성, 중요성뿐만 아니라 복잡한 시나리오의 내부 동작도 알아본다. 최근까지 그래프 분석을 하려면 상당한 전문 지식과 계산이 필요했다. 도구를 사용하기 어려울 뿐만 아니라 그래프 알고리즘을 문제에 적용하는 방법을 아는 사람이 거의 없었기 때문이다. 이를 변화시키는 것이 이 책의 목표다. 이 책을 통해 조직이 그래프 분석을 더 잘 활용해 새롭게 발견하고 지능형 솔루션을 더 빠르게 개발할 수 있도록 도울 것이다.

지은이 소개

마크 니덤(Mark Needham)

Neo4j의 그래프 Advocate이자 개발 엔지니어다. 사용자가 그래프와 Neo4j를 수용하게 돕고 까다로운 데이터 문제에 대한 정교한 솔루션을 구축했다. 이전에 Neo4j의 인과 클러스터링(Causal Clustering) 시스템 구축을 도왔고 그래프 데이터에 대한 깊은 전문성을 지니고 있다. 인기 블로그(https://markhneedham.com/blog/)에 그래피스타 경험에 대해 기고하고 있으며 트위터는 @markhneedham(https://twitter.com/markhneedham)을 사용한다.

에이미 호들러(Amy E. Hodler)

Neo4j의 네트워크 과학 전문가이자 AI와 그래프 분석 프로그램 관리자다. 네트워크 내의 구조를 밝히고 동적 동작을 예측할 수 있는 방법으로 그래프 분석을 추천한다. EDS, 마이크로소프트, HP(Hewlett-Packard), 히타치(Hitachi) IoT, 크레이(Cray Inc.) 같은 회사에서 팀이 새로운 기회를 창출할 수 있게끔 새로운 접근 방식을 적용하도록 도왔다. 복잡성 연구와 그래프 이론에 매료돼 과학과 예술을 좋아한다. 트위터는 @amyhodler(https://twitter.com/amyhodler)를 사용한다.

옮긴이의 말

그래프 알고리즘은 오래 전부터 일상생활에서 많이 활용돼 왔다. 특히 스마트폰의 지하철 애플리케이션이나 자동차의 내비게이션은 자주 사용한다. 서울역에서 강남역까지의 가장 빠른 길을 찾으려고 지하철로 이동할 수도 있고, 자가용으로 이동할 수도 있다. 하지만 어떻게 가야 가장 빨리 도착할 수 있는지는 판단하기 어렵다. 이러한 어려움을 해결할 때 그래프 알고리즘이 사용된다. 출발지와 목적지를 입력만 하면 어느 길이 빠른지, 환승을 줄일 수 있는지 모두 살펴볼 수 있다. 이때 사용되는 그래프 알고리즘이 바로 최단 경로 알고리즘이다. 최단 경로 알고리즘은 그래프상의 두 정점 사이를 연결하는 경로 중 가장 짧은 경로를 찾는 방법이다. 여기서 ‘짧다’는 것은 단지 물리적인 거리 외에도 시간과 비용 등의 다양한 기준을 사용할 수 있다.
이렇게 일상생활에서 중요한 위치를 차지하는 그래프 알고리즘은 개발자라면 누구든지 습득해야 하는 필수 지식으로 자리를 잡았다. 뉴욕 주립 대학교의 스티븐 스키에나 교수는 “그래프는 교통 시스템, 인간 상호작용 및 통신 네트워크의 조직을 설명하는 컴퓨터 과학의 추상적 통합 주제 중 하나이며, 그래프 교육을 받은 프로그래머는 매우 다양한 구조를 모델링할 수 있기 때문에 개발할 때 큰 도움이 된다.”라고 언급했다. 개발자들이 산업 전반에서 사용되는 그래프 이론을 현실의 개발에 적용하는 데 이 책은 많은 도움이 된다. 자동차 업계에 있는 개발자라면 자율 주행 알고리즘을 만드는 데 그래프 알고리즘을 가장 필수적으로 적용해야 하지 않을까? 여러 가지 그래프 알고리즘을 학습하고 그 알고리즘 중 어느 것을 사용할지 정하는 일은 매우 어려운 일이지만 이 책이 그 결정에 도움될 수 있을 것이다.
그래프 알고리즘의 다양한 주제를 다루며, 사용자가 자유롭게 사용할 수 있을 정도의 상세한 설명을 제공한다. 알고리즘의 기능에 대한 설명을 학습하고, 알고리즘의 사용 사례와 자세한 내용을 확인할 수 있다. 더불어 스파크, Neo4j 또는 두 가지 모두에서 구체적 알고리즘 사용 방법을 볼 수 있어서 실제로 알고리즘을 사용하려는 개발자들의 레퍼런스가 될 수 있다.
진심으로 이 책이 모든 독자가 그래프 알고리즘을 이해하고 실제로 구현하는 데 많은 도움이 되길 바란다.

옮긴이 소개

테크 트랜스 그룹 T4

최신 IT 테크놀로지에 대한 리서치를 목적으로 하는 스터디 그룹이다. 엔터프라이즈 환경에서 오픈소스를 활용한 프레임워크 구축에 관심이 많으며 알고리즘, 양자 컴퓨팅, OpenCV, ML 등의 기술에 주목하고 있다. 또한 다양한 오픈소스 기반의 플랫폼 개발 활용에 관심이 많다. 옮긴 책으로는 『OpenCV 4를 활용한 머신러닝 입문 2/e』(에이콘, 2020), 『OpenCV 4 마스터 3/e』(에이콘, 2020), 『양자 컴퓨팅 발전과 전망』(에이콘, 2020) 등이 있다.

목차

목차
  • 1장. 시작하기
    • 그래프란?
    • 그래프 분석과 알고리즘은 무엇인가?
    • 그래프 프로세싱, 데이터베이스, 질의, 알고리즘
      • OLTP와 OLAP
    • 그래프 알고리즘에 관심을 가져야 하는 이유
    • 그래프 분석 사례
    • 결론

  • 2장. 그래프 이론과 개념
    • 용어
    • 그래프 타입과 구조
      • 랜덤, 작은 세상, 척도 독립 구조
    • 그래프가 갖는 여러 특징
      • 연결과 비연결 그래프
      • 비가중 그래프와 가중 그래프
      • 비방향성 그래프와 방향성 그래프
      • 비순환 그래프와 순환 그래프
      • 희소 그래프와 밀집 그래프
      • 일분, 이분, k분 그래프
    • 그래프 알고리즘의 타입
      • 경로 찾기
      • 중심성
      • 커뮤니티 검출
    • 요약

  • 3장. 그래프 플랫폼과 프로세싱
    • 그래프 플랫폼과 프로세싱 고려 사항
      • 플랫폼 고려 사항
      • 프로세싱 고려 사항
    • 대표적인 플랫폼
      • 플랫폼 선택
      • 아파치 스파크
      • Neo4j 그래프 플랫폼
    • 요약

  • 4장. 경로 찾기와 그래프 탐색 알고리즘
    • 예제 데이터: 운송 그래프
      • 데이터를 아파치 스파크로 불러오기
      • 데이터를 Neo4j로 불러오기
    • 너비 우선 탐색
      • 너비 우선 탐색(아파치 스파크 활용)
    • 깊이 우선 탐색
    • 최단 경로
      • 언제 최단 경로를 사용해야 하는가?
      • 최단 경로(Neo4j 사용)
      • 최단 경로(Neo4j 사용)
      • 최단 경로(가중치 적용, 아파치 스파크 사용)
      • 최단 경로의 변형(Variation): A*
      • 최단 경로의 변형: 옌의 k-최단 경로
    • 모든 쌍의 최단 경로
      • 모든 쌍의 최단 경로를 자세히 알아보기
      • 모든 쌍의 최단 경로를 사용해야 할 경우
      • 모든 쌍의 최단 경로(아파치 스파크 사용)
      • 모든 쌍의 최단 경로(Neo4j 사용)
    • 단일 출발 최단 경로
      • 단일 출발 최단 경로를 사용해야 할 경우
      • 단일 출발 최단 경로(아파치 스파크 사용)
      • 단일 출발 최단 경로(Neo4j 사용)
    • 최소 신장 트리
      • 최소 신장 트리를 사용해야 할 경우
      • 최소 신장 트리(Neo4j 사용)
    • 랜덤 워크
      • 랜덤 워크를 사용해야 할 경우
      • Neo4j를 사용한 랜덤 워크
    • 요약

  • 5장. 중심성 알고리즘
    • 그래프 데이터 예: 소셜 그래프
      • 아파치 스파크로 데이터 가져오기
      • Neo4j로 데이터 가져오기
    • 연결 중심성
      • 도달
      • 연결 중심성을 사용해야 할 경우
      • 연결 중심성(아파치 스파크 사용)
    • 근접 중심성
      • 근접 중심성을 사용해야 할 경우
      • 근접 중심성(아파치 스파크 사용)
      • 근접 중심성(Neo4j 사용)
      • 근접 중심성 변형: 와서만과 파우스트
      • 근접 중심성 변형: 조화 중심성
    • 매개 중심성
      • 매개 중심성을 사용해야 할 경우
      • 매개 중심성(Neo4j 사용)
      • 매개 중심성 변형: 랜덤 근사 브랜드
    • PageRank
      • 영향력
      • PageRank 공식
      • 반복 동작, 랜덤 서퍼, 랭크 싱크
      • PageRank를 사용해야 할 경우
      • PageRank(아파치 스파크 사용)
      • PageRank(Neo4j 사용)
      • PageRank 변형: 개인화된 PageRank
    • 요약

  • 6장. 커뮤니티 검출 알고리즘
    • 예제 그래프 데이터: 소프트웨어 종속성 그래프
      • 아파치 스파크로 데이터 가져오기
      • Neo4j로 데이터 가져오기
    • 트라이앵글 수와 결집 계수
      • 지역 결집 계수
      • 전역 결집 계수
      • 트라이앵글 수와 결집 계수를 사용해야 할 경우
      • 트라이앵글 수(아파치 스파크 사용)
      • Neo4j 사용한 트라이앵글
      • 지역 결집 계수(Neo4j 사용)
    • 강한 연결 요소
      • 강한 연결 요소를 사용해야 할 경우
      • 강한 연결 요소(아파치 스파크 사용)
      • 강한 연결 요소(Neo4j 사용)
    • 연결 요소
      • 연결 요소를 사용해야 할 경우
      • 연결 요소(아파치 스파크 사용)
      • 연결 요소(Neo4j 사용)
    • 레이블 전파
      • 준지도 학습과 시드 레이블
      • 레이블 전파를 사용해야 할 경우
      • 레이블 전파(아파치 스파크 사용)
      • 레이블 전파(Neo4j 사용)
    • 루뱅 모듈성
      • 루뱅을 사용해야 할 때
      • 루뱅(Neo4j 사용)
    • 커뮤니티 검증
    • 요약

  • 7장. 실전 그래프 알고리즘
    • Neo4j를 사용한 옐프 데이터 분석
      • 옐프 소셜 네트워크
      • 데이터 불러오기
      • 그래프 모델
      • 옐프 데이터 개요
      • 여행 계획 애플리케이션
      • 여행 비즈니스 컨설팅
      • 유사 카테고리 찾기
    • 아파치 스파크로 항공사 비행 데이터 분석
      • 탐색적 분석
      • 인기 있는 공항
      • ORD에서 지연
      • SFO의 좋지 않은 비행 날짜
      • 항공사별 상호 연결 공항
    • 요약

  • 8장. 머신러닝 향상을 위한 그래프 알고리즘
    • 머신러닝과 문맥의 중요성
      • 그래프, 콘텍스트, 정확도
    • 연결 특징 추출과 선택
      • 그래프 특징
      • 그래프 알고리즘 특징
    • 실전 그래프와 머신러닝: 링크 예측
      • 도구와 데이터
      • Neo4j로 데이터 가져오기
      • 공동 저자 그래프
      • 균형된 훈련과 테스트용 데이터 세트 만들기
      • 누락된 링크를 예측하는 방법
      • 머신러닝 파이프라인 생성
      • 링크 예측: 기본 그래프 특징
      • 링크 예측: 트라이앵글과 결집 계수
      • 링크 예측: 커뮤니티 검출
    • 요약
    • 전체 내용 요약

  • 부록. 추가 정보와 자원
    • 기타 알고리즘
    • Neo4j 대량 데이터 가져오기와 옐프
      • APOC와 다른 Neo4j 도구
    • 데이터 세트 찾기
    • 아파치 스파크와 Neo4j 플랫폼 지원
    • 훈련

도서 오류 신고

도서 오류 신고

에이콘출판사에 관심을 가져 주셔서 고맙습니다. 도서의 오탈자 정보를 알려주시면 다음 개정판 인쇄 시 반영하겠습니다.

오탈자 정보는 다음과 같이 입력해 주시면 됩니다.

(예시) p.100 아래에서 3행 : '몇일'동안 -> 며칠동안