<p>There are loads of measures of nodes in a DAG you could use.  For example:</p>

<ul>
<li><p>How much the removal of node $v$ reduces the max flow from sources to sinks</p></li>
<li><p>the <a href="http://en.wikipedia.org/wiki/Centrality#Betweenness_centrality" rel="nofollow">betweenness centrality</a> of $v$</p></li>
<li><p>the in-degree of $v$ times the out-degree of $v$</p></li>
</ul>

<p>The question should not be <em>if</em> there is a measure, but rather which measure is most appropriate.  That depends on the problem you're trying to solve.</p>

CC BY-SA 3.0
2011-08-04T11:58:54.777Z
2011-08-04T11:58:54.777Z
James King
<p>Recently, I want to devise some kernelization (in the framework of parameterized complexity) for problem on DAG. So, find a proper parameter is essential.
Well, is there a measure for the importance of a node (like the cut vertex in undirected graph)? or how separated the DAG is? May be after small amount of edge deletion (or node deletion) the DAG was decomposed into separated components (Better if the components have similar cardinality)?</p>

CC BY-SA 3.0
2011-08-04T08:00:29.177Z
What you describe sounds to me like graph connectivity ( http://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29 ). However I know only of connectivities that are label-agnostic, i.e. it doesn't matter which edges or nodes participate in the cut.
chazisop
CC BY-SA 3.0
2011-08-04T08:31:46.510Z
Not like that. node connectivity or edge connectivity does not grab the property of DAG as I think.
Peng Zhang
CC BY-SA 3.0
2011-08-05T00:59:25.770Z
Dominator analysis: not a measure but one view of what important nodes are. Look up tree-width, which is how far a graph is from being a tree.
Vijay D
CC BY-SA 4.0
2021-09-21T16:12:47.503Z
Pagerank would certainly make a good candidate, and I asked a related question here: https://cstheory.stackexchange.com/questions/50507/pagerank-in-directed-acyclic-graphs-dag
Matthieu Latapy
<graph-theory><directed-acyclic-graph><parameterized-complexity><measure-theory>
measures for a DAG (directed acyclic graph)?
Peng Zhang
# measures for a DAG (directed acyclic graph)?

(Asked by: username_0 on 2011-08-04)

Recently, I want to devise some kernelization (in the framework of parameterized complexity) for problem on DAG. So, find a proper parameter is essential.
Well, is there a measure for the importance of a node (like the cut vertex in undirected graph)? or how separated the DAG is? May be after small amount of edge deletion (or node deletion) the DAG was decomposed into separated components (Better if the components have similar cardinality)?

**Tags:** graph-theory, directed-acyclic-graph, parameterized-complexity, measure-theory

> **Comments:**
> **username_1**: What you describe sounds to me like graph connectivity ( http://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29 ). However I know only of connectivities that are label-agnostic, i.e. it doesn't matter which edges or nodes participate in the cut.  
> **username_0**: Not like that. node connectivity or edge connectivity does not grab the property of DAG as I think.  
> **username_2**: Dominator analysis: not a measure but one view of what important nodes are. Look up tree-width, which is how far a graph is from being a tree.  
> **username_3**: Pagerank would certainly make a good candidate, and I asked a related question here: https://cstheory.stackexchange.com/questions/50507/pagerank-in-directed-acyclic-graphs-dag  

---

## 1 answers

### Answer by username_4 on 2011-08-04. Score: 7

There are loads of measures of nodes in a DAG you could use. For example:

* How much the removal of node $v$ reduces the max flow from sources to sinks
* the [betweenness centrality](http://en.wikipedia.org/wiki/Centrality#Betweenness_centrality) of $v$
* the in-degree of $v$ times the out-degree of $v$

The question should not be *if* there is a measure, but rather which measure is most appropriate. That depends on the problem you're trying to solve.


---

