Applications of random walks for the analysis of graphs, musical compositions and language phylogeny

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review


Random walks provide us with a powerful tool for studying the structure of graphs and databases in details. We analyze the structure of undirected graphs by random walks. We have analyzed transition matrices aggregated for the MIDI representations of 804 pieces of classical music written by 29 composers. The successful understanding of tonal music calls for an experienced listener, as entropy- contrary to human languages - dominates over information redundancy, in classical music. Large pieces of tonal music might contain just a few types of melodic lines translated over the entire diapason of pitches by chromatic transposition as complexity typically decreases rapidly with the number of pitches used in a classical composition. The maximum complexity is achieved on the blocks consisting of just a few notes (8 notes, for the musical dice games generated over Bach's compositions). First passage times to notes in musical scores can be used to reliably resolve tonality of a piece and feature a composer. A Markov chain analysis of a network generated by the matrix of lexical distances allows for representing complex relationships between different languages in a language family geometrically, in terms of distances and angles. The fully automated method for construction of language taxonomy is tested on a sample of fifty languages of the Indo-European language group and applied to a sample of fifty languages of the Austronesian language group. The Anatolian and Kurgan hypotheses of the Indo- European origin and the 'express train' model of the Polynesian origin are thoroughly discussed.

Original languageEnglish
Title of host publicationStatistical Mechanics and Random Walks
Subtitle of host publicationPrinciples, Processes and Applications
PublisherNova Science Publishers, Inc.
Number of pages66
ISBN (Print)9781614709664
StatePublished - Jan 2013


Dive into the research topics of 'Applications of random walks for the analysis of graphs, musical compositions and language phylogeny'. Together they form a unique fingerprint.

Cite this