Skip to content

Graph Algorithms Lessons

This section of the website has a list of lessons that are used in building your graph courses.

We begin with a lesson that introduces basic graph terminology and then proceed through different algorithms such as search, path-finding, centrality, influence ranking, matching, clustering and community detection.

Graph Algorithms By Type

  1. Search Algorithms: These algorithms explore graphs, either for general exploration or to find a particular node.

    • Depth-First Search (DFS)
    • Breadth-First Search (BFS)

  2. Pathfinding Algorithms: Focused on finding the shortest path or paths between nodes in a graph.

    • Dijkstra's Algorithm
    • A* Search Algorithm
    • Bellman-Ford Algorithm

  3. Centrality Measures: These algorithms help in identifying the most important vertices within a graph.

    • Degree Centrality
    • Betweenness Centrality
    • Eigenvector Centrality
    • Closeness Centrality

  4. Influence Ranking Algorithms: Useful in networks to rank nodes based on their influence.

    • PageRank
    • HITS Algorithm (Hyperlink-Induced Topic Search)
    • Katz Centrality

  5. Matching Algorithms: Aimed at solving matching problems in bipartite graphs or networks.

    • Stable Marriage Problem (Gale-Shapley Algorithm)
    • Hungarian Algorithm for Assignment Problems
    • Maximum Bipartite Matching

  6. Entity Resolution Algorithms: These algorithms identify and merge data that correspond to the same real-world entity.

    • Levenshtein Distance (for string matching)
    • Jaro-Winkler Distance
    • Record Linkage Techniques

  7. Graph Clustering and Community Detection: Focused on partitioning graphs into clusters or communities, often used in social network analysis.

    • K-means Clustering (applied to graph data)
    • Louvain Method for Community Detection
    • Girvan-Newman Algorithm

Each of these categories encompasses a set of algorithms tailored to specific types of problems and analysis within graph theory. It's important to note that some algorithms might fall into more than one category depending on their application and interpretation.