1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ Do you mean nearly complete components. How big are they relative to the vertex set and how dense? Imagine a square grid with $n^2$ points and $2n$ lines. Make it into a graph where each vertex is on $2n-2$ edges. If you order the matrix by rows then you have a block matrix with each block complete and a vertex having only one bridge to each other block. But you could organize by columns and swap roles of bridge and non-bridge. $\endgroup$
    – Aaron Meyerowitz
    Feb 1, 2013 at 16:43

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.