네트워크 (2 판)

마크뉴만

(MarkNewman)
1991년에옥스퍼드대학교에서물리학박사학위를받았다.뉴멕시코주에위치한복잡계연구에전념하며싱크탱크역할을하는산타페연구소(SantaFeInstitute)의일원으로합류하기전까지는코넬대학교에서박사후연구를수행했다.2002년에산타페를떠나미시간대학교로이직했다.현재그곳에서아나톨라포포트석좌교수(AnatolRapoportDistinguishedUniversityProfessor)이자대학의복잡계연구센터교수로재직중이다.

1장.도입

1부.실증적인네트워크연구

2장.기술분야네트워크
2.1인터넷
2.1.1트레이스라우트를사용한인터넷구조측정
2.1.2라우팅테이블을사용한인터넷구조측정
2.2전화망
2.3전력망
2.4교통망
2.5배송및분배네트워크

3장.정보네트워크
3.1월드와이드웹
3.2인용네트워크
3.2.1특허와법률인용
3.3그외정보네트워크
3.3.1P2P네트워크
3.3.2추천네트워크
3.3.3핵심어색인

4장.사회연결망
4.1사회연결망의실증연구
4.2인터뷰와설문조사
4.2.1자기주변네트워크
4.3직접관찰
4.4기록보관소또는제3자기록물에서얻은데이터
4.5소속네트워크
4.6좁은세상실험
4.7눈덩이표본추출,접촉자추적,마구걷기


5장.생물학적네트워크
5.1생화학적네트워크
5.1.1물질대사네트워크
5.1.2단백질-단백질상호작용네트워크
5.1.3유전자조절네트워크
5.1.4그밖의생화학적네트워크
5.2두뇌속의네트워크
5.2.1뉴런네트워크
5.2.2두뇌의기능적연결네트워크
5.3생태계네트워크
5.3.1먹이그물
5.3.2그밖의생태계네트워크

2부.네트워크이론의기초

6장.네트워크의수학표현
6.1네트워크와그표현
6.2인접행렬
6.3가중치네트워크
64방향성네트워크
6.4.1비순환네트워크
6.5하이퍼그래프
6.6이분네트워크
6.6.1접속행렬과네트워크투영
6.7다층네트워크와동적네트워크
6.8트리
6.9평면네트워크
6.10링크수
6.10.1조밀도와듬성도
6.10.2방향성네트워크
6.11걷기와경로
6.11.1최단경로
6.12덩어리
6.12.1방향성네트워크에서의덩어리
6.13독립경로,연결성,컷집합
6.13.1가중치네트워크의최대흐름과컷집합
6.14그래프라플라시안
6.14.1그래프분할
6.14.2네트워크시각화
6.14.3마구걷기
6.14.4저항네트워크
6.14.5그래프라플라시안의속성

7장.네트워크측정량과측정법
7.1중심도
7.1.1링크수중심도
7.1.2고유벡터중심도
7.1.3카츠중심도
7.1.4페이지랭크
7.1.5허브와권위자
7.1.6근접중심도
7.1.7사이중심도
7.2노드의그룹
7.2.1클리크
7.2.2중심
7.2.3덩어리와k-덩어리
7.3전이성과뭉침계수
7.3.1국소뭉침과여분연결
7.4상호성
7.5부호있는에지와구조균형
7.6유사도
7.6.1구조동등성측정량
7.6.2보편동등성측정량
7.7동종선호와끼리끼리섞임
7.7.1정렬할수없는성질을기준으로한끼리끼리섞임
7.7.2정렬할수있는성질을기준으로한끼리끼리섞임
7.7.3링크수를기준으로한끼리끼리섞임

8장.컴퓨터알고리듬
8.1네트워크분석과시각화를위한소프트웨어
8.2실행시간과계산복잡도
8.3네트워크데이터의저장
8.3.1인접행렬
8.3.2인접리스트
8.3.3그밖의네트워크표현법
8.4네트워크의기본적인측정량을구하는알고리듬
8.4.1링크수
8.4.2뭉침계수
8.5최단경로와너비우선탐색
8.5.1너비우선탐색알고리듬소개
8.5.2가장단순한구현방법
8.5.3더나은구현방법
8.5.4너비우선탐색의변형알고리듬
8.5.5최단경로찾기
8.5.6사이중심도
8.6에지의길이가변하는경우의최단경로
8.7최대흐름과최소컷
8.7.1증가경로알고리듬
8.7.2구현과실행시간
8.7.3왜이알고리듬은옳은답을주는가
8.7.4독립경로찾기와최소컷집합
8.7.5노드독립경로

9장.네트워크통계와측정오류
9.1오류의종류
9.2오류의원인
9.3오류의추정
9.3.1측정오류에대한전통적인통계방법론
9.3.2최대가능도기법
9.3.3네트워크데이터의오류
9.3.4EM알고리듬
9.3.5독립적인에지오류
9.3.6예시
9.3.7다른값들에대한추정
9.3.8그밖의에러모형
9.4에러의보정
9.4.1링크예측
9.4.2노드식별

10.실제네트워크의구조
10.1덩어리
10.1.1방향성네트워크의덩어리
10.2최단경로와좁은세상효과
10.3링크수분포
10.4거듭제곱법칙과척도없는네트워크
10.4.1거듭제곱법칙을발견하고시각화하기
10.4.2거듭제곱분포의성질
10.5그밖의중심도측정량들의분포
10.6뭉침계수
10.6.1국소뭉침계수
10.7동류성혼합(끼리끼리섞임)

3부.네트워크모형

11장.무작위그래프
11.1무작위그래프
11.2평균에지수와평균링크수
11.3링크수분포
11.4뭉침계수
11.5거대덩어리
11.5.1하나이상의거대덩어리가존재할수있을까?
11.6작은덩어리들
11.7경로길이
11.8무작위그래프의문제점

12장.구조모형
12.1구조모형
12.1.1구조모형에서의에지연결확률
12.1.2링크수의기댓값이주어진무작위모형
12.2남은링크수분포
12.3뭉침계수
12.4국소적으로트리인네트워크
12.5한노드의두번째이웃들의수
12.6거대덩어리
12.6.1예시
12.6.2거대덩어리크기에대한일반적인해법
12.7작은덩어리들
12.7.1작은덩어리들안에있는노드의링크수
12.7.2에지를따라도달할수있는평균노드수
12.8거듭제곱링크수분포를따르는네트워크
12.9지름
12.10생성함수방법
12.10.1생성함수
12.10.2예시
12.10.3거듭제곱분포
12.10.4정규화와모멘트
12.10.5생성함수의곱
12.10.6링크수분포에대한생성함수
12.10.7노드의두번째이웃의수
12.10.8작은덩어리들에대한생성함수
12.10.9작은덩어리들의크기에대한완전한분포
12.11그밖의무작위그래프모형
12.11.1방향성네트워크
12.11.2이분네트워크
12.11.3비순환네트워크
12.11.4링크수상관성
12.11.5뭉치기와전이성
12.11.6동류성혼합과커뮤니티구조
12.11.7동적네트워크
12.11.8좁은세상모형

13장.네트워크형성모형
13.1선호적연결
13.1.1프라이스모형의링크수분포
13.1.2프라이스모형의컴퓨터시뮬레이션
13.2바라바시와알버트의모형
13.3네트워크의시간변화와선발자효과
13.4선호적연결모형의확장
13.4.1여분에지의추가
13.4.2에지제거
13.4.3비선형선호적연결
13.5노드복제모형
13.6네트워크최적화모형
13.6.1여행시간과비용사이의상충

4부.응용

14장.커뮤니티구조
14.1네트워크를그룹으로나누기
14.2모듈도최대화
14.2.1모듈도함수의꼴
14.2.2간단한모듈도최대화알고리듬
14.2.3스펙트럼모듈도최대화
14.2.4둘보다더많은수의그룹으로나누기
14.2.5루뱅알고리듬
14.2.6모듈도최대화방법의해상도한계
14.3정보이론에기반한방법
14.4통계적추론에기반한방법
14.4.1통계적추론을사용한커뮤니티찾기
14.5커뮤니티를찾기위한그밖의알고리듬
14.5.1사이중심도를기반으로한방법
14.5.2계층적뭉치기
14.6알고리듬성능측정
14.6.1실제네트워크에대한테스트
14.6.2인공적으로만든테스트네트워크
14.6.3성능정량화
14.6.4커뮤니티찾기알고리듬간의비교
14.7다른종류의네트워크구조찾기
14.7.1중첩된커뮤니티
14.7.2계층적커뮤니티
14.7.3중심-주변부구조
14.7.4잠재적공간,계층화된네트워크,순위구조

15장.스미기와네트워크의회복력
15.1스미기
15.2노드를무작위로균일하게제거하기
15.2.1구조모형에서의균일한제거
15.3노드를불균일하게제거하기
15.4실제네트워크에서의스미기
15.5스미기를위한컴퓨터알고리듬
15.5.1실제네트워크에대한결과

16장.네트워크에서의감염병전파
16.1감염전파모형
16.1.1SI모형
16.1.2SIR모형
16.1.3SIR모형의풀이
16.1.4기초감염재생산수
16.1.5SIS모형
16.1.6SIRS모형
16.1.7그밖의감염병전파모형
16.1.8질병의조합
16.1.9복잡한전염과정보전파
16.2네트워크에서의감염병모형
16.3발병크기와스미기
16.3.1SIR모형에서발병규모
16.3.2SIR모형과구조모형
16.3.3공존하는질병
16.3.4동시감염
16.3.5복잡한감염
16.4네트워크에서일어나는전염병확산의시간에의존하는성질
16.5SI모형에서시간에의존하는성질
16.5.1쌍근사
16.5.2SI모형에서링크수기반의근사
16.6SIR모형에서시간에의존하는성질
16.6.1SIR모형에서링크수기반의근사
16.7SIS모형에서시간에의존하는성질
16.7.1SIS모형에서링크수기반의근사

17장.네트워크동역학시스템
17.1동역학시스템
17.1.1고정점과선형화
17.2네트워크동역학
17.2.1선형안정성분석
17.2.2특별한경우
17.2.3예시
17.3한노드에둘이상의변수가있을때의동역학
17.3.1특별한경우
17.4네트워크의스펙트럼
17.5동기화

18장.네트워크검색
18.1웹검색
18.2분산된데이터베이스검색
18.3메시지송신
18.3.1클라인버그모형
18.3.2메시지의계층모형

◈이책에서다루는내용◈

◆네트워크의측정
◆물리학,통계학,사회학에서개발된방법을포함하는네트워크데이터분석방법
◆그래프이론의기초
◆스펙트럼알고리듬과커뮤니티찾기를포함한컴퓨터알고리듬
◆무작위그래프모델과같은네트워크의수학적모델
◆네트워크에서일어나는동역학모델

◈이책의대상독자◈

기술적인수준은각부마다다르다.1부를이해하는데는어떠한수학적지식도필요하지않지만,2부는대학교학부수준의미적분학과일련의선형대수학지식이필요하다.3부와4부는수학적으로더심화되며우수한학부생이나대학원생,해당분야에서활동하고있는연구원에게적합하다.

◈이책의구성◈

네부분으로구성되어있다.머리말에해당하는짧은장에이어,1부에서는현시대과학이연구하는기본적인네트워크의유형과그구조를결정하는데사용하는테크닉을설명한다.2부에서는네트워크의구조를나타내는데사용하는수학적방법,네트워크의구조를정량적으로측정하는측도와통계량들,그리고그러한측도와통계량을계산하는컴퓨터알고리듬을포함해,네트워크학문에서사용하는핵심적인도구를소개한다.3부에서는네트워크화된시스템의행동을예측하고그형성과성장을이해하는데도움을줄수있는네트워크구조의수학적모델을설명한다.4부에서는네트워크회복력에대한모델,네트워크에서일어나는전염병,네트워크탐색과정등네트워크이론의응용사례를살펴본다.

◈옮긴이의말◈

네트워크가궁금한당신은이책을펼쳤습니다.이글을읽는순간,종이에인쇄된글자를만나반사된빛은당신의눈으로들어갑니다.망막에맺힌상(像)은아직은그저빛에서출발한신호,시신경이받은자극에불과합니다.이신호는뇌속에서촘촘하게얽혀있는뇌세포를따라시각자극을처리하는부위로전달되면서비로소정보로처리됩니다.그래서우리는지금이글을이해할수있습니다.뇌세포는이렇게시각정보를처리하는것을포함해미각,촉각,후각,청각등우리몸을구성하는모든신체기관과관련된정보를일시에조절하고통제하는데기여합니다.그복잡한신호처리를순식간에체계적으로해낸다는것은정말대단한일입니다.두뇌처럼매우복잡하지만정교하게통제되어주어진기능을성공적으로수행해내는고도화된체계가작동하는기반에는바로네트워크가있습니다.
이런복잡한네트워크는우리주변에매우다양하게존재합니다.예를들면,수많은컴퓨터와서버사이에서정보를전달하는인터넷,소식을전하고‘좋아요’로답할수있는사회연결망서비스,발전소에서만든전기를소비자가사용할수있게연결해주는전력망,자연계에서서로먹고먹히는관계로이어진먹이그물,인체내에서영양소가분해되어세포소기관이사용할때까지일련의화학반응으로진행되는물질대사등,사회학,물리학,생물학,공학같은실로매우다양한분야에서네트워크를찾아볼수있고활용하고있습니다.
이러한네트워크를분석할수있는이론적인기반을제공하고,궁극적으로는복잡한세상을이해할수있는새로운관점을제시하는것이네트워크과학입니다.그런데네트워크과학이매우활발하게활용되고있음에도,정작네트워크과학을체계적으로배울수있는한국어자료는그리많지않은상황입니다.그래서네트워크과학서적번역의두번째프로젝트로,기본서라할수있는서적인이책을번역했습니다.
원서의저자인마크뉴만은2002년부터현재까지미시간대학교물리학과에서교수로재직중이며,네트워크과학을이론적으로정립하는데기여한공로로2021년네트워크학회에서수여하는오일러상을수상한명실상부한네트워크과학분야의최고권위자중한명입니다.연구뿐만이아니라교육에서도탁월한역량을발휘해,2012년에는미시간대학교우수교육상을받았으며,2015년에해당대학에서수여하는최고권위의교수직인아나톨라포포트석학교수(AnatolRapoportDistinguishedUniversityProfessor)로임명됐고,지금까지총여섯편의서적을출판했습니다.이책은그중에서도네트워크이론을체계적으로설명하고다양한네트워크응용사례를충실하게소개하는입문서로서,네트워크를진지하게공부하려는사람들에게필독서로여겨질만큼매우훌륭한안내서입니다.2010년에출판된초판이2018년개정되면서방대한내용이추가됐고,지금읽어도부족함이없을만큼네트워크과학분야의최신지식을망라하고있습니다.
다양한분야를다루는이책을온전히번역하기위해,역시다양한분야에서네트워크과학을연구하고적용하고있는한국의네트워크과학자들이모였습니다.공동번역자대부분이최근『네트워크분석』(에이콘,2022)를함께번역및출판하면서,독자들이받아들이기편하고이해하기쉬운표현에대해고민을함께한바있습니다.그경험을바탕으로,이책을번역하면서일관된표현을사용하는데힘쓰고한국어네트워크용어를정립하고자노력했습니다.이책이한국어로편안하고쉽게읽을수있는또하나의지침서가되어,네트워크과학을배우고싶어하는독자들의필요를채워주는역할을할수있기를바랍니다.