capbtabboxtable[][]

# Automatic Stroke Classification of Tabla Accompaniment in Hindustani Vocal
Concert Audio

To appear in the JOURNAL OF ACOUSTICAL SOCIETY OF INDIA, April 2021

Rohit M. A. and Preeti Rao
Department of Electrical Engineering
Indian Institute of Technology Bombay, Mumbai, India
{rohitma<EMAIL_ADDRESS>
## ABSTRACT

The tabla is a unique percussion instrument due to the combined harmonic and
percussive nature of its timbre, and the contrasting harmonic frequency ranges
of its two drums. This allows a tabla player to uniquely emphasize parts of
the rhythmic cycle (theka) in order to mark the salient positions. An analysis
of the loudness dynamics and timing deviations at various cycle positions is
an important part of musicological studies on the expressivity in tabla
accompaniment. To achieve this at a corpus-level, and not restrict it to the
few recordings that manual annotation can afford, it is helpful to have access
to an automatic tabla transcription system. Although a few systems have been
built by training models on labeled tabla strokes, the achieved accuracy does
not necessarily carry over to unseen instruments. In this article, we report
our work towards building an instrument-independent stroke classification
system for accompaniment tabla based on the more easily available tabla solo
audio tracks. We present acoustic features that capture the distinctive
characteristics of tabla strokes and build an automatic system to predict the
label as one of a reduced, but musicologically motivated, target set of four
stroke categories. To address the lack of sufficient labeled training data, we
turn to common data augmentation methods and find the use of pitch-shifting
based augmentation to be most promising. We then analyse the important
features and highlight the problem of their instrument-dependence while
motivating the use of more task-specific data augmentation strategies to
improve the diversity of training data.

##  1 Introduction

Hindustani classical music is a genre of art music in India encompassing
several sub-genres and forms of presentation. Khyal, one of the more modern
forms, with roots in Dhrupad, consists of vocals as the lead, the harmonium
(or sometimes the saarangi) for melodic accompaniment, the tabla for
percussion accompaniment, and the tanpura in the background for the harmonic
drone [1]. The performance opens with a short unmetered raga improvisation
(alap) by the vocalist, performed to a mild accompaniment by the harmonium,
and is followed by the metered piece - the bandish, where the tabla also joins
in. For the most part, the melodic accompaniment shadows the vocals while the
tabla plays a fairly fixed cyclic pattern of beats called the ‘theka’ to
provide the rhythm.

The tabla is a pitched percussive membranophone, consisting of a pair of drums
called the bayan and dayan, or dagga and tabla, respectively. A unique
property of these drums that sets them apart from common percussion
instruments is their ability to produce ringing, pitched sounds. This is
facilitated by the additional metallic layer at the center of each drum’s
membrane. When struck freely, the bayan, bigger in size, produces bass
frequency sounds (F0111Fundamental frequency $\in$ 80-100 Hz), while the dayan
produces treble frequency sounds (F0 $\in$ 200-400 Hz). We therefore refer to
these drums as bass and treble in the remainder of this article. The treble
drum, tuned to the tonic note of the singing in a performance, is more
harmonic than the bass drum which evokes only a faint sense of pitch.

Due to the predominantly improvisatory nature of Hindustani music, and a lack
of precise performance-oriented theory, a greater emphasis has come to be
placed on the empirical analysis of performed concerts. While traditional
musicological studies would often be restricted to a few chosen concerts, the
advancement of computational methods has made it possible to analyse large
corpora. The focus of some of these studies has been to quantify aspects of
rhythm and tempo in khyal and instrumental music concerts from the perspective
of the percussion accompaniment, such as - stroke loudness dynamics and beat-
level timing deviations in the tabla playing [2], typical tempo ranges in
khyal performance and the variations in theka based on the chosen tempo [3],
and the possible interaction of this with the accompanied lead vocals or
melodic instrument. There is thus a large scope to help further such research
by making use of automatic tools for accurate tabla transcription to aid
large-scale analyses.

Supervised methods in machine learning achieve great success when provided
sufficient labeled data that is matched to the target domain. In the present
context, our target data, viz. tabla accompaniment from vocal concerts is
available as such only in specially created multi-track recordings where each
instrument is recorded with a separate microphone with sufficient physical
separation between the artists. Further, although musical source separation is
a rapidly developing area, there is no model currently available for the
Hindustani vocal concert context. So we develop our models on the more amply
available tabla solo, hoping to extend the trained models to accompaniment
tabla obtained from multi-track recordings or possibly future source
separation techniques. In the next section, we review the previous work in
tabla stroke classification. We then present our problem and dataset, followed
by a discussion of our method and a critical evaluation of its performance on
our test data.

##  2 Background

The approach to transcribing tabla most commonly found in literature is one
where segments of individual strokes are first represented using low-level
audio features and then classified into one of a set of 10 - 15 bols [4, 5, 6,
7, 8, 9]. The stroke segments are obtained either by extracting them from a
sequence of tabla strokes using a separate segmentation method [4, 5, 8], or
by building a dataset of individual strokes recorded in isolation [6, 9]. The
various systems reported so far can be compared via the following aspects -
the set of features used to characterize strokes, the models used for
classification, the nature and diversity of the dataset, and the evaluation
methods.

There is not a significant difference in the choice of features, with a
majority of the previous methods employing a similar set of somewhat generic
timbral descriptors such as Mel-Frequency Cepstral Coefficients (MFCC),
spectral distribution features like the spectral centroid, skewness, and
kurtosis, Linear Prediction Coefficients (LPC), and temporal features like the
zero crossing rate, temporal centroid, and attack time. A dimensionality
reduction step has been additionally used to select the most important subset
of these features [5, 6]. However, while it would appear, from the fairly high
classification accuracies reported, that these common low-level timbre
descriptors are well-suited to the task, it is important to note that these
descriptors tend to also depend on the physical characteristics of the tabla
and differences in stroke articulation [10]. Therefore, along with analysing
the quality of features based on the resulting separability of strokes [7], it
is also important to consider the instrument-independence of these features.

For the task of classification, a number of common models have been used,
ranging from simple decision trees, k-nearest neighbours, and single layer
feed-forward neural networks, to the slightly more complex random forests,
probabilistic neural networks, and hidden markov models (HMM). The use of an
HMM, which models temporal context information, seems to have helped in cases
where ambiguous stroke labels were present in the dataset [4, 11]. Such
ambiguities arise commonly in recordings of tabla compositions, where similar
sounding strokes sometimes have different labels and vice-versa. In other
cases, where the labels were based more on the stroke acoustics, or where the
dataset consisted of isolated strokes, high classification accuracies have
been achieved even without modelling the context.

The task of transcribing strokes drawn from continuous playing warrants a
consideration of a few additional points over isolated stroke recordings. One,
regarding the use of language models, is whether temporal context information
learnt from solo compositions would be appropriate for tabla accompaniment
transcription. While training language models on the basic thekas is a
possibility, this would not capture all of the expressivity observed in
concerts. An additional challenge is the overlap of harmonics from a previous
stroke with subsequent ones [12]. For instance, a damped stroke like ‘ke’
(played on the bass drum) could be mistaken for a stroke like ‘Na’ with a
sustained sound (produced on the treble drum) occurring just before it,
because of the harmonics from ‘Na’ that continue to sound during ‘ke’. Hence,
a system trained on isolated strokes is likely to be of limited value in
analysing tabla playing in concert audios.

The evaluation method is important not only in assessing the classification
accuracy of a proposed method but more importantly, its generalisation to
unseen instruments. Due to the drastic timbre differences between tabla sets
arising from diverse physical properties and tuning, building a robust
classifier that works equally well on a variety of instruments has been found
to be a difficult task [5]. This is evident from the high cross-validation
scores when models are evaluated on strokes from a tabla that they have
already seen during training, and the significantly poorer scores on an unseen
tabla. Therefore, it is necessary to not only build a diverse dataset, but
also to evaluate the instrument-independence of the proposed methods.

Regarding the specific task of transcribing tabla accompaniment, there has
been a recent attempt at identifying strokes in the theka of a few talas [8].
The dataset used is a diverse mix of several tabla sets, players, talas, and
tempi. However, the recordings are of the thekas in their prescribed format,
and limited in terms of fillers and extempore variations that we would find in
a real concert. Further, while the results reported do reflect the challenges
in transcribing stroke sequences as opposed to strokes recorded in isolation,
there is no instrument independent evaluation reported.

Figure 1: Classification of tabla bols based on the drum that is struck and
the nature of the sound produced [13]

| Stroke
---
Category
| Acoustic
---
Characteristics
| Damped (D)
---
(Ti, Ta, Tak, Ke,
Tra, Kda)
| No sustained harmonics,
---
only a burst of energy
at the onset
| Resonant
---
Treble (RT)
(Na, Tin, Tun)
| One or more strong
---
harmonics in the 200-2000 Hz
range persist after the onset
| Resonant
---
Bass (RB)
(Ghe, Dhe, Dhi)
| Usually a single strong
---
harmonic close to 100 Hz
persists after the onset
| Resonant
---
Both (B)
(Dha, Dhin)
| Both the above characteristics
---
of resonant treble and bass

Figure 2: The four target tabla stroke categories of the transcription and
their acoustic characteristics.

##  3 Problem Formulation

The main goal of the current work is to aid the analysis of tabla
accompaniment in vocal concerts by providing musicologically meaningful stroke
labels. While the outputs of a tabla transcription system can encompass all
the distinct tabla bols, an important level in the taxonomy of bols is the
classification into resonant and damped categories [13] (Figure 2). This is
based on the acoustic characteristics of the sound produced, which in turn
depends on the manner in which the drums are struck - resonant sounds,
produced using impulsive strikes, are harmonic and sustained, whereas damped
strokes are transient and are produced by preventing the membrane from
continuing to vibrate after the strike. More importantly, these categories
also have musically meaningful roles in the context of accompaniment, where
they help mark different sub-divisions and accent positions in the theka [2].
For example, in the theka of tintal, a 16-beat cycle, there are four sub-
divisions, each of 4 beats, which are primarily distinguished based on the
presence or absence of the bass resonant sound. In contrast, the different
sub-divisions of the theka of ektal, a 12-beat cycle, are distinguished based
on whether they contain damped or resonant strokes.

We therefore look at transcribing tabla into the following four categories -
Damped, Resonant Treble, Resonant Bass, and Resonant Both, based on which drum
is struck and whether the sound is resonant or damped. The damped category
refers to strokes that do not have a sustained decay and includes all such
strokes produced either by striking one of the drums or both simultaneously
(each producing a damped stroke). The resonant treble and resonant bass
categories correspond to strokes that produce sustained sounds on the
corresponding drums (while the other drum either remains silent or produces a
damped sound). Resonant both refers to strokes that are played simultaneously
on both the drums, each of which results in a sustained sound. The acoustic
characteristics of each category are described in Table 2, and Figure 3 shows
the spectrograms for an example stroke of each category. Although a
transcription into the exhaustive list of bols could be followed by then
mapping the labels to any reduced set of categories, a more reasonable and
also useful formulation of the problem, given the scarcity of data, is to
classify each stroke directly into the required categories.

(a) Damped

(b) Resonant Treble

(c) Resonant Bass

(d) Resonant Both

Figure 3: Magnitude spectrograms of a stroke from each of the four target
stroke categories (spectrum shown up to 4 kHz for better visualisation of the
strong harmonics whose frequency support distinguishes the resonant bass and
treble strokes).

##  4 Dataset Description

The test data for our experiments was carefully chosen to closely resemble a
realistic accompaniment scenario. Since most public concert audios are not
available in a multi-track format with instruments recorded in perfect
isolation, it was necessary for us to build such a dataset. For this, we first
obtained solo singing audios from expert singers, and then got expert tabla
players to play the corresponding tabla accompaniment while listening to the
pre-recorded vocals over headphones. There are a total of 10 such aligned
vocal-tabla audio pairs, spanning a net duration of nearly 20 minutes, and
yielding about 4500 strokes. 6 of the compositions are in madhya lay tintal
($130-160$ BPM), and the rest are in one each of jhaptal and bhajani theka in
madhya lay, and tintal and dadra in drut lay ($\approx 250$ BPM). The
accompaniment was played by 2 different musicians for half of the tracks each,
with one of the players using 2 different tabla sets based on the tonic of the
singing (there are thus a total of 3 distinct tabla sets each of different
tuning). All the tabla audios were recorded at a sampling rate of 44.1 kHz in
quiet environments using professional microphones.

On the other hand, given the expensive nature of collecting such data, we
obtained the data for training our classification model from three available
sources of tabla solo playing, each recorded in the absence of a lehra
(melodic accompaniment), as described in Table 1. The PP and AS subsets
consist of about 20 recordings each of short tabla solo compositions (5 of
which are common), with each track between 10 and 30 seconds long. The AHK
subset has seven short excerpts from a solo concert recording, each between 30
and 60 seconds long. The recording, taken from
YouTube222https://www.youtube.com/watch?v=mEFr1Tp801M, is of poorer quality
and at a lower sampling rate of 16 kHz. The excerpts were chosen by excluding
portions of extremely fast playing that are difficult to annotate. Each of
these subsets corresponds to a single unique tabla set and player.

Name | Source |  | Nature of playing
---
Duration | # strokes
PP |  | Rohit and Rao (2018) [14]
---
| Solo compositions
---
7 mins. | 2848
AS |  | Rohit and Rao (2019) [15]
---
| Solo compositions
---
5 mins. | 1432
AHK |  | Tabla solo concert
---
audio from YouTube
| Solo compositions
---
interspersed with theka
6 mins. | 2400
Test |  | Recordings made
---
for this study
| Isolated accompaniment
---
to pre-recorded vocals
20 mins. | 4470
Table 1: Description of the training (PP, AS, AHK) and testing datasets

The PP and AS subsets are available along with time-aligned bol annotations.
These bols were mapped according to their acoustic characteristics to the four
stroke categories, for the purpose of this study. As for the AHK and test
sets, the annotation was performed manually with the help of
Audacity333Audacity® software is copyright © 1999-2020 Audacity Team. The name
Audacity® is a registered trademark of Dominic Mazzoni. by the first author (a
tabla student) and an intern in the same lab. To aid the manual annotation
process, stroke onsets were first determined automatically using an automatic
onset detection algorithm (Section 5.1). In order to make up for missed soft
onsets, a fairly low threshold was used while picking the peaks in the onset
detection signal. This resulted in some false alarms, but ensured that soft
onsets were also detected, thus requiring the annotator to not add any onsets,
but only remove the false alarms and appropriately label the correct onsets.

The distribution of strokes across the four categories in each of these
subsets is shown in Figure 4. Comparing these with the test set, we see a few
similarities as well as differences. In all the subsets (train and test), the
damped category is the most populated and resonant bass is the least
populated. The high count of damped strokes can be attributed, in the case of
solo playing, to the nature of solo compositions - they contain more damped
strokes to allow playing at high speeds, and in the case of accompaniment, to
fillers and expressive embellishments. Further, in the test set, the resonant
both category has a higher count than any of the training subsets, possibly
because of the dominant nature of such strokes in accompaniment playing (for
instance, the theka for tintal has 12 out of its 16 strokes of this kind).

Figure 4: Distribution (% count) of strokes across categories in the training
and testing sets.

##  5 Methods

In the present study, we follow the same ‘segment and classify’ approach,
where stroke onsets are first determined and the labels are then assigned to
the segmented strokes. Each segment is the duration from the onset of a stroke
to the onset of the subsequent stroke. We extract features on these segments
and provide the feature vectors to a random forest classifier model to predict
the stroke category. All the tabla audios (training and testing) are first
down-sampled to 16 kHz, since the AHK set is not available at 44.1 kHz.

###  5.1 Onset Detection

Given the well-studied nature of onset detection, especially for percussive
sounds, we make use of a common onset detection method called the High
Frequency Content, and experiment with the post-processing hyperparameters to
arrive at the best settings for our data. This method involves calculating the
frequency-weighted sum of the magnitude spectrum to indicate the onset
strength in each frame [16]. The implementation is as provided in the software
library Essentia [17], with the window and hop size values set to 25 ms and 5
ms, respectively. The post-processing step involves smoothing the onset
detection signal and then picking the peaks above a certain threshold [18].
The size of the moving average filter (delay) used for smoothing and the
threshold value for peak-picking (alpha) are hyperparameters that we
experiment with. We first iteratively evaluate each of the methods on the
training set using a grid of values for alpha and delay, and pick the pair of
values that results in the highest f-score. Then, we keep these values fixed
and evaluate the onset detector on the test set.

###  5.2 Feature Extraction

The features we use in this work are modeled on those used in previous tabla
transcription methods (as reviewed in Section 2), along with a few important
modifications and additions. The total set of features, 49 in all, is given in
Table 2. Some of the features are calculated separately on band-passed
versions of the signal. Given that our four-way target stroke classes are
based closely on the differences in the resonant characteristics of each drum,
we decide on the following ranges for the bands: 50 - 200 Hz to capture the
base and 200 - 2000 Hz to capture the treble harmonics. These ranges are kept
broad in order to capture a wide F0 range of each drum, similar to the bands
used in [4]. They could, however, be tuned based on the tabla as well, by
first identifying the range of harmonic frequencies of each drum, as done
previously (for the treble drum alone) in [13]. This could be achieved by
analysing a few resonant strokes of each drum, which, in a testing scenario,
could be provided manually.

Category | Feature | Count
---|---|---
Spectral | $\left.\begin{tabular}[]{@{}l@{}}Spectral Centroid\\\ Skewness\\\ Kurtosis\\\ \phantom{Aardvark}\\\\[-12.0pt] \end{tabular}\hskip 28.45274pt\right\\}$ | 2 (mean, stdev.) |
MFCC | 13 (mean) |
| Flux (onset strength)
---
Energy
$\left.\begin{tabular}[]{@{}l@{}}1 (max.)\\\ 3 (sum, mean, stdev.)\\\ \phantom{Aardvark}\\\\[-12.0pt] \end{tabular}\right\\}$ x 2 (bass, treble) |
Temporal | Log Attack Time | 1 |
Temporal Centroid | 1 |
Zero Crossing Rate | 2 (mean, stdev.) |
| Early Decay Rate & Intercept
---
Late Decay Rate & Intercept
$R^{2}$
Spline Knot Location
$\left.\begin{tabular}[]{@{}l@{}}2\\\ 2\\\ 1\\\ 1\\\ \phantom{Aardvark}\\\\[-12.0pt] \end{tabular}\right\\}$ x 2 (bass, treble) |
Delta |  | Sum and Mean Energy
---
Late Decay Rate
$\left.\begin{tabular}[]{@{}l@{}}2\\\ 1\\\ \phantom{Aardvark}\\\\[-12.0pt] \end{tabular}\right\\}$ x 2 (bass, treble) |
|  | Total
---
49 |
Table 2: The set of features used for stroke classification.

All the spectral features, and the temporal zero-crossing rate feature, are
calculated frame-wise on overlapping short-time frames of size 25 ms, with a
hop of 5 ms, over the entire stroke segment. The shape-related spectral
features (spectral centroid, skewness, and kurtosis) are summarised using the
mean and standard deviation, MFCC using the mean, flux using the maximum, and
energy using the sum, mean, and standard deviation. The other two temporal
features - log attack time and temporal centroid are calculated from the
amplitude envelope of the entire time-domain audio signal of the stroke
segment. The implementation provided by Essentia is used for each of these
features.

For the remaining temporal features, the short-time energy envelope serves as
the base. A logarithmic transformation is first applied to make the decay
portion (the part beyond the peak) of the envelope more linear. By observing a
few plots of band-wise log-scaled short-time energy envelopes (Figure 5), we
see that the decay portion usually consists of two parts (early and late), and
the differences between the stroke categories seem to be based on the rates of
these decays. For instance, the decay patterns in both the bands are quite
similar for the damped stroke, with the late portion mostly corresponding to
noise, whereas in the resonant both stroke, the bands contain smooth decays at
different rates. Therefore, to capture the distinctive nature of the decay, a
linear spline model is fit to the decay portion. The ‘knot’ location for the
fit, which is the point of inflexion, is automatically estimated as the point
that yields the combined best fit for the two linear segments, in the sense of
the harmonic mean of the $R^{2}$ values of each fit. The slopes of both the
line segments, their y-intercepts, the harmonic mean of the $R^{2}$ values,
and the knot location are all used as features. The terms ‘early’ and ‘late’
are used to refer to the two line segments in terms of their relative
positions. The use of decay-related parameters as features is reported in
[13]. However, a key difference here is the use of a linear spline fit to the
log-scaled envelope instead of a single exponential fit to the un-scaled
envelope as done previously.

(a) Damped

(b) Resonant Both

Figure 5: Band-wise log-transformed short-time energy envelopes (marked by
‘x’) of a stroke from (a) Damped and (b) Resonant Both categories, along with
the best spline fit (solid lines).

Finally, to help determine whether the measured characteristics of a stroke
are not corrupted by possible overlap from a previous stroke, we incorporate
delta features. These are calculated as the difference between the values in a
given and its previous stroke for the following six features - bass and treble
late decay rates, and the sum and mean of base and treble short-time energy
values.

###  5.3 Stroke Classification

For stroke classification, we use a random forest classifier, with the
implementation provided in the scikit-learn library [19]. A random forest
classifier is an ensemble of decision trees in which the output is determined
by a majority vote across all the trees. The main motivation behind its design
is to prevent the overfitting that is commonly observed in the case of a
single decision tree. This model is also useful because it lends itself well
to an analysis of the important features in the input data (given by the
‘feature_importances_’ attribute of a trained model). The input to the model
is a feature vector comprising all the features listed in Table 2, extracted
on a single stroke segment, and the target is one of the four stroke
categories. For our initial experiments, we set the number of trees in the
forest to 200, the ‘max_features’ parameter to ‘sqrt’, and the ‘bootstrap’
parameter to ‘True’ (Section 5.3.1).

####  5.3.1 Feature Selection and Hyperparameter Tuning

The subset of features that are most relevant and non-redundant can be
obtained via a recursive feature elimination (RFE) strategy. This method uses
a classifier like the random forest to first estimate the relative feature
importances, and then removes the least important ones recursively until a
desired number of features is obtained. In order to obtain the optimum number
of features, it is performed in a cross-validation setting on the training
set, where a second classifier model is trained and evaluated on separate
folds to obtain the average cross-validation accuracy at a given number of
selected features. By repeating this for different values of the number of
selected features and recording the average classification score in each case,
a suitable point on this curve can be chosen while trading off performance for
complexity.

An important step in extracting the best performance out of a classifier is
the optimization of its hyperparameters. In the case of the random forest,
these determine various aspects of the model complexity and help control the
trade-off between bias and variance - a more complex model increases the
variance while a simpler model increases the bias. In the present work, we
look at optimizing the following hyperparameters - number of trees, maximum
allowed depth of each tree, size of the subset of features given to each tree
(also called ‘max_features’), and the use of bootstrapping in sampling subsets
of the training data. The optimization is carried out by sampling 40 random
combinations of these hyperparameters from a grid of values and evaluating
each combination in terms of the average cross-validation score on the
training set. The use of cross-validation here is intended to not bias the
model towards our test set of accompaniment audios in the process of tuning
the model hyperparameters.

####  5.3.2 Data Augmentation and Balancing

A recurring problem that has been noted by authors in some of the previous
work on tabla transcription is the scarcity and limited diversity of available
datasets. The process of building large, accurately annotated datasets is, in
general, extremely cumbersome, but especially so in the case of instruments
like tabla, which cannot be synthesized realistically using existing software
or electronic instruments (most software only has recorded samples of short
loops). This motivates the use of effective data augmentation strategies where
available labeled data is transformed in different ways that do not change the
validity of the labels, thus offsetting to an extent the need to collect more
data.

For our present work, we investigate the following three general data
balancing and augmentation methods - repeating the data samples (repeated
oversampling), interpolating in the feature space, and pitch-shifting the
audios. For pitch-shifting, we use the function provided in the software
library librosa [20], and only consider the three resonant stroke categories
(since damped strokes do not contain a pitched component). Each stroke’s audio
signal is pitch-shifted by each of 4 semitone levels: {-0.5, -0.25, 0.25,
0.5}. This rather small range of shifts compares well with the allowed range
for a high-pitched tabla of a small-diameter, which is what the tabla sets in
our training set resemble [21].

Given that our dataset is also highly imbalanced in terms of the distribution
of examples across the four categories, we use the methods of repeated
oversampling and interpolation as required to achieve a balanced distribution.
That is, we augment samples in all the categories except the majority class,
until a balance is obtained. For the interpolation, we use an algorithm called
SMOTE (Synthetic Minority Oversampling Technique) [22]. This uses a k-nearest
neighbours method to first estimate the k samples nearest to a given data
sample, after which, between every pair of the given sample and a neighbour, a
new feature vector is sampled by linearly interpolating between the feature
vector pair. The implementation for this is as provided in the library
imbalanced-learn [23].

##  6 Results and Discussion

For the stroke onset detection task, the commonly used metrics for evaluation
are the precision, recall, and f-score, which are calculated by determining
the correct and incorrect onset predictions. A correctly detected onset
(‘hit’) is one that lies within a tolerance window ($50ms$ wide) about an
unmatched ground truth onset [24]. The average f-score is calculated as the
mean value across all the tracks in a dataset. After the hyperparameter
tuning, we obtain a best f-score of 0.972 on the training set, while on the
test set, we obtain a comparably high f-score of 0.965.

To report stroke classification performance, we use the accuracy as well as
average f-score, calculated by averaging the per-class f-score value. We
perform cross-validation in a ‘Leave-One-Tabla-Out’ (LOTO) format, consisting
of 3 folds, one each corresponding to each of the 3 tabla sets in the training
dataset. This prevents the samples from a given tabla from being present in
both the training and evaluation folds and therefore results in a more
realistic evaluation of performance. The LOTO-CV results are reported for each
of the 3 tabla sets in Table 3 which also provides the test set performance
from a model trained on all the 3 solo tabla training sets. We present
different data augmentation and balancing strategies, including some
combinations of the two. The baseline method refers to training the classifier
on just the originally available dataset. Among the different methods, the use
of pitch-shifting leads to a significant rise in the test set score, while
resulting in no improvement over the baseline in the average cross-validation
f-score. On the other hand, the other two data balancing strategies (repeated
oversampling and SMOTE) improve the average CV scores, mainly due to an
improvement on the AS set alone, while not positively affecting the test set
scores (even when performed along with pitch-shifting). This indicates that
the latter two methods are perhaps resulting in an overfit on the training
data, whereas the pitch-shifting method is helping the model generalise
better. Further, among the three training sets, we see a consistently poorer
CV performance on the AHK set, while the other two are comparable.

Method | Cross-validation scores |  Test set scores
---|---|---
Accuracy | F-score
PP | AS | AHK | Mean | PP | AS | AHK | Mean | Acc. | F-sc.
| Baseline
---
(no augmentation)
0.80 | 0.73 | 0.57 | 0.70 | 0.70 | 0.58 | 0.49 | 0.59 | 0.59 | 0.50
| Repeated
---
oversampling
0.80 | 0.74 | 0.57 | 0.70 | 0.70 | 0.62 | 0.49 | 0.60 | 0.59 | 0.51
SMOTE | 0.79 | 0.76 | 0.57 | 0.70 | 0.70 | 0.67 | 0.49 | 0.62 | 0.59 | 0.51
Pitch-shifting | 0.76 | 0.66 | 0.55 | 0.66 | 0.69 | 0.58 | 0.49 | 0.59 | 0.65 | 0.60
| Pitch-shifting
---
\+ Rep. Oversampling
0.76 | 0.67 | 0.56 | 0.66 | 0.69 | 0.61 | 0.49 | 0.60 | 0.64 | 0.59
| Pitch-shifting
---
\+ SMOTE
0.76 | 0.70 | 0.56 | 0.67 | 0.69 | 0.62 | 0.48 | 0.60 | 0.64 | 0.58
Table 3: Leave-One-Tabla-Out cross-validation scores (on each fold and the
mean) and the test set scores for stroke classification using the various
augmentation methods (the highest mean CV and test scores obtained are
highlighted in bold).

(a) Baseline

(b) Pitch-shifting

Figure 6: Confusions in the test set stroke classification with (a) baseline
method and (b) pitch-shifting augmentation. (D: ‘Damped’, RT: ‘Resonant
Treble’, RB: ‘Resonant Bass’, B: ‘Resonant Both’)

From Figure 6, which shows the confusions in stroke label predictions on the
test set, we see that the model is clearly biased towards the ‘damped’ class
in the baseline method due to the large class imbalance in the training set.
With the use of pitch-shifting augmentation, the errors in all the resonant
categories reduce, but at the cost of a slight increase in errors in the
damped category. Most of the remaining errors are in the resonant bass and
resonant both categories.

Method | Stroke category |  Balanced accuracy
---|---|---
D | RT | RB | B
Prec. | Rec. | Prec. | Rec. | Prec. | Rec. | Prec. | Rec.
Baseline | 0.82 | 0.93 | 0.60 | 0.95 | 0.86 | 0.20 | 0.63 | 0.29 | 0.59
Pitch-shifting | 0.93 | 0.69 | 0.48 | 0.96 | 0.71 | 0.36 | 0.45 | 0.39 | 0.60
| Pitch-shifting
---
\+ SMOTE
0.92 | 0.75 | 0.53 | 0.96 | 0.74 | 0.39 | 0.50 | 0.43 | 0.63
Table 4: Class-wise validation scores on the AS set in the LOTO-CV. The
balanced accuracy is the average per-class accuracy (suitable for imbalanced
datasets).

To help explain the previously noted drop in CV accuracies in the course of
pitch-shifting based augmentation, we look at the class-wise precision and
recall values on the AS set alone when it is evaluated in the LOTO-CV
procedure (Table 4). Also reported is the ‘balanced accuracy’ - the average
per-class accuracy, which is more suitable for evaluating the performance on
imbalanced datasets. The significant drop in the recall value for the damped
stroke with the use of pitch-shifting, coupled with its higher count in the
dataset, brings out the reason for a drop in the overall accuracy. However,
the balanced accuracy improves with the use of pitch-shifting augmentation,
and further, with SMOTE. Further, the opposite trends in the precision and
recall values for the resonant stroke categories with the use of pitch-
shifting explain the lack of improvement in the CV f-score.

In Table 5, we offer a comparison of our baseline cross-validation results
(without any augmentation) with a few relevant tabla transcription results
from the literature. We also evaluate our method using a random 3-fold CV (as
opposed to the LOTO-CV reported in Table 3) to aid this comparison. The
dataset size, number of tabla sets, number of target classes, and modes of
evaluation are all different in each of the methods. Some of the scores are
reported as ranges because the average accuracy reported by Chordia is
calculated over a number of individual results on a few subsets of the data.
Some of these subsets include single tabla sets out of the total of 7,
contributing sometimes to the high average accuracy. Hence, the ranges
reported here are an attempt to cover the whole set of accuracies reported
under the different conditions. A similar approach was taken to arrive at the
accuracy range reported for our method as well. Although a direct comparison
is difficult due to the larger target class set in the previous methods
(comprising all the distinct bols), a key observation is the huge range of
LOTO-CV score reported by Chordia [5], pointing again to the larger problem of
generalisation to unseen instruments.

Method |  | # Target
---
classes
| # strokes,
---
tabla-sets
| Random
---
CV acc.
| LOTO-CV
---
acc.
Ours | 4 | 6678, 3 | 0.71 - 0.92 | 0.57 - 0.80
Sarkar et. al. [8] | 10 | 3964, 7 | 0.85 | -
Gupta et. al. [11] | 18 | 8200, 1 | 0.66 | -
Chordia [5] | 10-16 | 16384, 7 | 0.77 - 0.94 | 0.15 - 0.95
Table 5: Comparing the cross-validation results of our method with previous
tabla transcription studies.

Next, we look at the results from the feature selection and model
hyperparameter tuning. The plot of average LOTO-CV f-score versus the number
of features shows a rise till about 30 features, after which it first plateaus
and then dips slightly towards the end (Figure 7). The RFE method was then
applied to the entire training set in order to pick the best set of 30
features, and the model tuning was performed only using this subset of all
features. At the outset, there was no significant improvement in the average
CV f-score compared to the results of Table 3. A decrease in the number of
trees was not found to cause a significant drop in the f-score, perhaps due to
the small size of our dataset. And, as expected, at a given number of trees,
setting the maximum features to ‘None’ (i.e., providing each tree with all
features) was found to cause a significant drop in performance due to
overfitting.

Figure 7: Plot of average LOTO-CV f-score versus the number of features
selected in the recursive feature elimination procedure (RFE). The shaded
region represents the standard deviation of the score across the CV folds.

Rank Feature PP AS AHK All 1 Bass onset strength Bass onset strength Bass
onset strength Bass onset strength 2 Treble energy sum MFCC 1 MFCC 12 Treble
energy sum 3 Treble onset strength MFCC 4 Treble energy sum MFCC 1 4 MFCC 3
MFCC 3 Treble early decay rate Treble onset strength 5 Treble early decay rate
Treble energy sum Log attack time Treble early decay rate 6 MFCC 1 Spec.
centroid mean Spec. centroid stdev. MFCC 2 7 MFCC 2 Treble onset strength
Spec. centroid mean MFCC 3 8 ZCR mean Treble early decay rate MFCC 2 Spec.
centroid mean 9 Log attack time ZCR mean Bass early decay rate Log attack time
10 MFCC 4 MFCC 12 ZCR mean ZCR mean

Table 6: The 10 highest ranked features based on importance by a random forest
model when fit on different training subsets (entries in bold are features
important only to one subset).

Finally, given the lower performance on the AHK set in the LOTO-CV, a closer
look at it can help analyse the instrument dependence of the task. As a first
step, we look at models fit separately on each of the three subsets in the
training set, with each subset augmented using the pitch-shifting method.
Table 6 shows the ten most important features according to their contribution
to the model fit on each tabla set, in comparison with a model fit on the
entire training set. The features highlighted in bold refer to those that are
exclusive to a subset. We find that almost all the features are common to the
three subsets, although with slightly different rankings. This can be taken as
a point in favour of the aptness of the features for the stroke classification
task, across tabla sets. However, the feature distributions shown in Figure 8,
of the top two features (from the last column in Table 6) shed light on the
instrument dependence of the feature values. While the distribution of bass
onset strength is similar in all the subsets, in the case of treble energy
sum, the PP and AS subsets have a similar distribution that is quite different
from that of AHK. This is a likely cause of the poor generalisation of the
model.

(a) Treble energy sum

(b) Bass onset strength

Figure 8: Boxplots of the distributions in each training subset of (a) treble
energy sum and (b) bass onset strength. (D: ‘Damped’, RT: ‘Resonant Treble’,
RB: ‘Resonant Bass’, B: ‘Resonant Both’)

##  7 Concluding Remarks

The presented study brings out the challenges in transcribing tabla stroke
sequences when labeled training data from the same tabla set is unavailable.
Further, the imbalanced nature of the datasets built using recordings of tabla
compositions makes it difficult to train an unbiased model, making it
necessary to employ appropriate data balancing and augmentation strategies.
The use of pitch-shifting augmentation to increase the size of the less
populated resonant stroke categories is found to help, but not on all tabla
sets - the cross-validation scores do not improve, while the test set scores
do. On the other hand, augmenting in the feature space by interpolating
between feature vectors improves the cross-validation scores but leads to an
overfit when applied to the entire training set, thus not really improving the
test set scores. A preliminary analysis of the feature importances in the
models trained separately on each tabla set reveals that the same few features
are ranked highest in each case. Most of these features are not the standard
MFCC or spectral shape-related ones, but happen to be ones that are easier to
relate to tabla acoustics (such as onset strength, decay rate, etc). However,
the feature distributions vary significantly across tabla sets consistent with
the observed instrument-dependence. Therefore, a way to perform more effective
data augmentation would be to selectively transform more features that
represent the tabla instrument characteristics. The augmentation methods used
in the present work are general and do not leverage any specificity of the
task. Future work will target acquiring a larger dataset, possibly using
unsupervised labeling to reduce the manual transcription effort. Further, data
augmentation methods that modify those acoustic attributes that are not
important to the distinctions between strokes will be explored to better embed
the necessary diversity in the training dataset. Finally, we look forward to a
system that can be coupled with musical source separation to achieve the
automatic transcription of tabla accompaniment in the typical context of a
vocal concert’s mixed audio.

## References

  * [1] Bonnie C Wade  “Music in India : The Classical Traditions”  Prentice-Hall, 1979
  * [2] Ajay Srinivasamurthy, Andre Holzapfel, Kaustuv Kanti Ganguli and Xavier Serra  “Aspects of Tempo and Rhythmic Elaboration in Hindustani Music: A Corpus Study”  In _Frontiers in Digital Humanities_ 4, 2017, pp. 20
  * [3] Martin Clayton  “Theory and practice of long-form non-isochronous metres”  In _Music Theory Online_ 26.1, 2020
  * [4] Olivier Gillet and Gaël Richard  “Automatic labelling of tabla signals”  In _Proc. of the 4th Int. Society for Music Information Retrieval Conf._ , 2003
  * [5] Parag Chordia  “Segmentation and Recognition of Tabla Strokes”  In _Proc. of the 6th Int. Society for Music Information Retrieval Conf._ , 2005
  * [6] Subodh Deolekar and Siby Abraham  “Classification of Tabla Strokes Using Neural Network”  In _Computational Intelligence in Data Mining - Volume 1_ Springer India, 2016, pp. 347–356
  * [7] Subodh Deolekar and Siby Abraham  “Tree-based classification of tabla strokes”  In _Current Science (00113891)_ 115.9, 2018, pp. 1724–1731
  * [8] Rajib Sarkar, Ankita Singh, Anjishnu Mondal and Sanjoy Kumar Saha  “Automatic Extraction and Identification of Bol from Tabla Signal”  In _Advanced Computing and Systems for Security: Volume Five_ Springer Singapore, 2018, pp. 139–151
  * [9] Shambhavi Shete and Saurabh Deshmukh  “Analysis and Comparison of Timbral Audio Descriptors with Traditional Audio Descriptors Used in Automatic Tabla Bol Identification of North Indian Classical Music”  In _Proceeding of International Conference on Computational Science and Applications_ Springer Singapore, 2020, pp. 295–307
  * [10] Anirban Patranabis et al.  “Harmonic and timbre analysis of tabla strokes”  In _arXiv preprint arXiv:1510.04880_ , 2015
  * [11] Swapnil Gupta et al.  “Discovery of Syllabic Percussion Patterns in Tabla Solo Recordings”  In _Proc. of the 16th Int. Society for Music Information Retrieval Conf._ , 2015
  * [12] Parag Chordia and Alex Rae  “Tabla Gyan: a System for Realtime Tabla Recognition and Resynthesis”  In _Proc. of the International Computer Music Conference_ , 2008
  * [13] Krish Narang and Preeti Rao  “Acoustic features for determining goodness of tabla strokes”  In _Proc. of the 18th Int. Society for Music Information Retrieval Conf._ , 2017
  * [14] M. A. Rohit and Preeti Rao  “Acoustic-Prosodic Features of Tabla Bol Recitation and Correspondence with the Tabla Imitation”  In _Proc. of Interspeech_ , 2018
  * [15] M. A. Rohit and P. Rao  “Separation of Tabla Strokes from Tabla Solo Audios Using Non-negative Matrix Factorization”  In _Technical Report_ Indian Institute of Technology Bombay, 2019
  * [16] Juan Pablo Bello et al.  “A tutorial on onset detection in music signals”  In _IEEE Transactions on Speech and Audio Processing_ 13.5 IEEE, 2005
  * [17] D. Bogdanov et al.  “ESSENTIA: an Audio Analysis Library for Music Information Retrieval”  In _Proc. of the 14th Int. Society for Music Information Retrieval Conf._ , 2013
  * [18] P. Brossier, J. P. Bello and M. D. Plumbley  “Fast labelling of notes in music signals”  In _Proc. of the 5th Int. Society for Music Information Retrieval Conf._ , 2004
  * [19] F. Pedregosa et al.  “Scikit-learn: Machine Learning in Python”  In _Journal of Machine Learning Research_ 12, 2011
  * [20] Brian McFee et al.  “librosa: Audio and music signal analysis in python”  In _Proc. of the 14th Python in Science Conference_ , 2015
  * [21] David Courtney  “Manufacture and Repair of Tabla”  Sur Sangeet Services, 2016
  * [22] Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall and W Philip Kegelmeyer  “SMOTE: Synthetic Minority Over-sampling Technique”  In _Journal of Artificial Intelligence Research_ 16, 2002
  * [23] Guillaume Lemaître, Fernando Nogueira and Christos K. Aridas  “Imbalanced-learn: A Python Toolbox to Tackle the Curse of Imbalanced Datasets in Machine Learning”  In _Journal of Machine Learning Research_ 18.17, 2017
  * [24] Colin Raffel et al.  “mir_eval: A Transparent Implementation of Common MIR Metrics”  In _Proc. of the 15th Int. Society for Music Information Retrieval Conf._ , 2014


# Comparing Eigenvector and Degree Dispersion with the Principal Ratio of a
Graph

Gregory J. Clark
Saïd Business School
University of Oxford

###### Abstract

The principal ratio of a graph is the ratio of the greatest and least entry of
its principal eigenvector. Since the principal ratio compares the extreme
values of the principal eigenvector it is sensitive to outliers. This can be
problematic for graphs (networks) drawn from empirical data. To account for
this we consider the dispersion of the principal eigenvector (and degree
vector). More precisely, we consider the coefficient of variation of the
aforementioned vectors, that is, the ratio of the vector’s standard deviation
and mean. We show how both of these statistics are bounded above by the same
function of the principal ratio. Further this bound is sharp for regular
graphs. The goal of this paper is to show that the coefficient of variation of
the principal eigenvector (and degree vector) can converge or diverge to the
principal ratio in the limit. In doing so we find an example of a graph family
(the complete split graph) whose principal ratio converges to the golden
ratio. We conclude with conjectures concerning extremal graphs of the
aforementioned statistics and interesting properties of the complete split
graph.

##  1 Introduction

There are several measures of graph irregularity which are used to determine
how ‘close’ a given graph is to being regular. One such measure, the principal
ratio, is the ratio of the greatest and least entry of the principal
eigenvector of a graph $G$. Throughout we assume that graphs are connected,
simple, and undirected. We reserve $(\lambda,x)$ to denote the principal
eigenpair of the adjacency matrix of $G$. The principal ratio, then, is
denoted $\gamma(G)=x_{\text{max}}/x_{\text{min}}$. A limitation of this
statistic is its sensitivity to the position (and to an extent the degree) of
individual vertices in the graph. For example, its applicability to empirical
networks where the principal eigenvector is highly dispersed (e.g., scale-free
networks [4, 6, 18]). This motivates the study of the underlying vector’s
dispersion.

Given a vector $x\in\mathbb{R}^{n}_{+}$ let $\mu$ denote its mean and $\sigma$
its standard deviation. The coefficient of variation of $x$ is the ratio
$\sigma/\mu$. For convenience we will consider the square of the coefficient
of variation which we denote

$c_{x}:=\left(\frac{\sigma}{\mu}\right)^{2}.$

The coefficient of variation and its square appear frequently across multiple
disciplines: economic inequality [1], reliability of measures [21], and
efficiency of experimental designs [13]. Interestingly, the inverse of the
coefficient of variation, $\mu/\sigma$, is the signal-to-noise ratio (SNR).
The SNR is used informally to measure the ratio of useful to irrelevant
information in a conversation [12]. It has further found use in information
theory [20], optics [19], internet topology [16], medical imaging [8], and
nuclear engineering [15].

Studying the distribution of vectors associated to graphs is not new. Notably
the variance of the degree vector was an early irregularity measure [3]. As
such, we consider the coefficient of variation of the degree vector in
addition to the principal eigenvector. We reserve $d$ to denote the degree
vector of a graph $G$. We denote the square of the coefficient of variation of
the principal eigenvector as $c_{e}$ and the degree vector as $c_{d}$.
Studying the distribution of these two vectors in tandem will further aid in
motivating their use in practice. As we will see there are instances where
$c_{e}$ and $c_{d}$ diverge.

The goal of this paper is to determine how much the principal ratio and the
coefficient of variation of the principal eigenvector (and degree vector) can
differ. We begin by showing that $c_{d}$ and $c_{e}$ are both bounded above by
the same function of principal ratio (namely, $\gamma^{2}-1$). We then
consider various graph families and compute the limit of the aforementioned
statistics of said graphs. In particular, we present graph families for which
the limit is 0, non-zero, or diverges to infinity. We summarize our results in
Table 1 and note that all six cases for the limit of the principal ratio and
the coefficient of variation (for the principal eigenvector or degree vector,
respectively) are achieved. We provide conjectures for which graphs are
extremal for the greatest eigenvector and degree dispersion. In doing so we
introduce a statistic

$\Gamma(G)=\frac{c_{d}(G)-c_{e}(G)}{\gamma^{2}(G)}$

and provide a conjecture for which graph achieves the lower bound. We show
that the limit of the principal ratio of the complete split graph ratio tends
to $\varphi$, the golden ratio. We conclude by showing that the complete spit
graph also has an interesting empirical property: its local and global
clustering diverge. This is (to the best of our knowledge) the third such
example of a graph family to do so.

Table 1: The limit of $\gamma^{2}-1$, $c_{e}$, and $c_{d}$ for various graph families including the complete graph with an edge removed; a particular complete triparite graph, a complete split graph (i.e., $S(n,m)=K_{n+m}-K_{m})$; the complete graph with a pendant edge, a kite whose head is an $r$-regular graph; the star; and the Cartesian product of a graph with itself. $G_{n}$ | $\lim\gamma^{2}-1$ | $\lim c_{e}$ | $\lim c_{d}$
---|---|---|---
$K_{n}-K_{2}$ | $0$ | $0$ | $0$
$K_{1,n,n}$ | $3$ | $0$ | $0$
$S(n,kn)$ | $\left(\frac{\sqrt{4k+1}+1}{2}\right)^{2}-1$ | $\frac{k\left(\frac{\sqrt{4k+1}-1}{k}-2\right)^{2}}{(\sqrt{4k+1}+1)^{2}}$ | $\frac{k^{3}}{(2k+1)^{2}}$
$P_{2}K_{n-1}$ | $\infty$ | $0$ | $0$
$P_{n}G_{n}^{r}$ | $\infty$ | $-$ | $\left(\frac{r-2}{r+2}\right)^{2}$
$K_{1,n}$ | $\infty$ | 1 | $\infty$
$G^{\square n}$ | $\infty$ | $\infty$ | 0

##  2 Background

Throughout we assume that graphs are connected, simple, and undirected. We
consider the distribution of a vector so that the indices are often
irrelevant. To better facilitate the discussion we will abuse notation and
write

$x=((x_{i},m_{i}))_{i\geq 1}\text{ for }x\in\mathbb{R}^{n}$

to mean that $x_{i}$ occurs multiplicity $m_{i}$ in $x$. Let $\mu$ and
$\sigma$ denote the mean and standard deviation of $x$, then the _square of
the coefficient of variation_ is $c_{x}=(\sigma/\,u)^{2}$. With a slight abuse
of notation we write $c_{e}(G)$ and $c_{d}(G)$ to be the square of the
coefficient of variation for the principal eigenvector and degree vector of
$G$, respectively. When the context is clear we will simply write $c_{e}$
(respectively, $c_{d}$).

In some cases we consider the difference of two graphs. Let $H\subseteq G$ be
two graphs on the same vertex set. We write $G-H$ to be the graph formed by
removing the edges of $H$ from $G$. That is $E(G-H)=\\{e\in G:e\notin H\\}$
and $V(G-H)=V(G)$.

We begin with the following fact about the coefficient of variation of a
positive vector.

###### Lemma 1

Let $x\in\mathbb{R}^{n}_{+}$ then

$c_{x}=n\frac{||x||_{2}^{2}}{||x||_{1}^{2}}-1.$ (1)

Moreover,

$c_{x}\leq\left(\frac{x_{\text{max}}}{x_{\text{min}}}\right)^{2}-1.$

###### Proof.

Let $X$ to be the random variable which takes on $x_{i}$ with probability
$1/n$. Intuitively, $X$ draws a coordinate-value of $x$ uniformly at random.
We have

$\mathbb{E}[X]=\frac{||x||_{1}}{n}\text{ and
}\mathbb{E}[X^{2}]=\frac{||x||^{2}_{2}}{n}$

so that

$||x||_{1}^{2}=n^{2}\mathbb{E}[X]^{2}\text{ and
}||x||_{2}^{2}=n\mathbb{E}[X^{2}].$

It follows that

$\frac{||x||_{2}^{2}}{||x||_{1}^{2}}=\frac{\mathbb{E}[X^{2}]}{n\mathbb{E}[X]^{2}}.$

Whence $\mathrm{Var}(x)=\mathbb{E}[X^{2}]-\mathbb{E}[X]^{2}$ we have

$\frac{||x||_{2}^{2}}{||x||_{1}^{2}}=\frac{\mathrm{Var}(X)+\mathbb{E}[X]^{2}}{n\mathbb{E}[X]^{2}}.$

Indeed

$n\left(\frac{||x||_{2}^{2}}{||x||_{1}^{2}}\right)-1=\frac{\mathrm{Var}(X)+\mathbb{E}[X]^{2}}{\mathbb{E}[X]^{2}}-1=\frac{\mathrm{Var}(X)}{\mathbb{E}[X]^{2}}=c_{v}(x).$

Now assume that $||x||_{2}^{2}=1$. By an averaging argument we have that
$x_{\text{max}}\geq n^{-1/2}$ so that

$||x||_{1}^{2}\geq
n^{2}x_{\text{min}}^{2}=x_{\text{max}}^{2}n^{2}\left(\frac{x_{\text{min}}}{x_{\text{max}}}\right)^{2}\geq
n\left(\frac{x_{\text{min}}}{x_{\text{max}}}\right)^{2}.$

The desired inequality follows by substitution into Equation 1. ∎

This immediately implies the following.

###### Lemma 2

$c_{e}(G)\leq\gamma^{2}(G)-1$.

Consider $c_{d}(G)$ and note that Lemma 1 yields
$c_{d}\leq(\Delta/\delta)^{2}-1$. Since $c_{d}(G)$ is a function of the degree
vector and $\gamma(G)$ is a function of the principal eigenvector it is
natural to think that they are incomparable, a priori. Surprisingly $c_{d}(G)$
is similarly bounded above and the bound is sharp for regular graphs.

###### Lemma 3

$c_{d}(G)\leq\gamma^{2}(G)-1$.

###### Proof.

We have

$||d||_{1}^{2}=(2|E|)^{2}\text{ and }||d||_{2}^{2}=\sum_{uv\in
E(G)}\deg(u)+\deg(v)\leq 2|E|\Delta$

so that by Equation 1,

$c_{d}\leq
n\left(\frac{2|E|\Delta}{4|E|^{2}}\right)-1=\frac{n\Delta}{2|E|}-1=\frac{\Delta}{\bar{d}}-1\leq\frac{\Delta}{\delta}-1.$

From [7, 30] we have $\sqrt{\Delta/\delta}\leq\gamma$ yielding
$c_{d}\leq\gamma^{2}-1$ as desired. ∎

The coefficient of variation is invariant under normalization. When
considering $c_{e}$ it can be useful to specify a given normalization. In some
cases we will assume that $||x||_{2}^{2}=1$ or we will assume $x_{\text{max}}$
(vis-a-vis $x_{\text{min}}$) is 1.

We have further shown the following.

###### Lemma 4

$c_{e}\leq\frac{n}{\lambda+1}-1$.

###### Proof.

Let $(\lambda,x)$ be the principal eigenpair of $G$ so that $||x||_{2}^{2}=1$.
Appealing to the Rayleigh quotient definition of the principal eigenvector we
have

$\lambda=2\sum_{uv\in E}x_{u}x_{v}.$

Note that

$||x||_{1}^{2}=\sum_{u,v\in V}x_{u}x_{v}\geq\left(2\sum_{uv\in
E}x_{u}x_{v}\right)+\sum_{u\in V}x_{u}^{2}+=\lambda+1.$

By Equation 1 we have

$c_{e}(G)=n\frac{||x||_{2}^{2}}{||x||_{1}^{2}}-1\leq\frac{n}{\lambda+1}-1.$

∎

The following was a desideratum of Lemma 3.

###### Lemma 5

$c_{d}(G)\leq(\Delta/\overline{d})-1$ where $\overline{d}$ is the average
degree.

##  3 Dispersion of Various Graph Families

We now consider the graph families listed in Table 1 in descending order.

###  3.1 The complete graph with an edge removed

In this section we consider $K_{n}-K_{2}$, the complete graph with an edge
removed.

###### Theorem 6

Let $G_{n}=K_{n}-\\{1,2\\}$ with $n>2$. Then

$\lim_{n\to\infty}\gamma(G_{n})=0,\;\lim_{n\to\infty}c_{e}(G_{n})=0,\;\text{
and }\lim_{n\to\infty}c_{d}(G_{n})=0.$

###### Proof.

Let $G_{n}=K_{n}-\\{1,2\\}$ with $n>2$ and let $(\lambda,x)$ be its principal
eigenpair.

By symmetry we have $a:=x_{1},x_{2}$ and $b:=x_{i}$ for $i>2$ so that the
eigenequations satisfy

$\displaystyle\lambda a$ $\displaystyle=(n-3)a+2b$ $\displaystyle\lambda b$
$\displaystyle=(n-2)a.$

Setting $b=1$ yields

$(n-2)a^{2}-(n-3)a-2=0$

so that

$a=\frac{(n-3)+\sqrt{n^{2}+2n-7}}{2(n-2)}.$

Note that

$x=\left(\left(\frac{(n-3)+\sqrt{n^{2}+2n-7}}{2(n-2)},2\right),(1,n-2)\right)$

We have that

$\lim_{n}\gamma(K_{n}-K_{2})=\lim_{n}a=1.$

As $\lambda=(n-2)a$ we appeal to Lemma 4 to conclude

$\lim_{n\to\infty}c_{e}\leq\lim_{n\to\infty}\frac{n}{\lambda+1}-1=\lim_{n\to\infty}\frac{n}{n}-1=0.$

Finally, whence $\Delta=n-1$ and $\delta=n-2$ we have from Lemma 5

$\lim_{n\to\infty}c_{d}\leq\lim_{n\to\infty}\frac{\Delta}{\delta}-1=\lim_{n\to\infty}\frac{n-1}{n-2}-1=0.$

∎

###  3.2 The complete tripartite graph

Let $K_{a,b,c}$ be the complete tripartite graph with clouds of size $a,b,c$.

###### Theorem 7

We have

$\lim\gamma(K_{1,n,n})=2,\lim c_{e}(K_{1,n,n})=0,\text{ and }\lim
c_{d}(K_{1,n,n})=0.$

###### Proof.

Consider $K_{1,n,n}$ and let $(\lambda,x)$ be its principal eigenpair. By
symmetry we have that $a:=x_{1}$ and $b:=x_{i}$ for $i>1$ so that

$x=((a,1),(b,2n)).$

Thus the eigenequations of $K_{1,n,n}$ are

$\displaystyle\lambda a$ $\displaystyle=2nb$ $\displaystyle\lambda b$
$\displaystyle=1+nb.$

Setting $a=1$ and solving for $b$ yields

$b=\frac{n+\sqrt{n^{2}+8n}}{4n}$

so that

$x=\left((1,1),\left(\frac{n+\sqrt{n^{2}+8n}}{4n},2n\right)\right)$

We have

$\lim_{n\to\infty}\gamma(K_{1,n,n})=\lim_{n\to\infty}\frac{4n}{n+\sqrt{n^{2}+8n}}=2.$

We further have

$||x||_{2}^{2}=1+2nb^{2}\text{ and }||x||_{1}^{2}=(1+2nb)^{2}$

which yields

$\lim_{n\to\infty}c_{e}(K_{1,n,n})=\lim_{n\to\infty}(2n+1)\frac{||x||_{2}^{2}}{||x||_{1}^{2}}-1=2n\left(\frac{n/2}{n^{2}}\right)-1=0.$

Moreover,

$d=((2n,1),(n+1,2n))$

implying

$||d||_{2}^{2}=(2n)^{2}+2n(n+1)^{2},||d||_{1}^{2}=(2n+2n(n+1))^{2}.$

It follows that

$\lim_{n\to\infty}c_{d}(K_{1,n,n})=\lim_{n\to\infty}(2n+1)\frac{||d||_{2}^{2}}{||d||_{1}^{2}}-1=2n\left(\frac{2n^{3}}{4n^{4}}\right)-1=0.$

∎

###  3.3 The complete split graph

Figure 1: The complete split graph $S(n,n)$ for $2\leq n\leq 5$.

We define the complete split graph to be a clique on $n$ vertices an
independent set with $m$ vertices, $S(n,m)=K_{n+m}-K_{m}$ [11, 14, 26]. A
drawing of $S(n,n)$ is given in Figure 1. There are several existing graph
structures related to $S(n,m)$. Observe that the complete split graph can be
seen as the union of a complete bipartite graph and a clique,
$S(n,m)=K_{n,m}\cup K_{n}$ where multiple edges are ignored. Note that
$S(1,m)=K_{1,m}$ is the star with $m$ rays and $S(2,m)$ is the agave graph as
described in [10]. Further $S(n,m)$ can be viewed as the _multicone_ of a
complete graph joined with isolated vertices (as in [27]) so that
$K_{n}\triangledown\overline{K}_{m}$ where $\overline{K}_{m}$ is the edgeless
graph on $m$ vertices.

###### Lemma 8

Let $(\lambda,x)$ be the principal eigenpair of $S(n,m)$ then

$x_{v}=\left\\{\begin{array}[]{lr}1&:v\leq n\\\
\frac{1-n+\sqrt{(n-1)^{2}+4nm}}{2m}&:v>n.\end{array}\right.$

Furthermore, under this normalization $x_{\text{max}}=1$.

###### Proof.

We have by symmetry that $a=x_{v}$ for $v\leq n$ and $b=x_{v}$ for $v>n$. The
eigenequations are of the form

$\displaystyle\lambda a$ $\displaystyle=(n-1)a+mb$ $\displaystyle\lambda b$
$\displaystyle=na.$

Setting $a=1$ and substituting the first eigenequation into the second yields

$mb^{2}+(n-1)b-n=0.$

Solving for $b$ gives the desired result.

By straight forward computation we find that

$\frac{1-n+\sqrt{(n-1)^{2}+4nm}}{2m}<1$

if and only if $m(m-1)>0$. Since $m>1$ the inequality is always satisfied. ∎

###### Theorem 9

Fix $k\geq 1$,

$\lim_{n\to\infty}\gamma(S(n,k\cdot n))=\frac{\sqrt{4k+1}+1}{2}.$

###### Proof.

From Lemma 8 we have that the principal ratio of $S(n,m)$ is

$\gamma(S(n,kn))=\frac{1}{b}=\frac{2kn}{1-n+\sqrt{(n-1)^{2}+4kn^{2}}}.$

We have then

$\lim_{n\to\infty}\gamma(S(n,kn))=\lim_{n\to\infty}\frac{2kn}{(\sqrt{4k+1}-1)n}=\frac{\sqrt{4k+1}+1}{2}.$

∎

###### Corollary 10

We have $\lim_{n\to\infty}\gamma(S(n,n))=\varphi$ is the golden ratio.

###### Theorem 11

Fix $k\geq 1$,

$\lim_{n\to\infty}c_{e}(S(n,kn))=\frac{k\left(\frac{\sqrt{4k+1}-1}{k}-2\right)^{2}}{(\sqrt{4k+1}+1)^{2}}.$

###### Proof.

Let $(\lambda,x)$ be the principal eigenpair of $S(n,m)$ as in Lemma 8.
Clearly

$\mu=\frac{n+mb}{n+m}$

and

$\sigma^{2}=\frac{(b-1)^{2}(nm^{2}+n^{2}m)}{(n+m)^{3}}.$

We have then

$c_{e}=\frac{\sigma^{2}}{\mu^{2}}=\frac{(b-1)^{2}(nm^{2}+n^{2}m)}{(n+m)(n+mb)^{2}}.$

Setting $m=kn$ yields

$c_{e}=\frac{(b-1)^{2}k}{(kb+1)^{2}}.$

From the proof of Theorem 9 we have

$\lim_{n\to\infty}b=\lim_{n\to\infty}\gamma(S(n,kn))^{-1}=\frac{2}{\sqrt{4k+1}+1}$

so that

$\lim_{n\to\infty}c_{e}(S(n,kn))=\lim_{n\to\infty}\frac{(b-1)^{2}k}{(kb+1)^{2}}=\frac{k\left(\frac{\sqrt{4k+1}-1}{k}-2\right)^{2}}{(\sqrt{4k+1}+1)^{2}}.$

∎

###### Theorem 12

Fix $k$ then

$\lim_{n\to\infty}c_{d}(S(n,kn))=\frac{k^{3}}{(2k+1)^{2}}.$

###### Proof.

Let $d$ be the degree vector of $S(n,m)$ so that

$d=((n+m-1,n),(n,m)).$

We have

$\mu=\frac{n^{2}+2nm-n}{n+m}$

and

$\sigma^{2}=\frac{(n(n+m-1-\mu)^{2}+m(n-\mu)^{2}}{n+m}=\frac{(m-1)^{2}(nm^{2}+n^{2}m)}{(n+m)^{3}}.$

We equate

$c_{d}(S(n,m)=\frac{\sigma^{2}}{\mu^{2}}=\frac{(m-1)^{2}(nm^{2}+n^{2}m)}{(n+m)(n^{2}+2nm-n)^{2}}$

substituting $m=kn$ yields

$c_{d}(S(n,kn)=\frac{kn^{2}(kn-1)^{2}}{(n^{2}(2k+1)-n)^{2}}.$

It follows that

$\lim_{n\to\infty}c_{d}(S(n,kn)=\frac{k^{3}}{(2k+1)^{2}}.$

∎

###  3.4 The kite graph

The kite graph (aka lollipop graph) $P_{m}K_{s}$ is formed by identifying the
last vertex of a path on $m$ vertices with a vertex from the complete graph on
$s$ vertices. Examples are given in Figure 2. Kite graphs appear frequently in
the literature of the principal ratio [5, 23]. We begin with a bound on the
spectral radius of the kite graph and an explicit formula for the principal
eigenvector of the kite graph as provided in [7].

Figure 2: $P_{4}K_{3},P_{4}K_{4}$ and $P_{4}K_{5}$.

###### Lemma 13

([7]) For $m\geq 2$ and $s\geq 3$,

$s-1+\frac{1}{s(s-1)}<\lambda(P_{m}\cdot K_{s})<s-1+\frac{1}{(s-1)^{2}}.$

We now show how the entries of the principal eigenvector of $P_{m}K_{s}$ can
be expressed in terms of the spectral radius.

###### Lemma 14

([7]) Let $\lambda$ be the greatest eigenvalue of $P_{m}K_{s}$ and let $x$ be
its principal eigenvector. Let $\sigma=(\lambda+\sqrt{\lambda-4})/2$ and
$\tau=\sigma^{-1}$ then

$x_{k}=\frac{\sigma^{k}-\tau^{k}}{\sigma-\tau}x_{1}\text{ for }1\leq k\leq m,$

and

$x_{k}=\frac{1}{s-1}\frac{\sigma^{m+1}-\tau^{m+1}}{\sigma-\tau}x_{1}\text{ for
}m+1\leq k\leq n.$

For simplicity we consider the kite whose path is of length 2 (i.e., $K_{n}$
with a pendant edge).

###### Theorem 15

Consider $P_{2}K_{n-1}$. We have

$\lim_{n\to\infty}\gamma(P_{2}K_{n-1})=\infty,\lim_{n\to\infty}c_{e}(P_{2}K_{n-1})=0,\lim_{n\to\infty}c_{d}(P_{2}K_{n-1})=0.$

###### Proof.

From Lemma 14 we have

$\gamma(P_{2}K_{n-1})=\frac{\sigma^{2}-\tau^{2}}{\sigma-\tau}=\sigma+\tau>\sigma.$

Appealing to Lemma 13 we find $\lambda>n-2$ so that $\sigma>(n-2)/2$ hence

$\lim\gamma(P_{2}K_{n-1})=\infty.$

Similarly, we have from Lemma 4 that

$c_{e}(P_{2}K_{n-1})\leq\frac{n}{\lambda+1}-1\leq\frac{n}{n-1}-1$

which yields $\lim c_{e}(P_{2}K_{n-1})=0$. Finally, we have that
$\Delta(P_{2}K_{n-1})=n-1$ and

$\overline{d}=\frac{n-1+(n-2)^{2}+1}{n}=\frac{n^{2}-3n+4}{n}$

appealing to Lemma 5

$\lim c_{d}(P_{2}K_{n-1})\leq\lim\frac{n(n-1)}{n^{2}-3n+4}-1=0.$

∎

###  3.5 A kite whose head is a regular graph

Let $G_{n}^{r}$ be an $r$-regular connected graph on $n$ labeled vertices.
Consider the graph $P_{m}G_{n}^{r}$ which is formed from identifying the
$m$-vertex of $P_{m}$ with the $1$-vertex in $G_{n}^{r}$. Two examples are
given in Figure 3.

Figure 3: $P_{4}C_{5}$ and $P_{5}K_{3,3}$.

###### Theorem 16

We have

$\lim_{n\to\infty}c_{d}(P_{n}G_{n}^{r})=\left(\frac{r-2}{r+2}\right)^{2}.$

###### Proof.

By construction,

$d=((1,1),(2,n-2),(r,n-1),(r+1,1))$

so that

$||d||_{2}^{2}=r^{2}n+4n+2r-6\text{ and
}||d||_{1}^{2}=r^{2}n^{2}+4rn^{2}+4n^{2}-4rn-8n+4.$

We have by Equation 1

$\displaystyle\lim_{n\to\infty}c_{d}(P_{n}G_{n}^{r})$
$\displaystyle=\lim_{n\to\infty}\frac{(2n-1)(r^{2}n+4n+2r-6)}{r^{2}n^{2}+4rn^{2}+4n^{2}-4rn-8n+4}-1$
$\displaystyle=\frac{2(r^{2}+4)}{r^{2}+4r+4}-1=\left(\frac{r-2}{r+2}\right)^{2}.$

∎

We make use of the following Theorem.

###### Theorem 17

[7] Let $G$ be a connected graph of order $n$ with spectral radius $\lambda>2$
and principal eigenvector $x$. Let $d$ be the shortest distance from a vertex
on which $x$ is maximum to a vertex on which it is minimum. Then

$\gamma(G)\leq\frac{\sigma^{d+1}-\tau^{d+1}}{\sigma-\tau}$

where $\sigma=\frac{1}{2}(\lambda+\sqrt{\lambda^{2}-4})$ and
$\tau=\sigma^{-1}$. Equality is attained if and only if $G$ is regular or
there is an induced path of length $d>0$ whose endpoints index $x_{min}$ and
$x_{max}$ and the degrees of the endpoints are $1$ and $3$ or more,
respectively, while all other vertices of the path have degree 2 in $G$.

###### Theorem 18

Fix $r\geq 4$. Then

$\lim_{n\to\infty}\gamma(P_{n}G_{n}^{r})=\infty.$

###### Proof.

Let $(\lambda,x)$ be the principal eigenpair of $P_{n}G_{n}^{r}$. Since
$G_{n}^{r}$ is an induced subgraph of $P_{n}G_{n}^{r}$ we have that
$\lambda\geq r-1$. Clearly $x_{\text{min}}=x_{1}$ and $x_{\text{max}}=x_{n}$.
As $P_{n}G_{n}^{r}$ satisfies the conditions of Theorem 17 we have that

$\gamma(P_{n}G_{n}^{r})=\frac{\sigma^{n+1}-\tau^{n+1}}{\sigma-\tau}\geq\sigma^{n}.$

Whence $r\geq 4$ we have that $\sigma>1$ so that

$\lim_{n\to\infty}\gamma(P_{n}G_{n}^{r})=\infty.$

∎

###  3.6 The star

We now consider the star graph $K_{1,n}$.

###### Theorem 19

We have

$\lim_{n\to\infty}\gamma(K_{1,n})^{2}-1=\infty,\;\lim_{n\to\infty}c_{e}(K_{1,n})=1,\;\text{
and }\lim_{n\to\infty}c_{d}(K_{1,n})=\infty.$

###### Proof.

Let $K_{1,n}$ denote the star with $n$ rays. It is well known that

$x=((1,1),(n^{-1/2},n))\text{ and }d=((n,1),(1,n)).$

Clearly

$\lim_{n\to\infty}\gamma(K_{1,n})^{2}-1=\lim_{n\to\infty}n-1=\infty.$

We have that $||d||_{1}^{2}=4n^{2}$ and $||d||_{2}^{2}=n^{2}+n$ so that

$c_{d}(K_{1,n})=(n+1)\frac{||d||_{2}^{2}}{||d||_{1}^{2}}-1=\frac{n^{3}+2n^{2}+n}{4n^{2}}-1$

and $\lim_{n}c_{d}(K_{1,n})=\infty$.

Moreover,

$||x||_{1}^{2}=(1+n^{-1/2})^{2}\text{ and }||x||_{2}^{2}=2.$

As such

$c_{e}(K_{1,n})=(n+1)\frac{||x||_{2}^{2}}{||x||_{1}^{2}}-1=\frac{2(n+1)}{(n^{1/2}+1)^{2}}-1$

so that $\lim_{n\to\infty}c_{e}(K_{1,n})=1$. ∎

###  3.7 Cartesian powers of a graph

Given two graphs $A$ and $B$, the Cartesian product $A\square B$ is the graph
on $|V(A)||V(B)|$ vertices where $V(A\square B)=\\{(a,b):a\in V(A),b\in
V(B)\\}$ and $(a,b)$ is incident to $(a^{\prime},b^{\prime})$ if and only if
$(a,a^{\prime})\in E(A)$ and $b=b^{\prime}$ or $(b,b^{\prime})\in E(B)$ and
$a=a^{\prime}$. An example is given in Figure 4. We begin by presenting a
folkloric result.

Figure 4: A randomly generated BA(10,1) graph [2], $P_{3}$, and their
Cartesian product, respectively.

###### Lemma 20

Let $(\lambda,x)$ and $(\rho,y)$ be the principal eigenvectors of $A$ and $B$,
respectively. Let $z\in\mathbb{R}^{|A||B|}$ where $z=x\otimes y$ that is
$z_{ab}=x_{a}y_{b}$. Then $(\lambda+\rho,z)$ is the principal eigenpair of
$A\square B$.

###### Proof.

We have

$\displaystyle(A\square B)z_{ab}$ $\displaystyle=\left(\sum_{a^{\prime}\in
N_{A}(a)}z_{a^{\prime}b}+\sum_{b^{\prime}\in
N_{B}(b)}a_{ab^{\prime}}\right)z_{ab}$ $\displaystyle=\sum_{a^{\prime}\in
N_{A}(a)}z_{a^{\prime}b}z_{ab}+\sum_{b^{\prime}\in
N_{B}(b)}z_{ab^{\prime}}z_{ab}$ $\displaystyle=\sum_{a^{\prime}\in
N_{A}(a)}(x_{a^{\prime}}y_{b})(x_{a}y_{b})+\sum_{b^{\prime}\in
N_{B}(b)}(x_{a}y_{b^{\prime}})(x_{a}y_{b})$
$\displaystyle=y_{b}\left(\sum_{a^{\prime}\in
N_{A}(a)}x_{a^{\prime}}\right)x_{a}+x_{a}\left(\sum_{b^{\prime}\in
N_{B}(b)}y_{b^{\prime}}\right)y_{b}$
$\displaystyle=y_{b}Ax_{a}+x_{a}By_{b}=y_{b}(\lambda x_{a})+x_{a}(\rho y_{b})$
$\displaystyle=(\lambda+\rho)x_{a}y_{b}=(\lambda+\rho)z_{ab}.$

∎

We show that $c_{e}(G^{\square k})$ has the following form.

###### Lemma 21

We have

$c_{e}(A\square B)=c_{e}(A)c_{e}(B)+c_{e}(A)+c_{e}(B).$

###### Proof.

Let $(\lambda,x)$ and $(\rho,y)$ be the principal eigenpair of $A$ and $B$,
respectively. From Lemma 20 we have that $z=x\otimes y$ is the principal
eigenvector of $A\square B$. Note that

$\frac{||z||_{2}^{2}}{||z||_{1}^{2}}=\frac{\sum(x_{a}y_{b})^{2}}{(\sum
x_{a}y_{b})^{2}}=\frac{(\sum x_{a}^{2})(\sum y_{b}^{2})}{(\sum x_{a})^{2}(\sum
y_{b})^{2}}=\frac{||x||_{2}^{2}||y||_{2}^{2}}{||x||_{1}^{2}||y||_{1}^{2}}.$

So that

$\displaystyle c_{e}(A\square B)$
$\displaystyle=|V(A)||V(B)|\left(\frac{||x||_{2}^{2}||y||_{2}^{2}}{||x||_{1}^{2}||y||_{1}^{2}}\right)-1$
$\displaystyle=\left(|V(A)|\frac{||x||_{2}^{2}}{||x||_{1}^{2}}\right)\left(|V(B)|\frac{||y||_{2}^{2}}{||y||_{1}^{2}}\right)-1$
$\displaystyle=(c_{e}(A)+1)(c_{e}(B)+1)-1$
$\displaystyle=c_{e}(A)c_{e}(B)+c_{e}(A)+c_{e}(B).$

∎

We now consider $c_{d}(G^{\square k})$. We adopt the notation $A+B=\\{a+b:a\in
A,b\in B\\}$ to be the multiset sum. For convenience, we write
$kA=\sum_{i=1}^{k}A$. Note that $|kA|=|A|^{k}$. We make use of the following
facts.

###### Lemma 22

Let $A\subset\mathbb{Z}^{+}$ be a multiset. Then

$||kA||_{1}=k|A|^{k-1}||A||_{1}.$

###### Proof.

The case of $k=1$ is trivial. Proceeding by induction we find

$\displaystyle||kA||_{1}$
$\displaystyle=\sum_{i_{1}}\dots\sum_{i_{k}}(a_{i_{1}}+\dots+a_{i_{k}})$
$\displaystyle=\sum_{i_{1}}\dots\sum_{i_{k-1}}\left(|A|(a_{i_{1}}+\cdots+a_{k-1})+||A||_{1}\right)$
$\displaystyle=|A|\left(\sum_{i_{1}}\dots\sum_{i_{k-1}}a_{i_{1}}+\cdots+a_{k-1}\right)+|A|^{k-1}||A||_{1}$
$\displaystyle=|A|((k-1)|A|^{k-2}||A||_{1})+A^{k-1}||A||_{1}=k|A|^{k-1}||A||_{1}.$

∎

###### Lemma 23

Let $A\subset\mathbb{Z}^{+}$ be a multiset. Then

$||kA||_{2}^{2}=k|A|^{k-2}(|A|\cdot||A||_{2}^{2}+(k-1)||A||_{1}^{2})$

###### Proof.

The case of $k=1,2,3$ are clear. We further have that

$\displaystyle||kA||_{2}^{2}$
$\displaystyle=\sum_{i_{1}}\dots\sum_{i_{k}}(a_{i_{1}}+\dots+a_{i_{k}})^{2}$
$\displaystyle=\sum_{i_{1}}\dots\sum_{i_{k}}\left((a_{i_{1}}+\dots+a_{i_{k-1}})^{2}+a_{i_{k}}(2(a_{i_{1}}+\dots+a_{i_{k-1}})+a_{i_{k}})\right)$
$\displaystyle=\left(\sum_{i_{1}}\dots\sum_{i_{k}}(a_{i_{1}}+\dots+a_{i_{k-1}})^{2}\right)+\left(\sum_{i_{1}}\dots\sum_{i_{k}}a_{i_{k}}(2(a_{i_{1}}+\dots+a_{i_{k-1}})+a_{i_{k}})\right)$
$\displaystyle=|A|\cdot||(k-1)A||_{2}^{2}+\left(2||A||_{1}||(k-1)A||_{1}+|A|^{k-1}||A||_{2}^{2}\right)$
$\displaystyle=|A|\big{(}(k-1)|A|^{k-3}(|A|||A||_{2}^{2}+(k-2)||A||_{1}^{2}\big{)}$
$\displaystyle=k|A|^{k-1}||A||_{2}^{2}+k(k-1)|A|^{k-2}||A||_{1}^{2}$
$\displaystyle=k|A|^{k-2}(|A|\cdot||A||_{2}^{2}+(k-1)||A||_{1}^{2}).$

∎

We now find a simple equation for $c_{d}(G^{\square k})$.

###### Lemma 24

For a graph $G$,

$c_{d}(G^{\square k})=\frac{c_{d}(G)}{k}.$

###### Proof.

We have that

$\displaystyle c_{d}(G^{\square k})$
$\displaystyle=|kd|\frac{||kd||_{2}^{2}}{||kd||_{1}^{2}}-1$
$\displaystyle=|d|^{k}\left(\frac{k|d|^{k-2}(|d|\cdot||d||_{2}^{2}+(k-1)||d||_{1}^{2})}{(k|d|^{k-1}||d||_{1})^{2}}\right)-1$
$\displaystyle=\frac{|d|\cdot||d||_{2}^{2}+(k-1)||d||_{1}^{2}}{k||d||_{1}^{2}}-1$
$\displaystyle=\frac{|d|\cdot||d||_{2}^{2}-||d||_{1}^{2}}{k||d||_{1}^{2}}=\frac{1}{k}\left(|d|\frac{||d||_{2}^{2}}{||d||_{1}^{2}}-1\right)$
$\displaystyle=\frac{c_{d}(G)}{k}.$

∎

###### Theorem 25

Let $G$ be a non-regular graph. Then

$\lim_{k\to\infty}\gamma^{2}(G^{\square
k})-1=\infty,\lim_{k\to\infty}c_{e}(G^{\square k})=\infty,\text{ and
}\lim_{k\to\infty}c_{d}(G^{\square k})=0.$

###### Proof.

Let $(\lambda,x)$ be the principal eigenpair of $G$. By Lemma 20,
$\gamma=x_{\text{max}}/x_{\text{min}}$ and $\gamma(G^{\square
k})=(x_{\text{max}}/x_{\text{min}})^{k}$. Further since $G$ is non-regular we
have that $\gamma(G)>1$ from which it follows

$\lim_{k\to\infty}\gamma^{2}(G^{\square k})-1=\infty.$

The remaining two limits follow from Lemmas 21 and 24, respectively. ∎

##  4 Extremal Graphs

We conclude with conjectures concerning the extremal graphs of $c_{e}$ and
$c_{d}$.

The kite graph (aka lollipop graph) is the extremal graph for the maximum
hitting time of a graph as well as the maximum principal ratio for graphs on
$n$ vertices [5, 23]. In each case, the head size (i.e., $s$ in $P_{m}K_{s}$)
is a function of $n$. The maximum hitting time occurs when $s\approx(2n+1)/3$
while maximising the principal ratio requires $s\approx n/\log n$. We
conjecture that a kite graph maximises $c_{e}$ when the head size is precisely
$s=4$.

###### Conjecture 1

(“Four’s a Crowd”) The connected graph which achieves the maximum of $c_{e}$
on $n\geq 6$ vertices is $P_{n-3}K_{4}$.

We also make the following conjecture about $c_{d}$.

###### Conjecture 2

The connected graph which achieves the maximum of $c_{d}$ on $n$ vertices is
the star $K_{1,n-1}$.

Consider the irregularity measure

$\Gamma(G):=\frac{c_{e}(G)-c_{d}(G)}{\gamma^{2}(G)}$

which satisfies $-1\leq\Gamma(G)\leq 1$. We have evidence to suggest that
$|\Gamma|<1$. Consider the following.

###### Theorem 26

$\lim_{n\to\infty}\Gamma(K_{1,n})=-1/4.$

Moreover,

$\lim_{k\to\infty}\lim_{n\to\infty}\Gamma(S(k,nk))=-1/4.$

###### Proof.

Let $(\lambda,x)$ be the principal eigenpair of $K_{1,n}$. Recall from Lemma
19 that $\gamma=\sqrt{n}$. We have then

$\lim_{n\to\infty}\Gamma(K_{1,n})=\lim_{n\to\infty}\frac{\left(\frac{2n}{n}-1\right)-\left(\frac{n^{3}}{4n^{2}}-1\right)}{n}=-1/4.$

Moreover we have

$\lim_{k\to\infty}\lim_{n\to\infty}\Gamma(S(k,nk)=\lim_{k\to\infty}\frac{\frac{k\left(\frac{\sqrt{4k+1}-1}{k}-2\right)^{2}}{(\sqrt{4k+1}+1)^{2}}-\frac{k^{3}}{(2k+1)^{2}}}{\left(\frac{\sqrt{4k+1}+1}{2}\right)^{2}}=\lim_{k\to\infty}\frac{\frac{4}{4k}-\frac{k}{4}}{\frac{4k}{4}}=-1/4.$

∎

Based on experimental evidence we make the following conjecture.

###### Conjecture 3

$\Gamma(G)\geq-1/4$ and the star is extremal.

##  5 Properties of Complete Split Graphs

We showed that the complete split graph $S(n,m)$ has several interesting
properties. Firstly, the principal ratio, eigenvector dispersion, and degree
dispersion of $S(n,nk)$ all converge to a positive number for fixed $k$. In
the case when $k=1$, we showed that the principal ratio of $S(n,n)$ converges
to $\varphi$, the golden ratio. We conclude by showing that the average
clustering coefficient and transitivity diverge for $S(n,kn)$ as we take $n$
and $k$ to be arbitrarily large. To the best of our knowledge this is the
third such graph family to have this property [9] (c.f., the friendship (aka
windmill, $n$-fan) graph [4] and the agave graph [10]). Notably, this property
was observed in brokerage networks formed by illicit marketplaces which are
closely approximated by complete split graphs [22, 24, 25].

The Watts-Strogatz clustering coefficient (see [29]) of a vertex $i$ is a
measure of the transitivity of local connections in a network

$C_{i}=\frac{2t_{i}}{d_{i}(d_{i}-1)}$

where $t_{i}$ is the number of triangles which contain $i$. The average Watts-
Strogatz clustering coefficient of a graph $G$ is defined

$\overline{C}=\frac{1}{n}\sum_{i=1}^{n}C_{i}.$

Finally the transitivity of a graph (see [17, 28]) is defined to be

$T=\frac{3(\\#\text{ of triangles})}{\sum_{i=1}^{n}\binom{d_{i}}{2}}.$

###### Lemma 27

Consider $S(n,m)$. Let $u\in K_{n}$ and $v\notin K_{n}$. Then

$C_{u}=\frac{(n-1)(n-2)+2(n-1)m}{(n+m-1)(n+m-2)}\text{ and }C_{v}=1$

so that

$\overline{C}=\frac{m+\frac{{\left({\left(n-1\right)}{\left(n-2\right)}+2\,{\left(n-1\right)}m\right)}n}{{\left(n+m-1\right)}{\left(n+m-2\right)}}}{n+m}.$

Moreover,

$T=\frac{{\left(n-1\right)}{\left(n-2\right)}n+3\,{\left(n-1\right)}nm}{{\left(n+m-1\right)}{\left(n+m-2\right)}n+{\left(n-1\right)}nm}.$

###### Proof.

We have that

$C_{u}=\frac{2t_{u}}{d_{u}(d_{u}-1)}=\frac{2\left(\binom{n-1}{2}+\binom{n-1}{1}\binom{m}{1}\right)}{(n+m-1)(n+m-2)}=\frac{(n-1)(n-2)+2(n-1)m}{(n+m-1)(n+m-2)}$

and

$C_{v}=\frac{2t_{v}}{d_{v}(d_{v}-1)}=\frac{2\binom{n}{2}}{n(n-1)}=1.$

The formula for $\overline{C}$ follows by straight forward computation.
Moreover, our equation for $T$ follows naturally from the fact that the number
of triangles in $S(n,m)$ is

$\binom{n}{3}+\binom{n}{2}\binom{m}{1}$

and

$\sum_{i}\binom{d_{i}}{2}=n\binom{n+m-1}{2}+m\binom{n}{2}.$

∎

###### Theorem 28

$\lim_{m\to\infty}\overline{C}(S(n,m))=1\text{ and
}\lim_{m\to\infty}T(S(n,m))=0$

and

$\lim_{k\to\infty}\lim_{n\to\infty}\overline{C}(S(n,kn))=1\text{ and
}\lim_{k\to\infty}\lim_{n\to\infty}T(S(n,kn))=0.$

###### Proof.

From Lemma 27 we have

$\lim_{m\to\infty}\overline{C}(S(n,m))=\lim_{n\to\infty}\frac{m+\frac{2n^{2}m}{m^{2}}}{m}=1$

and

$\lim_{m\to\infty}T(S(n,m))=\lim_{m\to\infty}\frac{3n^{2}m}{m^{2}}=0.$

Now let $m=nk$. By substitution we find

$\overline{C}(S(n,nk))=\frac{kn+\frac{{\left(2\,k{\left(n-1\right)}n+{\left(n-1\right)}{\left(n-2\right)}\right)}n}{{\left(kn+n-1\right)}{\left(kn+n-2\right)}}}{kn+n}.$

and

$T(S(n,nk))=\frac{3\,k{\left(n-1\right)}n^{2}+{\left(n-1\right)}{\left(n-2\right)}n}{k{\left(n-1\right)}n^{2}+{\left(kn+n-1\right)}{\left(kn+n-2\right)}n}$

By straight forward computation we find

$\lim_{n\to\infty}\overline{C}(S(n,kn))=\frac{k^{3}+2\,k^{2}+3\,k+1}{k^{3}+3\,k^{2}+3\,k+1}\text{
and }\lim_{n\to\infty}T(S(n,kn))=\frac{3\,k+1}{k^{2}+3\,k+1}.$

so that

$\lim_{k\to\infty}\lim_{n\to\infty}\overline{C}(S(n,kn))=1\text{ and
}\lim_{k\to\infty}\lim_{n\to\infty}T(S(n,kn))=0.$

as desired. ∎

## References

  * [1] Anthony B Atkinson et al.  On the measurement of inequality.  Journal of economic theory, 2(3):244–263, 1970.
  * [2] Albert-László Barabási and Réka Albert.  Emergence of scaling in random networks.  science, 286(5439):509–512, 1999.
  * [3] Francis K Bell.  A note on the irregularity of graphs.  Linear Algebra and its Applications, 161:45–54, 1992.
  * [4] Béla Bollobás and Oliver M Riordan.  Mathematical results on scale-free random graphs.  Handbook of graphs and networks: from the genome to the internet, pages 1–34, 2003.
  * [5] Graham Brightwell and Peter Winkler.  Maximum hitting time for random walks on graphs.  Random Structures & Algorithms, 1(3):263–276, 1990.
  * [6] Fan Chung, Linyuan Lu, and Van Vu.  Eigenvalues of random power law graphs.  Annals of Combinatorics, 7(1):21–33, 2003.
  * [7] Sebastian Cioaba and David Gregory.  Principal eigenvectors of irregular graphs.  The Electronic Journal of Linear Algebra, 16, 2007.
  * [8] WA Edelstein, GH Glover, CJ Hardy, and RW Redington.  The intrinsic signal-to-noise ratio in nmr imaging.  Magnetic resonance in medicine, 3(4):604–618, 1986.
  * [9] Ernesto Estrada.  When local and global clustering of networks diverge.  Linear Algebra and its Applications, 488:249–263, 2016.
  * [10] Ernesto Estrada and Eusebio Vargas-Estrada.  Distance-sum heterogeneity in graphs and complex networks.  Applied Mathematics and Computation, 218(21):10393–10405, 2012\.
  * [11] Stéphane Foldes and Peter L Hammer.  Split graphs having dilworth number two.  Canadian Journal of Mathematics, 29(3):666–672, 1977.
  * [12] Will Gragido, Johnl Pirc, Nick Selby, and Daniel Molina.  Chapter 4 - signal-to-noise ratio.  In Will Gragido, Johnl Pirc, Nick Selby, and Daniel Molina, editors, Blackhatonomics, pages 45 – 55. Syngress, Boston, 2013.
  * [13] Frank Ephraim Grubbs.  Statistical measures of accuracy for riflemen and missile engineers.  FE Grubbs, 1991.
  * [14] Peter L Hammer and Bruno Simeone.  The splittance of a graph.  Combinatorica, 1(3):275–284, 1981.
  * [15] David I Hoult and RE Richards.  The signal-to-noise ratio of the nuclear magnetic resonance experiment.  Journal of Magnetic Resonance (1969), 24(1):71–85, 1976.
  * [16] Ravi Kumar, P Ragbavan, Sridhar Rajagopalan, and Andrew Tomkins.  The web and social networks.  Computer, 35(11):32–36, 2002.
  * [17] Mark EJ Newman.  The structure of scientific collaboration networks.  Proceedings of the national academy of sciences, 98(2):404–409, 2001.
  * [18] Romualdo Pastor-Satorras and Alessandro Vespignani.  Epidemic spreading in scale-free networks.  Physical review letters, 86(14):3200, 2001.
  * [19] Albert Rose.  Vision: human and electronic.  Springer Science & Business Media, 2013.
  * [20] Claude Elwood Shannon.  Communication in the presence of noise.  Proceedings of the IRE, 37(1):10–21, 1949.
  * [21] Orit Shechtman.  The coefficient of variation as an index of measurement reliability.  In Methods of clinical epidemiology, pages 39–49. Springer, 2013\.
  * [22] Paolo Spagnoletti, Federica Ceci, and Bendik Bygstad.  Online black-markets: An investigation of a digital infrastructure in the dark.  Information Systems Frontiers, pages 1–16, 2021.
  * [23] Michael Tait and Josh Tobin.  Characterizing graphs of maximum principal ratio.  The Electronic Journal of Linear Algebra, 34:61–70, 2018.
  * [24] Felipe Thomaz.  The digital and physical footprint of dark net markets.  Journal of International Marketing, 28(1):66–80, 2020.
  * [25] Felipe Thomaz and John Hulland.  Abnormal structure of digital black markets.  In preparation., 2022.
  * [26] Regina I Tyshkevich and Arkady A Chernyak.  Canonical partition of a graph defined by the degrees of its vertices.  Isv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk, 5:14–26, 1979.
  * [27] Jianfeng Wang, Haixing Zhao, and Qiongxiang Huang.  Spectral characterization of multicone graphs.  Czechoslovak Mathematical Journal, 62(1):117–126, 2012.
  * [28] Stanley Wasserman, Katherine Faust, et al.  Social network analysis: Methods and applications.  1994\.
  * [29] Duncan J Watts and Steven H Strogatz.  Collective dynamics of ‘small-world’networks.  nature, 393(6684):440–442, 1998.
  * [30] Xiao-Dong Zhang.  Eigenvectors and eigenvalues of non-regular graphs.  Linear Algebra and its Applications, 409:79–86, 2005.