Kosaraju’s Algorithm, Strongly Connected Components, and Advertising
A graph is strongly connected if every vertex is reachable from every other vertex, and SCCs (Strongly Connected Components) of a graph are subgraphs that themselves are strongly connected. There actually exists an algorithm called Kosaraju’s Algorithm, created by S. Rao Kosaraju, a professor at Johns Hopkins University, that can find all strongly connected components of a graph. This algorithm first could use Depth-First Search, an iconic traversal/search algorithm for graphs that uses either a stack or a backtracking recursive approach, to get a list of all nodes in a graph. Then, using the reversed list of nodes gathered from Depth-First Search, it assigns all nodes to a strongly connected component. It does this by iterating though all nodes in the reversed list and checking if a node has been assigned to a component or not. If it has not, then it creates a new component, adds the node to the component, and runs Depth-First Search again on that node, this time using the algorithm to add nodes that is reachable from that node to the new strongly connected component. This makes sense intuitively because it makes sure that all nodes in each component are reachable to each other and only creates new components for nodes that have not been assigned to previous components (nodes who are unreachable by the nodes in previous components). This algorithm can be used to better understand airline traffic patterns to determine which airports are directly reachable by others or how many flights does one have to take to get from one airport to another, but it also has many applications in social networks and advertising, which are topics especially relevant to this class. The relationships between various users and pages on Twitter, for example, can be represented as a graph. By running Kosaraju’s algorithm on this graph, it becomes apparent that there are subgroups of users or pages that are related to each other through criteria such as common interests or followed pages or friends. These communities then can be targeted by advertisers. Companies can identify exactly who in Twitter make up their potential customer base and deliver the right ads only for those people. A sports bar in New York City can specifically target a strongly connected component of users who all like the New York Knicks. By using this algorithm to pinpoint exactly which users are interested in a specific ad and only needing to how these people the ad, it can reduce costs for advertisers on Twitter by around 10 times!
Source: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.741.3957&rep=rep1&type=pdf