cluster-analysisnetworkxgraph-theorynetworkit
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
- 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
- Clustering Coefficient of 0.0 on Network Analyzer in Cytoscape
- Clustering algorithm that keeps separated a given set of pairs
- create a bubble plot (or something similar) from cluster analysis in R
- 1D Number Array Clustering
- hierarchical clustering on correlations in Python scipy/numpy?
- How to specify the memory directory for Agglomerative clustering using sklearn
- Divide data into clusters by a linear function
- Identify connected subnetworks, constrained by edge attributes
- In scikit-learn's agglomerative clustering algorithm how would you get all the intermediate clusters?
- Collapse List into Unique Combinations Using Index Values
- Spectral embedding - spectral clustering
- Spectral Clustering a graph in python
- TypeError: len() of unsized object in pyclustering library
- variation_of_information results of cdlib and igraph are different
- Is there a way to use found sequential patterns as input for a clustering algorithm
- Clustering of 3 dimensions set of points