Atjaunināt sīkdatņu piekrišanu

Generating Random Networks and Graphs [Hardback]

(In), (Lecturer in Disordered Systems, Institute for Mathematical and Molecular Biomedicine, King's College London, UK), (Professor of Applied Mathematics, Institute for Mathematical and Molecular Biomedicine, King's College London, UK)
  • Formāts: Hardback, 324 pages, height x width x depth: 253x179x24 mm, weight: 790 g
  • Izdošanas datums: 16-Mar-2017
  • Izdevniecība: Oxford University Press
  • ISBN-10: 0198709897
  • ISBN-13: 9780198709893
Citas grāmatas par šo tēmu:
  • Hardback
  • Cena: 95,03 €
  • Grāmatu piegādes laiks ir 3-4 nedēļas, ja grāmata ir uz vietas izdevniecības noliktavā. Ja izdevējam nepieciešams publicēt jaunu tirāžu, grāmatas piegāde var aizkavēties.
  • Daudzums:
  • Ielikt grozā
  • Piegādes laiks - 4-6 nedēļas
  • Pievienot vēlmju sarakstam
Generating Random Networks and GraphsPalielināt
  • Formāts: Hardback, 324 pages, height x width x depth: 253x179x24 mm, weight: 790 g
  • Izdošanas datums: 16-Mar-2017
  • Izdevniecība: Oxford University Press
  • ISBN-10: 0198709897
  • ISBN-13: 9780198709893
Citas grāmatas par šo tēmu:
Permanent link: https://www.kriso.lv/db/9780198709893.html
Keywords:
This book describes how to correctly and efficiently generate random networks based on certain constraints. Being able to test a hypothesis against a properly specified control case is at the heart of the 'scientific method'.

Generating random networks efficiently and accurately is an important challenge for practical applications, and an interesting question for theoretical study. This book presents and discusses common methods of generating random graphs. It begins with approaches such as Exponential Random Graph Models, where the targeted probability of each network appearing in the ensemble is specified. This section also includes degree-preserving randomisation algorithms, where the aim is to generate networks with the correct number of links at each node, and care must be taken to avoid introducing a bias. Separately, it looks at growth style algorithms (e.g. preferential attachment) which aim to model a real process and then to analyse the resulting ensemble of graphs. It also covers how to generate special types of graphs including modular graphs, graphs with community structure and temporal graphs.

The book is aimed at the graduate student or advanced undergraduate. It includes many worked examples and open questions making it suitable for use in teaching. Explicit pseudocode algorithms are included throughout the book to make the ideas straightforward to apply.

With larger and larger datasets, it is crucial to have practical and well-understood tools. Being able to test a hypothesis against a properly specified control case is at the heart of the 'scientific method'. Hence, knowledge on how to generate controlled and unbiased random graph ensembles is vital for anybody wishing to apply network science in their research.

Recenzijas

It succeeds to reach a high degree of learning osmosis for the reader; moreover, relative transmission of research experience, to name a few advantages of the volume at hand. The authors succeed in doing many things well, e.g. inventing a lot of suitable paradigms. * Nikolaos E. Myridis, Contemporary Physics * This is a magnificent guide through a subject that is deeper, more subtle and much more important for data-based applications than one might suspect, and it fully reflects the authors' technical prowess and teaching abilities. Advanced readers will find much food for thought in these pages. * Andrea De Martino, National Research Council of Italy & Human Genetics Foundation *

PART I THE BASICS
1 Introduction
3(6)
2 Definitions and concepts
9(10)
2.1 Definitions of graphs and their local characteristics
9(2)
2.2 Macroscopic characterizations of graphs
11(6)
2.3 Solutions of exercises
17(2)
3 Random graph ensembles
19(14)
3.1 The Erdos--Renyi graph ensemble
20(2)
3.2 Graph ensembles with hard or soft topological constraints
22(3)
3.3 The link between ensembles and algorithms
25(3)
3.4 Solutions of exercises
28(5)
PART II RANDOM GRAPH ENSEMBLES
4 Soft constraints: exponential random graph models
33(31)
4.1 Definitions and basic properties of ERGMs
33(3)
4.2 ERGMs that can be solved exactly
36(4)
4.3 ERGMs with phase transitions: the two-star model
40(7)
4.4 ERGMs with phase transitions: the Strauss (triangle) model
47(10)
4.5 Stochastic block models for graphs with community structure
57(2)
4.6 Strengths and weaknesses of ERGMs as null models
59(3)
4.7 Solutions of exercises
62(2)
5 Ensembles with hard constraints
64(19)
5.1 Basic properties and tools
64(4)
5.2 Nondirected graphs with hard-constrained number of links
68(2)
5.3 Prescribed degree statistics and hard-constrained number of links
70(3)
5.4 Ensembles with prescribed numbers of links and two-stars
73(2)
5.5 Ensembles with constrained degrees and short loops
75(4)
5.6 Solutions of exercises
79(4)
PART III GENERATING GRAPHS FROM GRAPH ENSEMBLES
6 Markov Chain Monte Carlo sampling of graphs
83(22)
6.1 The Markov Chain Monte Carlo sampling method
83(6)
6.2 MCMC sampling for exponential random graph models
89(5)
6.3 MCMC sampling for graph ensembles with hard constraints
94(3)
6.4 Properties of move families -- hinge flips and edge swaps
97(5)
6.5 Solutions of exercises
102(3)
7 Graphs with hard constraints: further applications and extensions
105(48)
7.1 Uniform versus non-uniform sampling of candidate moves
105(7)
7.2 Graphs with a prescribed degree distribution and number of links
112(5)
7.3 Ensembles with controlled degrees and degree correlations
117(4)
7.4 Generating graphs with prescribed degrees and correlations
121(7)
7.5 Edge swaps revisited
128(3)
7.6 Non-uniform sampling of allowed edge swaps
131(4)
7.7 Non-uniform sampling from a restricted set of moves: a hybrid MCMC algorithm
135(4)
7.8 Extensions to directed graphs
139(2)
7.9 Solutions of exercises
141(12)
PART IV GRAPHS DEFINED BY ALGORITHMS
8 Network growth algorithms
153(16)
8.1 Configuration model
153(4)
8.2 Preferential attachment and scale-free networks
157(6)
8.3 Analyzing growth algorithms
163(3)
8.4 Solutions of exercises
166(3)
9 Specific constructions
169(18)
9.1 Watts--Strogatz model and the `small world' property
169(4)
9.2 Geometric graphs
173(4)
9.3 Planar graphs
177(2)
9.4 Weighted graphs
179(2)
9.5 Solutions of exercises
181(6)
PART V FURTHER TOPICS
10 Graphs on structured spaces
187(20)
10.1 Temporal networks
187(6)
10.2 Multiplex graphs
193(4)
10.3 Networks with labelled nodes
197(5)
10.4 Relations and connections between models
202(2)
10.5 Solutions of exercises
204(3)
11 Applications of random graphs
207(14)
11.1 Power grids
207(1)
11.2 Social networks
208(4)
11.3 Food webs
212(3)
11.4 World Wide Web
215(1)
11.5 Protein-protein interaction networks
216(5)
Key symbols and terminology
221(8)
Appendix A The delta distribution
229(2)
Appendix B Clustering and correlations in Erdos-Renyi graphs
231(5)
B.1 Clustering coefficients
231(2)
B.2 Degree correlations in the sparse regime
233(3)
Appendix C Solution of the two-star exponential random graph model (ERGM) in the sparse regime
236(4)
Appendix D Steepest descent integration
240(2)
Appendix E Number of sparse graphs with prescribed average degree and degree variance
242(2)
Appendix F Evolution of graph mobilities for edge-swap dynamics
244(3)
Appendix G Number of graphs with prescribed degree sequence
247(2)
Appendix H Degree correlations in ensembles with constrained degrees
249(4)
Appendix I Evolution of triangle and square counters due to ordered edge swaps
253(3)
Appendix J Algorithms
256(41)
J.1 Algorithms based on link flips
259(9)
J.2 MCMC algorithms sampling from graphs with hard constraints
268(3)
J.3 Algorithms based on hinge flips
271(6)
J.4 Algorithms based on edge swaps
277(5)
J.5 Growth Algorithms
282(7)
J.6 Auxiliary routines
289(8)
References 297(12)
Index 309
Ton Coolen received his PhD in Theoretical Physics from the University of Utrecht, followed by postdoctoral work at Utrecht, Nijmegen and Oxford. Since 1995 he has been working at King's College London. During this time he had developed a special interest in multidisciplinary research. This is expressed firstly through applying his expertise in statistical mechanics to problems including medical survival analysis, cellular signalling networks, econophysics and immunology. He also set up the Institute for Mathematical and Molecular Biomedicine in order to bring together colleagues in biology, medicine, physics, computer science and mathematics to work on developing effective quantitative tools for biomedical researchers.

Alessia Annibale obtained her undergraduate and Master degrees from the University of Rome "La Sapienza" before moving to the Disordered System and Neural Networks group in King's College London to complete her PhD. She has continued to work as a lecturer in King's College London, with papers published on spin glasses, network dynamics and stochastic processes on finitely connected random graphs. She is a member of the Institute for Mathematical and Molecular Biomedicine, and in recent years has taken a particular interest in applying the mathematical tools of disordered systems to understand the properties of biological networks.

Ekaterina Roberts obtained her undergraduate degree from Imperial College, London. After this she worked at the UK's Financial Services Authority, contributing to regulatory policies on how financial institutions should measure and capitalise their credit risk, as well as undertaking direct supervisory oversight of some small banks and insurers. She then joined the Randall Division of Cell and Molecular Biophysics to complete a cross-disciplinary PhD which used statistical mechanics to create tools to analyse random graph ensembles which share topological properties with real molecular networks.