Graph Algorithms for Data Science

Graph Algorithms for Data Science

by Tomaz Bratanic
Released February 2024
Publisher(s): Manning Publications
ISBN: 9781617299469

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

Practical methods for analyzing your data with graphs, revealing hidden connections and new insights.

Graphs are the natural way to represent and understand connected data. This book explores the most important algorithms and techniques for graphs in data science, with concrete advice on implementation and deployment. You don’t need any graph experience to start benefiting from this insightful guide. These powerful graph algorithms are explained in clear, jargon-free text and illustrations that makes them easy to apply to your own projects.

In Graph Algorithms for Data Science you will learn:

  • Labeled-property graph modeling
  • Constructing a graph from structured data such as CSV or SQL
  • NLP techniques to construct a graph from unstructured data
  • Cypher query language syntax to manipulate data and extract insights
  • Social network analysis algorithms like PageRank and community detection
  • How to translate graph structure to a ML model input with node embedding models
  • Using graph features in node classification and link prediction workflows

Graph Algorithms for Data Science is a hands-on guide to working with graph-based data in applications like machine learning, fraud detection, and business data analysis. It’s filled with fascinating and fun projects, demonstrating the ins-and-outs of graphs. You’ll gain practical skills by analyzing Twitter, building graphs with NLP techniques, and much more.

About the Technology
A graph, put simply, is a network of connected data. Graphs are an efficient way to identify and explore the significant relationships naturally occurring within a dataset. This book presents the most important algorithms for graph data science with examples from machine learning, business applications, natural language processing, and more.

About the Book
Graph Algorithms for Data Science shows you how to construct and analyze graphs from structured and unstructured data. In it, you’ll learn to apply graph algorithms like PageRank, community detection/clustering, and knowledge graph models by putting each new algorithm to work in a hands-on data project. This cutting-edge book also demonstrates how you can create graphs that optimize input for AI models using node embedding.

What's Inside
  • Creating knowledge graphs
  • Node classification and link prediction workflows
  • NLP techniques for graph construction


About the Reader
For data scientists who know machine learning basics. Examples use the Cypher query language, which is explained in the book.

About the Author
Tomaž Bratanič works at the intersection of graphs and machine learning.

Arturo Geigel was the technical editor for this book.

Quotes
Undoubtedly the quickest route to grasping the practical applications of graph algorithms. Enjoyable and informative, with real-world business context and practical problem-solving.
- Roger Yu, Feedzai

Brilliantly eases you into graph-based applications.
- Sumit Pal, Independent Consultant

I highly recommend this book to anyone involved in analyzing large network databases.
- Ivan Herreros, talentsconnect

Insightful and comprehensive. The author’s expertise is evident. Be prepared for a rewarding journey.
- Michal Štefaňák, Volke

Table of contents

  1. inside front cover
  2. Graph Algorithms for Data Science
  3. Copyright
  4. contents
  5. front matter
    1. foreword
    2. preface
    3. acknowledgments
    4. about this book
      1. Who should read this book
      2. How this book is organized
      3. About the code
      4. liveBook discussion forum
    5. about the author
    6. about the cover illustration
  6. Part 1 Introduction to graphs
  7. 1 Graphs and network science: An introduction
    1. 1.1 Understanding data through relationships
    2. 1.2 How to spot a graph-shaped problem
      1. 1.2.1 Self-referencing relationships
      2. 1.2.2 Pathfinding networks
      3. 1.2.3 Bipartite graphs
      4. 1.2.4 Complex networks
    3. Summary
  8. 2 Representing network structure: Designing your first graph model
    1. 2.1 Graph terminology
      1. 2.1.1 Directed vs. undirected graph
      2. 2.1.2 Weighted vs. unweighted graphs
      3. 2.1.3 Bipartite vs. monopartite graphs
      4. 2.1.4 Multigraph vs. simple graph
      5. 2.1.5 A complete graph
    2. 2.2 Network representations
      1. 2.2.1 Labeled-property graph model
    3. 2.3 Designing your first labeled-property graph model
      1. 2.3.1 Follower network
      2. 2.3.2 User-tweet network
      3. 2.3.3 Retweet network
      4. 2.3.4 Representing graph schema
    4. 2.4 Extracting knowledge from text
      1. 2.4.1 Links
      2. 2.4.2 Hashtags
      3. 2.4.3 Mentions
      4. 2.4.4 Final Twitter social network schema
    5. Summary
  9. Part 2 Network analysis
  10. 3 Your first steps with Cypher query language
    1. 3.1 Cypher query language clauses
      1. 3.1.1 CREATE clause
      2. 3.1.2 MATCH clause
      3. 3.1.3 WITH clause
      4. 3.1.4 SET clause
      5. 3.1.5 REMOVE clause
      6. 3.1.6 DELETE clause
      7. 3.1.7 MERGE clause
    2. 3.2 Importing CSV files with Cypher
      1. 3.2.1 Clean up the database
      2. 3.2.2 Twitter graph model
      3. 3.2.3 Unique constraints
      4. 3.2.4 LOAD CSV clause
      5. 3.2.5 Importing the Twitter social network
    3. 3.3 Solutions to exercises
    4. Summary
  11. 4 Exploratory graph analysis
    1. 4.1 Exploring the Twitter network
    2. 4.2 Aggregating data with Cypher query language
      1. 4.2.1 Time aggregations
    3. 4.3 Filtering graph patterns
    4. 4.4 Counting subqueries
    5. 4.5 Multiple aggregations in sequence
    6. 4.6 Solutions to exercises
    7. Summary
  12. 5 Introduction to social network analysis
    1. 5.1 Follower network
      1. 5.1.1 Node degree distribution
    2. 5.2 Introduction to the Neo4j Graph Data Science library
      1. 5.2.1 Graph catalog and native projection
    3. 5.3 Network characterization
      1. 5.3.1 Weakly connected component algorithm
      2. 5.3.2 Strongly connected components algorithm
      3. 5.3.3 Local clustering coefficient
    4. 5.4 Identifying central nodes
      1. 5.4.1 PageRank algorithm
      2. 5.4.2 Personalized PageRank algorithm
      3. 5.4.3 Dropping the named graph
    5. 5.5 Solutions to exercises
    6. Summary
  13. 6 Projecting monopartite networks
    1. 6.1 Translating an indirect multihop path into a direct relationship
      1. 6.1.1 Cypher projection
    2. 6.2 Retweet network characterization
      1. 6.2.1 Degree centrality
      2. 6.2.2 Weakly connected components
    3. 6.3 Identifying the most influential content creators
      1. 6.3.1 Excluding self-loops
      2. 6.3.2 Weighted PageRank variant
      3. 6.3.3 Dropping the projected in-memory graph
    4. 6.4 Solutions to exercises
    5. Summary
  14. 7 Inferring co-occurrence networks based on bipartite networks
    1. 7.1 Extracting hashtags from tweets
    2. 7.2 Constructing the co-occurrence network
      1. 7.2.1 Jaccard similarity coefficient
      2. 7.2.2 Node similarity algorithm
    3. 7.3 Characterization of the co-occurrence network
      1. 7.3.1 Node degree centrality
      2. 7.3.2 Weakly connected components
    4. 7.4 Community detection with the label propagation algorithm
    5. 7.5 Identifying community representatives with PageRank
      1. 7.5.1 Dropping the projected in-memory graphs
    6. 7.6 Solutions to exercises
    7. Summary
  15. 8 Constructing a nearest neighbor similarity network
    1. 8.1 Feature extraction
      1. 8.1.1 Motifs and graphlets
      2. 8.1.2 Betweenness centrality
      3. 8.1.3 Closeness centrality
    2. 8.2 Constructing the nearest neighbor graph
      1. 8.2.1 Evaluating features
      2. 8.2.2 Inferring the similarity network
    3. 8.3 User segmentation with the community detection algorithm
    4. 8.4 Solutions to exercises
    5. Summary
  16. Part 3 Graph machine learning
  17. 9 Node embeddings and classification
    1. 9.1 Node embedding models
      1. 9.1.1 Homophily vs. structural roles approach
      2. 9.1.2 Inductive vs. transductive embedding models
    2. 9.2 Node classification task
      1. 9.2.1 Defining a connection to a Neo4j database
      2. 9.2.2 Importing a Twitch dataset
    3. 9.3 The node2vec algorithm
      1. 9.3.1 The word2vec algorithm
      2. 9.3.2 Random walks
      3. 9.3.3 Calculate node2vec embeddings
      4. 9.3.4 Evaluating node embeddings
      5. 9.3.5 Training a classification model
      6. 9.3.6 Evaluating predictions
    4. 9.4 Solutions to exercises
    5. Summary
  18. 10 Link prediction
    1. 10.1 Link prediction workflow
    2. 10.2 Dataset split
    3. 10.2.1 Time-based split
    4. 10.2.2 Random split
    5. 10.2.3 Negative samples
    6. 10.3 Network feature engineering
    7. 10.3.1 Network distance
    8. 10.3.2 Preferential attachment
    9. 10.3.3 Common neighbors
    10. 10.3.4 Adamic-Adar index
    11. 10.3.5 Clustering coefficient of common neighbors
    12. 10.4 Link prediction classification model
    13. 10.4.1 Missing values
    14. 10.4.2 Training the model
    15. 10.4.3 Evaluating the model
    16. 10.5 Solutions to exercises
    17. Summary
  19. 11 Knowledge graph completion
    1. 11.1 Knowledge graph embedding model
      1. 11.1.1 Triple
      2. 11.1.2 TransE
      3. 11.1.3 TransE limitations
    2. 11.2 Knowledge graph completion
      1. 11.2.1 Hetionet
      2. 11.2.2 Dataset split
      3. 11.2.3 Train a PairRE model
      4. 11.2.4 Drug application predictions
      5. 11.2.5 Explaining predictions
    3. 11.3 Solutions to exercises
    4. Summary
  20. 12 Constructing a graph using natural language processing techniques
    1. 12.1 Coreference resolution
    2. 12.2 Named entity recognition
      1. 12.2.1 Entity linking
    3. 12.3 Relation extraction
    4. 12.4 Implementation of information extraction pipeline
      1. 12.4.1 SpaCy
      2. 12.4.2 Corefence resolution
      3. 12.4.3 End-to-end relation extraction
      4. 12.4.4 Entity linking
      5. 12.4.5 External data enrichment
    5. 12.5 Solutions to exercises
    6. Summary
  21. Appendix. The Neo4j environment
    1. A.1 Cypher query language
    2. A.2 Neo4j installation
      1. A.2.1 Neo4j Desktop installation
      2. A.2.2 Neo4j Docker installation
      3. A.2.3 Neo4j Aura
    3. A.3 Neo4j Browser configuration
  22. references
  23. index

Product information

  • Title: Graph Algorithms for Data Science
  • Author(s): Tomaz Bratanic
  • Release date: February 2024
  • Publisher(s): Manning Publications
  • ISBN: 9781617299469