# Vertex centric algorithms

The second category of algorithms are `vertex centric` and return a value for each node in the graph. These results are stored within a AlgorithmResult object which has functions for sorting, grouping, top_k and conversion to dataframes. To demonstrate these functions below we have run PageRank and Weakly Connected Components.

## Continuous Results (PageRank)

`PageRank` is an 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 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 code below we first get the result of an individual character (Gandalf), followed by the values of the top 5 most important characters.

``````from raphtory import algorithms as rp

results = rp.pagerank(lotr_graph)

# Getting the results for an individual character (Gandalf)
gandalf_rank = results.get("Gandalf")
print(f"Gandalf's ranking is {gandalf_rank}\n")

# Getting the top 5 most important characters and printing out their scores
top_5 = results.top_k(5)
for rank, (name, score) in enumerate(top_5, 1):
print(f"Rank {rank}: {name} with a score of {score:.5f}")
``````

Output

``````Gandalf's ranking is 0.015810830531114206

Rank 1: Aragorn with a score of 0.09526
Rank 2: Faramir with a score of 0.06148
Rank 3: Elrond with a score of 0.04042
Rank 4: Boromir with a score of 0.03468
Rank 5: Legolas with a score of 0.03323
``````

## Discrete Results (Connected Components)

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

This algorithm returns the id of the component each vertex is a member of - these are discrete values, meaning we can use `group_by` to find additional insights like the size of the largest connected component.

In the code below we first run the algorithm and turn the results into a dataframe so we can see what they look like.

Info

The `component ID (value)` is generated from the lowest `vertex ID` in the component, hence why they look like a random numbers in the print out.

Next we take the results and group the vertices by these IDs and calculate the size of the largest component.

Info

Almost all vertices are within this component (134 of the 139), as is typical for social networks.

``````from raphtory import algorithms as rp

results = rp.weakly_connected_components(lotr_graph)

# Convert the results to a dataframe so we can have a look at them
df = results.to_df()
print(f"{df}\n")

# Group the components together
components = results.group_by()
print(f"{components}\n")

# Get the size of each component
component_sizes = {key: len(value) for key, value in components.items()}
# Get the key for the largest component
largest_component = max(component_sizes, key=component_sizes.get)
# Print the size of the largest component
print(
f"The largest component contains {component_sizes[largest_component]} of the {lotr_graph.num_vertices()} vertices in the graph."
)
``````

Output

``````           Key              Value
0      Dúnhere  45256802920602448
2      Anárion  45256802920602448
3        Gimli  45256802920602448
4     Barliman  45256802920602448
..         ...                ...
134    Thingol  45256802920602448
135    Elessar  45256802920602448
136      Merry  45256802920602448
137     Hirgon  45256802920602448
138  Goldberry  45256802920602448

[139 rows x 2 columns]

{10447362470584615464: ['Blanco', 'Marcho'], 4954526713244181378: ['Bard', 'Brand', 'Bain'], 45256802920602448: ['Dúnhere', 'Gil-galad', 'Anárion', 'Gimli', 'Barliman', 'Radagast', 'Sauron', 'Anborn', 'Horn', 'Haldir', 'Tom', 'Orophin', 'Thorin', 'Erkenbrand', 'Findegil', 'Elwing', 'Hamfast', 'Lúthien', 'Fengel', 'Folcwine', 'Glóin', 'Wormtongue', 'Elrond', 'Hador', 'Galdor', 'Daeron', 'Gandalf', 'Théoden', 'Gamling', 'Galadriel', 'Lotho', 'Éomer', 'Bill', 'Imrahil', 'Celebrían', 'Folca', 'Odo', 'Faramir', 'Balin', 'Mablung', 'Ghân-buri-Ghân', 'Meneldor', 'Goldilocks', 'Smaug', 'Halbarad', 'Shelob', 'Beregond', 'Grimbeorn', 'Celebrimbor', 'Rúmil', 'Isildur', 'Valandil', 'Bergil', 'Aldor', 'Saruman', 'Éowyn', 'Arwen', 'Déor', 'Fundin', 'Helm', 'Baldor', 'Legolas', 'Fëanor', 'Meneldil', 'Gorbag', 'Maggot', 'Déagol', 'Pippin', 'Shagrat', 'Fredegar', 'Treebeard', 'Nazgûl', 'Nimloth', 'Bofur', 'Denethor', 'Thranduil', 'Sméagol', 'Gollum', 'Barahir', 'Elendil', 'Glorfindel', 'Peregrin', 'Brego', 'Thrór', 'Ecthelion', 'Eärendil', 'Meriadoc', 'Halfast', 'Fastred', 'Finduilas', 'Aragorn', 'Samwise', 'Harding', 'Sam', 'Grimbold', 'Butterbur', 'Forlong', 'Boromir', 'Beorn', 'Círdan', 'Ori', 'Damrod', 'Ohtar', 'Bilbo', 'Lobelia', 'Celeborn', 'Amroth', 'Goldwine', 'Gram', 'Óin', 'Frodo', 'Nob', 'Dwalin', 'Thengel', 'Ungoliant', 'Fréa', 'Shadowfax', 'Angbor', 'Bombur', 'Túrin', 'Bob', 'Erestor', 'Robin', 'Beren', 'Dior', 'Eärnur', 'Húrin', 'Arvedui', 'Walda', 'Thingol', 'Elessar', 'Merry', 'Hirgon', 'Goldberry']}

The largest component contains 134 of the 139 vertices in the graph.
``````