Mathematical Foundations of Complex Networked Information Systems
Politecnico di Torino, Verrès, Italy 2009
Published on 19. May 2015
VII, 135 pages
978-3-319-16967-5 (ISBN)
Description
Introducing the reader to the mathematics beyond complex networked systems, these lecture notes investigate graph theory, graphical models, and methods from statistical physics. Complex networked systems play a fundamental role in our society, both in everyday life and in scientific research, with applications ranging from physics and biology to economics and finance.
The book is self-contained, and requires only an undergraduate mathematical background.
More details
Series
Language
English
Place of publication
Cham
Switzerland
Publishing group
Springer International Publishing
Target group
Professional and scholarly
Product notice
Reflowable
Illustrations
VII, 135 p. 34 illus., 24 illus. in color.
File size
3,16 MB
ISBN-13
978-3-319-16967-5 (9783319169675)
DOI
10.1007/978-3-319-16967-5
Schweitzer Classification
Other editions
Additional editions
P.R. Kumar | Martin J. Wainwright | Riccardo Zecchina
Mathematical Foundations of Complex Networked Information Systems
Politecnico di Torino, Verrès, Italy 2009
Book
06/2015
Springer
€37.44
Shipment within 10-15 days
Content
- Intro
- Preface
- Contents
- Some Introductory Notes on Random Graphs
- 1 Introduction
- 2 Generalities on Graphs
- 2.1 Basic Definitions and Notation
- 2.2 Large Scale Networks
- 3 Erdos-Rényi Model
- 3.1 Connectivity and Giant Component
- 3.2 Branching Processes
- 3.3 Behavior at the Giant Component Threshold
- 4 Configuration Model
- 4.1 Connectivity and Giant Component
- 5 Random Geometric Graph
- 5.1 Connectivity
- 5.2 Giant Component
- References
- Statistical Physics and Network Optimization Problems
- 1 Statistical Physics and Optimization
- 2 Elements of Statistical Physics
- 3 Statistical Physics Approach to Percolation in Random Graphs
- 3.1 The Potts Model Representation
- 3.1.1 Symmetric Saddle-Point
- 3.1.2 Symmetry Broken Saddle-Point
- 4 Statistical Physics Methods for More Complex Problems
- 5 Bethe Approximation and Message Passing Algorithms
- 5.1 Belief Propagation
- 5.1.1 Marginals
- 5.1.2 Free Energy
- 5.1.3 Graphs with Loops
- 5.2 The ß8 Limit: Minsum Algorithm
- 5.3 Finding a Solution: Decimation and Reinforcement Algorithms
- 5.3.1 Decimation
- 5.3.2 Reinforcement
- 5.4 Replica Symmetry Breaking and Higher Levels of BP
- References
- Graphical Models and Message-Passing Algorithms: Some Introductory Lectures
- 1 Introduction
- 2 Probability Distributions and Graphical Structure
- 2.1 Directed Graphical Models
- 2.1.1 Conditional Independence Properties for Directed Graphs
- 2.1.2 Equivalence of Representations
- 2.2 Undirected Graphical Models
- 2.2.1 Factorization for Undirected Models
- 2.2.2 Markov Property for Undirected Models
- 2.2.3 Hammersley-Clifford Equivalence
- 2.2.4 Factor Graphs
- 3 Exact Algorithms for Marginals, Likelihoods and Modes
- 3.1 Elimination Algorithm
- 3.1.1 Graph-Theoretic Versus Analytical Elimination
- 3.1.2 Complexity of Elimination
- 3.2 Message-Passing Algorithms on Trees
- 3.2.1 Sum-Product Algorithm
- 3.2.2 Sum-Product on General Factor Trees
- 3.2.3 Max-Product Algorithm
- 4 Junction Tree Framework
- 4.1 Clique Trees and Running Intersection
- 4.2 Triangulation and Junction Trees
- 4.3 Constructing the Junction Tree
- 5 Basics of Graph Estimation
- 5.1 Parameter Estimation for Directed Graphs
- 5.2 Parameter Estimation for Undirected Graphs
- 5.2.1 Maximum Likelihood for Undirected Trees
- 5.2.2 Maximum Likelihood on General Undirected Graphs
- 5.2.3 Iterative Proportional Scaling
- 5.3 Tree Selection and the Chow-Liu Algorithm
- 6 Bibliographic Details and Remarks
- Appendix: Triangulation and Equivalent Graph-Theoretic Properties
- References
- Bridging the Gap Between Information Theory and WirelessNetworking
- 1 Introduction
- 2 Shannon's Point to Point Results
- 3 The Multiple-Access and Gaussian Broadcast Channels
- 4 A Spatial Model of a Wireless Network
- 5 Multi-Hop Transport
- 6 The Transport Capacity
- 7 Best Case Transport Capacity and Scaling Laws
- 8 An Upper Bound on Transport Capacity
- 9 Implication of Square-Root Law for Transport Capacity
- 10 The Need for an Information-Theoretic Analysis
- 11 Wireless Network Information Theory
- 12 Information-Theoretic Definition of Transport Capacity
- 13 Information-Theoretic Bounds
- 14 Implication of Information-Theoretic Scaling Law
- 15 Extensions
- References
- Lecture Notes in Math ematics
