Generate clusters from a graph based on edges within cluster

oxuser 0
Viewed 36

Let's say we have an undirected and unweighted network graph.

What is the best algorithm to use to generate "clusters" that have the following properties:

  • Within a given cluster, each node must have an edge to at least x other nodes in the cluster. For example, if we choose a value of x = 5, it means that each node in that cluster must have an edge to at least 5 of the other nodes in the cluster
  • A node can belong to more than one "cluster". I'm not trying to determine "subgraphs". A node could be part of 20 clusters, so long as the cluster property above (eg. at least x edges to the other nodes in the cluster) is met.

Is there an algorithm that can be used to determine this?

networkit cluster-analysis graph-theory networkx
1 Answers
LOOP N over nodes 
   IF N has less than X edges 
       Remove N and all its edges from graph
REPEAT until no more nodes can be removed.

You now have one or more clusters that meet the requirement. Use a component finder algorithm ( https://en.wikipedia.org/wiki/Component_(graph_theory)#Algorithms ) to identify the clusters.

Here is a typical result of running the algorithm on a graph with two clusters that meet your requirement.

Original graph. The algorithm removes the red nodes and edges

enter image description here

Result - it is a graph with two components

enter image description here

ravenspoint0
Related