Graph Metrics

Graph or structural metrics calculate the structure of ontologies.

Cardinality

Cardinality is a property of graphs which expresses a graph related number of specific elements.

Absolute root cardinality

Absolute root cardinality is a property of a directed graph which represents the number of root nodes of the graph.

 $m = n_{ROO \subseteq g}$

$n_{ROO \subseteq g}$ is the cardinality of the set $ROO$ in the directed graph $g$.

Absolute leaf cardinality

Absolute root cardinality is a property of a directed graph which is related to leaf node sets and represents the number of leaf nodes of the graph.

 $m = n_{LEA \subseteq g}$

$n_{LEA \subseteq g}$ is the cardinality of the set $LEA$ in the directed graph $g$.

Absolute sibling cardinality

Absolute root cardinality is a property of a directed graph which is related to sibling node sets and represents the number of sibling nodes of the graph.

 $\sum_{j}^{SIB} N_{j \in SIB}$

$N_{j \in SIB}$ is the cardinality of a sibling set $j$ from $SIB$ in the graph $g$.

Depth

Depth is a property of graphs which is related to cardinality of paths existing in the graph. The arcs which are considered are only subClassOf (isa) arcs but this only applies to directed graphs.

Absolute depth

The value of the absolute depth is calculated as follows:

 $m = \sum_{j}^P N_{j \in P}$

$N_{j \in P}$ is the cardinality of each path $j$ from the set of paths $P$ in a graph $g$.

Average depth

The average depth states at which degree the ontology has a vertical modelling of hierarchies.

 $m = \frac{1}{n_{P \subseteq g}} \sum_{j}^P N_{j \in P}$

$N_{j \in P}$ is the cardinality of each path $j$ from the set of paths $P$ in a graph $g$ and $n_{P \subseteq g}$ is the cardinality of $P$.

Maximal depth

The height of a graph is its maximal depth and it is the result of the following:

 $m = N_{j \in P}
  \forall i \exists j (N_{j \in P} \geq N_{i \in P})$

$N_{i \in P}$ and $N_{j \in P}$ is the cardinality of each path $j$ from the set of paths $P$ in a graph $g$.

Breadth

Here are again only subClassOf (isa) arcs considered to get a property called breadth which is related to the cardinality of levels, so-called generations, in a directed graph.

Absolute breadth

The value of the absolute breadth is calculated as follows:

 $m = \sum_{j}^L N_{j \in L}$

$N_{j \in L}$ is the cardinality of each level/generation $j$ from the set of generations $L$ in a directed graph $g$.

Average breadth

The average breadth states at which degree the ontology has a horizontal modelling of hierarchies.

 $m = \frac{1}{n_{L \subseteq g}} \sum_{j}^L N_{j \in L}$

$N_{j \in L}$ is the cardinality of each generation $j$ from the set of generations $L$ in a directed graph $g$ and $n_{L \subseteq g}$ is the cardinality of $L$.

Maximal breadth

The maximal breadth of a directed graph is calculated the following way:

 $m = N_{j \in L}
  \forall i \exists j (N_{j \in L} \geq N_{i \in L})$

$N_{i \in L}$ and $N_{j \in L}$ is the cardinality of each generation $j$ from the set of generations $L$ in a graph $g$.

Fan-outness

Fan-outness is related to the “dispersion” of graph nodes. The arcs considered for this property are again subClassOf (isa) arcs. There are two different measures which can be distinguished: those which are related to leaf node set, like the following ratio of leaf fan-outness, and those which are related to sibling node sets ("internal dispersion"), like the following ratio of sibling fan-outness.

Ratio of leaf fan-outness

The ratio of leaf fan-outness is the result of the absolute leaf cardinality divided by the cardinality of the graph.

 $m = \frac{n_{LEA} \subseteq g}{n_G}$

$n_{LEA} \subseteq g$ is the cardinality of the set $LEA$ in a directed graph $g$ and $n_G$ is the cardinality of $G$.

Ratio of sibling fan-outness

The ratio of sibling fan-outness is the result of the absolute sibling cardinality divided by the cardinality of the graph.

 $m = \frac{\sum_{j}^{SIB} N_{j \in SIB}}{n_G}$

$\sum_{j}^{SIB} N_{j \in SIB}$ is the absolute sibling cardinality for the directed graph $g$ and $n_G$ is the cardinality of $G$.

Tangledness

Tangledness is related to the multihierarchical nodes of a graph, where the arcs considered here are again only subClassOf (isa) arcs and the measure again only applies to directed graphs. The tangledness of a class tree is subject of multiple hierarchy knots of a graph. It means, that this knot has more than one incoming edge. This is the formula for this measurement:

 $m = \frac{n_G}{t_{\in G \wedge \exists a_1 ,a_2 (isa(m,a_1 )\wedge (isa(m,a_2)))}}$

$n_G$ is the cardinality of $G$ and $t_{\in G \wedge \exists a_1 ,a_2 (isa(m,a_1 )\wedge (isa(m,a_2)))}$ is the cardinality of the set of nodes with more than one ingoing subClassOf (isa) arc in $g$.

Total number of paths

The total number of paths is the sum of distinct paths which exists in (set of) graphs where each path start at a root node and ends at a leaf node.

 $m = n_{DP \subseteq g}$

$n_{DP \subseteq g}$ is the cardinality of the set $DP$ in the directed graph $g$.

Average number of paths

The average number of paths is the quotient of the total number of distinct paths and the number of graphs.

 $m = \frac{n_{DP \subseteq g}}{j}$

$n_{DP \subseteq g}$ is the cardinality of the set $DP$ in the directed graphs $g$ and the number of graphs $j$.

Sources

1. Aldo Gangemi, Carola Catenacci, Massimiliano Ciaramita, Jos Lehmann:
   Ontology evaluation and validation - An integrated formal model for the quality diagnostic task
   September 2005 , pp 11-16.
   http://www.loa.istc.cnr.it/old/Files/OntoEval4OntoDev_Final.pdf