![PageRank & Personalized PageRank Measures the transitive (directional) influence of nodes and considers the influence of neighbors and their neighbors Personalized PageRank CALL algo.pageRank('Page', 'LINKS', {iterations:20, dampingFactor:0.85, sourceNodes: [siteA]})](https://image.slidesharecdn.com/dev3-graphalgorithmsforappsandexploration-190731183556/75/Graph-Algorithms-for-Developers-40-2048.jpg)
Uploaded byNeo4j
Graph Algorithms for Developers
This document provides an overview of graph algorithms and how they can be used with Neo4j. It discusses how graph algorithms can extract structure and infer behavior from networked data. It covers categories of graph algorithms like pathfinding, centrality measures, community detection, and similarity measures. The document demonstrates how these algorithms can be used through Neo4j to enhance applications, like using PageRank and personalized PageRank on a business reviews dataset. It provides examples of graph algorithms and discusses how they can be accessed and run through Neo4j.
Graph Algorithms for Developers
- 1. Graph Algorithms For Developers AmyHodler & William Lyon, @Neo4j Seattle Graph Tour July 2019 bit.ly/seattlealgos
- 3. Relationships The Strongest Predictorsof Behavior! “Increasingly we're learning that you can make better predictions about people by getting all the information from their friends and their friends’ friends than you can from the information you have about the person themselves” James Fowler David Burkus Albert-László Barabási 3
- 4. William Lyon @lyonwj 4 Neo4j LabsEngineer Amy Hodler @amyhodler Analytics & AI Program Manager
- 5. Graph Platform ● Databasemanagement system (DBMS) ● Property Graph data model ● Cypher query language ● Graph analytics ● Data visualization ● Developer tool for building applications What is Neo4j? neo4j.com/
- 6.
- 7. Query (e.g. Cypher/Python) Real-time,local decisioning and pattern matching Graph Algorithms Libraries Global analysis and iterations You know what you’re looking for and making a decision You’re learning the overall structure of a network, updating data, and predicting Local Patterns Global Computation
- 8. What Do People Dowith Graph Algorithms?
- 9. Understand & PredictComplex Behavior Requires Understanding Relationships and Structures Flow & Dynamics Interactions & Resiliency Propagation Pathways
- 10. Using Graph Algorithms Explore,Plan, Measure Find significant patterns and plan for optimal structures Score outcomes and set a threshold value for a prediction Feature Engineering for Machine Learning The measures as features to train 1st Node 2nd Node Common Neighbors Preferential Attachment label 1 2 4 15 1 3 4 7 12 1 5 6 1 1 0
- 11. • Current datascience models ignore network structure & complex relationships • Graphs add highly predictive features to existing ML models • Otherwise unattainable predictions based on relationships More Accurate Predictions with the Data You Already Have Machine Learning Pipeline
- 12. Financial Crimes Recommendations Cybersecurity Predictive Maintenance Customer Segmentation Churn Prediction Search & MDM GraphData Science Applications EXAMPLES Drug Discovery 12
- 13. Why Not Use Other Typesof Analytics?
- 14. Structure is Hard toUnfold
- 15. 15 NumberofNODES Number of RELATIONSHIPSper Node Average Distribution Most nodes have the same number of relationships “No Network in Nature that we know of that would be described by the Random network model.” –Albert-László Barabási Random Network
- 16. 16 NumberofNODES Number of RELATIONSHIPSper Node Power-Law Distribution Some nodes have a lot of relationships but MOST have very few Structured Network
- 17. 17 NumberofNODES Number of RELATIONSHIPSper Node Many approaches erroneously focus on the average population where few entities actually exist Graphs help us invest in populous areas Find strategic entities Uncover structural information
- 18. Graph Algorithms Extract Structureand Infer Behavior Source: “Communities, modules and large-scale structure in networks“ - Mark Newman Source: “Hierarchical structure and the prediction of missing links in networks”; ”Structure and inference in annotated networks” - A. Clauset, C. Moore, and M.E.J. Newman.
- 19.
- 20. Graph Algorithm Categoriesin Neo4j neo4j.com/ graph-algorithms- book/ Book Signing 3:15 Pathfinding & Search Centrality / Importance Community Detection Link Prediction Finds optimal paths or evaluates route availability and quality Determines the importance of distinct nodes in the network Detects group clustering or partition options Evaluates how alike nodes are Estimates the likelihood of nodes forming a future relationship Similarity
- 21. Graph Algorithms inNeo4j • Parallel Breadth First Search & DFS • Shortest Path • Single-Source Shortest Path • All Pairs Shortest Path • Minimum Spanning Tree • A* Shortest Path • Yen’s K Shortest Path • K-Spanning Tree (MST) • Random Walk • Degree Centrality • Closeness Centrality • CC Variations: Harmonic, Dangalchev, Wasserman & Faust • Betweenness Centrality • Approximate Betweenness Centrality • PageRank • Personalized PageRank • ArticleRank • Eigenvector Centrality • Triangle Count • Clustering Coefficients • Connected Components (Union Find) • Strongly Connected Components • Label Propagation • Louvain Modularity – 1 Step & Multi- Step • Balanced Triad (identification) • Euclidean Distance • Cosine Similarity • Jaccard Similarity • Overlap Similarity • Pearson Similarity Pathfinding & Search Centrality / Importance Community Detection Similarity neo4j.com/docs/ graph-algorithms/current/ Updated June 2019 Link Prediction • Adamic Adar • Common Neighbors • Preferential Attachment • Resource Allocations • Same Community • Total Neighbors +35
- 22.
- 23. Yelp Public Dataset(as a graph) https://yelp.com/dataset
- 24. 24 How To UseGraph Algos To Enhance An Application? ● Category hierarchy - knowledge graph ○ Overlap similarity algorithm ● Showing relevant reviews ○ Personalized PageRank ● Personalized recommendations ○ Jaccard similarity ○ Label propagation
- 25. 25 Business Reviews Application Neo4jJavaScript Driver
- 26.
- 27.
- 28. Neo4j Graph AlgorithmsPlugin One-click install in Neo4j Desktop … or grab plugin directly https://neo4j.com/download-center/
- 29. 1. Call asCypher procedure 1. Pass in specification (Label, Prop, Query) and configuration 1. stream variant returns (a lot) of results CALL algo.<name>.stream('Label','TYPE',{conf}) YIELD nodeId, score 2. non-stream variant writes results to graph returns statistics CALL algo.<name>('Label','TYPE',{conf}) How To… Pathfinding & Search Centrality / Importance Community Detection Link Prediction Similarity
- 30.
- 31.
- 32. Overlap Similarity Algorithm Ideal choicefor finding hierarchy in data and developing super and sub- categories Overlap similarity coefficient represents the co-occurrence of items between groups A B A B
- 33. Jaccard Similarity Algorithm Often usedto find recommendations of similar items as well as part of link prediction Jaccard similarity measures the similarity between sets A B A B
- 34.
- 35. 36 Running Overlap SimilarityIn Neo4j 1) Find category co- occurences 1) Pass to overlap similarity procedure
- 36.
- 37. 38 Find Top LevelCategories Only return categories without an outgoiong NARROWER_THAN relationship
- 38.
- 39.
- 40. PageRank & PersonalizedPageRank Measures the transitive (directional) influence of nodes and considers the influence of neighbors and their neighbors Personalized PageRank CALL algo.pageRank('Page', 'LINKS', {iterations:20, dampingFactor:0.85, sourceNodes: [siteA]})
- 41. 44 Using Personalized PageRankTo Surface Relevant Reviews ● Find influential reviewers in my network ● Find users who have reviewed the same businesses as me
- 42.
- 43. 46 Projected User-User Graph Leverageinferred relationships. We can run graph algorithms on these projected graphs.
- 44.
- 45.
- 46.
- 47.
- 48. 51 Query Using TRUSTSRelationships Order reviews by PageRank score on TRUSTS relationship
- 49. 53 Personalized Recommendations Content basedvs collaborative filtering ● Photo based recommendations: 1) Similar photos using Jaccard similarity 2) Cluster similar photos using Label Propagation 3) Recommend businesses connected to photos in the same community
- 50. Label Propagation Nodes adoptlabels based on neighbors to infer clusters IterateIterate Community Detection
- 51.
- 52. 56 Photo Labels Labeledusing Google’s Vision API https://cloud.google.com/vision/ https://github.com/moxious/vision-api
- 53.
- 54. A B A BB JaccardSimilarity
- 55. 59 How Similar AreThese Photos?
- 56.
- 57. Label Propagation IterateIterate Community Detection Addspartition property to group photos by community Group by community and count photos per community
- 58.
- 59. Photo Based RecommendationsWhat photos do you like?
- 60.
- 61.
- 62. Enter the NEuler(Algorithms Playground)
- 63.
- 64. 69 Game of Thrones(TV-Series) • Based on Andrew Beveridge's script to graph work • 400 Nodes (people) • 3,550 Relationships (interactions)
- 65. Triangles and ClusteringCoefficient Communities Measures can be counted/normalized globally u Triangles = 2 CC= 0.2 Triangle Count determines the number of triangles passing through a node in the graph Clustering Coefficient is the probability that neighbors of a particular node are connected to each other u Triangles = 2 CC= 0.33
- 66. Triangles and ClusteringCoefficient Communities Use When Basic network analysis, e.g. does the network exhibit small-world structures? Estimating stability Finding structural holes Scoring for machine learning Spam Classification Semi-streaming web page analysis (local triangle and CC) I don’t like spam!
- 67.
- 68. A C D E B F G StronglyConnected Components All nodes can reach each other following direction, but not necessarily directly Find cycles, collapse tight communities, estimate similarity in-group Connected Components All nodes can each other when disregarding direction Find disconnected subgraphs or nodes in common, preprocess data Communities
- 69.
- 70. Betweenness Centrality Influence Tip /Caution Computationally intensive: use RA Brandes approximation on large graphs. Assumes all communication between nodes happens along the shortest path and with the same frequency (not always the case in real life) The sum of the % shortest paths that pass through a node, calculated by pairs
- 71. Betweenness Centrality -Uses Influence Use When Identify bridges Uncover control points Find bottlenecks and vulnerabilities Network Resilience Key points of cascading failure
- 72.
- 73.
- 74.
- 75. 81 Online Training! Applied GraphAlgorithms Data Science With Neo4j https://neo4j.com/graphacademy/online-training/data-science https://neo4j.com/graphacademy/online-training/applied-graph-algorithms
- 76. Free Digital Book neo4j.com/ graph-algorithms-book •Spark & Neo4j Examples • Machine Learning Chapter
- 77.
- 78.