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
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
上传资源赚积分or赚钱
最新推荐
02 Graph Theory and Complex Networks An Introduction 10积分/C币 立即下载
1/127
02 Graph Theory and Complex Networks An Introduction第1页
02 Graph Theory and Complex Networks An Introduction第2页
02 Graph Theory and Complex Networks An Introduction第3页
02 Graph Theory and Complex Networks An Introduction第4页
02 Graph Theory and Complex Networks An Introduction第5页
02 Graph Theory and Complex Networks An Introduction第6页
02 Graph Theory and Complex Networks An Introduction第7页
02 Graph Theory and Complex Networks An Introduction第8页
02 Graph Theory and Complex Networks An Introduction第9页
02 Graph Theory and Complex Networks An Introduction第10页
02 Graph Theory and Complex Networks An Introduction第11页
02 Graph Theory and Complex Networks An Introduction第12页
02 Graph Theory and Complex Networks An Introduction第13页
02 Graph Theory and Complex Networks An Introduction第14页
02 Graph Theory and Complex Networks An Introduction第15页
02 Graph Theory and Complex Networks An Introduction第16页
02 Graph Theory and Complex Networks An Introduction第17页
02 Graph Theory and Complex Networks An Introduction第18页
02 Graph Theory and Complex Networks An Introduction第19页
02 Graph Theory and Complex Networks An Introduction第20页

试读结束, 可继续阅读

10积分/C币 立即下载 >