Modern Graph Theory Algorithms with Python

Modern Graph Theory Algorithms with Python

by Colleen M. Farrelly, Franck Kalala Mutombo
Released June 2024
Publisher(s): Packt Publishing
ISBN: 9781805127895

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Solve challenging and computationally intensive analytics problems by leveraging network science and graph algorithms

Key Features

  • Learn how to wrangle different types of datasets and analytics problems into networks
  • Leverage graph theoretic algorithms to analyze data efficiently
  • Apply the skills you gain to solve a variety of problems through case studies in Python
  • Purchase of the print or Kindle book includes a free PDF eBook

Book Description

We are living in the age of big data, and scalable solutions are a necessity. Network science leverages the power of graph theory and flexible data structures to analyze big data at scale.

This book guides you through the basics of network science, showing you how to wrangle different types of data (such as spatial and time series data) into network structures. You’ll be introduced to core tools from network science to analyze real-world case studies in Python. As you progress, you’ll find out how to predict fake news spread, track pricing patterns in local markets, forecast stock market crashes, and stop an epidemic spread. Later, you’ll learn about advanced techniques in network science, such as creating and querying graph databases, classifying datasets with graph neural networks (GNNs), and mining educational pathways for insights into student success. Case studies in the book will provide you with end-to-end examples of implementing what you learn in each chapter.

By the end of this book, you’ll be well-equipped to wrangle your own datasets into network science problems and scale solutions with Python.

What you will learn

  • Transform different data types, such as spatial data, into network formats
  • Explore common network science tools in Python
  • Discover how geometry impacts spreading processes on networks
  • Implement machine learning algorithms on network data features
  • Build and query graph databases
  • Explore new frontiers in network science such as quantum algorithms

Who this book is for

If you’re a researcher or industry professional analyzing data and are curious about network science approaches to data, this book is for you. To get the most out of the book, basic knowledge of Python, including pandas and NumPy, as well as some experience working with datasets is required. This book is also ideal for anyone interested in network science and learning how graph algorithms are used to solve science and engineering problems. R programmers may also find this book helpful as many algorithms also have R implementations.

Table of contents

  1. Modern Graph Theory Algorithms with Python
  2. Foreword
  3. Contributors
  4. About the authors
  5. About the reviewer
  6. Preface
    1. Who this book is for
    2. What this book covers
    3. To get the most out of this book
    4. Download the example code files
    5. Conventions used
    6. Get in touch
    7. Share Your Thoughts
    8. Download a free PDF copy of this book
  7. Part 1:Introduction to Graphs and Networks with Examples
  8. Chapter 1: What is a Network?
    1. Technical requirements
    2. Introduction to graph theory and networks
      1. Formal definitions
      2. Creating networks in Python
      3. Random graphs
    3. Examples of real-world social networks
    4. Other type of networks
    5. Advanced use cases of network science
    6. Summary
    7. References
  9. Chapter 2: Wrangling Data into Networks with NetworkX and igraph
    1. Technical requirements
    2. Introduction to different data sources
      1. Social interaction data
      2. Spatial data
      3. Temporal data
      4. Biological networks
      5. Other types of data
    3. Wrangling data into networks with igraph
    4. Social network examples with NetworkX
    5. Summary
    6. References
  10. Part 2: Spatial Data Applications
  11. Chapter 3: Demographic Data
    1. Technical requirements
    2. Introduction to demography
      1. Demographic factors
      2. Geographic factors
      3. Homophily in networks
    3. Francophone Africa music spread
    4. AIMS Cameroon student network epidemic model
    5. Summary
    6. References
  12. Chapter 4: Transportation Data
    1. Technical requirements
    2. Introduction to transportation problems
      1. Paths between stores
      2. Fuel costs
      3. Time to deliver goods
      4. Navigational hazards
    3. Shortest path applications
    4. Traveling salesman problem
    5. Max-flow min-cut algorithm
    6. Summary
    7. References
  13. Chapter 5: Ecological Data
    1. Technical requirements
    2. Introduction to ecological data
      1. Exploring methods to track animal populations across geographies
      2. Exploring methods to capture plant distributions and diseases
    3. Spectral graph tools
    4. Clustering ecological populations using spectral graph tools
      1. Spectral clustering on text notes
    5. Summary
    6. References
  14. Part 3: Temporal Data Applications
  15. Chapter 6: Stock Market Data
    1. Technical requirements
    2. Introduction to temporal data
      1. Stock market applications
    3. Introduction to centrality metrics
    4. Application of centrality metrics across time slices
    5. Extending network metrics for time series analytics
    6. Summary
    7. References
  16. Chapter 7: Goods Prices/Sales Data
    1. Technical requirements
    2. An introduction to spatiotemporal data
      1. The Burkina Faso market dataset
      2. Store sales data
    3. Analyzing our spatiotemporal datasets
    4. Summary
    5. References
  17. Chapter 8: Dynamic Social Networks
    1. Technical requirements
    2. Social networks that change over time
      1. Friendship networks
      2. Triadic closure
    3. A deeper dive into spreading on networks
      1. Dynamic network introduction
      2. SIR models, Part Two
      3. Factors influencing spread
    4. Example with evolving wildlife interaction datasets
      1. Crocodile network
      2. Heron network
    5. Summary
    6. References
  18. Part 4: Advanced Applications
  19. Chapter 9: Machine Learning for Networks
    1. Technical requirements
    2. Introduction to friendship networks and friendship relational datasets
      1. Friendship network introduction
      2. Friendship demographic and school factor dataset
    3. ML on networks
      1. Clustering based on student factors
      2. Clustering based on student factors and network metrics
      3. Spectral clustering on the friendship network
    4. DL on networks
      1. GNN introduction
      2. Example GNN classifying the Karate Network dataset
    5. Summary
    6. References
  20. Chapter 10: Pathway Mining
    1. Technical requirements
    2. Introduction to Bayesian networks and causal pathways
      1. Bayes’ Theorem
      2. Causal pathways
      3. Bayesian networks
    3. Educational pathway example
      1. Outcomes in education
      2. Course sequences
      3. Antecedents to success
    4. Analyzing course sequencing to find optimal student pathways to graduation
      1. Introduction to a dataset
      2. bnlearn analysis
      3. Structural equation models
    5. Summary
    6. References
  21. Chapter 11: Mapping Language Families – an Ontological Approach
    1. Technical requirements
    2. What is an ontology?
      1. Introduction to ontologies
      2. Representing information as an ontology
    3. Language families
      1. Language drift and relationships
      2. Nilo-Saharan languages
    4. Mapping language families
    5. Summary
    6. References
  22. Chapter 12: Graph Databases
    1. Introduction to graph databases
      1. What is a graph database?
      2. What can you represent in a graph database?
    2. Querying and modifying data in Neo4j
      1. Basic query example
      2. More complicated query examples
    3. Summary
    4. References
  23. Chapter 13: Putting It All Together
    1. Technical requirements
    2. Introduction to the problem
      1. Ebola spread in the Democratic Republic of Congo – 2018-2020 outbreak
      2. Geography and logistics
    3. Introduction to GEEs
      1. Mathematics of GEEs
      2. Our problem and GEE formulation
    4. Data transformation
      1. Python wrangling
      2. GEE input
    5. Data modeling
      1. Running the GEE in Python
    6. Summary
    7. References
  24. Chapter 14: New Frontiers
    1. Quantum network science algorithms
      1. Graph coloring algorithms
      2. Max flow/min cut
    2. Neural network architectures as graphs
      1. Deep learning layers and connections
      2. Analyzing architectures
    3. Hierarchical networks
      1. Higher-order structures and network data
      2. An example using gene families
    4. Hypergraphs
      1. Displaying information
      2. Metadata
    5. Summary
    6. References
  25. Index
    1. Why subscribe?
  26. Other Books You May Enjoy
    1. Packt is searching for authors like you
    2. Share Your Thoughts
    3. Download a free PDF copy of this book

Product information

  • Title: Modern Graph Theory Algorithms with Python
  • Author(s): Colleen M. Farrelly, Franck Kalala Mutombo
  • Release date: June 2024
  • Publisher(s): Packt Publishing
  • ISBN: 9781805127895