Fundamentals of Complex Networks E-Book

Guanrong Chen

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 726

Veröffentlichungsjahr: 2014

Beschreibung

Complex networks such as the Internet, WWW, transportation networks, power grids, biological neural networks, and scientific cooperation networks of all kinds provide challenges for future technological development. * The first systematic presentation of dynamical evolving networks, with many up-to-date applications and homework projects to enhance study * The authors are all very active and well-known in the rapidly evolving field of complex networks * Complex networks are becoming an increasingly important area of research * Presented in a logical, constructive style, from basic through to complex, examining algorithms, through to construct networks and research challenges of the future

Leseprobe

Table of Contents

Title Page

Copyright

About the Authors

Preface

Acknowledgements

Part One: Fundamental Theory

Chapter 1: Introduction

1.1 Background and Motivation

1.2 A Brief History of Complex Network Research

1.3 New Era of Complex-Network Studies

Exercises

References

Chapter 2: Preliminaries

2.1 Elementary Graph Theory

2.2 Elementary Probability and Statistics

2.3 Elementary Dynamical Systems Theory

Exercises

References

Chapter 3: Network Topologies: Basic Models and Properties

3.1 Introduction

3.2 Regular Networks

3.3 ER Random-Graph Model

3.4 Small-World Network Models

3.5 Navigable Small-World Network Model

3.6 Scale-Free Network Models

Exercises

References

Part Two: Applications - Selected Topics

Chapter 4: Internet: Topology and Modeling

4.1 Introduction

4.2 Topological Properties of the Internet

4.3 Random-Graph Network Topology Generator

4.4 Structural Network Topology Generators

4.5 Connectivity-Based Network Topology Generators

4.6 Multi-Local-World Model

4.7 HOT Model

4.8 Dynamical Behaviors of the Internet Topological Characteristics

4.9 Traffic Fluctuation on Weighted Networks

References

Chapter 5: Epidemic Spreading Dynamics

5.1 Introduction

5.2 Epidemic Threshold Theory

5.3 Epidemic Spreading on Spatial Networks

5.4 Immunization on Complex Networks

5.5 Computer Virus Spreading over the Internet

References

Chapter 6: Community Structures

6.1 Introduction

6.2 Community Structure and Modularity

6.3 Modularity-Based Community Detecting Algorithms

6.4 Other Community Partitioning Schemes

6.5 Some Recent Progress

References

Chapter 7: Network Games

7.1 Introduction

7.2 Two-Player/Two-Strategy Evolutionary Games on Networks

7.3 Multi-Player/Two-Strategy Evolutionary Games on Networks

7.4 Adaptive Evolutionary Games on Networks

References

Chapter 8: Network Synchronization

8.1 Introduction

8.2 Complete Synchronization of Continuous-Time Networks

8.3 Complete Synchronization of Some Typical Dynamical Networks

8.4 Phase Synchronization

References

Chapter 9: Network Control

9.1 Introduction

9.2 Spatiotemporal Chaos Control on Regular CML

9.3 Pinning Control of Complex Networks

9.4 Pinning Control of General Complex Networks

9.5 Time-Delay Pinning Control of Complex Networks

9.6 Consensus and Flocking Control

References

Chapter 10: Brief Introduction to Other Topics

10.1 Human Opinion Dynamics

10.2 Human Mobility and Behavioral Dynamics

10.3 Web PageRank, SiteRank and BrowserRank

10.4 Recommendation Systems

10.5 Network Edge Prediction

10.6 Living Organisms and Bionetworks

10.7 Cascading Reactions on Networks

References

Index

End User License Agreement

Pages

xi

xiii

xv

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

139

140

141

142

144

143

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

225

226

227

228

229

230

231

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

253

252

254

232

255

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

363

364

365

366

Guide

Cover

Table of Contents

Preface

Part One: Fundamental Theory

Begin Reading

List of Illustrations

Figure 1.1

Figure 1.2

Figure 1.3

Figure 2.1

Figure 2.2

Figure 2.3

Figure 2.4

Figure 2.5

Figure 2.6

Figure 2.7

Figure 2.8

Figure 2.9

Figure 2.10

Figure 2.11

Figure 2.12

Figure 2.13

Figure 2.14

Figure 2.15

Figure 2.16

Figure 2.17

Figure 2.18

Figure 2.19

Figure 2.20

Figure 2.21

Figure 2.22

Figure 2.23

Figure 2.24

Figure 2.25

Figure 2.26

Figure 2.27

Figure 2.28

Figure 2.29

Figure 2.30

Figure 2.31

Figure 2.32

Figure 2.33

Figure 2.34

Figure 2.35

Figure 2.36

Figure 2.37

Figure 2.38

Figure 2.39

Figure 2.40

Figure 2.41

Figure 2.42

Figure 2.43

Figure 2.44

Figure 2.45

Figure 2.46

Figure 2.47

Figure 2.48

Figure 2.49

Figure 2.50

Figure 2.51

Figure 2.52

Figure 2.53

Figure 2.54

Figure 2.55

Figure 2.56

Figure 2.57

Figure 2.58

Figure 2.59

Figure 2.60

Figure 2.61

Figure 2.62

Figure 2.63

Figure 2.64

Figure 2.65

Figure 2.66

Figure 2.67

Figure 2.68

Figure 2.69

Figure 2.70

Figure 2.71

Figure 2.72

Figure 2.73

Figure 2.74

Figure 3.1

Figure 3.2

Figure 3.3

Figure 3.4

Figure 3.5

Figure 3.6

Figure 3.7

Figure 3.8

Figure 3.9

Figure 3.10

Figure 3.11

Figure 3.12

Figure 3.13

Figure 3.14

Figure 3.15

Figure 3.16

Figure 3.17

Figure 3.18

Figure 3.19

Figure 3.20

Figure 3.21

Figure 4.1

Figure 4.2

Figure 4.3

Figure 4.4

Figure 4.5

Figure 4.6

Figure 4.7

Figure 4.8

Figure 4.9

Figure 4.10

Figure 4.11

Figure 4.12

Figure 4.13

Figure 4.14

Figure 4.15

Figure 4.16

Figure 4.17

Figure 4.18

Figure 4.19

Figure 4.20

Figure 4.21

Figure 4.22

Figure 4.23

Figure 4.24

Figure 4.25

Figure 4.26

Figure 4.27

Figure 4.28

Figure 4.29

Figure 4.30

Figure 4.31

Figure 4.32

Figure 4.33

Figure 4.34

Figure 4.35

Figure 4.36

Figure 4.37

Figure 4.38

Figure 4.39

Figure 4.40

Figure 4.41

Figure 4.42

Figure 4.43

Figure 4.44

Figure 4.45

Figure 4.46

Figure 4.47

Figure 4.48

Figure 4.49

Figure 4.50

Figure 4.51

Figure 5.1

Figure 5.2

Figure 5.3

Figure 5.4

Figure 5.5

Figure 5.6

Figure 5.7

Figure 5.8

Figure 5.9

Figure 5.10

Figure 5.11

Figure 5.12

Figure 5.13

Figure 5.14

Figure 5.15

Figure 5.16

Figure 5.17

Figure 5.18

Figure 6.1

Figure 6.2

Figure 6.3

Figure 6.4

Figure 6.5

Figure 6.6

Figure 6.7

Figure 6.8

Figure 6.9

Figure 6.10

Figure 6.11

Figure 6.12

Figure 6.13

Figure 6.14

Figure 6.15

Figure 6.16

Figure 6.17

Figure 6.18

Figure 6.19

Figure 6.20

Figure 6.21

Figure 6.22

Figure 6.23

Figure 6.24

Figure 6.25

Figure 6.26

Figure 6.27

Figure 6.28

Figure 6.29

Figure 7.1

Figure 7.2

Figure 7.3

Figure 7.4

Figure 7.5

Figure 7.6

Figure 7.7

Figure 7.8

Figure 7.9

Figure 7.10

Figure 7.11

Figure 7.12

Figure 7.13

Figure 7.14

Figure 7.15

Figure 7.16

Figure 7.17

Figure 7.18

Figure 7.19

Figure 7.20

Figure 7.21

Figure 7.22

Figure 7.23

Figure 7.24

Figure 7.25

Figure 7.26

Figure 7.27

Figure 7.28

Figure 7.29

Figure 7.30

Figure 7.31

Figure 8.1

Figure 8.2

Figure 8.3

Figure 8.4

Figure 8.5

Figure 8.6

Figure 8.7

Figure 8.8

Figure 8.9

Figure 8.10

Figure 8.11

Figure 8.12

Figure 8.13

Figure 8.14

Figure 8.15

Figure 8.16

Figure 8.17

Figure 8.18

Figure 8.19

Figure 9.1

Figure 9.2

Figure 9.3

Figure 9.4

Figure 9.5

Figure 9.6

Figure 9.7

Figure 9.8

Figure 9.9

Figure 9.10

Figure 9.11

Figure 9.12

Figure 9.13

Figure 9.14

List of Tables

Table 1.1

Table 1.2

Table 2.1

Table 3.1

Table 4.1

Table 4.2

Table 4.3

Table 4.4

Table 4.5

Table 4.6

Table 4.7

Table 4.8

Table 6.1

Table 6.2

FUNDAMENTALS OF COMPLEX NETWORKS

MODELS, STRUCTURES AND DYNAMICS

Guanrong Chen

City University of Hong Kong, China

Xiaofan Wang

Shanghai Jiao Tong University, Shanghai, China

Xiang Li

Fudan University, Shanghai, China

This edition first published 2015

© 2015 Higher Education Press. All rights reserved.

Published by John Wiley & Sons Singapore Pte. Ltd., 1 Fusionopolis Walk, #07-01 Solaris South Tower, Singapore 138628, under exclusive license granted by Higher Education Press for all media and languages excluding Simplified and Traditional Chinese and throughout the world excluding Mainland China, and with non-exclusive license for electronic versions in Mainland China.

For details of our global editorial offices, for customer services and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com.

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, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as expressly permitted by law, without either the prior written permission of the Publisher, or authorization through payment of the appropriate photocopy fee to the Copyright Clearance Center. Requests for permission should be addressed to the Publisher, John Wiley & Sons Singapore Pte. Ltd., 1 Fusionopolis Walk, #07-01 Solaris South Tower, Singapore 138628, tel: [phone], fax: [phone], email: [email protected].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

Designations used by companies to distinguish their products are often claimed as trademarks. All brand names and product names used in this book are trade names, service marks, trademarks or registered trademarks of their respective owners. The Publisher is not associated with any product or vendor mentioned in this book. This publication is designed to provide accurate and authoritative information in regard to the subject matter covered. It is sold on the understanding that the Publisher is not engaged in rendering professional services. If professional advice or other expert assistance is required, the services of a competent professional should be sought.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. It is sold on the understanding that the publisher is not engaged in rendering professional services and neither the publisher nor the author shall be liable for damages arising herefrom. If professional advice or other expert assistance is required, the services of a competent professional should be sought.

MATLAB® is a trademark of The MathWorks, Inc. and is used with permission. The MathWorks does not warrant the accuracy of the text or exercises in this book. This book's use or discussion of MATLAB® software or related products does not constitute endorsement or sponsorship by The MathWorks of a particular pedagogical approach or particular use of the MATLAB® software.

Library of Congress Cataloging-in-Publication Data

Chen, G. (Guanrong)

Fundamentals of complex networks : models, structures, and dynamics / Guanrong Chen, Xiaofan

Wang, Xiang Li.

pages cm

Includes bibliographical references and index.

ISBN 978-1-118-71811-7 (cloth)

1. System theory. I. Wang, Xiaofan, 1967– II. Li, Xiang, 1976 February 8– III. Title.

Q295.C4524 2015

003′.72— dc23

2014034304

About the Authors

Guanrong Chen is Chair Professor and Founding Director of the Centre for Chaos and Complex Networks at the City University of Hong Kong. He was awarded the 2011 Euler Gold Medal, Russia, and was conferred Honorary Doctorate by the Saint Petersburg State University, Russia in 2011 and by the University of Le Havre, France in 2014. He is a member of the Academia Europaea.

Xiaofan Wang is Distinguished Professor of the Department of Automation at Shanghai Jiao Tong University, China. He received the 2002 National Science Foundation Award for Distinguished Young Scholars and the 2008 Distinguished Professorship from the Chang Jiang Scholars Program by the Ministry of Education, China. He is the 2014–2017 Chair of the IFAC Technical Committee on Large-Scale Complex Systems.

Xiang Li is Full Professor and Head of Department of Electronic Engineering, Fudan University, China. He received the 2005 Guillemin-Cauer Best Paper Award from the IEEE Circuits and Systems Society and the 2014 National Science Foundation Award for Distinguished Young Scholars, China.

Preface

The extensive study of complex networks is pervading sciences and engineering today, from physical, technological, biological, to social sciences. Their impacts on engineering and technology, in particular, are prominent and their influence is deemed to be far-reaching. Familiar complex networks include the Internet, the World Wide Web, wireless communication networks, biological neural networks, power grids, social relation and scientific cooperation networks, and so on. Research on fundamental properties and dynamical behaviors of various complex networks has recently become overwhelming.

The field of complex networks is indeed developing so fast and so wide that most newcomers typically find it quite difficult to know where to start their learning and research on the subject. Although there are some well-written textbooks and research monographs that can be adopted for studies by newcomers, these references are generally too advanced or too broad for those readers to comprehend, especially in a relatively short period of time; they are not easily used as textbooks for a short course on the subject either. Driven by such teaching and learning demands, this book has been designed to serve as a concise textbook for newcomers to the field. It is written as a one-semester introductory text for upper-division undergraduate or first-year graduate students in natural science, mathematics and engineering, or as an edited volume for self-study, or as a handy reference for research.

The book title retains the adjective “complex” to reflect the historical perspective and to emphasize the nature of the subject, which is in line with the common phrases of complex systems and complex dynamics alike, and therefore should not be seen as redundant.

The style of writing in this book is intended to be informal, emphasizing basic ideas and methodologies with elementary and sometimes heuristic mathematical arguments, easily readable by anyone having minimal knowledge of calculus, linear algebra and ordinary differential equations. In this regard, and to be self-contained, a preliminary chapter on graph theory, probability and statistics as well as dynamical systems is included after the first overview chapter. The book is divided into two parts: Part I Fundamental Theory is a detailed text consisting of three chapters, presenting background information and basic materials needed to learn the subject, with a variety of exercises for illustrating fundamental concepts and familiarizing related modeling and analysis techniques. Part II Applications – Selected Topics contains several selected application-oriented topics, which are all independent of each other, in the sense that one can choose any chapter to teach or to learn individually without referring to the contents of the other chapters in this part. Of course, the current arrangement of chapters would also be a logical ordering if one decided to read through this whole portion of the book. The last chapter of this part provides only outlines of several emerging topics which are believed important and promising, with sufficient numbers of key references provided for interested readers' future studies.

This book is a slightly modified and extended version of the same authors' earlier version of the book entitled Introduction to Complex Networks: Models, Structures and Dynamics, published by the Higher Education Press, Beijing in 2012. The basic materials of this book have been used in teaching a postgraduate course on Complex Networks: Modeling, Dynamics and Control at the City University of Hong Kong since 2007, received valuable feedback from students which has made the present version better suited to a text for both teaching and learning.

Owing to the introductory nature of the book, it does not cover the most advanced developments in the field, especially those in the last five years or so. It is the authors' hope that after learning this elementary text, readers are ready to read recent literature so as to pursue state-of-the-art research in the field of network science and engineering. For Chinese readers, there is a complementary volume written in Chinese by the same authors, entitled Network Science: An Introduction (Higher Education Press, Beijing, 2012), which has very little overlapping with the present book and hence should be fairly referential and informative.

Guanrong ChenCity University of Hong KongXiaofan WangShanghai Jiao Tong UniversityXiang LiFudan UniversitySummer 2014

Acknowledgements

The authors would like to express their appreciation to their families for their long-term strong support and their great patience and understanding.

The authors also wish to thank those colleagues who have provided many helpful comments and suggestions to enhance the contents or to improve the descriptions of the book, especially Zhengping Fan (Section 3.6.4), Jun-An Lu and Housheng Su (Section 8.2), and Shi Zhou (Section 3.2.3), as well as the following individuals who have provided basic information and materials for Chapter 10, “Brief Introduction to Other Topics”: Lin Wang (Section 10.2), Yuting Liu and Zhiming Ma (Section 10.3), Tao Zhou (Section 10.4), Linyuan Lu (Section 10.5), and Luonan Chen (Section 10.6). In addition, the authors would like to thank their students Jing Cui, Jingyuan Zhan and Yiqing Zhang, for their assistance.

The authors appreciate the courtesy of the following publishers in granting them permission to use various simulation and illustration figures from their journals, which have mostly been modified and have all been cited and acknowledged: The American Association for the Advancement of Science, American Physical Society, Association for the Advancement of Science, American Association for Computing Machinery Inc., Cambridge University Press, Elsevier, Europhysics Letter, IEEE, IOP Publishing, Macmillan Publishers Ltd (Nature), National Academy of Sciences U.S.A., Springer Science and Business Media, Society for Industrial and Applied Mathematics, University of Chicago Press, Wiley, and World Scientific Publishing.

The authors would also like to thank the following individuals for permission to use some of their artistic drawings or figures: L. Backstrom, J. Byer, B. Karrer, D. Krioukov, C. Marlow, I. Matta, A. Medina, V. Paxson, S. Sinha, S. Staniford, J. Ugander, N. Weaver, and Cliff C. Zou.

The authors are especially grateful to Ms Ying Liu, Editor of the Higher Education Press, Beijing, for her kind assistance and friendly cooperation throughout the process of the preparation and production of the book.

Finally, the authors acknowledge the Ministry of Education and the National Natural Science Foundation of China, and the Hong Kong Research Grants Council, for the long-term continuous research grants support for their research projects closely-related to the topics of this book.

Guanrong ChenCity University of Hong KongXiaofan WangShanghai Jiao Tong UniversityXiang LiFudan UniversitySummer 2014

Part OneFundamental Theory

Chapter 1Introduction

1.1 Background and Motivation

Between two randomly selected persons in the world, roughly how many friends are there connecting them together? When searching from one webpage to another through the World Wide Web (WWW), how many clicks are needed on average? How can computer viruses propagate so fast and so wide through the Internet? How are people infected by epidemics such as AIDS, SARS, and Avian Influenza all over the world? How do rumors spread in human societies? How does a regional financial recession trigger a global economic crisis? How does an electric power blackout emerge from a small local system failure through the huge-scale power grid? How can the human brain work so efficiently while every brain cell is relatively so simple? … All these seemingly different issues have something to do with “networks” – Internet, WWW, social relationship networks, viruses and rumors propagation networks, economic trading and competition networks, power and traffic flow networks, wired and wireless communication networks, biological neural networks, ecosystem networks, and so on. Noticeably, and most important above all, these apparently different networks have a lot in common.

Since the 1990s, the rapid growth of the Internet as an icon of the high-tech era has led our life to an age of networks. The influence of various complex and dynamical networks is currently pervading all kinds of sciences, ranging from physical to biological, even to social sciences. Its impact on modern engineering and technology is prominent and will be far-reaching. There is no doubt that we are living in a networked world today. On the one hand, networks bring us convenience and benefits, improve our efficiency of work and quality of life, and create tremendous advantages and opportunities which we never had before. On the other hand, however, networks also generate harm and damage to nature and human societies, typically with epidemic spreading, computer virus propagation, and power blackouts, to name just a few. Therefore, the increasing demand for networks and networking also requires a correct view and a serious investigation of the complex properties of various networks and the dynamic mechanisms of networking. For a long time in history, studies of communication networks, power networks, biological networks, economic networks, social networks, etc., were carried out separately and independently. However, recently there has been some rethinking of the general concept and theory of complex dynamical networks towards a better understanding of the intrinsic relations, common properties and shared features of all kinds of networks in the real world, which are not isolated but actually networked together – network of systems and, more generally, network of networks. The new intention and desire of studying the fundamental properties and dynamical behaviors of most if not all complex networks, both qualitatively and quantitatively, is important and timely, although very challenging technically. The current research along this line has been considered as a “new science of networks” [1, 2], or network science and engineering, and has become overwhelming today.