Betweenness Centrality
Betweenness centrality is a measure used in network analysis to identify nodes that act as bridges or mediators between different parts of a network. It quantifies the number of times a node acts as a bridge along the shortest path between two other nodes in the network.
For a meaningful demonstration, let's create a hypothetical scenario where we have a social network representing friendships between individuals. We'll use the Betweenness Centrality algorithm to identify key individuals who serve as a connection between different social groups within the network.
First, we need to import the relationalai library and define our model, which we call MyBCGraph. We also create a type called Person.
%pip install relationalai
import relationalai as rai
from relationalai.std.graphs import Graph
from relationalai.std import aggregates
import colorsys
model = rai.Model("MyBCGraph")
Person = model.Type("Person")
Let's add some data to our model
Let's create a simple social network graph representing friendships between individuals. Using a RelationalAI rule, we're going to populate the model with the data from the friendship list we define. Person.add adds a new object of the Person type to the model, with a name property.
We also set friends property as a link between every pair of people from the friendship list.
friendships = [
('Alice', 'Bob'),
('Alice', 'Charlie'),
('Bob', 'Charlie'),
('Charlie', 'David'),
('David', 'Eve'),
('Eve', 'Frank'),
('Alice', 'David'),
('Bob', 'Eve'),
('Charlie', 'Frank'),
('David', 'George'),
('Eve', 'Hannah'),
('Frank', 'Isabella'),
('George', 'Jack'),
('Hannah', 'Kevin'),
('Isabella', 'Liam'),
]
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 graph
graph = Graph(model, undirected = True)
Node, Edge = graph.Node, graph.Edge
# add all Person instances as Nodes, assign `name` property (for displaying)
Node.extend(Person, label = Person.name)
# add all `friends` properties as Edges
Edge.extend(Person.friends)
Running the algorithm
To compute the betweenness centrality of each node in the graph, we use the betweenness_centrality function. We define a rule, that runs the algorithms and then adds the betweenness centrality score to each Person as a property of the node.
with model.rule():
person = Person()
person_node = Node(person)
centrality = graph.compute.betweenness_centrality(person_node)
person_node.set(centrality = centrality)
Visualizing the results
We can visualize the graph using the visualize function on the graph object. We set the node size and color to be the centrality score from the previous step.
def get_gradient_color(value):
rgb = colorsys.hsv_to_rgb(1, value * 0.03, 1) # Adjust the value multiplier to control the gradient range
return '#{:02x}{:02x}{:02x}'.format(int(rgb[0] * 255), int(rgb[1] * 255), int(rgb[2] * 255))
graph.visualize(three = False, style = {
"node": {
"color": lambda n: get_gradient_color(n['centrality']),
"size": lambda n: 20 + n['centrality'],
},
"edge": {
"color": "green",
}
}).display(inline = True)
Tip. We can see that the nodes with the highest betweenness centrality scores are the ones that act as bridges between different social groups in the network.
Querying the graph
We can also query the graph to get all the nodes and their betweenness centrality scores. This is done using model.query() context and graph.Node() or graph.Edge() types.
with model.query() as select:
person = Person()
node = Node(person)
response = select(person.name, node.centrality)
response
| name | centrality |
|---|---|
| Alice | 1.0 |
| Bob | 2.5 |
| Charlie | 10.0 |
| David | 20.5 |
| Eve | 25.0 |
| Frank | 19.0 |
| George | 10.0 |
| Hannah | 10.0 |
| Isabella | 10.0 |
| Jack | 0.0 |
| Kevin | 0.0 |
| Liam | 0.0 |
Let's find out who has the highest score
We can add a filter to the query to get the node with the highest betweenness centrality score. In this case, we use the top function from the aggregates module.
with model.query() as select:
person = Person()
node = Node(person)
aggregates.top(1, node.centrality)
response = select(person.name, node.centrality)
response
| name | centrality |
|---|---|
| Eve | 25.0 |