Nội dung

Graph Theory and Complex Networks An Introduction Maarten van Steen Copyright © 2010 Maarten van Steen Published by Maarten van Steen ISBN: 978-90-815406-1-2 Edition: 1. Printing: 01 (April 2010) All rights to text and illustrations are reserved by Maarten van Steen. This work may not be copied, reproduced, or translated in whole or part without written permission of the publisher, except for brief excerpts in reviews or scholarly analysis. Use with any form of information storage and retrieval, electronic adaptation or whatever, computer software, or by similar or dissimilar methods now known or developed in the future is strictly forbidden without written permission of the publisher. To Mariëlle, Max, and Elke C ONTENTS Preface 1 2 3 ix Introduction 1.1 Communication networks . . . Historical perspective . . . . . . From telephony to the Internet The Web and Wikis . . . . . . . 1.2 Social networks . . . . . . . . . Online communities . . . . . . Traditional social networks . . 1.3 Networks everywhere . . . . . 1.4 Organization of this book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . 4 . 4 . 6 . 8 . 9 . 9 . 10 . 11 . 13 Foundations 2.1 Formalities . . . . . . . . . Graphs and vertex degrees Degree sequence . . . . . . Subgraphs and line graphs 2.2 Graph representations . . Data structures . . . . . . Graph isomorphism . . . 2.3 Connectivity . . . . . . . . 2.4 Drawing graphs . . . . . . Graph embeddings . . . . Planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 18 18 23 28 31 31 33 37 45 45 50 Extensions 55 3.1 Directed graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Basics of directed graphs . . . . . . . . . . . . . . . . . . . . . . 57 v PERSONALIZED FOR Connectivity for directed graphs Weighted graphs . . . . . . . . . Colorings . . . . . . . . . . . . . . Edge colorings . . . . . . . . . . . Vertex colorings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 65 69 69 71 Network traversal 4.1 Euler tours . . . . . . . . . . . . . Constructing an Euler tour . . . . The Chinese postman problem . 4.2 Hamilton cycles . . . . . . . . . . Properties of Hamiltonian graphs Finding a Hamilton cycle . . . . . Optimal Hamilton cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 81 82 87 92 92 97 100 Trees 5.1 Background . . . . . . . . . . . . . . Trees in transportation networks . . Trees as data structures . . . . . . . . 5.2 Fundamentals . . . . . . . . . . . . . 5.3 Spanning trees . . . . . . . . . . . . . 5.4 Routing in communication networks Dijkstra’s algorithm . . . . . . . . . . The Bellman-Ford algorithm . . . . . A note on algorithmic performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 107 107 109 112 116 119 120 123 127 Network analysis 6.1 Vertex degrees . . . . . . . Degree distribution . . . . Degree correlations . . . . 6.2 Distance statistics . . . . . 6.3 Clustering coefficient . . . Some effects of clustering Local view . . . . . . . . . Global view . . . . . . . . 6.4 Centrality . . . . . . . . . 3.2 3.3 4 5 6 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 133 134 136 140 143 143 144 146 150 Random networks 7.1 Introduction . . . . . . . . . . . . 7.2 Classical random networks . . . Degree distribution . . . . . . . . Other metrics for random graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 157 158 159 162 . . . . . . . . . . . . . . . . . . . . . . . . . . . EEGCHEN@CITYU.EDU.HK vi PERSONALIZED FOR 7.3 7.4 8 9 Small worlds . . . . . . . . . . . . Scale-free networks . . . . . . . . Fundamentals . . . . . . . . . . . Properties of scale-free networks Related networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 172 172 178 181 Modern computer networks 8.1 The Internet . . . . . . . . . . . . . . . . Computer networks . . . . . . . . . . . . Measuring the topology of the Internet . 8.2 Peer-to-peer overlay networks . . . . . . Structured overlay networks . . . . . . . Random overlay networks . . . . . . . . 8.3 The World Wide Web . . . . . . . . . . . The organization of the Web . . . . . . . Measuring the topology of the Web . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 187 187 192 195 196 204 212 212 214 . . . . . . . . . . . . . 223 225 225 227 231 234 234 240 246 252 255 255 258 259 Social networks 9.1 Social network analysis: introduction Examples . . . . . . . . . . . . . . . . . Historical background . . . . . . . . . Sociograms in practice: a teacher’s aid 9.2 Some basic concepts . . . . . . . . . . Centrality and prestige . . . . . . . . . Structural balance . . . . . . . . . . . . Cohesive subgroups . . . . . . . . . . Affiliation networks . . . . . . . . . . . 9.3 Equivalence . . . . . . . . . . . . . . . Structural equivalence . . . . . . . . . Automorphic equivalence . . . . . . . Regular equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusions 261 Mathematical notations 267 Index 271 Bibliography 279 EEGCHEN@CITYU.EDU.HK vii