1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Is there any lower bound on the size of the required subgraph in terms of $n:$ the total number of nodes? $\endgroup$
    – Inuyasha Yagami
    Jan 24, 2022 at 15:36
  • $\begingroup$ @InuyashaYagami no, but for speed reasons I could imagine setting an arbitrary lower bound. Would a lower bound significantly increase speed? $\endgroup$
    – Gabriel
    Jan 24, 2022 at 16:36

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.