02GraphTheoryandComplexNetworksAnIntroduction-讲义文档类资源-CSDN下载

02 Graph Theory and Complex Networks An Introduction

所需积分/C币：10 2015-09-30 21:09:43 5.02MB PDF
收藏
举报

Graph Theory and Complex Networks An Introduction
Copyright o 2010 Maarten van Steen Published by Maarten van Steen 工SBN: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 Marielle, max, and elke CONTENTS reface 1 Introductio 1.1 Communication networks Historical perspective From telephony to the Internet The Web and wikis 8 1.2 Social networks Online communities Traditional 1.3 Networks everywhere 1.4 Organization of this book 2 Foundations 2.1 Formalities 18 Graphs and vertex degrees Degree sequenc 231 Subgraphs and line graphs 28 2.2 Graph representations Data structures 31 Graph isomorphism 33 2.3 Connectivity 2.4 Drawing graphs 15 Graph embeddings Planar graphs 3 Extensions 55 3.1 Directed graphs Basics of directed graphs Connectivity for directed graphs 3. 2 Weighted graphs 3. 3 Colorings 69 Edge colorings Vertex colorings 4 Network traversal 4.1 Euler tours Constructing an euler tour The Chinese postman problem 4.2 Hamilton cycles 2 Properties of hamiltonian graphs 92 Finding a hamilton cycle 97 Optimal hamilton cycles 5 Trees 105 5.1 Background Trees in transportation networks 107 Trees as data structures 5.2 Fundamentals 2 5.3 Spanning trees 116 5.4 Routing in communication networks n19 Dijkstra's algorithm ....120 The Bellman-Ford algorithm .....①23 A note on algorithmic performance 127 6 Network analysis 131 6.1 Vertex degrees 133 Degree distribution 134 Degree correlations 136 6.2 Distance statistics 140 6.3 Clustering coefficient 143 Some effects of clustering 143 Local view 144 Global view 146 6.4 Centrality 150 7 Random networks 155 7. 1 Introduction 157 7.2 Classical random networks Degree distribution 159 Other metrics for random graphs ...[62 7.3 Small worlds 166 7.4 Scale-free networks Fundamentals Properties of scale-free networks ①78 Related networks 8 Modern computer networks 8.1 The Internet Computer networks 187 Measuring the topology of the Internet 92 8.2 Peer-to-peer overlay networks 95 Structured overlay networks 196 Random overlay networks ....204 8.3 The world wide web P12 The organization of the Web 212 Measuring the topology of the Web 214 9 Social networks 9.1 Social network analysis: introduction 225 Examples 2251 Historical background 227 Sociograms in practice: a teacher's aid 231 9. 2 Some basic concepts Centrality and prestige Structural balance 240 Cohesive subgroups 24 Affiliation networks 252 9.3 Equival 255 Structural equivalence 255 Automorphic equivalence Regular equivalence 25 Conclusions 261 Mathematical notations 267 Index 21 Bibliography 279

...展开详情

数学建模

试读 127P 02 Graph Theory and Complex Networks An Introduction