Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to derive a taxonomy from sparse "is-a" relationships and am looking for a linear algebraic solution.

More specifically, the data is noisy and I want to detect relations that violate anti-transitivity, remove the least offenders, and then fill-in the transitive relationships, inheriting all relations from parents to children.

Is anyone aware of mathematical methods to:

  1. compute a general statistic of "transitivity" of some graph matrix?
  2. compute a matrix of relations in violation of anti-transitivity?

I could remove the offending rows from (2) and see how they affect (1). Then, I could compute transitive closure, which I already know how to do [1].

[1] http://www.cs.nmsu.edu/~ipivkina/TransClosure/index.html Warning: contains god-forsaken Java Applet.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

I think what you're looking for is "transitive reduction", which gives the smallest relation whose transitive closure is the same as the transitive closure of the given relation.

And this makes me think, why even bother with the transitive reduction when you can just take the transitive closure to begin with...that is, why worry about the 'noise' and just add in all the missing transitive arcs.

If your noise is such that you have -cycles-... well, that's a whole nother problem (how do you know which edge is the 'bad' one?)


From the comments, I'm adding to my answer. I think the question really is something like this:

"Given a directed acyclic graph plus some additional edges (which may induce cycles), return some kind of poset (a transitive directed acyclic graph)".

Once the cycles are broken, one can then take a transitive closure (algebraically, as you like by $A^* = I + A + A^2 + ... + A^n = (I - A)^{-1}$ (OK, I threw in reflexive there too).

Now the difficulty is to get rid of the cycles. There is no way to know which ones are spurious, so you have to arbitrarily throw away edges to get rid of cycles. A naive approach would be to DFS repeatedly (this isn't particularly algebraic), removing the edge on which a cycle is recognized, until no more cycles are found. This isn't particularly elegant because it may remove more edges than necessary (to induce acyclicity).

The next idea is to try to get rid of the -fewest- edges possible, which off the top of my head sounds so very NP-complete that I wouldn't bother (can somebody confirm or not?).

When that happens, we can take off the theoretician hat and just be practical...how many spurious edges do you expect? If very few, I'd say go with the DFS approach, there won't be many intertwining cycles.

You may be concerned that such a thing will result in a taxonomy that is not ... right. Say, a dog is an animal is a beagle (you wanted the algorithm to throw out the spurious 'an animal is a beagle' and not 'a beagle is a dog'). But if your algorithm is to be anonymous, it can't (it's not possible to) know which is the best edge to remove (in a cycle, no edge is distinguished). That is, the bad example I gave is unavoidable in a general setting.

PS: since we moved to dealing with cycles rather than transitivity (since any acyclic graph has an acyclic transitive closure), I realize now that an appropriate 'statistic' might by 'girth', the length of the largest cycle (with an acyclic graph having infinite girth). And ...I don't know of a fractional analog to girth. See Scheinerman, Fractional Graph Theory for ideas.

PPS: I'm sure there are heuristics that might help choose bad edges (edges that you want to remove), for example, to make the hierarchy more ... pyramidal... try to minimize the number of 'top' nodes (nodes with no in-edges) or try to maximize the number of descendants of these top nodes. This might be expensive (for each edge in a cycle, compute descendants for everybody, then compare these results and pick the best one).

share|improve this answer
    
Thanks for the information. Yes, the data does have cycles, which is why I was wondering if there's a global "score" for the anti/transitivity. If xRy and yRx, I could use the score to remove the relation that was most consistent with the overall transitivity. –  trope Feb 24 '11 at 3:44
    
I'm going to be a bit intrusive and say that you really shouldn't want a 'measure' of how transitive a graph is. A graph is either transitive or it is not (all it takes is one edge to prevent it). There might be a fractional version of this 0-1 property (sort of like fractional chromaticity) but I'm not fluent enough with that to come up with a meaningful fractional-transitive property. Instead I think you want to get rid of cycles (in a directed graph). Then you can take a transitive closure to get the 'is-a' poset. I'm editing my answer to reflect this. –  Mitch Feb 28 '11 at 4:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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