Modern Graph Theory Algorithms with Python

Learn to create a simple social network graph with networkx and matplotlib by initializing an undirected graph and adding initial nodes like Alice, Paul, Charlie, and Diana.

Add nodes and edges to build a social network graph with Python, representing friendships between individuals like Alice and Bob, and visualize the network with matplotlib.

Visualize graphs with matplotlib and NetworkX using the spring layout to balance nodes, reveal central nodes and clusters, and customize with colors, sizes, and labels. Explore path length and degree.

Analyze basic graph properties by calculating node degrees and shortest path lengths in social networks using Python and NetworkX, revealing influencers and information flow.

Explore depth first search traversing graphs from a root node, visiting unvisited neighbors and backtracking to explore as far as possible with Python and NetworkX, web crawling and file searches.

Learn breadth-first search (BFS), a graph traversal that explores nodes at the current depth from a source, visiting neighbors level by level. Applications include finding shortest paths and web crawling.

Explore recursive vs iterative implementations of depth first search and breadth first search in Python, comparing recursion, stacks and deques, and memory considerations for graph traversal and shortest path problems.

Explore graph traversal for graph exploration, using BFS and Dijkstra to find shortest paths and detect communities in social networks and other large networks.

Represent a city map as a weighted graph, with nodes as intersections and edges as routes, visualize it using NetworkX data and a spring layout, then apply shortest path algorithms.

Explore the Dijkstra algorithm for finding the shortest paths from a source node in directed and undirected weighted graphs with non-negative weights, using a greedy, nearest-node approach.

Visualize weighted shortest paths on city maps by highlighting the calculated route. Initialize the graph, select target nodes, and plot labeled edges to verify the shortest path.

Explore the performance of shortest-path algorithms on a city map by implementing and timing Dijkstra’s algorithm versus A*, highlighting how the Euclidean distance heuristic speeds searches.

Learn to identify connected components in graphs with Python and networkx, including undirected, strongly and weakly connected components, maximal sets, and paths for real-world networks.

Explore articulation points and bridges in graphs, learning how removing them increases connected components. Identify these critical nodes and edges in a synthetic network to improve resilience and planning.

Model real-world networks to assess resilience by locating articulation points and bridges, adding redundancy, and simulating failures to maintain connectivity.

Explore Kruskal's algorithm for building a minimum spanning tree by sorting edges, adding them without cycles via union-find, and applying the method to a Python network graph.

Prim's algorithm builds the spanning tree by starting at a vertex and adding the cheapest edge to an unvisited vertex, preventing cycles, with Python implementation and minimum spanning tree visualization.

Explore how MST algorithms optimize network design by linking nodes in a weighted graph at minimal cost. Apply Kruskal's and Prim's methods to create a fault-tolerant, cost-efficient network.

Implement MST algorithms in Python by building a weighted graph and applying Kruskal and Prim using NetworkX's minimum spanning tree function, then compare results to verify minimal cost.

Design an optimal optical network by modeling cities as nodes with distances as weighted edges using geodesic distances with GOP. Apply MST algorithms like Kruskal's and Prim's to compare results.

Apply Prim's and Kruskal's MST algorithms to a weighted city graph, compare their total costs using Network X, and prepare for visualizing the optical fiber network in the next class.

Visualize the optical network and its MST via Prim's and Kruskal's algorithms, compare original vs MST designs, highlight MST edges, and illustrate installation cost savings for robust fiber routes.

Analyze the MST-based optical network's cost efficiency by comparing the MST installation cost to the full network and computing cost savings, with attention to redundancy.

Explore centrality measures—degree, betweenness, and closeness—for social networks, analyze a synthetic network with network X, and visualize results by node size. Preview community detection with Girvan-Newman and the Louvain method.

Explore community detection algorithms to identify clusters of nodes in social networks. Compare the Girvan-newman and Louvain algorithms, highlighting betweenness centrality, modularity, and the Karate Club dataset.

Explore the PageRank algorithm, scoring node importance by inbound links and quality with a 0.85 damping factor and iterative convergence, demonstrated on a NetworkX miserable dataset.

Explore real-world graph applications in social media, including influencer detection via degree and betweenness centrality, link prediction for recommendations, and Louvain-based community detection on the Facebook SNAP dataset.

Explore graph based machine learning with node and edge embeddings, gcn and gnns, applying them to node classification on karate club dataset, 34 nodes and 78 edges, achieving 0.91 accuracy.

Explore biological graphs by modeling proteins as nodes and interactions as weighted edges, using degree and betweenness centrality to identify key proteins and apply the Louvain algorithm to detect communities.

Explore graphs in transportation and networks, modeling locations as nodes and connections as edges with weights, using Dijkstra's algorithm, centrality, and karate club graph examples.

Model the web as a directed graph of pages linked by hyperlinks, and rank pages with PageRank using the damping factor, demonstrated on a small networkx web graph.

Design a graph-based movie recommendation system with the Movielens 100k dataset, using centrality, community detection, and link prediction to suggest movies.

Explore advanced network flow optimization by applying Ford-Fulkerson to a transportation network, identify bottlenecks through centrality measures and shortest paths, and enhance connectivity with link prediction.

Analyze Zachary's karate club network in network X, compute centralities (degree, closeness, betweenness, eigenvector), apply Louvain detection, perform link prediction with the Jaccard coefficient, and assess robustness.