most recent 30 from http://mathoverflow.net 2013-05-23T05:54:44Z http://mathoverflow.net/feeds/question/120522 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120522/how-to-identify-bridge-nodes-between-nearly-connected-graph-components-in-partiti Vass 2013-02-01T14:15:58Z 2013-02-01T20:13:51Z

<p>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. </p> <p>What ways exist to identity these nodes linking groups? These nodes that act as bridges between these nearly connected components.</p> <p>It appears that each method I have seen has some element of it being a heuristic in some way.</p>

http://mathoverflow.net/questions/120522/how-to-identify-bridge-nodes-between-nearly-connected-graph-components-in-partiti/120541#120541 Aaron Meyerowitz 2013-02-01T20:02:25Z 2013-02-01T20:02:25Z

<p>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.</p> <p>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. </p>

http://mathoverflow.net/questions/120522/how-to-identify-bridge-nodes-between-nearly-connected-graph-components-in-partiti/120542#120542 Felix Goldberg 2013-02-01T20:13:51Z 2013-02-01T20:13:51Z

<p>I think that in this very special case you can get the answer just by computing a <a href="http://en.wikipedia.org/wiki/Minimum_cut" rel="nofollow">minimum cut</a>. 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.</p>