Structural Analysis of Complex Networks

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. This self-contained book presents theoretical results and current applications of structural network analysis to synthetic and real-world networks. The individual chapters are a careful balance of classical and novel approaches, ranging in scope from determining the structural information of networks, partitions, and distances in graphs to applying structural graph analysis to biological networks. A major goal of the book is to highlight the need for theoretical and applied results to enhance knowledge and understanding of networks, in general, and to solve challenging practical problems. Another major theme of the work is to show that very large and complex data sets - for example, in biology or chemistry - require novel approaches to take into account the size and complexity of such networks under investigation. Each chapter is written comprehensively, focusing not only on the presentation of a method or an algorithm, but also providing additional background information on graph theory, computer science, machine learning, statistics, or biology. Emphasis is not only on mathematical methods; the applications presented demonstrate the potential for each method examined. This book is unique in the literature: no existing book surveys such a broad range of mathematical methods for structurally analyzing networks. It gathers information and topics that are scattered throughout journal articles. It may be used as a supplementary textbook in graduate-level seminars on structural graph analysis or network-based machine learning methods. "Structural Analysis of Complex Networks" is suitable for an interdisciplinary readership of researchers, practitioners, and graduate students working in pure and applied discrete mathematics, statistical data analysis, computer science, machine learning, artificial intelligence, bioinformatics, computational biology, web or text mining and related disciplines 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: applications in biology, chemistry, linguistics, and data analysis; graph colorings; graph polynomials; information measures for graphs; metrical properties of graphs; partitions and decompositions; and 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. Front Matter....Pages i-xiii A Brief Introduction to Complex Networks and Their Analysis....Pages 1-26 Partitions of Graphs....Pages 27-47 Distance in Graphs....Pages 49-72 Domination in Graphs....Pages 73-104 Spectrum and Entropy for Infinite Directed Graphs....Pages 105-136 Application of Infinite Labeled Graphs to Symbolic Dynamical Systems....Pages 137-168 Decompositions and Factorizations of Complete Graphs....Pages 169-196 Geodetic Sets in Graphs....Pages 197-218 Graph Polynomials and Their Applications I: The Tutte Polynomial....Pages 219-255 Graph Polynomials and Their Applications II: Interrelations and Interpretations....Pages 257-292 Reconstruction Problems for Graphs, Krawtchouk Polynomials, and Diophantine Equations....Pages 293-317 Subgraphs as a Measure of Similarity....Pages 319-334 A Chromatic Metric on Graphs....Pages 335-356 Some Applications of Eigenvalues of Graphs....Pages 357-379 Minimum Spanning Markovian Trees: Introducing Context-Sensitivity into the Generation of Spanning Trees....Pages 381-401 Link-Based Network Mining....Pages 403-419 Graph Representations and Algorithms in Computational Biology of RNA Secondary Structure....Pages 421-437 Inference of Protein Function from the Structure of Interaction Networks....Pages 439-461 Applications of Perfect Matchings in Chemistry....Pages 463-482 Back Matter....Pages 483-486 Filling a gap in literature, this self-contained book presents theoretical and application-oriented results that allow for a structural exploration of 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. Applications to biology, chemistry, linguistics, and data analysis are emphasized. The book 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. It may also be used as a supplementary textbook in graduate-level seminars on structural graph analysis, complex networks, or network-based machine learning methods.