I have a large network of 10,000 nodes and I am trying to identify subgraphs which are clique-like, in that they share many connections. I don't a priori know how many subgraphs fit this criteria.
To solve this task, I have been trying to use the highly connected subgraph (HCS) algorithm for this, but it seems to run very slowly. In particular, it relies on iteratively finding minimum edge cuts, which is a very slow process, particularly as implemented on networkX (I am using python).
Additionally, I have tried heuristics such as removing low-degree vertices to make the graph smaller, but this has not worked yet.
Does anyone have recommendations for faster or simpler approaches to solving a similar problem? i.e. Identifying regions of the graph with very high connectivity?