第1页 / 共789页
第2页 / 共789页
第3页 / 共789页
第4页 / 共789页
第5页 / 共789页
第6页 / 共789页
第7页 / 共789页
第8页 / 共789页
复杂网络导论.pdf
Contents
Preface
1 Introduction
I: The empirical study of networks
2 Technological networks
2.1 The Internet
2.2 The telephone network
2.3 Power grids
2.4 Transportation networks
2.5 Delivery and distribution networks
3 Social networks
3.1 The empirical study of social networks
3.2 Interviews and questionnaires
3.3 Direct observation
3.4 Data from archival or third-party records
3.5 Affiliation networks
3.6 The small-world experiment
3.7 Snowball sampling, contact tracing, and random walks
4 Networks of information
4.1 The World Wide Web
4.2 Citation networks
4.3 Other information networks
5 Biological networks
5.1 Biochemical networks
5.2 Neural networks
5.3 Ecological networks
II: Fundamentals of network theory
6 Mathematics of networks
6.1 Networks and their representation
6.2 The adjacency matrix
6.3 Weighted networks
6.4 Directed networks
6.5 Hypergraphs
6.6 Bipartite networks
6.7 Trees
6.8 Planar networks
6.9 Degree
6.10 Paths
6.11 Components
6.12 Independent paths, connectivity, and cut sets
6.13 The graph Laplacian
6.14 Random walks
7 Measures and metrics
7.1 Degree centrality
7.2 Eigenvector centrality
7.3 Katz centrality
7.4 PageRank
7.5 Hubs and authorities
7.6 Closeness centrality
7.7 Betweenness centrality
7.8 Groups of vertices
7.9 Transitivity
7.10 Reciprocity
7.11 Signed edges and structural balance
7.12 Similarity
7.13 Homophily and assortative mixing
8 The large-scale structure of networks
8.1 Components
8.2 Shortest paths and the small-world effect
8.3 Degree distributions
8.4 Power laws and scale-free networks
8.5 Distributions of other centrality measures
8.6 Clustering coefficients
8.7 Assortative mixing
III: Computer algorithms
9 Basic concepts of algorithms
9.1 Running time and computational complexity
9.2 Storing network data
9.3 The adjacency matrix
9.4 The adjacency list
9.5 Trees
9.6 Other network representations
9.7 Heaps
10 Fundamental network algorithms
10.1 Algorithms for degrees and degree distributions
10.2 Clustering coefficients
10.3 Shortest paths and breadth-first search
10.4 Shortest paths in networks with varying edge lengths
10.5 Maximum flows and minimum cuts
11 Matrix algorithms and graph partitioning
11.1 Leading eigenvectors and eigenvector centrality
11.2 Dividing networks into clusters
11.3 Graph partitioning
11.4 The Kernighan–Lin algorithm
11.5 Spectral partitioning
11.6 Community detection
11.7 Simple modularity maximization
11.8 Spectral modularity maximization
11.9 Division into more than two groups
11.10 Other modularity maximization methods
11.11 Other algorithms for community detection
IV: Network models
12 Random graphs
12.1 Random graphs
12.2 Mean number of edges and mean degree
12.3 Degree distribution
12.4 Clustering coefficient
12.5 Giant component
12.6 Small components
12.7 Path lengths
12.8 Problems with the random graph
13 Random graphs with general degree distributions
13.1 Generating functions
13.2 The configuration model
13.3 Excess degree distribution
13.4 Clustering coefficient
13.5 Generating functions for degree distributions
13.6 Number of second neighbors of a vertex
13.7 Generating functions for the small components
13.8 Giant component
13.9 Size distribution for small components
13.10 Power-law degree distributions
13.11 Directed random graphs
14 Models of network formation
14.1 Preferential attachment
14.2 The model of Barabási and Albert
14.3 Further properties of preferential attachment models
14.4 Extensions of preferential attachment models
14.5 Vertex copying models
14.6 Network optimization models
15 Other network models
15.1 The small-worldmodel
15.2 Exponential random graphs
V: Processes on networks
16 Percolation and network resilience
16.1 Percolation
16.2 Uniform random removal of vertices
16.3 Non-uniform removal of vertices
16.4 Percolation in real-world networks
16.5 Computer algorithms for percolation
17 Epidemics on networks
17.1 Models of the spread of disease
17.2 The SI model
17.3 The SIR model
17.4 The SIS model
17.5 The SIRS model
17.6 Epidemic models on networks
17.7 Late-time properties of epidemics on networks
17.8 Late-time properties of the SIR model
17.9 Time-dependent properties of epidemics on networks
17.10 Time-dependent properties of the SI model
17.11 Time-dependent properties of the SIR model
17.12 Time-dependent properties of the SIS model
18 Dynamical systems on networks
18.1 Dynamical systems
18.2 Dynamics on networks
18.3 Dynamics with more than one variable per vertex
18.4 Synchronization
19 Network search
19.1 Web search
19.2 Searching distributed databases
19.3 Message passing
References
Index
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
Y
Z
NETWORKS
This page intentionally left blank
Networks
An Introduction
M. E. J. Newman
University of Michigan
and
Santa Fe Institute
1
3
Great Clarendon Street, Oxford OX2 6DP
Oxford University Press is a department of the University of Oxford.
It furthers the University’s objective of excellence in research, scholarship,
and education by publishing worldwide in
Oxford New York
Auckland Cape Town Dar es Salaam Hong Kong Karachi
Kuala Lumpur Madrid Melbourne Mexico City Nairobi
New Delhi Shanghai Taipei Toronto
With offices in
Argentina Austria Brazil Chile Czech Republic France Greece
Guatemala Hungary Italy Japan Poland Portugal Singapore
South Korea Switzerland Thailand Turkey Ukraine Vietnam
Oxford is a registered trade mark of Oxford University Press
in the UK and in certain other countries
Published in the United States
by Oxford University Press Inc., New York
© M. E. J. Newman 2010
The moral rights of the author have been asserted
Database right Oxford University Press (maker)
First printed 2010
All rights reserved. No part of this publication may be reproduced,
stored in a retrieval system, or transmitted, in any form or by any means,
without the prior permission in writing of Oxford University Press,
or as expressly permitted by law, or under terms agreed with the appropriate
reprographics rights organization. Enquiries concerning reproduction
outside the scope of the above should be sent to the Rights Department,
Oxford University Press, at the address above
You must not circulate this book in any other binding or cover
and you must impose the same condition on any acquirer
British Library Cataloguing in Publication Data
Data available
Library of Congress Cataloging in Publication Data
Data available
Typeset by SPI Publisher Services, Pondicherry, India
Printed in Great Britain
on acid-free paper by
CPI Antony Rowe, Chippenham, Wiltshire
ISBN 978–0–19–920665–0 (Hbk.)
1 3 5 7 9 10 8 6 4 2
CONTENTS
Preface
1 Introduction
I The empirical study of networks
2 Technological networks
.
.
.
2.1
2.2
2.3
2.4
2.5
.
.
The Internet
.
.
The telephone network .
.
Power grids
.
Transportation networks .
Delivery and distribution networks . . . . . . . .
. . . . .
. . . . . .
. . . . .
. . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . . .
. . . . . . .
. . . . .
. .
. . . .
. . . . . .
. . . . .
. .
. . . . .
. . . . . . . . .
3 Social networks
3.1
3.2
3.3
3.4
3.5
3.6
3.7
The empirical study of social networks . . . . . . . . . . . . . .
Interviews and questionnaires . . . . . . . . . . . . . . . . . . .
Direct observation . . . . . . . . . . . . . . . . . . . . . . . . . .
Data from archival or third-party records
. . . . . . . . . . . .
Affiliation networks . . . . . . . . . . . . . . . . . . . . . . . . .
The small-world experiment . .
. . . . . . . . . . . . . . . . . .
Snowball sampling, contact tracing, and random walks . . . .
4 Networks of information
4.1
4.2
4.3
.
The World Wide Web .
Citation networks .
.
.
Other information networks .
.
.
.
.
.
.
.
5 Biological networks
5.1
5.2
5.3
Biochemical networks
Neural networks .
.
Ecological networks .
.
.
.
.
.
.
.
.
.
. .
.
.
.
.
v
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . . . . . .
. .
. . . . . . .
. . . . . . . . .
. . . .
. . . . . . . . .
. . . . . . . . . .
. . . .
. . . .
. .
. . . . . . . . . .
. . . . . . . . . .
. .
. .
. . . .
. . . . . . . . . .
x
1
15
17
18
28
31
32
33
36
36
39
46
47
53
54
58
63
63
67
72
78
78
94
99
CONTENTS
II Fundamentals of network theory
107
6 Mathematics of networks
Networks and their representation . . . . . . .
The adjacency matrix . .
. . . . . . . . . . .
.
. . .
6.1
6.2
6.3 Weighted networks . . . . . . . .
Directed networks .
. . . .
6.4
Hypergraphs . . . . . . . .
6.5
Bipartite networks .
6.6
Trees
. . . . . . . . . .
6.7
Planar networks . . . . . .
6.8
Degree .
. . . . . . . . . .
6.9
6.10
. . . . . .
.
Paths .
6.11 Components . . . .
6.12
6.13
6.14 Random walks . . .
. . . . .
. . . . .
. . .
. .
. . .
. . . . . . .
. . . . . .
.
.
. . . .
. . . . . . . . . . .
. . . . . . . . . . . . . .
. . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . . .
. .
. .
. . . .
109
. . . . . . . 109
. . . . . . . 110
. . . . . . . . . . . . . 112
. . . . . . . 114
. . . . 122
. . 123
. . . . 127
. . 129
. . . . 133
. . . . . . . 136
. . . . . . . 142
.
. 145
. . . . . . . 152
. . . . 157
. .
. . . .
.
. . . .
.
.
.
.
.
.
. . . . . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . .
Independent paths, connectivity, and cut sets .
The graph Laplacian . .
. . . . . . . . . . .
7 Measures and metrics
. . . . . . . . . . .
. . . . . . . . .
. . . . . . . . . . .
. . . . . . . . .
. . . .
. . . . .
Degree centrality .
Eigenvector centrality . . . . . . . .
. . . . .
Katz centrality . . .
PageRank .
. . . . .
. . . . .
Hubs and authorities . . . .
Closeness centrality .
Betweenness centrality . . .
Groups of vertices . . . . .
. . . . .
Transitivity . . . .
7.1
7.2
7.3
7.4
7.5
7.6
7.7
7.8
7.9
7.10 Reciprocity . .
7.11
7.12
7.13 Homophily and assortative mixing . . . .
. . . . . . . . . . . .
. . . . . . . . . . .
. . . .
. . . .
Signed edges and structural balance . . . . . . . . .
Similarity . . . . .
. . . . . . . . . . .
. . . . .
. .
. . . .
. .
. . . .
. .
168
. . . . . . . 168
. . . . . . . . . . . . 169
. . . . . . . 172
. . . . . . . 175
. . . . . . . 178
. . . . . . . . . . 181
. . 185
. . . . 193
. . 198
. . . . . . . . . 204
. . . . . . 206
. . 211
. . . 220
. . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . .
. . .
. . . . . . . . . . .
. .
. . . . . . . . . . .
. . .
. . . . . . . . .
8 The large-scale structure of networks
. .
. . . .
Components . . . . . . . .
Shortest paths and the small-world effect
Degree distributions
Power laws and scale-free networks
Distributions of other centrality measures .
. . . . . . . . .
Clustering coefficients
. . . . . . . . . . . . .
. . .
. . . . . .
. . . .
. .
. . . .
. . . .
. . . . . . . . . . . . .
. . . . . . . .
235
. . 235
. . . . 241
. . . . . . . 243
. . . . . . . 247
. . . . . . . 261
. . . . . . . 262
8.1
8.2
8.3
8.4
8.5
8.6
vi
8.7
Assortative mixing .
.
.
.
.
.
.
.
.
. . . .
. . . . .
. . . . . . . 266
III Computer algorithms
273
CONTENTS
9 Basic concepts of algorithms
275
Running time and computational complexity . . . . . . . . . . 278
Storing network data . . . . . . . . . . . . . . . . . . . . . . . . 282
The adjacency matrix .
. . . . . . . . . . . . . . . . . . . . . . . 283
The adjacency list . . . . . . . . . . . . . . . . . . . . . . . . . . 286
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
Trees
Other network representations
. . . . . . . . . . . . . . . . . . 298
Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
9.1
9.2
9.3
9.4
9.5
9.6
9.7
10 Fundamental network algorithms
308
10.1 Algorithms for degrees and degree distributions . . . . . . . . 308
10.2 Clustering coefficients
. . . . . . . . . . . . . . . . . . . . . . . 310
Shortest paths and breadth-first search . . . . . . . . . . . . . . 315
10.3
10.4
Shortest paths in networks with varying edge lengths .
. . . . 329
. . . . . . . . . . . . . . 333
10.5 Maximum flows and minimum cuts .
11 Matrix algorithms and graph partitioning
345
11.1
Leading eigenvectors and eigenvector centrality . . . . . . . . 345
11.2 Dividing networks into clusters . . . . . . . . . . . . . . . . . . 354
11.3 Graph partitioning . . . . . . . . . . . . . . . . . . . . . . . . . 358
The Kernighan–Lin algorithm . . . . . . . . . . . . . . . . . . . 360
11.4
11.5
Spectral partitioning . . . . . . . . . . . . . . . . . . . . . . . . 364
11.6 Community detection . . . . . . . . . . . . . . . . . . . . . . . . 371
Simple modularity maximization . . . . . . . . . . . . . . . . . 373
11.7
Spectral modularity maximization . . . . . . . . . . . . . . . . 375
11.8
11.9 Division into more than two groups
. . . . . . . . . . . . . . . 378
11.10 Other modularity maximization methods . . . . . . . . . . . . 380
11.11 Other algorithms for community detection . . . . . . . . . . . 382
IV Network models
12 Random graphs
12.1 Random graphs .
12.2 Mean number of edges and mean degree . . .
12.3 Degree distribution .
. . . . . .
. . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
395
. . . .
397
. . . . . . 398
. . . . . . . . . 400
. . . . . . 401
. .
vii
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
