Degree analysis
Degree analysis is widely used in network analysis to identify the most important nodes in a graph. It can be used to enrich the graph with additional information about the nodes. That can be used later on for further analysis with other algorithms.
The degree of a node in an undirected graph is the number of edges connected to it. And for directed graphs, in-degree is the number of edges coming into the node, and out-degree is the number of edges going out of the node.
Let us look at a very small example social graph and see how we can compute the degrees of its nodes.
First, we need to import the relationalai library and define our model, which we call DegreeAnalysis. We also create a type called Person.
%pip install relationalai
import relationalai as rai
from relationalai.std.graphs import Graph
model = rai.Model("DegreeAnalysis")
Person = model.Type("Person")
Let's add some data to our model
We're going to use use a friendship list we define as a data source to iterate over it and populate our model with objects. We create Person objects with a name property and also add a link from one person to the other as a friends property.
friendships = [
("Alice", "Bob"), ("Alice", "David"),
("Bob", "David"), ("Charlie", "David"),
("David", "Emily"), ("Emily", "Frank"),
("Emily", "Henry"), ("Frank", "Grace"),
("Frank", "Henry"), ("Grace", "Henry"),
("Kevin", "Mark"), ("Lily", "Mark"),
("Mark", "Nancy"), ("Nancy", "Lily"),
("Mark", "Oscar"), ("Oscar", "Nancy")
]
with model.rule(dynamic = True):
for (person_name, friend_name) in friendships:
person = Person.add(name = person_name)
person.friends.add(Person.add(name = friend_name))
Creating the Graph
Let's start by creating a graph with nodes and edges. We add all Person instances to Node type, and assign the label property so that we can visualize it later in the graph. We then add the friends property to Edge type.
# Create a directed graph
graph = Graph(model, undirected = False)
Node, Edge = graph.Node, graph.Edge
# add all Person instances as Nodes, assign `label` property (for displaying)
Node.extend(Person, label = Person.name)
# add all `friends` properties as Edges
Edge.extend(Person.friends)
Running the algorithm
To calculate the degree of each node, we use the degree function from RelationalAI's compute object of a graph. We set the result as a property of a Node representing a person.
with model.rule():
person = Person()
person_node = Node(person)
degree = graph.compute.degree(person_node)
person_node.set(degree = degree)
Visualizing the results
To better understand the results, we can visualize the graph using the visualize function on the graph object. We set the node size to be proportional to the degree score from the previous step. We also set the color for the nodes and edges.
graph.visualize(three = False, style = {
"node": {
"color": "blue",
"size": lambda n: n['degree'] * 10,
},
"edge": {
"color": "green",
}
}).display(inline = True)
Tip. As we can see nodes with higher degree are shown in a larger size.
Querying the graph
We can also query the graph to get all the nodes and their degree, using model.query() context and graph.Node() or graph.Edge() types. This is useful when we want to use the degree information in further analysis.
with model.query() as select:
person = Person()
node = Node(person)
response = select(person.name, node.degree)
response.results.sort_values(by = 'degree', ascending = False)
| name | degree | |
|---|---|---|
| 3 | David | 4 |
| 10 | Mark | 4 |
| 4 | Emily | 3 |
| 5 | Frank | 3 |
| 7 | Henry | 3 |
| 11 | Nancy | 3 |
| 0 | Alice | 2 |
| 1 | Bob | 2 |
| 6 | Grace | 2 |
| 9 | Lily | 2 |
| 12 | Oscar | 2 |
| 2 | Charlie | 1 |
| 8 | Kevin | 1 |
We can also filter the nodes based on the degree value. For example, we can get all the nodes with degree greater or equal to 4.
with model.query() as select:
person = Person()
node = Node(person)
node.degree >= 4
response = select(person.name, node.degree)
response
| name | degree |
|---|---|
| David | 4 |
| Mark | 4 |
In-degree and Out-degree
We can also calculate the in-degree and out-degree of each node in a directed graph. We can use the in_degree and out_degree functions. We're going to use the same graph as before, and enrich each node with the in-degree and out-degree information.
with model.rule():
person = Person()
person_node = Node(person)
in_degree = graph.compute.indegree(person_node)
out_degree = graph.compute.outdegree(person_node)
person_node.set(in_degree = in_degree, out_degree = out_degree)
As a final step, we can query the graph to get the degree, in-degree, and out-degree of each node.
with model.query() as select:
person = Person()
node = Node(person)
response = select(person.name, node.degree, node.in_degree, node.out_degree)
response
| name | degree | in_degree | out_degree |
|---|---|---|---|
| Alice | 2 | 0 | 2 |
| Bob | 2 | 1 | 1 |
| Charlie | 1 | 0 | 1 |
| David | 4 | 3 | 1 |
| Emily | 3 | 1 | 2 |
| Frank | 3 | 1 | 2 |
| Grace | 2 | 1 | 1 |
| Henry | 3 | 3 | 0 |
| Kevin | 1 | 0 | 1 |
| Lily | 2 | 1 | 1 |
| Mark | 4 | 2 | 2 |
| Nancy | 3 | 2 | 1 |
| Oscar | 2 | 1 | 1 |