I have a digraph that represents a taxonomy of sorts, where nodes are "concepts" (i.e., person, animal, plant, etc) and the edges represent an is-a relationship. Hence, we can have dog -> animal, for example.

The problem is the graph is not actually a taxonomy, in the sense that is not a tree. Sometimes the is-a relation is symmetric, and sometimes there are larger cycles.

I want to build an approximated tree that I can use as a taxonomy. Of course this involves dropping some of the edges. My idea is to use some network metric that defines an "importance" for nodes and ignore all edges that go from more "important" to less "important" nodes. So far I have considered betweenness and load centrality metrics.

My question is regarding what metric is better for this. I know this is a subjective question, and the response can only be approximated, so I would consider different possibilities. I think the "ideal" metric is such that nodes in which more paths end are ranked higher (they would be "parents" of more concepts). In the extreme case, for an actual tree, such a metric should rank the nodes according to their height in the tree.

NOTE: Just for additional background information, the graph is a subset of the ConceptNet semantic network, using only the IsA.


Your Answer

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

Browse other questions tagged or ask your own question.