I have adjacency matrices which have nearly connected components. That is partitions with a dense number of edges between nodes in the same group and few edges acting as bridges between these groups. I have clustered them so that they form a band matrix.
What ways exist to identity these nodes linking groups? These nodes that act as bridges between these nearly connected components.
It appears that each method I have seen has some element of it being a heuristic in some way.
As i commented, you need to be more specific about the details. Here is an idea though which might work well if within groups there are lots (or at least a reasonable number of) triangles but no triangles involve bridges: Take the adjacency matrix $A.$ and compare it to $A^2.$ If the $u,v$ position is positive in both then the edge $uv$ is definitely not a bridge. So temporarily consider just these edges. They will split the graph into disjoint connected components which one hopes will be your blocks.
This will not work perfectly if some bridges are in triangles. It also won't work if the groups are complete bipartite graphs because there are then no triangle within a block. However you could look at powers of $A+I$ and the larger numbers should tend to be for vertices in the same group. Perhaps compute $M=(A+I)^k$ for $k=3$ or $4$, pick some cutoff value $v$ (maybe the median of the entries of $M$) and replace each entry $m_{ij}$ by $\lfloor\frac{m_{i,j}}{v}\rfloor$ (the integer quotient). Then multiply that by $A+I.$ The exact $k$ and $v$ might have to be tuned to your matrix. But a program could vary them until the final matrix has a sharp dichotomy of values indicating vertices in the same and different blocks.
I think that in this very special case you can get the answer just by computing a minimum cut. If the two subgraphs are really dense and the bridges between them are few, then the minimum cut will be just the set of bridges.
