How to highlight the most connected groups of elements in a graph?

Question

Mathematics

There are many elements. Pairs of elements can be linked. How to single out connected groups and separate them in places where there are few connections?

for example

It is not difficult to select a connected group of elements (1,2,3,4,5,6,7,8). It is not difficult to determine with a human eye that there is a thin spot in this group - the only connection between elements 6 and 8.
How to algorithmically search for such thin spots and divide groups?
Here is the original matrix from the example:
_ 0 1 0 0 0 0 0 0
0 _ 1 0 0 1 0 0 0
1 1 _ 0 0 1 0 0 0
0 0 0 _ 1 0 1 1 0
0 0 0 1 _ 0 0 1 0
0 1 1 0 0 _ 0 1 0
0 0 0 1 0 0 _ 1 0
0 0 0 1 1 1 1 _ 0
0 0 0 0 0 0 0 0 _
Any materials in Russian or in programming languages ​​will be welcome.

I will add that you do not need to remove element 1 from groupA, because the connection may be thin, but on this connection only one element is attached to the group and this connection will fully withstand it. A thin spot can also consist of several links if they connect subgroups with a large number of elements. And it is also desirable to consider a situation with weighted connections:


PS Discrete mathematics, etc. I haven't used it for a long time, I could confuse the terminology.

Answer 1

What you describe is very similar to the "graph partitioning" problem. en.wikipedia.org/wiki/Graph_partition
If you want to understand - look at the work of Gerorge Karypis. He is a living classic in the field and his Metis package is state of the art today. If you have a very large graph, then you can use the parallel version of ParMETIS. There is also a Zoltan package developed as part of the Trilinos project at Sandia National Lab. It is notable for the fact that it uses a hypergraph approach, which gives the best (in theory) quality of the partition. However, they have obvious performance problems, and the assembly of Trilinos is still a pleasure. In general, for a more detailed analysis, you need to know what kind of graph you have: the characteristic dimensions and the degree of connectivity (i.e., the connectivity matrix is ​​full).
Good luck...
PS I have a poor command of Russian terminology, so I apologize in advance for the anglicisms ...

Answer 2

Maybe you need to find the minimum balanced cut? As an option, it can be formulated as follows: divide the vertices of the graph into two parts of equal size so that the number of edges between them is minimal.
There's something here: theory.stanford.edu/ ~trevisan/cs359g/

Answer 3

Maybe this will help?
And if the graph is weighted, then the use of the flow problem is probably suitable

Answer 4

Isn't this cluster analysis? (see the same wikipedia)