Community detection
One important feature of graphs is the degree of clustering and presence of community structures. Groups of nodes that are densely connected amongst members of the group but have comparatively few connections with the rest of the graph can be considered distinct communities.
Identifying clusters can be informative in social, biological and technological networks. For example, identifying clusters in web clients accessing a site can help optimise performance using a CDN or spotting changes in the communities amongst a baboon pack over time might inform theories about group dynamics. Raphtory provides a variety of algorithms to analyse community structures in your graphs.
Exploring Zachary's karate club network
As an example, we use a data set from the paper "An Information Flow Model for Conflict and Fission in Small Groups" by Wayne W. Zachary which captures social links between the 34 members of the club.
Load data and run Louvain
Raphtory provides multiple algorithms to perform community detection, including:
louvain- a commonly used and well understood modularity based algorithmlabel_propagation- a more efficient cluster detection algorithm when used at scale
Here we load the data, create a Graph, and use the louvain algorithm to identify distinct clusters of nodes.
The algorithm identifies four clusters of nodes which could be interpreted as four social groups amongst the students.
Explore the data
You can explore the results of our cluster detection algorithm in greater detail using the Raphtory UI.
To do this, assign a type to nodes of each cluster using set_node_type() and start a GraphServer. Each unique node type will be assigned a colour in the Graph canvas so that you can distinguish them visually.
You should see that there are four distinct communities. For each node you can see its node type in the Node Statistics panel of the Selected menu and by visual inspection verify that each node is connected mostly to its own group.
You may also spot other features that could be investigated further, for example the nodes with the highest degree are members of the 'Cobra Kai' cluster.
