Hubiness, length, crossings and their relationships in dependency trees

Abstract

Here tree dependency structures are studied from three different perspectives: their degree variance (hubiness), the mean dependency length and the number of dependency crossings. Bounds that reveal pairwise dependencies among these three metrics are derived. Hubiness (the variance of degrees) plays a central role: the mean dependency length is bounded below by hubiness while the number of crossings is bounded above by hubiness. Our findings suggest that the online memory cost of a sentence might be determined not just by the ordering of words but also by the hubiness of the underlying structure. The 2nd moment of degree plays a crucial role that is reminiscent of its role in large complex networks.

The upper bound for for the number of crossings has been improved

Cited by in corpus (11)

• Networks in Cognitive Science
• The placement of the head that minimizes online memory: a complex systems approach
• Are crossing dependencies really scarce?
• Memory limitations are hidden in grammar
• Crossings as a side effect of dependency lengths
• The sum of edge lengths in random linear arrangements
• Bounds of the sum of edge lengths in linear arrangements of trees
• Edge crossings in random linear arrangements
• Linear-time calculation of the expected sum of edge lengths in random projective linearizations of trees
• The optimal placement of the head in the noun phrase. The case of demonstrative, numeral, adjective and noun
• The Maximum Linear Arrangement Problem for trees under projectivity and planarity