Information Technology Reference
In-Depth Information
Chapter 7
Exploring Hierarchies Using the DAGMap
Pierre-Yves Koenig
7.1
Introduction
Hierarchical data appears naturally in many applications. In their simplest form,
hierarchies are trees. Tree structures, such as classifications (for instance, ge-
olocalization classifies continent, country, states or region), phylogenetic trees,
and company organization charts, are but a few examples. In richer hierarchical
organizations, cross links allow elements to belong to several non-distinct classes.
Inheritance relations of classes in object oriented programming is a typical exam-
ple. Classifying concepts extracted from documents, for instance, can sometimes
require concepts to be “duplicated”, depending on the possible interpretations. The
“network” concept, for example, can refer to both social network analysis and low
level computer hardware. Additionally, both concepts may be required to index a
collection of documents. Such a classification naturally leads to the construction of
a directed acyclic graph (a
DAG
).
In a DAG, nodes are ordered using
ancestor
/
child relationships
just as with trees,
with the exception that nodes may have multiple parents. Nodes without ancestors
are called
source
nodes, while those without any children are called
sinks
.
The case study we shall explore in this chapter is made up of companies linked to
one another through subsidiary links, i.e., company
c
1
is linked to company
c
2
if
c
2
is a subsidiary of
c
1
. Clearly, this graph structure is a DAG: subsidiaries themselves
have subsidiaries and a subsidiary may be held by several “ancestor” companies.
The dataset also collects attributes measuring how much of a subsidiary is held
Search WWH ::
Custom Search