*****  To join INSNA, visit  *****

On 3 Oct 2005, at 13:12, Ken Cousins wrote:

> *****  To join INSNA, visit  *****
> I apologize for what I'm sure is a trivial question, but I'm
> stumped. I
> have a number of acyclical digraphs (representing hierarchies), which
> often have multiple paths between the uppermost (originating) and
> terminal nodes.
> I am comparing these graphs according to the longest path in each
> (i.e., "slack" in the chain of command), but have not been able to
> find
> a metric that fits this exact problem. Since I'm sure this can't be
> the
> first time this question has come up, I turn to the SOCNET
> community for
> guidance.
> What is the correct terminology for such a metric?

Just making sure we're on the same page: it sounds like what you're
asking for is the term for the length of the longest path between any
"source" of the digraph (corresponding to an individual with no
supervisors) and any "sink" (an individual who does not supervise

In the terminology of graph theory, the height of a tree (minimally
connected acyclic digraph) is defined to be the maximum over all
nodes' depths (path length between the root and the node).  While a
tree is a special case of an acyclic digraph, I'd say that the term
"height" would be reasonably appropriate for acyclic digraphs in
general as well (at least in the sense that people will probably
understand what you mean if you use the term).

Hope this helps--

Joshua Per
Joshua O'Madadhain: Information Scientist, Musician, and Philosopher-
   It's that moment of dawning comprehension that I live for--Bill
   My opinions are too rational and insightful to be those of any

SOCNET is a service of INSNA, the professional association for social
network researchers ( To unsubscribe, send
an email message to [log in to unmask] containing the line
UNSUBSCRIBE SOCNET in the body of the message.