Re: Co-optation Today

John Harshman wrote:
Rusty Sites wrote:
John Harshman wrote:
Rusty Sites wrote:
John Harshman wrote:
Rusty Sites wrote:
John Harshman wrote:
Rusty Sites wrote:
John Harshman wrote:
Rusty Sites wrote:
John Harshman wrote:
Rusty Sites wrote:
John Harshman wrote:
Rusty Sites wrote:
John Harshman wrote:
Rusty Sites wrote:
John Harshman wrote:
Rusty Sites wrote:
John Harshman wrote:
r norman wrote:

In other words, every tree can be interpreted to be a nested
hierarchy. You have to do the same with phylogenetic trees. The
nesting requires that a node be associated not only with the species
that occupies that node but with the clade descended from that
species.

I agree. Every tree *can be interpreted* as a nested hierarchy. Or it could be interpreted as a non-nested hierarchy. That's why I say that a tree is a representation of the hierarchy, not the hierarchy itself. This is not a big deal. But a nested hierarchy is best understood and defined in terms of sets, not trees. And of course a natural nested hierarchy is best *explained* by a tree.


Well trees can be defined in terms of sets. From Donald Knuth

A finite set T of one or more nodes such that:

1. there is one specially designated node called the root of the tree, root(T); and
2. the remaining nodes (excluding the root) are partitioned into
m >= 0 disjoint sets T1, ..., Tm, and each of these sets in
turn is a tree. The trees T1, ..., Tm are called the subtrees
of the root.

I think this is properly called a rooted tree.

A rooted tree can be represented as

{a, {b, {c, d}}, {e, f}}

which is a nested hierarchy of sets. I don't see how it could be interpreted as a non-nested hierarchy.

A tree is just a graph. That graph can be interpreted as you like. I gave an example of a tree interpreted as a non-nested hierarchy. Now it's true that any rooted tree can be interpreted as only one nested hierarchy in which its terminal nodes, but not its internal nodes, are elements, but there is no a priori reason why you have to interpret the tree that way. To put it another way, every nested hierarchy implies a tree, but a tree doesn't imply anything; it's just a topological figure.


I am not sure how you are using graph, but in the mathematical sense a tree is a special case of a graph. Every tree is a graph, but not every graph is a tree. In the most general definition of a tree, there is no specified root node, so there is not a one to one correspondence to a nested hierarchy. (At least, a root has to be specified to construct a nested hierarchy) A rooted tree (which is commonly what people think of when they speak of trees) does have a specified root so it avoids the problem. Your definition of nested hierarchy,

I agree that a nested hierarchy can be described using a rooted tree, and that each nested hierarchy corresponds to exactly one rooted tree. By "graph" I meant a figure composed of branches and nodes, each node connecting either 3 or more branches or being at the end of only one branch. In systematics, a tree is a graph in which there is one and only one path between any pair of nodes. A rooted tree is a tree in which a point on one of the branches has been designated the root node. Terminology in mathematics may be different.

From ancient memory, a graph is a set of nodes with at most one arc from one node to another. That would include cases where there is no path from some nodes to other nodes. A connected graph adds the requirement that there be at least one path between any two nodes. I am sure that the correct definition, if I am not giving it, is different than that which you stated.

Sorry, I got ahead of myself. I meant merely to say that a graph was a figure of branches and nodes. Your requirement eliminates redundant branches, which sounds good. Now if I recall a tree is called an acyclic connected graph, which means that there is no path from a node back to the same node without retracing steps. And a rooted tree adds a direction to each branch, i.e. away from the root. In systematics at least, you are not allowed to have a node connecting only two branches, except for the root node. And we don't generally consider the root to be a real node.

Here: a nested hierarchy is a set of groups in which each group has one of two relationships with each other group; either the two groups are wholly disjunct, or one group is entirely included within the other. Partially overlapping groups are right out. Phylogenies can further be described as natural nested hierarchies: only one hierarchical arrangement of groups will work.

is, I believe entirely equivalent to the definition given for a rooted tree if a common ancestor of all members of the hierarchy is included. Otherwise, a nested hierarchy might contain no root node. It would then be a set of rooted trees. The groups in your definition translate to subtrees. Given two subtrees, they are either disjoint or one contains the other.

Well, in practice we never have a common ancestor. Instead we designate some particular branch as containing the root node, because of information extraneous to the tree itself. But a tree described as nested sets wouldn't seem to need an element identified as the ancestor. Why, mathematically, is a common ancestor needed? It would seem to be a superfluous member of the set, since the first division of the set defines a root.

I think {{a, b}, {c, d}} would represent a nested hierarchy, but no tree could be constructed from it without an implied root node.

But there is an implied root node (at least in systematics); the root must be between {a,b} and {c,d}. If the root were elsewhere those two subsets would not exist. There are 15 possible rooted trees with those four elements, but all others would have different subsets. For example, the tree {a,{b, {c,d}}} has an implied root between a and the rest.


Now I realize that my set notation for trees doesn't work. There is no place to put a root. I know there is such a notation, but without a current ACM or IEEE membership, I can't look at the papers I found that seem to address the issue online. Anyway, when I said "if a common ancestor of all members of the hierarchy was included", I was thinking of an implied node like the ancestor of all life, not necessarily an actual ancestor.

Right, but I don't see why you need any explicit representation of the root. Given that set notation, which works just fine (and is the notation used by systematists), there is only one possible place for the root to be. So what's the problem?


No practical problem, but I said there was a one to one correspondence between the set notation and trees, but that's not true unless the set notation is augmented to include a root. In your case, it isn't necessary because the root doesn't require any value. In general, it does.

Wouldn't your notation work in that case? If you want x to be the root, you can easily have the set {x, {a,b},{c,d}}. But I suppose there needs to be some kind of explicit notation for the root, because I could also interpret this as a trichotomy, with x a terminal node at the end of some branch. In phylogenetics, the root can't have a value, because there is no way to estimate states at the root node. And we can know that the root is somewhere along a particular branch, but we can't say where along that branch.


I suppose the cleanest way is to say a nested hierarchy is equivalent to an unordered forest of rooted trees.

No, it's equivalent to exactly one rooted tree. There are many rooted trees compatible with one unrooted tree. 2N-3 of them, to be exact, where N is the number of terminal nodes.

Why have a root with no value?

Because the only purpose of the root is to determine the direcction of time on the tree and thus the identities of clades. Sure, it might be nice to have something to say about the root, but there is no way to estimate its nature, except that it probably shares all the characteristics shared by each of its two immediate descendants. When the two descendants are different, there is no way to tell which is the root state.

If you really must draw one, I suppose it's ok. Forest is actually a mathematical term but unordered forest might be a non-sequiter. So I guess you were right. A nested hierarchy isn't exactly the same as a tree.

I relish the victory, but I have no idea how it was achieved, and I disagree with the statements you make in support of me being right. What's up with that?

Ok, forget the last post. You only have values for the leaves, so all the other nodes are implied by grouping. So it is a special kind of tree, one with values only for the leaves. I don't know if that is a victory for you or not.

I don't understand how you would use set notation to describe the kind of tree you're talking about, since only the terminal nodes are identified as elements. The internal nodes are only implied as patterns of parentheses.


I have been caught somewhere between trees as a useful data structure and trees in the abstract. In its bare essence, a tree is nothing but nodes and arcs. It has no values associated with it. I don't think a nested hierarchy can exist even in the abstract with no values. Otherwise, there is nothing to distinguish one member from another. The meaning of nested hierarchy in set notation is obvious. Allow nested sets and don't let any member appear twice. There is also a very obvious translation between nested hierarchies and trees with values associated with the leaf nodes. So nested hierarchies are equivalent to trees with values associated with their leaves. That's my final answer.

Sounds reasonable, if by "value" you mean only some kind of label, and if by "leaf" you refer to a branch with one end free (i.e. a node with only one branch connected to it, a terminal node).

Yes except one such node is the root, the rest are leaves.

Actually, I misspoke. I should have said one such node *could* be the root. In fact, any node in a tree can be chosen as the root.

It would be my hope that the root would have at least two branches connected to it.

Differences in terminology for the same thing between mathematics and systematics can be confusing,


I realized that the messages on this newsgroup form a nested hierarchy.

I would call it a non-nested hierarchy, since no message is part of another message. Both nested and non-nested hierarchies correspond to trees.

I was really only considering the ID's and group name as the message.

Every message contains a unique ID and the newsgroup on which it was posted. It also contains a reference string. When a message starts a new thread, its reference string is null. Each time a message is posted in response to another message, the reference string of the new message is formed by appending the message ID of the previous message to the reference string of the previous message. Each message ID in the reference string is a characteristic or attribute. All messages in a subthread have reference strings that begin with the same substring. Because ID's are unique, none of the individual ID's in that substring appear anywhere outside that subthread. Obviously, a newsgroup reader is able to construct a tree from the nested hierarchy. The root is actually outside the display of the newsgroup messages in the newsreaders I am familiar with. I am not very familiar with nntp, but I am pretty sure that the readers use the information in the reference strings and the newsgroup field of the headers to construct the trees.

Makes sense to me. Note that this tree (I suppose you can call it a nested hierarchy if you really want to) arises from a process of descent with modification and branching. In this case the modification is purely additive and very simple.

Interestingly, this tree can't be represented by set notation. If the reference string and the ID of each message are considered as the characteristics of each message, the tree could be reconstructed from the leaves, however. All nodes that differ in just one characteristic are descended from a node that had just the characteristics that these nodes have in common. Maybe that is cheating. By the definition you gave for a nested hierarchy, all the messages on the newsgroup really don't represent a nested hierarchy because they can't be represented as a set of groups, but the leaf messages do.

.

Relevant Pages

  • Re: Co-optation Today
    ... hierarchy. ... hierarchy is best *explained* by a tree. ... of the root. ... which is a nested hierarchy of sets. ...
    (talk.origins)
  • Re: Co-optation Today
    ... hierarchy. ... But a nested hierarchy is best understood and defined in ... hierarchy is best *explained* by a tree. ... definition of a tree, there is no specified root node, so there ...
    (talk.origins)
  • Re: Co-optation Today
    ... hierarchy. ... But a nested hierarchy is best understood and defined in ... hierarchy is best *explained* by a tree. ... definition of a tree, there is no specified root node, so there ...
    (talk.origins)
  • Re: Co-optation Today
    ... hierarchy. ... But a nested hierarchy is best understood and defined in ... hierarchy is best *explained* by a tree. ... definition of a tree, there is no specified root node, so there ...
    (talk.origins)
  • Re: Co-optation Today
    ... hierarchy. ... That's why I say that a tree is a representation of the hierarchy, ... But a nested hierarchy is best understood and defined in terms of sets, ... of the root. ...
    (talk.origins)