Community Detection using Louvain¶
Louvain
is an algorithm that can quickly find non-overlapping communities within large networks. It is a hierarchical clustering algorithm, that recursively merges communities into a single node and executes the modularity clustering on the condensed graphs.
Our graph will model a social network in which people have friends and their friendship can be of different strength. We will first apply the algorithm to an unweighted undirected graph, then add friendship strength as weights to the edges and look at the difference in the results.
First, we start by importing the relationalai
library and define our model, which we call MyLouvainGraph
. We also create two types called Person
and Friendship
.
def install_packages():
import os
os.system('pip install relationalai')
install_packages()
import relationalai as rai
from relationalai.std import alias
from relationalai.std.graphs import Graph
model = rai.Model("MyLouvainGraph")
# Graph will hold these types:
# Represents nodes
Person = model.Type("Person")
# Represents connections between nodes
Friendship = model.Type("Friendship")
Let's add some data to our model¶
We first create a dictionary of people names, who are friends with each other, and a number representing the strength of their friendship. Then we iterate over the dictionary to create objects of type Person
with a name
property. We also create Friendship
objects with strength
property, representing connection between two people. We will use it to create weighted edges between nodes in our graph.
data = {
("Mary", "Bob"): 1.0,
("Mary", "Jessy"): 0.5,
("Mary", "Erica"): 0.1,
("Mary", "Tom"): 0.1,
("Bob", "Frank"): 0.1,
("Jessy", "Erica"): 1.0,
("Erica", "Tom"): 1.0,
("Tom", "Jessy"): 1.0,
("Frank", "Anna"): 1.0,
("Frank", "Mark"): 1.0,
("Frank", "Peter"): 0.5,
("Anna", "Peter"): 0.1,
("Anna", "Mark"): 1.0,
("Peter", "Mark"): 0.1,
}
with model.rule(dynamic = True):
for ((name, friend_name), strength) in data.items():
person = Person.add(name = name)
friend = Person.add(name = friend_name)
Friendship.add(person = person, friend = friend).set(strength = strength)
Creating the graph¶
Let's start by creating a graph
with Node
and Edge
types. We add all Person
instances as nodes, and assign the name
property so that we can use them in our queries and for visualization purposes. The Friendship
instances are then used to form the edges in our graph.
# Create graph
graph = Graph(model, undirected = True)
Node, Edge = graph.Node, graph.Edge
# add all Person instances as Nodes and assign `name` property (for displaying)
Node.extend(Person, name = Person.name)
# add all Friendship instances as Edges from `person` to `friend` Nodes
with model.rule():
f = Friendship()
Edge.add(f.person, f.friend)
Running the algorithm¶
Let's add a rule that calculates for every node of the graph the community that it belongs_to
. To derive this value for each node using the Louvain algorithm, we can simply use Graph(model).compute.louvain()
.
# run the Louvain algorithm on the Graph,
# for every Person node assign the community it belongs to
with model.rule():
p = Person()
community = graph.compute.louvain(p)
p.set(belongs_to = community)
Node(p).set(community_id = community)
Querying the Graph¶
Graph Nodes, Edges and their properties are queried using model.query()
context and graph.Node()
or graph.Edge()
types.
Alternatively, the entire graph representation can be fetched using Graph(model).fetch()
(not recommended to be used for large graphs). This returns a dictionary with two keys, nodes
and edges
, that represents the entire graph.
# query all Edges with `name` and `community_id` properties of the Nodes they connect
with model.query() as select:
e = Edge()
n1 = Node(e.from_)
n2 = Node(e.to)
response = select(alias(n1.name,"from"),alias(n1.community_id,"community (from)"), alias(n2.name,"to"),alias(n2.community_id,"community (to)"))
response
from | community (from) | to | community (to) |
---|---|---|---|
Anna | 1 | Mark | 1 |
Anna | 1 | Peter | 1 |
Bob | 2 | Frank | 1 |
Erica | 2 | Tom | 2 |
Frank | 1 | Anna | 1 |
Frank | 1 | Mark | 1 |
Frank | 1 | Peter | 1 |
Jessy | 2 | Erica | 2 |
Mary | 2 | Bob | 2 |
Mary | 2 | Erica | 2 |
Mary | 2 | Jessy | 2 |
Mary | 2 | Tom | 2 |
Peter | 1 | Mark | 1 |
Tom | 2 | Jessy | 2 |
How many communities were found? And to which community do people belong to?¶
# For each Person, fetch the name and the community it belongs to
with model.query() as select:
p = Person()
response = select(p.name, p.belongs_to)
response
name | belongs_to |
---|---|
Anna | 1 |
Bob | 2 |
Erica | 2 |
Frank | 1 |
Jessy | 2 |
Mark | 1 |
Mary | 2 |
Peter | 1 |
Tom | 2 |
# Group the response from the above query by the belongs_to property to separate the communities
communities = response.results.groupby("belongs_to").name.apply(list)
# Print the number of communities
count_communities = len(communities)
print(f"Number of communities: {count_communities}")
# Print communities and people that belong to them
for i, c in enumerate(communities):
print(f"Community N{i+1}: {c}")
Number of communities: 2 Community N1: ['Anna', 'Frank', 'Mark', 'Peter'] Community N2: ['Bob', 'Erica', 'Jessy', 'Mary', 'Tom']
Let's find out who is in the same community as Frank¶
person_name = "Frank"
with model.query() as select:
p1 = Person(name = person_name)
p2 = Person()
# We want to skip the person itself
p1 != p2
p1.belongs_to == p2.belongs_to
response = select(p2.name)
response
name |
---|
Anna |
Mark |
Peter |
Visualizing the results¶
Let's visualize our graph, to better understand the results. We use Graph(model).visualize()
to visualize our graph. We define a color for each of the communities.
graph.visualize(three = False, style = {
"node": {
"color": lambda n : ['blue', 'pink'][ list(communities.keys()).index(n['community_id']) % 2 ],
"label": lambda n : n['name'],
"hover": lambda n: n['community_id'],
"size": 30
},
"edge": {
"color": "green"
}
}).display(inline = True)
Adding weights to the graph edges¶
As a final step, let's see how adding weights to the graph edges affects the result of the algorithm.
Let's create a new graph with the same Nodes and Edges, but now using Friendship.strength
property as a weight of an edge.
# Create weighted graph
weighted_graph = Graph(model, undirected = True, weighted = True)
# add all same Person instances as Nodes and assign `name` property
weighted_graph.Node.extend(Person, name = Person.name)
# add all Friendship instances as Edges from `person` to `friend` Nodes with weight property
with model.rule():
f = Friendship()
weighted_graph.Edge.add(f.person, f.friend, weight = f.strength)
# run Louvain algorithm on the new Graph
with model.rule():
n = weighted_graph.Node()
n.set(community_id = weighted_graph.compute.louvain(n))
How many communities were found now?¶
# query weighted graph nodes names and communities they were assigned to
with model.query() as select:
n = weighted_graph.Node()
response = select(n.name, n.community_id)
# group names by community_id
communities = response.results.groupby("community_id").name.apply(list)
# print communities and names of people that belong to them
for i, c in enumerate(communities):
print(f"Community N{i+1}: {c}")
Community N1: ['Anna', 'Frank', 'Mark', 'Peter'] Community N2: ['Erica', 'Jessy', 'Tom'] Community N3: ['Bob', 'Mary']
Visualizing the weighted graph¶
Let's make the size of the Edges proportional to the weight. Additionally, we'll define more colors since we now have more communities.
weighted_graph.visualize(three = False, style = {
"node": {
"color": lambda n : ['yellow', 'orange', 'blue', 'pink'][ list(communities.keys()).index(n['community_id']) % 4 ],
"label": lambda n : n['name'],
"hover": lambda n: n['community_id'],
"size": 30
},
"edge": {
"color": "green",
"size": lambda e: e['weight'] * 3.5
}
}).display(inline = True)