Time evolution of the hierarchical networks between PubMed MeSH terms

Abstract

Hierarchical organisation is a prevalent feature of many complex networks appearing in nature and society. A relating interesting, yet less studied question is how does a hierarchical network evolve over time? Here we take a data driven approach and examine the time evolution of the network between the Medical Subject Headings (MeSH) provided by the National Center for Biotechnology Information (NCBI, part of the U. S. National Library of Medicine). The network between the MeSH terms is organised into 16 different, yearly updated hierarchies such as "Anatomy", "Diseases", "Chemicals and Drugs", etc. The natural representation of these hierarchies is given by directed acyclic graphs, composed of links pointing from nodes higher in the hierarchy towards nodes in lower levels. Due to the yearly updates, the structure of these networks is subject to constant evolution: new MeSH terms can appear, terms becoming obsolete can be deleted or be merged with other terms, and also already existing parts of the network may be rewired. We examine various statistical properties of the time evolution, with a special focus on the attachment and detachment mechanisms of the links, and find a few general features that are characteristic for all MeSH hierarchies. According to the results, the hierarchies investigated display an interesting interplay between non-uniform preference with respect to multiple different topological and hierarchical properties.

Fig 1. Changes between subsequent time steps in a MeSH hierarchy.

a) A small part of the hierarchy ‘A’ (Anatomy) in 2002. Red links are deleted in the next time step b) The corresponding part of the same hierarchy in 2003. Nodes and links colored red are newly appearing elements.

Fig 2. Testing W(x) by simulated attachments.

The property x here corresponds to the number of children, and the full symbols connected by continuous lines show the measured W(x) for random attachment (independent of x) in orange (circles), and for preferential attachment with an additive constant (i.e. when a newly added node connects to node i with a probability $\frac{k_i+a}{{\sum }_i{k}_i+a}$ where a is an arbitrary constant) in blue (squares). Dashed lines correspond to the analytic mean for W(x), whereas the shaded areas indicate the standard deviation around the mean.

Fig 3. Measuring preference in attachment and detachment events.

In each panel we compare W_emp(x) defined in (8) to the mean and standard deviation of W(x) for random events, given in (9 and 10) and indicated by dashed lines in shaded areas. The pictograms beside the panels show the type of the studied attachment/detachment events and highlight in red whether the given property x was measured on the source or on the target of the links involved in the events. a) Results for the total number of descendants of source nodes in attachments of new links pointing from old nodes to new nodes in hierarchies D (orange) and C (blue). b) W_emp(x) for the number of ancestors of source nodes on new links appearing between old nodes, measured in hierarchies D (orange) and C (blue). c) The same plots when x is equal to the number of ancestors of the target nodes in link deletion events for hierarchies D (orange) and C (blue). d) W_emp(x) in case x is corresponding to the number of ancestors of the target node in attachment of new links between old nodes.