Structural Analysis of Complex Networks

Front Cover
Matthias Dehmer
Springer Science & Business Media, Oct 14, 2010 - Mathematics - 486 pages

Because of the increasing complexity and growth of real-world networks, their analysis by using classical graph-theoretic methods is oftentimes a difficult procedure. As a result, there is a strong need to combine graph-theoretic methods with mathematical techniques from other scientific disciplines, such as machine learning and information theory, in order to analyze complex networks more adequately.

Filling a gap in literature, this self-contained book presents theoretical and application-oriented results to structurally explore complex networks. The work focuses not only on classical graph-theoretic methods, but also demonstrates the usefulness of structural graph theory as a tool for solving interdisciplinary problems.

Special emphasis is given to methods related to the following areas:

* Applications to biology, chemistry, linguistics, and data analysis

* Graph colorings

* Graph polynomials

* Information measures for graphs

* Metrical properties of graphs

* Partitions and decompositions

* Quantitative graph measures

Structural Analysis of Complex Networks is suitable for a broad, interdisciplinary readership of researchers, practitioners, and graduate students in discrete mathematics, statistics, computer science, machine learning, artificial intelligence, computational and systems biology, cognitive science, computational linguistics, and mathematical chemistry. The book may be used as a supplementary textbook in graduate-level seminars on structural graph analysis, complex networks, or network-based machine learning methods.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Chapter 1 A Brief Introduction to Complex Networksand Their Analysis
1
Chapter 2 Partitions of Graphs
27
Chapter 3 Distance in Graphs
49
Chapter 4 Domination in Graphs
73
Chapter 5 Spectrum and Entropy for Infinite Directed Graphs
105
Chapter 6 Application of Infinite Labeled Graphs to Symbolic Dynamical Systems
137
Chapter 7 Decompositions and Factorizations of Complete Graphs
169
Chapter 8 Geodetic Sets in Graphs
197
Chapter 12 Subgraphs as a Measure of Similarity
319
Chapter 13 A Chromatic Metric on Graphs
335
Chapter 14 Some Applications of Eigenvalues of Graphs
357
Chapter 15 Minimum Spanning Markovian Trees Introducing ContextSensitivity into the Generation of Spanning Trees
381
Chapter 16 LinkBased Network Mining
403
Chapter 17 Graph Representations and Algorithms in Computational Biology of RNA Secondary Structure
421
Chapter 18 Inference of Protein Function from the Structureof Interaction Networks
439
Chapter 19 Applications of Perfect Matchings in Chemistry
463

Chapter 9 Graph Polynomials and Their Applications IThe Tutte Polynomial
219
Chapter 10 Graph Polynomials and Their Applications II Interrelations and Interpretations
257
Chapter 11 Reconstruction Problems for Graphs Krawtchouk Polynomials and Diophantine Equations
293

Other editions - View all

Common terms and phrases

About the author (2010)

Frank Emmert-Streib studied physics at the University of Siegen, Germany, and received his PhD in Theoretical Physics from the University of Bremen, Germany. He is currently Senior Fellow at the University of Washington in Seattle, USA, in Biostatistics and Genome Sciences.
Matthias Dehmer studied mathematics at the University of Siegen, Germany, and received his PhD in Computer Science from the Technical University of Darmstadt, Germany. Currently, he holds a research position at Vienna University of Technology, Institute of Discrete Mathematics and Geometry in Vienna, Austria.

Bibliographic information