Graph algorithms (the pre–deep learning era)
Initial work in graph analysis often focused on developing methods to better understand the structure of graphs. They aimed to uncover hidden patterns, properties, and relationships within graphs (e.g., community structures or centrality within a network) and were concerned with gaining insights into the graph’s overall organization and meaning. Meanwhile, parallel efforts focused on designing algorithms to operate over graph structure. These algorithms used the graph as input and performed specific computations or transformations on it (e.g., to calculate shortest paths, maximum flows, etc.). They were concerned with solving well-defined problems based on a graph’s existing connections and nodes.
With the rise of web data in the late 1990s and social media in the early 2000s, graph algorithms came into their own. Instead of being mathematical curiosities, they now played a critical role in the rapidly growing Internet. For example, in 1996, Google founders Larry Page and Sergey Brin created PageRank, which would eventually become the backbone of Google Search, and, as such, one of the world’s most popular and oft-used graph algorithms. PageRank applied graph theory principles to the web, turning the internet into a giant, interconnected graph of pages (nodes) and hyperlinks (edges). This made it one of the earliest and most influential examples of using graph-based methods to solve real-world problems.
