Mathematical Foundations of Complex Networked Information Systems : Politecnico di Torino, Verrès, Italy 2009 / by P.R. Kumar, Martin J. Wainwright, Riccardo Zecchina ; edited by Fabio Fagnani, Sophie M. Fosson, Chiara Ravazzi.

Format:

Book

Author/Creator:

Kumar, P.R., Author.

Wainwright, Martin J., Author.

Zecchina, Riccardo, Author.

Contributor:

Fagnani, Fabio, Editor.

Fosson, Sophie M., Editor.

Ravazzi, Chiara, Editor.

Series:

C.I.M.E. Foundation Subseries ; 2141

Language:

English

Subjects (All):

System theory.

Graph theory.

Mathematical physics.

Physics.

Complex Systems.

Graph Theory.

Mathematical Applications in the Physical Sciences.

Applications of Graph Theory and Complex Networks.

Local Subjects:

Complex Systems.

Graph Theory.

Mathematical Applications in the Physical Sciences.

Applications of Graph Theory and Complex Networks.

Physical Description:

1 online resource (VII, 135 p. 34 illus., 24 illus. in color.)

Edition:

1st ed. 2015.

Place of Publication:

Cham : Springer International Publishing : Imprint: Springer, 2015.

Language Note:

English

Summary:

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.

Contents:

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 Erdős-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 β→∞ 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

Graphical Models and Message-Passing Algorithms: Some Introductory Lectures

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

Bridging the Gap Between Information Theory and WirelessNetworking

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

Lecture Notes in Math ematics.

Notes:

Bibliographic Level Mode of Issuance: Monograph

Includes bibliographical references.

Description based on publisher supplied metadata and other sources.

ISBN:

3-319-16967-X

OCLC:

910302521