Complex graphs and networks. (English) Zbl 1114.90071
CBMS Regional Conference Series in Mathematics 107. Providence, RI: American Mathematical Society (AMS) (ISBN 0-8218-3657-9/pbk). vii, 264 p. (2006).
This book, divided into 12 chapters, investigates complex graphs and networks as they arise in real-life situations. The book starts with an overview of graphs and networks together with a series of useful definitions around sparse and large-scale graphs. Several examples where complex graphs arise in practice are given, which are taken from real-life data sources such as web-site messaging use or Hollywood film interactions.
The next chapters investigate the various models that can be used to study these graphs. Two main approaches are described: off-line and on-line graphs, with the key difference bing the dynamic addition and deletion of graph vertices in the latter. Chapter 4 studies in detail duplication models that can be used for biological models, whereas chapter 5 gives a theoretical background to random graphs.
In chapter 6, the authors consider the rise of a giant component in graphs. They present the situations and the conditions in which a giant component can arise, and give both theoretical and practical reasons to verify their observations and results. The next three chapters deal with distance issues in networks, such as diameters and average distances where upper and lower bounds are calculated.
The book concludes with a series of chapters to study the differences between off-line and on-line graphs, as well as models for hybrid graphs that are common in so-called “small world phenomena”. The book also contains a useful set of references of related literature and an index.
The next chapters investigate the various models that can be used to study these graphs. Two main approaches are described: off-line and on-line graphs, with the key difference bing the dynamic addition and deletion of graph vertices in the latter. Chapter 4 studies in detail duplication models that can be used for biological models, whereas chapter 5 gives a theoretical background to random graphs.
In chapter 6, the authors consider the rise of a giant component in graphs. They present the situations and the conditions in which a giant component can arise, and give both theoretical and practical reasons to verify their observations and results. The next three chapters deal with distance issues in networks, such as diameters and average distances where upper and lower bounds are calculated.
The book concludes with a series of chapters to study the differences between off-line and on-line graphs, as well as models for hybrid graphs that are common in so-called “small world phenomena”. The book also contains a useful set of references of related literature and an index.
Reviewer: Efstratios Rappos (Athens)
MSC:
90C06 | Large-scale problems in mathematical programming |
05C12 | Distance in graphs |
90-02 | Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming |
05-02 | Research exposition (monographs, survey articles) pertaining to combinatorics |
05C80 | Random graphs (graph-theoretic aspects) |
05C85 | Graph algorithms (graph-theoretic aspects) |
05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
68R10 | Graph theory (including graph drawing) in computer science |
68U35 | Computing methodologies for information systems (hypertext navigation, interfaces, decision support, etc.) |
68W20 | Randomized algorithms |
90B10 | Deterministic network models in operations research |
90C35 | Programming involving graphs or networks |
94C15 | Applications of graph theory to circuits and networks |