Node centric algorithms

The second category of algorithms are node centric which return a value for each node in the graph. These results are stored within a NodeState object which has functions for sorting, grouping, top_k, and conversion to dataframes.

Continuous Results: PageRank

PageRank is a centrality metric developed by Google's founders to rank web pages in search engine results based on their importance and relevance. This has since become a standard ranking algorithm for a whole host of other usecases.

Raphtory's pagerank implementation returns the score for each node. These are continuous values, meaning we can discover the most important characters in our Lord of the Rings dataset via top_k().

In the example below we first get the result of an individual character (Gandalf), followed by the values of the top 5 most important characters.

Discrete Results: Connected Components

Weakly connected components in a directed graph are subgraphs where every node is reachable from every other node if edge direction is ignored.

For each node, weakly_connected_components finds which component it is a member of and returns the id of the component. These are discrete values, meaning we can use groups() to find additional insights like the size of the largest connected component.

In the example below we first run the algorithm and print the result so we can see what it looks like.

Next we take the results and group the nodes by these IDs and calculate the size of the largest component. Almost all nodes are within this component (134 of the 139), as is typical for social networks.