2
$\begingroup$

Given a particular undirected graph with n nodes, is there an index that would characterize the vulnerability of each of the nodes? By vulnerability I mean the susceptibility of the graph to fragmentation.

Let's say that I remove a particular node i which results in the graph being fragmented into five parts; and when I remove node j it results in the graph being fragmented into two parts (and there would be nodes which would not fragment the graph)...is there an index which gives me this information for all the nodes?

The goal of the above is to identify vulnerable nodes in a graph (made from healthy subjects) and look at node properties of these nodes in another graph (made from patients suffering from various medical conditions).

For the sake of completeness, my nodes are representatives of different brain regions and the edges between these nodes represent correlation coefficient between some form of time series from each of these brain regions. However, the problem can be generalized to other contexts (the "key player" problem in graph theory...identifying key people in a social network, for example).

$\endgroup$
  • 1
    $\begingroup$ There are metrics for identifying cut-sets. Moody and White's algorithm was intended for graph level metrics, but nodes in leaves farther down are less vulnerable. If you start from there, how many separate connected components in the next stage down would be the fragmentation, and the those at further down levels would be less vulnerable. $\endgroup$ – Andy W Mar 8 '16 at 12:48
  • 1
    $\begingroup$ You may just find the cut-set's though for the entire graph, and then count up the separate components when they are removed compared to the whole graph, that is pretty simple. $\endgroup$ – Andy W Mar 8 '16 at 12:49
4
$\begingroup$

I think you should have a look at the block-cut tree of our graph. The number of biconnected components a node is contained in is exactly the number of fragments the graph decomposes into when this node is removed. Or, put differently, your index is the degree of that node in the block-cut tree.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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