Generate clusters from a graph based on edges within cluster

Question

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?

Answer 1

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

Result - it is a graph with two components