Skip to main content

Graph Clustering

Description​

In graph theory, graph clustering is used to find subsets of similar nodes and group them together. It is part of graph analysis which has been attracting increasing attention in the recent years due the ubiquity of networks in the real world.

Graph clustering also known as network partitioning can be of two types:

  • structure based
  • attribute based clustering

The structure based can be further divided into two categories, namely community based, and structurally equivalent clustering.

Community-based methods aim to find dense subgraphs with high number of intra-cluster edges, and low number of inter-cluster edges. Examples are following algorithms:

community-clustering

Structure based community clustering

Structural equivalence clustering on the contrary, is designed to identify nodes with similar roles (like bridges and hubs). Example is SCAN: A Structural Clustering Algorithm for Networks

community-clustering

Structure based structural equivalence clustering

One example that can vary between community based and structurally equivalent clustering is Node2Vec.

Attribute based methods utilize node labels, in addition to observed links, to cluster nodes like following algorithm: Graph clustering based on structural/attribute similarities

Materials​

Implementation​

Node2Vec

Node2Vec

Node2Vec is implemented within project MAGE. Be sure to check it out in the link above.

Also, finding communities in dynamic graphs is possible with Dynamic Node2Vec.

Node2Vec
Online

Node2Vec
Online

Dynamic Node2Vec is implemented within the project MAGE. Be sure to check it out in the link above.

Use cases​

Social
networks

Biggest use case for graph clustering is in social networks. There communities can be explored, hubs found and many more.