Generate clusters from a graph based on edges within cluster
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?
Solution
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
- Filter rows based on combined set of values in a string
- Problems with creating a mathematical clustering model with an additive criterion in CPLEX OPL Studio
- How to group dataframes to get a subset that represents the full range of the larger set
- DBSCAN on 3d coordinates doesn't find clusters
- Best way to validate DBSCAN Clusters
- Clustering with a distance matrix
- How can we interpret negative adjusted rand index?
- sklearn: Get Distance from Point to Nearest Cluster
- Adding a Bubble Plot as a Complex Heatmap Annotation
- Clustering geometries recursively exceeds cluster size limit
- Topic modelling many documents with low memory overhead
- How to delete edges based on cluster_edge_betweenness output
- scikit-learn DBSCAN memory usage
- How to define exact number of communities in a igraph object,?
- How to Cluster Parts of a Mask in an Image Using Python?
- matplotlib detect and isolate in circles different groups of points
- Julia - AssertionError in K-medoids algorithm
- How Fast Can We Approximate Set Jaccard Scores?
- Clustering using Python
- How reliable is the Elbow curve in finding K in K-Means?
- Complicated for-loop in Python
- silhouette calculation in R for a large data
- Keep column AND row order in a data set EXACTLY the same as in the HEATMAP
- Algorithm to find k optimal representatives for subsets of a set with arbitrary cost function
- Create a Heatmap for gene expression analyses in R
- Python data filtering to remove outliers around a density plot
- Error in do_one(nmeth) : NA/NaN/Inf in foreign function call (arg 1)
- Number of observations changing significantly after imputing using mice() in R
- How to use the Agglomerative Clustering algorithm from scikit-learn python library with a declared number of objects in the cluster?
- Finding the center of a cluster