网络导论（英文）-789页.doc
N E T W O R K SThis page intentionally left blankNetworksAn IntroductionM. E. J. NewmanUniversity of MichiganandSanta Fe Institute13Great Clarendon Street, Oxford OX2 6DPOxford University Press is a department of the University of Oxford.It furthers the Universitys objective of excellence in research, scholarship,and education by publishing worldwide inOxford New YorkAuckland Cape Town Dar es Salaam Hong Kong KarachiKuala Lumpur Madrid Melbourne Mexico City NairobiNew Delhi Shanghai Taipei TorontoWith offices inArgentina Austria Brazil Chile Czech Republic France GreeceGuatemala Hungary Italy Japan Poland Portugal SingaporeSouth Korea Switzerland Thailand Turkey Ukraine VietnamOxford is a registered trade mark of Oxford University Pressin the UK and in certain other countriesPublished in the United Statesby Oxford University Press Inc., New York© M. E. J. Newman 2010The moral rights of the author have been assertedDatabase right Oxford University Press (maker)First printed 2010All 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 appropriatereprographics rights organization. Enquiries concerning reproduction outside the scope of the above should be sent to the Rights Department, Oxford University Press, at the address aboveYou must not circulate this book in any other binding or coverand you must impose the same condition on any acquirerBritish Library Cataloguing in Publication DataData availableLibrary of Congress Cataloging in Publication DataData availableTypeset by SPI Publisher Services, Pondicherry, IndiaPrinted in Great Britainon acid-free paper byCPI Antony Rowe, Chippenham, WiltshireISBN 9780199206650 (Hbk.)1 3 5 7 9 10 8 6 4 2CONTENTSPrefacex1Introduction1I The empirical study of networks152Technological networks172.1The Internet . . . . . . . . . . . . . . . . . . . . . . . . . . . . .182.2The telephone network . . . . . . . . . . . . . . . . . . . . . . .282.3Power grids . . . . . . . . . . . . . . . . . . . . . . . . . . . . .312.4Transportation networks . . . . . . . . . . . . . . . . . . . . . .322.5Delivery and distribution networks . . . . . . . . . . . . . . . .333Social networks363.1The empirical study of social networks . . . . . . . . . . . . . .363.2Interviews and questionnaires . . . . . . . . . . . . . . . . . . .393.3Direct observation . . . . . . . . . . . . . . . . . . . . . . . . . .463.4Data from archival or third-party records . . . . . . . . . . . .473.5Affiliation networks . . . . . . . . . . . . . . . . . . . . . . . . .533.6The small-world experiment . . . . . . . . . . . . . . . . . . . .543.7Snowball sampling, contact tracing, and random walks . . . .584Networks of information634.1The World Wide Web . . . . . . . . . . . . . . . . . . . . . . . .634.2Citation networks . . . . . . . . . . . . . . . . . . . . . . . . . .674.3Other information networks . . . . . . . . . . . . . . . . . . . .725Biological networks785.1Biochemical networks . . . . . . . . . . . . . . . . . . . . . . .785.2Neural networks . . . . . . . . . . . . . . . . . . . . . . . . . . .945.3Ecological networks . . . . . . . . . . . . . . . . . . . . . . . . .99vCONTENTSII Fundamentals of network theory1076Mathematics of networks1096.1Networks and their representation . . . . . . . . . . . . . . . .1096.2The adjacency matrix . . . . . . . . . . . . . . . . . . . . . . . .1106.3Weighted networks . . . . . . . . . . . . . . . . . . . . . . . . .1126.4Directed networks . . . . . . . . . . . . . . . . . . . . . . . . . .1146.5Hypergraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1226.6Bipartite networks . . . . . . . . . . . . . . . . . . . . . . . . . .1236.7Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1276.8Planar networks . . . . . . . . . . . . . . . . . . . . . . . . . . .1296.9Degree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1336.10Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1366.11Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1426.12Independent paths, connectivity, and cut sets . . . . . . . . . .1456.13The graph Laplacian . . . . . . . . . . . . . . . . . . . . . . . .1526.14Random walks . . . . . . . . . . . . . . . . . . . . . . . . . . . .1577Measures and metrics1687.1Degree centrality . . . . . . . . . . . . . . . . . . . . . . . . . .1687.2Eigenvector centrality . . . . . . . . . . . . . . . . . . . . . . . .1697.3Katz centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . .1727.4PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1757.5Hubs and authorities . . . . . . . . . . . . . . . . . . . . . . . .1787.6Closeness centrality . . . . . . . . . . . . . . . . . . . . . . . . .1817.7Betweenness centrality . . . . . . . . . . . . . . . . . . . . . . .1857.8Groups of vertices . . . . . . . . . . . . . . . . . . . . . . . . . .1937.9Transitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1987.10Reciprocity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2047.11Signed edges and structural balance . . . . . . . . . . . . . . .2067.12Similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2117.13Homophily and assortative mixing . . . . . . . . . . . . . . . .2208 The large-scale structure of networks2358.1Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2358.2Shortest paths and the small-world effect . . . . . . . . . . . .2418.3Degree distributions . . . . . . . . . . . . . . . . . . . . . . . .2438.4Power laws and scale-free networks . . . . . . . . . . . . . . .2478.5Distributions of other centrality measures . . . . . . . . . . . .2618.6Clustering coefficients . . . . . . . . . . . . . . . . . . . . . . .262viCONTENTS8.7Assortative mixing . . . . . . . . . . . . . . . . . . . . . . . . .266III Computer algorithms2739Basic concepts of algorithms2759.1Running time and computational complexity . . . . . . . . . .2789.2Storing network data . . . . . . . . . . . . . . . . . . . . . . . .2829.3The adjacency matrix . . . . . . . . . . . . . . . . . . . . . . . .2839.4The adjacency list . . . . . . . . . . . . . . . . . . . . . . . . . .2869.5Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2909.6Other network representations . . . . . . . . . . . . . . . . . .2989.7Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30110Fundamental network algorithms30810.1Algorithms for degrees and degree distributions . . . . . . . .30810.2Clustering coefficients . . . . . . . . . . . . . . . . . . . . . . .31010.3Shortest paths and breadth-first search . . . . . . . . . . . . . .31510.4Shortest paths in networks with varying edge lengths . . . . .32910.5Maximum flows and minimum cuts . . . . . . . . . . . . . . .33311Matrix algorithms and graph partitioning34511.1Leading eigenvectors and eigenvector centrality . . . . . . . .34511.2Dividing networks into clusters . . . . . . . . . . . . . . . . . .35411.3Graph partitioning . . . . . . . . . . . . . . . . . . . . . . . . .35811.4The KernighanLin algorithm . . . . . . . . . . . . . . . . . . .36011.5Spectral partitioning . . . . . . . . . . . . . . . . . . . . . . . .36411.6Community detection . . . . . . . . . . . . . . . . . . . . . . . .37111.7Simple modularity maximization . . . . . . . . . . . . . . . . .37311.8Spectral modularity maximization . . . . . . . . . . . . . . . .37511.9Division into more than two groups . . . . . . . . . . . . . . .37811.10Other modularity maximization methods . . . . . . . . . . . .38011.11Other algorithms for community detection . . . . . . . . . . .382IV Network models39512Random graphs39712.1Random graphs . . . . . . . . . . . . . . . . . . . . . . . . . . .39812.2Mean number of edges and mean degree . . . . . . . . . . . .40012.3Degree distribution . . . . . . . . . . . . . . . . . . . . . . . . .401viiCONTENTS12.4Clustering coefficient . . . . . . . . . . . . . . . . . . . . . . . .40212.5Giant component. . . . . . . . . . . . . . . . . . . . . . . . . .40312.6Small components . . . . . . . . . . . . . . . . . . . . . . . . . .40812.7Path lengths . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41912.8Problems with the random graph . . . . . . . . . . . . . . . . .42313 Random graphs with general degree distributions42813.1Generating functions . . . . . . . . . . . . . . . . . . . . . . . .42913.2The configuration model . . . . . . . . . . . . . . . . . . . . . .43413.3Excess degree distribution . . . . . . . . . . . . . . . . . . . . .44513.4Clustering coefficient . . . . . . . . . . . . . . . . . . . . . . . .44913.5Generating functions for degree distributions . . . . . . . . . .45013.6Number of second neighbors of a vertex . . . . . . . . . . . . .45113.7Generating functions for the small components . . . . . . . . .45613.8Giant component. . . . . . . . . . . . . . . . . . . . . . . . . .46013.9Size distribution for small components . . . . . . . . . . . . . .46513.10 Power-law degree distributions . . . . . . . . . . . . . . . . . .47013.11 Directed random graphs . . . . . . . . . . . . . . . . . . . . . .47314 Models of network formation48614.1Preferential attachment . . . . . . . . . . . . . . . . . . . . . . .48714.2The model of Barabasi´ and Albert . . . . . . . . . . . . . . . . .50014.3Further properties of preferential attachment models. . . . .50314.4Extensions of preferential attachment models . . . . . . . . . .51414.5Vertex copying models . . . . . . . . . . . . . . . . . . . . . . .53414.6Network optimization models . . . . . . . . . . . . . . . . . . .54115 Other network models55215.1The small-world model . . . . . . . . . . . . . . . . . . . . . . .55215.2Exponential random graphs . . . . . . . . . . . . . . . . . . . .565VProcesses on networks58916 Percolation and network resilience59116.1Percolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .59216.2Uniform random removal of vertices . . . . . . . . . . . . . . .59416.3Non-uniform removal of vertices . . . . . . . . . . . . . . . . .60916.4Percolation in real-world networks . . . . . . . . . . . . . . . .61516.5Computer algorithms for percolation . . . . . . . . . . . . . . .616viiiCONTENTS17 Epidemics on networks62717.1Models of the spread of disease . . . . . . . . . . . . . . . . . .62717.2The SI model . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62817.3The SIR model . . . . . . . . . . . . . . . . . . . . . . . . . . . .63117.4The SIS model . . . . . . . . . . . . . . . . . . . . . . . . . . . .63617.5The SIRS model . . . . . . . . . . . . . . . . . . . . . . . . . . .63717.6Epidemic models on networks . . . . . . . . . . . . . . . . . . .63917.7Late-time properties of epidemics on networks . . . . . . . . .64017.8Late-time properties of the SIR model. . . . . . . . . . . . . .64217.9Time-dependent properties of epidemics on networks . . . . .64817.10 Time-dependent properties of the SI model . . . . . . . . . . .64817.11 Time-dependent properties of the SIR model. . . . . . . . . .66117.12 Time-dependent properties of the SIS model. . . . . . . . . .66918 Dynamical systems on networks67618.1Dynamical systems . . . . . . . . . . . . . . . . . . . . . . . . .67718.2Dynamics on networks . . . . . . . . . . . . . . . . . . . . . . .68618.3Dynamics with more than one variable per vertex. . . . . . .69518.4Synchronization . . . . . . . . . . . . . . . . . . . . . . . . . . .70119 Network search70519.1Web search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .70519.2Searching distributed databases . . . . . . . . . . . . . . . . . .70919.3Message passing . . . . . . . . . . . . . . . . . . . . . . . . . . .713References727Index740ixPREFACEThe scientific study of networks, such as computer networks, biological net-works, and social networks, is an interdisciplinary field that combines ideas from mathematics, physics, biology, computer science, the social sciences, and many other areas. The field has benefited enormously from the wide range of viewpoints brought to it by practitioners from so many different disciplines, but it has also suffered because human knowledge about networks is dispersed across the scientific community and researchers in one area often do not have ready access to discoveries made in another. The goal of this book is to bring our knowledge of networks together and present it in consistent language and notation, so that it becomes a coherent whole whose elements complement one another and in combination teach us more than any single element can alone.The book is divided into five parts. Following a short introductory chap-ter, Part I describes the basic types of networks studied by present-day science and the empirical techniques used to determine their structure. Part II intro-duces the fundamental mathematical tools used in the study of networks as well as measures and statistics for quantifying network structure. Part III de-scribes computer algorithms for the efficient analysis of network data, while Part IV describes mathematical models of network structure that can help us predict the behavior of networked systems and understand their formation and growth. Finally, Part V describes theories of processes taking place o
