# Non-Terrestrial Network (NTN): a Novel Alternate Fractional Programming for
the Downlink Channels Power Allocation

Mahfuzur Rahman, Zoheb Hassan, Jeffrey H. Reed, and Lingjia Liu M. Rahman, J.
H. Reed, L. Liu are with Wireless@Virginia Tech, Bradley Department of
Electrical and Computer Engineering, Virginia Tech. Z. Hassan is with the
Electrical and Computer Engineering Department, Université Laval, QC, Canada.
This work was funded in part by U.S. National Science Foundation (NSF) under
grant CNS-2148212.

###### Abstract

Non-terrestrial network (NTN) communication has garnered considerable
attention from government entities, industries, and academia in recent times.
NTN networks encompass a variety of systems, including Low Earth Orbit (LEO)
satellites, Medium Earth Orbit (MEO) satellites, Geostationary Earth Orbit
(GEO) satellites, High Altitude Platforms (HAPS), and Low Altitude Platforms
(LAPS). Furthermore, the deployment of high-throughput satellites (HTS/VHTS)
in the GEO space has gained momentum. While LEO and MEO satellites offer
advantages such as low latency and reduced launching costs compared to GEO
satellites, this study focuses on GEO satellites due to their stationary
nature and broader coverage. In traditional cellular networks, each user
equipment (UE) is allocated at least one resource block (RB), which is not
shared with other UEs. However, in NTN communications, where the coverage area
is extensive, dedicating an RB to only one UE is an inefficient utilization of
radio resources. To address this challenge, fractional programming (FP),
cognitive radio, and rate splitting multiple access (RSMA) are existing
technologies that enable multiple UEs to share the same RB, thereby enhancing
spectral and power efficiency. This paper aims to maximize spectral
efficiency, average RBG rate, and sum rate for GEO satellite systems. However,
achieving this objective involves dealing with a non-convex, NP-hard problem,
as it requires the logarithmic sum of different fractions. Finding a global
solution to such an NP-hard problem presents significant challenges. This
paper introduces a novel alternate fractional programming algorithm
specifically designed to tackle these complex NP-hard problems in the context
of GEO NTN cellular networks. By employing this innovative approach, the study
seeks to contribute to the optimization of NTN communication systems, enabling
efficient resource allocation and improved network performance.

###### Index Terms:

5G, 6G, Terrestrial Network (TN), Non-Terrestrial Network (NTN), Enhanced
mobile broadband (eMBB), ultra-reliable low latency communication (URLLC),
Power allocation, Fractional Programming (FP).

##  I Background and Motivation

###  I-A Introduction

The widespread deployment of commercial 5G networks has already had a
transformative impact on our lives. Researchers from both academia and
industries are now actively directing their attention towards the development
of the next-generation cellular technology, 6G [1, 2]. As the number of
cellular data users continues to surge, meeting the demands of these users and
catering to their diverse data requirements has become crucial, making the
deployment of 5G and beyond imperative. The 5G wireless system is designed to
support a wide range of use cases, including Enhanced Mobile Broadband (eMBB),
Ultra-Reliable Low Latency Communication (uRLLC), and Massive Machine Type
Communication (mMTC) [3]. In 3GPP TR Release 17, [4], 3GPP has provided
guidelines on the Technical Specification for Narrow-Band Internet of Things
(NB-IoT) / enhanced Machine Type Communication (eMTC) to facilitate the
operation of Non-Terrestrial Networks (NTN). However, to effectively
accommodate eMBB traffic everywhere, the deployment of 5G networks
necessitates the implementation of 5G through the use of the NTN
infrastructure.

###  I-B Non-Terrestrial Network

The Non-Terrestrial Network (NTN) offers a significantly wider coverage
footprint compared to terrestrial networks. The coverage range of non-
geostationary satellites, such as Medium Earth Orbit (MEO) and Low Earth Orbit
(LEO) satellites, can extend from 100 meters to 500 kilometers, while Geo-
Satellites can provide even better coverage ranging from 200 kilometers to
1000 kilometers [5, 6]. The expansive coverage of NTN 5G enables the provision
of cellular network connectivity in areas that traditional terrestrial
networks cannot reach to such an extent. Non-terrestrial 5G can be deployed in
different configurations based on specific use cases. In situations where
latency is not a critical factor and delay can be tolerated, Non-Terrestrial
5G can be implemented using the Bent Pipe Transparent payload, both with and
without a Relay Node. On the other hand, for delay-sensitive applications
requiring Ultra Low Latency Reliable Communication (uLLRC), Non-Terrestrial
5G/6G can be deployed using the Regenerative Payload, again with or without a
Relay Node. In scenarios involving high-speed trains or airplanes, these
vehicles can serve as the relay node for Non-Terrestrial 5G/6G deployment.

###  I-C NTN Use Cases and Motivation

The impact of Non-Terrestrial Cellular Networks on various sectors, including
general cellular usage, emergency services, disaster relief, maritime
operations, US government and defense, transportation, energy, aviation,
autonomous systems, and healthcare, has already begun to revolutionize our
lives. Key players such as SpaceX Starlink, Amazon project Kuiper, Hughes, and
Iridium are fiercely competing in the race to dominate the market. SpaceX has
already launched more than 4000 Low Earth Orbit (LEO) satellites, providing
global broadband connectivity, with plans to launch an additional 12000 LEO
satellites in the near future. This number may further increase to a
staggering 42000 LEO satellites in the coming years [7]. Similarly, Amazon’s
project Kuiper aims to deploy 3236 LEO satellites to deliver fast, cost-
effective, and reliable broadband services to underserved communities
worldwide [8]. Hughes, with a significant presence in North and South America,
offers services through both GEO and LEO satellites. Their Jupiter series GEO
satellites provide a capacity of 200 Gbps, and they have plans to launch the
next-generation Jupiter GEO satellite (XXIV) in the first half of 2023, which
alone will provide a capacity of 500 Gbps [9]. Considering the wide range of
applications and the guidelines provided in 3GPP Release 17 [10], and Release
16 [6, 5] have motivated us to explore the NTN cellular domain.

##  II Related Research and Contribution

###  II-A Fractional programming

Fractional programming (FP) is an essential branch of optimization techniques
that deals with objective functions containing ratio terms [11]. In wireless
communication systems, the data rate is often calculated using the logarithm
of the signal-to-interference-plus-noise ratio (SINR), denoted as
$log_{2}(1+SINR)$. As wireless systems involve multiple SINR terms, solving
optimization problems with these ratios requires the application of Fractional
Programming (FP). However, such problems are known to be Non-Polynomial
(NP)-hard, making them challenging to solve. FP techniques have proven
valuable in addressing power control, energy efficiency optimization, and
beamforming challenges within the communication domain [12].

The use of fractional programming and related optimization techniques has
demonstrated their effectiveness and applicability across various domains,
including wireless communication, mobile edge computing, and unmanned aerial
vehicles. These techniques provide valuable tools for solving complex
optimization problems and enable the efficient allocation of resources in the
pursuit of improved performance and cost-effectiveness.

###  II-B Current research on NTN

In their work [13, 14], researchers provide a comprehensive overview of the
current Non-Terrestrial Network (NTN) standard and highlight the challenges
associated with integrating NR 5G with satellite access. In [15] the authors
present detailed analysis of the space-air-ground integrated network (SAGIN),
restricted and uneven allocation of computational and communication resources
hinders the ability to provide reliable quality-of-service (QoS) assurances
for particular types of traffic. In [16] the authors aim to reduce the overall
energy usage of user equipment (UEs) through a comprehensive optimization
approach. This approach encompasses optimizing user associations, adjusting
uplink power levels, managing channel allocations, distributing computation
capacities, and determining the three-dimensional placement of unmanned aerial
vehicles (UAVs). Researchers focus on the Ka-band, which supports a maximum
frequency offset of 66 kHz through the use of higher sub-carrier spacing
(SCS). Higher SCS values result in shorter symbol durations, necessitating
adjustments in the timing requirements for successful Random Access (RA)
procedures. The performance analysis of RA procedures for NTN NB-IoT is
investigated in the study conducted by the authors in [17]. They find that the
standard periodicities of 40 ms and 80 ms are not suitable for RA procedures
in NTN due to its large coverage footprint. Instead, an extra-large
periodicity of 1280 ms is required, which leads to a reduction in the number
of RA occasions. In [18], the authors employ Software-defined radios (SDR)
B210 and Raspberry Pi4 to emulate an NTN network. They utilize a cubesat
constellation for data collection pertaining to IoT services for NTN mMTC
(massive Machine Type Communication). This experimental setup allows for
valuable insights into the performance and behavior of NTN systems.
Investigating the interference between Terrestrial Networks (TN) and Non-
Terrestrial Networks (NTN), Lee et al. examine the reverse pairing scenario in
their work [19].

###  II-C Contribution

In this work, we make significant contributions to the performance analysis of
Non-Terrestrial Network (NTN) cellular networks, focusing on power allocation
techniques. Our contributions can be summarized as follows: First, we
introduce a novel alternate Fractional Programming algorithm for power
allocation in the NTN downlink channels. By comparing the network performance
in different scenarios, we demonstrate that our algorithm outperforms
conventional approaches [12]. Second, we extend the application of Fractional
Programming and WMMSE (Weighted Minimum Mean Square Error) Power Allocation
techniques, which are widely used in Terrestrial networks, to the NTN domain.
This marks the first introduction of these power allocation techniques in the
context of NTN networks. Third, we conduct benchmark performance analysis for
both Ka-band and S-band frequencies in the NTN network. Our analysis covers
both single-spot beam (SSB) and multi-spot beam (MSB) scenarios, considering
various performance metrics. Specifically, we evaluate the spectral
efficiency, average rate per RBG (Resource Block Group), and sum rate in
different scenarios. Notably, our work represents the first benchmark
performance analysis conducted for NTN networks, providing valuable insights
into the network’s capabilities and performance characteristics.

##  III System Model

###  III-A System Overview

Figure 1: Non-Terrestrial Network Architecture

We consider a GEO satellite that can operate both in single beam and multi
beams operation and serves the ground UEs as shown in Fig 1. The service link
between UEs and the Satellite is based on the 3GPP protocol stack whereas the
feeder link between the satellite and the gateway is based on the satellite
DVB-S2X protocol.

On-board Non-Terrestrial Network (NTN) gNB serves a set of U ground users
group = $\\{{ug_{1},ug_{2},ug_{3},....ug_{k}}\\}$. Each ground user group can
have several UEs that share the same resource block group (RBG) and each RBG
consists of one or multiple resource blocks (RBs). Group of UEs share the same
resource block. As specified in [20, 21], Multi-user MIMO effectively enhances
spectral efficiency however its efficacy is reduced to cell-edge users due to
inter-cell interference. This traffic could be offloaded to satellite on-board
gNB to enhance the overall performance. Each of bandwidths $bw_{m}$, and
$bw_{s}$ has a set of N RBs based on the 5G numerology, which is uniformly
distributed into K non-overlapping RBGs to each service beam, each beam then
serves each of those users’ ground. The set of K RBG for the K UEs
=$\\{{rbg_{1},rbg_{2},rbg_{3},.....,rbg_{k}}\\}$, and each set of RBG consists
of =$\\{{rb_{1},rb_{2},rb_{3},.....,rb_{l}}\\}$.

Each NTN beam operates with a set of orthogonal frequencies so that inter-user
group interference can be avoided. Additionally, UEs in each user group
receive differentiated power levels operating on the same RBG to mitigate
intra-user group interference.

###  III-B Non-terrestrial Channel model

As introduced by 3GPP [5] and [6], the Non-Terrestrial channel is just the
extension of the Terrestrial channel where losses associated with rain, cloud,
fog, and scintillation are incorporated.

####  III-B1 Pathloss Model

Pathloss of the NTN channel can be formulated as

$PL_{total}=PL_{basic}+PL_{gas}+PL_{scin}+PL_{entry}$ (1)

where $PL_{total}$ is the total pathloss in dB for the radio link,
$PL_{basic}$ is the basic pathloss component in dB, $PL_{gas}$ is the gaseous
attenuation loss in dB, $PL_{sin}$ is the scintillation loss for the
atmospheric layers in dB, $PL_{entry}$ is the associated building entry loss
in dB. The basic pathloss ($PL_{basic}$ ) is associated with the signal
propagation in the free space, surrounding clutter, and shadow fading effects.
Gases has an effect on radio channel at frequency higher than 52 GHz, as such
gases effect can be neglected. As specified in the 3GPP [5] and [6], all of
these scenarios are outdoor with clear sky, hence scintillation loss due the
atmospheric layers, $PL_{scin}$ and building entry loss, $PL_{entry}$, both
can be neglected as well. Clutter loss in basic pathloss model is
significantly low, clutter is also neglect. Shadow fading expressed in dB is a
zero-mean normal distribution with standard deviation 4, included in the basic
pathloss equation. The free space path loss model is expressed as follows:

$FSPL(d,f_{c})=32.45+20log_{10}(f_{c})+20log_{10}(d)$ (2)

where FSPL is the free space path loss in dB for the distance d in meter and
$f_{c}$ is the operational frequency in GHz.

###  III-C Spectral Efficiency

In this technique, NTN gNB splits its total available power before
transmitting to its corresponding UEs. Data streams, $s_{ntn}$ are
independently encoded for each $N_{ntn}$ NTN UEs. After linear precoding, data
streams, $s_{ntn}$ are then transmitted over the same resource block group
(RBG) by the NTN gNB. Signals transmitted from the i-th gNB are expressed as:

${x}_{i,j}=\sum_{j=1}^{J}\sqrt{P_{i,j,ntn}}s_{ntn}$ (3)

where $P_{i,j,ntn}$ is the transmitted power from the $i$-th gNB to the $j$-th
UE and $P=[P_{i,1,ntn},P_{i,2,ntn},P_{i,3,ntn},.....,P_{i,J,ntn}]$ is the
power profile for all the UEs associated with the $i$-th gNB, whereas
$P_{k,l,ntn}$ is the transmitted power from $k$-th TBS to the $l$-th UE and
$P_{tn}=[P_{k,1,tn},P_{k,2,tn},P_{k,3,tn},.....,P_{k,L,tn}]$ is the power
profile for all the UEs associated with the $k$-th TBS. At time slot $t$,
received signals at $j$-th UE is expressed as:

$\text{y}_{i,j}=\sqrt{g_{i,j}^{m}(t)}x_{i,j}+n_{0}$ (4)

where $g_{i,j}^{m}(t)$ is channel gain between $i$-th gNB and the $j$-th UE
during $m$-th RBG, $n_{0}$ is the additive white Gaussian noise
$\mathcal{N}(0,\sigma^{2})$. For shake of simplicity, all the UEs have the
same noise spectral density, $n_{0}$. Each UE associated with the $i$-th gNB
SB also receives interference from the signals transmitted for other UEs
associated with the $i$-th gNB SB only. As to neglect inter-beam interference,
we consider orthogonal frequencies are allocated to all gNB SBs, and UE can
only connect to one SB at a time with gNB SB. As such, rate for the non-
terrestrial stream for $j$-th UE is expressed as:

$R_{i,j}(m)=\log_{2}\left(1+\frac{P_{i,j}^{m}g_{i,j}^{m}}{\sum_{\begin{subarray}{c}j^{\prime}=1\\\
j^{\prime}\neq
j\end{subarray}}^{J}P_{i,j^{\prime}}^{m}g_{i,j}^{m}+\sigma^{2}}\right)$ (5)

##  IV Problem Formulation

In this section, we would like to maximize - the overall sum rate in the Non-
terrestrial cellular networks through the optimization of the transmission
power allocation at the non-terrestrial base station, P; user association to
the Non-Terrestrial network, $\alpha$. We consider binary optimization
variable, $\alpha$ such that $\alpha$=1 if $m$-th RBG of the gNB SB is
assigned to the $j$-th UE; $\alpha$=0 otherwise. The total sum rate of the
Non-Terrestrial cellular network is the total achievable rate by all NTN UE
for the available bandwidth. Total sum rates depend on the following two
constraints.

(1) Power constraints $P_{i,j}^{m}$ is the allocated power for the $j$-th user
from the $i$-th gNB SB for the duration of $m$-th RBG. $P_{i,max}$ is the
maximum transmitted power of the $i$-th gNB SB for all the associated users.
Then non-terrestrial power allocation constraint is:

$\begin{split}(\text{C1})\hskip
5.69046pt&\sum_{j=1}^{J}\alpha_{i,j}P_{i,j}^{(m)}\leq P_{i,max},\forall
i\in\mathcal{I}\end{split}$ (6)

(2) Cost constraints $c_{i,j}^{m}$ is the cost for the $m$-th RBG of the
$i$-th gNB SB. $C_{i,max}$ is the maximum allowable cost of the $i$-th gNB SB
for all the associated users. Then non-terrestrial cost constraint is:

$\begin{split}(\text{C2})\hskip
5.69046pt&\sum_{j=1}^{J}\alpha_{i,j}c_{i,j}^{(m)}\leq C_{i,max},\forall
i\in\mathcal{I}\end{split}$ (7)

The utility function can be designed as:

$\begin{split}f(p,\alpha)=\sum_{i=1}^{I}\sum_{j=1}^{J}\alpha_{i,j}\log_{2}\left(1+\frac{P_{i,j}^{m}g_{i,j}^{m}}{\sum_{\begin{subarray}{c}j^{\prime}=1\\\
j^{\prime}\neq
j\end{subarray}}^{J}P_{i,j^{\prime}}^{m}g_{i,j^{\prime}}^{m}+\sigma^{2}}\right)\\\
\end{split}$ (8)

The RBG of the radio resource is the cost of the cellular network. For ease of
simplicity, we consider a fixed number of RGB for users’ groups, hence cost
constraints can be ignored here. Then we formulate a novel spectral efficiency
optimization problem as follows:

$\begin{split}\text{P0:}&\max_{\bm{p}\geq
0,\bm{\alpha}\in\\{0,1\\}}f(\bm{p},\bm{\alpha})\\\
&\text{s.t.}\quad\text{(C1)}.\end{split}$ (9)

##  V Introduced Solution for NTN network

Optimization of the spectral efficiency of (9) involves maximization of the
signal-to-interference plus noise ratio terms in (8). After applying
Lagrangian dual transform to the optimization problem P0, the equivalent
objective function be:

$\begin{split}\text{P1:}&\max_{\bm{p}\geq
0,\bm{\alpha}\in\\{0,1\\},\bm{x_{j}}\geq\frac{A_{j}}{B_{j}}}f_{1}(\bm{p},\bm{\alpha},\bm{x_{j}})\\\
&\text{s.t.}\quad\text{(C1)}.\end{split}$ (10)

Then the new introduced Lagrangian dual function can be written as -

$\begin{split}&f_{2}(p,\alpha,x_{j})=\sum_{i=1}^{I}\sum_{j=1}^{J}\alpha_{i,j}\log_{2}\left(1+x_{j}\right)\\\
&-\sum_{i=1}^{I}\sum_{j=1}^{J}\alpha_{i,j}x_{j}+\sum_{i=1}^{I}\sum_{j=1}^{J}\frac{\alpha_{i,j}(x_{j}-1)A_{j}}{A_{j}-B_{j}},\end{split}$
(11)

where
$A_{j}=P_{i,j}^{m}g_{i,j}^{m},B_{j}=\sum_{\begin{subarray}{c}j^{\prime}=1\\\
j^{\prime}\neq
j\end{subarray}}^{J}P_{i,j^{\prime}}^{m}g_{i,j^{\prime}}^{m}+\sigma^{2}$ and
for strict duality condition case, optimum $x_{j}$ can be derived as:

$\begin{split}&x_{j}^{*}=\frac{P_{i,j}^{m}g_{i,j}^{m}}{\sum_{\begin{subarray}{c}j^{\prime}=1\\\
j^{\prime}\neq
j\end{subarray}}^{J}P_{i,j^{\prime}}^{m}g_{i,j^{\prime}}^{m}+\sigma^{2}}.\end{split}$
(12)

After applying to quadratic transformation to (11)

$\begin{split}&f_{3}(p,\alpha,x_{j},y)=\sum_{i=1}^{I}\sum_{j=1}^{J}(\alpha_{i,j}\log_{2}\left(1+x_{j}\right)\\\
&-\alpha_{i,j}x_{j}+2y\sqrt{\alpha_{i,j}(x_{j}-1)A_{j}}-y^{2}(A_{j}-B_{j})),\end{split}$
(13)

Then applying KKT condition to eq. (13) and for fixed values of
$p,\alpha,x_{j}$, optimal $y$ can be derived when
${\partial{f_{3}}}/{\partial{y}}=0$ as:

$\begin{split}y^{*}&=\sqrt{\frac{\alpha_{i,j}x_{j}}{A_{j}-B_{j}}}\\\
&=\sqrt{\frac{\alpha_{i,j}x_{j}}{P_{i,j}^{m}g_{i,j}^{m}-(\sum_{\begin{subarray}{c}j^{\prime}=1\\\
j^{\prime}\neq
j\end{subarray}}^{J}P_{i,j^{\prime}}^{m}g_{i,j^{\prime}}^{m}+\sigma^{2})}}\end{split}$
(14)

Similarly applying KKT condition to eq. (13) and for fixed values of
$y,\alpha,x_{j}$, optimal $p$ can be derived when
${\partial{f_{3}}}/{\partial{p}}=0$ as:

$\begin{split}p_{i,j}^{*}&=\frac{g_{i,j}\alpha_{i,j}(x_{j}-1)}{y^{2}(g_{i,j}-\sum_{\begin{subarray}{c}j^{\prime}=1\\\
j^{\prime}\neq j\end{subarray}}g_{i,j^{\prime}})}\end{split}$ (15)

Finally $j$-th ue’s association to the $i$-th NBS can be considered as:

$\begin{split}\alpha_{i,j}=\begin{cases}&1,~{}\text{if}\hskip
5.69046ptE1>0;\\\ &0,\hskip 5.69046ptOtherwise\end{cases}\end{split}$ (16)

where
$E1=\alpha_{i,j}\log_{2}\left(1+x_{j}\right)-\alpha_{i,j}x_{j}+2y\sqrt{\alpha_{i,j}(x_{j}-1)A_{j}}-y^{2}(A_{j}-B_{j})$
for $j$-th ue. Then the entire process is summarized as Algorithm 1:

Algorithm 1 Transmit power allocations in NTN network only

Step 0: Initialize $p_{i,j}$ and $x_{j}$ to feasible values.

repeat

Step 1: Update $y$ by (14).

Step 2: Update $x_{j}$ by (12).

Step 3: Update $p_{i,j}$, $\alpha$ jointly by (15) and (16) respectively.

until the value of function $f_{3}$ in (13) converges.

##  VI Simulation Result and analysis

In this section, we present the numerical results and performance analysis for
both single beam and multi-beam operations in the Non-Terrestrial Network
(NTN). Our simulations are conducted considering a Geostationary Earth Orbit
(GEO) satellite positioned at an altitude of 35,786 km, operating in either
S-band or Ka-band, and serving ground User Equipment (UE) through single or
multiple beams. The ground UEs are uniformly distributed within each beam,
ensuring coverage across the target area.

For multi-beam operations, we employ an orthogonal frequency separation
approach to minimize interference between beams. Each beam covers a designated
region, equivalent to the coverage area of 19 Terrestrial Base Stations (BS).
The link-level parameters are set based on the recommendations specified in
[5, 22, 6], unless otherwise stated.

It is important to note that our analysis in this paper is focused solely on
the link-level simulation. To obtain a comprehensive understanding of the NTN
system, a system-level simulation is also necessary. Such a simulation should
consider factors such as antenna gain calculation, high propagation delay, and
large Doppler spread if applicable. In the case of Low Earth Orbit (LEO)
satellites, accurate positional information, including velocity and other
parameters, can be obtained through the Satellite Two Line Element (TLE) data.
Therefore, incorporating TLE information becomes crucial for system-level
simulations involving LEO satellites. However, for Medium Earth Orbit (MEO)
and Geostationary (GEO) satellites, where their positions remain stationary
with negligible velocity, TLE information may not be as critical.

###  VI-A Spectral efficiency of S-band single spot beam (SSB) and multi-spot
beams (MSB)

Figure 2: Spectral efficiency of S-band single spot beam (SSB) and multi-spot
beams (MSB)

In this scenario, we assume that the satellite has a clear line of sight with
the user equipment. The base station antenna (gNB O-RU) is mounted on the
satellite, and the user equipment’s height is varied from 0 to 1.5 m above the
ground. Our analysis focuses on the spectral efficiency of the Non-Terrestrial
Network (NTN) in the S-band (sub-6 GHz) for both single-spot beam (SSB) and
multi-spot beams (MSB) 5G operations. To account for different orientations of
the user equipment, we perform 20 iterations.

Figure 2 illustrates the spectral efficiency performance with varying user
equipment positions. We observe that the performance of the NTN network is
dependent on the positioning of the user equipment. In our analysis, our
introduced algorithm demonstrates superior performance compared to the
conventional method introduced by [12], for both Ka-band and S-band
operations.

###  VI-B Spectral efficiency of S-band and K-band

Next, we extend our analysis to include both Ka-band (mmWave 20 GHz) and
S-band (sub-6 GHz) for the Non-Terrestrial Network (NTN) 5G operation. In this
case, the spectral efficiency is evaluated with respect to the variation in
the number of user equipment (UEs). We conduct our analysis for a specific set
of UEs in each iteration.

Figure 3 presents the results of the spectral efficiency analysis. We observe
that the new introduced Fractional Programming (FP) algorithm outperforms the
conventional FP approach, demonstrating higher spectral efficiency for both
S-band and Ka-band operations. This improvement in spectral efficiency
highlights the effectiveness of our introduced algorithm in optimizing the
performance of the NTN network.

Figure 3: Spectral efficiency of single spot beam (SSB) for S-band and K-band

###  VI-C Avg. RBG rate for S-band and K-band

Next, we evaluate the average Resource Block Group (RBG) rate for both S-band
and Ka-band operations with a single spot beam (SSB). In 5G networks, the sub-
carrier spacing (SCS) is determined by the chosen numerology, which ranges
from 1 to 4 [1-4]. Each RBG’s capacity is influenced by the available
bandwidth and the SCS. The number of RBs in each RBG is determined based on a
network cost analysis.

In our analysis, we consider an SCS of 15 KHz, which is the same as LTE, and
each RBG contains only one RB. Figure 4 illustrates the results of our
evaluation. We observe that the average RBG rate for all three algorithms is
nearly identical for Ka-band. However, for S-band, we observe a significant
improvement in the average RBG rate when using our introduced Fractional
Programming (FP) algorithm compared to the conventional FP approach. This
improvement highlights the superiority of our introduced algorithm in
optimizing the average RBG rate for S-band operations.

Figure 4: Avg. RBG rate for S-band and K-band single spot beam (SSB)

###  VI-D Total Sum Rate

Finally, we evaluate the total sum rate for both S-band and Ka-band operations
in both single beam and multi-beam scenarios. The total available bandwidth
for S-band is 30 MHz, while for Ka-band, it is 400 MHz [1-4]. We calculate the
total sum rate for S-band using the allocated 30 MHz bandwidth.

Figure 5 presents the results of our analysis. We observe that for both single
spot beam (SSB) and multi-spot beams (MSB) cases, our introduced Fractional
Programming (FP) algorithm outperforms the conventional FP approach introduced
by Wei and Yu [5]. This improvement in total sum rate demonstrates the
effectiveness of our algorithm in optimizing the overall system performance
for both S-band and Ka-band operations.

Figure 5: Total sum rate for S-Band for single and multi spot beams (SSB, MSB)

##  VII Conclusion

In this study, we introduce a novel fractional programming algorithm for power
allocation in both terrestrial and non-terrestrial networks (NTN). We compare
the performance of our algorithm with a conventional approach in various
scenarios to demonstrate its superiority. Initially, we focus on the
terrestrial network and conduct a comprehensive analysis. Our introduced
algorithm consistently outperforms the conventional algorithm across different
scenarios. Subsequently, we extend our analysis to non-terrestrial networks.
In all scenarios, our introduced fractional programming algorithm consistently
outperforms the conventional algorithm when the networks are heavily crowded
making it advantageous from both capital expenditure (capex) and operational
expenditure (opex) perspectives.

## References

  * [1] X. Lin, S. Cioni, G. Charbit, N. Chuberre, S. Hellsten, and J.-F. Boutillon, “On the Path to 6G: Embracing the Next Wave of Low Earth Orbit Satellite Access,” _IEEE Communications Magazine_ , vol. 59, no. 12, pp. 36–42, 2021-12.
  * [2] R. Shafin, L. Liu, V. Chandrasekhar, H. Chen, J. Reed, and J. C. Zhang, “Arificial intelligence-enabled cellular networks: A criical path to beyond-5g and 6g,” _IEEE Wireless CommunicaIons_ , vol. 27, no. 2, pp. 212–217, 2020.
  * [3] H.-H. Chang, H. Song, Y. Yi, J. Zhang, H. He, and L. Liu, “Distribuive dynamic spectrum access through deep reinforcement learning: A reservoir compuing-based approach,” _IEEE Internet of Things Journal_ , vol. 6, no. 2, pp. 1938–1948, 2019.
  * [4] “Study on Narrow-Band Internet of Things (NB-IoT) / enhanced Machine Type Communication (eMTC) support for Non- Terrestrial Networks (NTN),” 3rd Generation Partnership Project (3GPP), Technical Report (TR), TR 36.763, June 2021, V17.0.0.
  * [5] “Study on New Radio (NR) to support non-terrestrial networks,” 3rd Generation Partnership Project (3GPP), Technical Report (TR), TR 38.811, Sept. 2020, V15.4.0.
  * [6] “Solutions for NR to support non-terrestrial networks (NTN),” 3rd Generation Partnership Project (3GPP), Technical Report (TR), TR 38.821, May 2021, V16.1.0.
  * [7] Starlink, “Wikipedia ,” 2023, accessed on June 12, 2023. [Online]. Available: https://en.wikipedia.org/wiki/Starlink
  * [8] Amazon, “Project Kuiper - Low Earth Orbit (LEO) mega constellation ,” 2023, accessed on June 12, 2023. [Online]. Available: https://www.aboutamazon.com/what-we-do/devices-services/project-kuiper
  * [9] Hughes, “JUPITER GEO Satellites,” 2023, accessed on June 12, 2023. [Online]. Available: https://www.hughes.com/what-we-offer/satellite-services/jupiter-geo-satellites
  * [10] “Solutions for NR to support non-terrestrial networks (NTN): Non-terrestrial networks (NTN) related RF and co-existence aspects,” 3rd Generation Partnership Project (3GPP), Technical Report (TR), TR 38.863, March 2023, V17.2.0.
  * [11] J. B. Frenk and S. Schaible, _Fractional programming_. Springer, 2005.
  * [12] K. Shen and W. Yu, “Fractional Programming for Communication Systems—Part I: Power Control and Beamforming,” vol. 66, no. 10, pp. 2616–2630, 2018-05.
  * [13] M. Hosseinian, J. P. Choi, S.-H. Chang, and J. Lee, “Review of 5G NTN Standards Development and Technical Challenges for Satellite Integration With the 5G Network,” _IEEE Aerospace and Electronic Systems Magazine_ , vol. 36, no. 8, pp. 22–31, 2021.
  * [14] S. Li, Q. Chen, W. Meng, and C. Li, “Civil Aircraft Assisted Space-Air-Ground Integrated Networks: An Innovative NTN of 5G and Beyond,” _IEEE Wireless Communications_ , vol. 29, no. 4, pp. 64–71, 2022.
  * [15] B. Shang, Y. Yi, and L. Liu, “Computing over space-air-ground integrated networks: Challenges and opportunities,” _IEEE Network_ , vol. 35, no. 4, pp. 302–309, 2021.
  * [16] B. Shang and L. Liu, “Mobile-edge computing in the sky: Energy optimization for air–ground integrated networks,” _IEEE Internet of Things Journal_ , vol. 7, no. 8, pp. 7443–7456, 2020.
  * [17] C. Amatetti, M. Conti, A. Guidotti, and A. Vanelli-Coralli, “NB-IoT random access procedure via NTN: system level performances,” in _ICC 2022 - IEEE International Conference on Communications_ , 2022, pp. 2381–2386.
  * [18] Y. Jiang, W. He, W. Liu, S. Wu, X. Wei, and Q. Mo, “A B5G Non-Terrestrial-Network (NTN) and Hybird Constellation Based Data Collection System (DCS),” _Aerospace_ , vol. 10, no. 4, 2023. [Online]. Available: https://www.mdpi.com/2226-4310/10/4/366
  * [19] H.-W. Lee, A. Medles, V. Jie, D. Lin, X. Zhu, I.-K. Fu, and H.-Y. Wei, “Reverse Spectrum Allocation for Spectrum Sharing between TN and NTN,” in _2021 IEEE Conference on Standards for Communications and Networking (CSCN)_ , 2021, pp. 1–6.
  * [20] L. Liu, R. Chen, S. Geirhofer, K. Sayana, Z. Shi, and Y. Zhou, “Downlink mimo in lte-advanced: Su-mimo vs. mu-mimo,” _IEEE CommunicaIons Magazine_ , vol. 50, no. 2, pp. 140–147, 2012.
  * [21] L. Liu, J. Zhang, and Z. Pi, “Inter-cell interference avoidance for downlink transmission,” Aug. 7 2012, uS Patent 8,238,954.
  * [22] “Study on channel model for frequencies from 0.5 to 100 GHz,” 3rd Generation Partnership Project (3GPP), Technical Report (TR), TR 38.901, December 2019, V16.1.0.


# Who is the best player ever? A complex network analysis of the history of
professional tennis

Filippo Radicchi  Chemical and Biological Engineering, Northwestern
University, 2145 Sheridan Road, Evanston, IL 60208, US

###### Abstract

We consider all matches played by professional tennis players between $1968$
and $2010$, and, on the basis of this data set, construct a directed and
weighted network of contacts. The resulting graph shows complex features,
typical of many real networked systems studied in literature. We develop a
diffusion algorithm and apply it to the tennis contact network in order to
rank professional players. Jimmy Connors is identified as the best player of
the history of tennis according to our ranking procedure. We perform a
complete analysis by determining the best players on specific playing surfaces
as well as the best ones in each of the years covered by the data set. The
results of our technique are compared to those of two other well established
methods. In general, we observe that our ranking method performs better: it
has a higher predictive power and does not require the arbitrary introduction
of external criteria for the correct assessment of the quality of players. The
present work provides a novel evidence of the utility of tools and methods of
network theory in real applications.

##  I Introduction

Social systems generally display complex features castellano09 . Complexity is
present at the individual level: the behavior of humans often obeys complex
dynamical patterns as for example demonstrated by the rules governing
electronic correspondence barabasi05 ; malmgren08 ; radicchi09a ; wu10 . At
the same time, complexity is present also at the global level. This can be
seen for example when social systems are mathematically represented in terms
of graphs or networks, where vertices identify individuals and edges stand for
interactions between pairs of social agents. Social networks are in most of
the cases scale-free Barabasi1999 , indicating therefore a strong degree of
complexity from the topological and global points of view.
During last years, the analysis of social systems has become an important
topic of interdisciplinary research and as such has started to be not longer
of interest to social scientists only. The presence of a huge amount of
digital data, describing the activity of humans and the way in which they
interact, has made possible the analysis of large-scale systems. This new
trend of research does not focus on the behavior of single agents, but mainly
on the analysis of the macroscopic and statistical properties of the whole
population, with the aim to discover regularities and universal rules. In this
sense, professional sports also represent optimal sources of data. Soccer
onody04 ; duch10 ; heuer10 , football girvan02 ; naim05 , baseball petersen08
; sire09 ; saavedra09 ; Petersen2011  and basketball naim07 ; skinner10  are
some remarkable cases in which network analysis revealed features not visible
with traditional approaches. These are practical examples of the general
outcome produced by the intense research activity of last years: network tools
and theories do not serve only for descriptive purposes, but have also wide
practical applicability. Representing a real system as a network allows in
fact to have a global view of the system and simultaneously use the entire
information encoded by its complete list of interactions. Particularly
relevant results are those regarding: the robustness of networks under
intentional attacks albert00 ; the spreading of viruses in graphs satorras01 ;
synchronization processes arenas08 , social models castellano09 , and
evolutionary and coevolutionary games Szabo2007 ; perc10  taking place on
networks. In this context fall also ranking techniques like the PageRank
algorithm Brin1 , where vertices are ranked on the basis of their “centrality”
in a diffusion process occurring on the graph. Diffusion algorithms,
originally proposed for ranking web pages, have been recently applied to
citation networks price65 . The evaluation of the popularity of papers chen07
, journals west08 ; west10  and scientists radicchi09  is performed not by
looking at local properties of the network (i.e., number of citations) but by
measuring their degree of centrality in the flow of information diffusing over
the entire graph. The use of the whole network leads to better evaluation
criteria without the addition of external ingredients because the complexity
of the citation process is encoded by the topology of the graph.

Figure 1: Properties of the data set. In panel a, we report the total number
of tournaments (top panel) and players (bottom panel) as a function of time.
In panel b, we plot the fraction of players having played (black circles), won
(red squares) and lost (blue diamonds) a certain number of matches. The black
dashed line corresponds to the best power-law fit with exponent consistent
with the value $1.2(1)$.

In this paper we continue in this direction of research and present a novel
example of a real system, taken from the world of professional sports,
suitable for network representation. We consider the list of all tennis
matches played by professional players during the last $43$ years
($1968$-$2010$). Matches are considered as basic contacts between the actors
in the network and weighted connections are drawn on the basis of the number
of matches between the same two opponents. We first provide evidence of the
complexity of the network of contacts between tennis players. We then develop
a ranking algorithm similar to PageRank and quantify the importance of tennis
players with the so-called “prestige score”. The results presented here
indicate once more that ranking techniques based on networks outperform
traditional methods. The prestige score is in fact more accurate and has
higher predictive power than well established ranking schemes adopted in
professional tennis. More importantly, our ranking method does not require the
introduction of external criteria for the assessment of the quality of players
and tournaments. Their importance is self-determined by the various
competitive processes described by the intricate network of contacts. Our
algorithm does nothing more than taking into account this information.

##  II Methods

###  II.1 Data set

Data were collected from the web site of the Association of Tennis
Professionals (ATP, www.atpworldtour.com). We automatically downloaded all
matches played by professional tennis players from January $1968$ to October
$2010$. We restrict our analysis only to matches played in Grand Slams and ATP
World Tour tournaments for a total of $3\,640$ tournaments and $133\,261$
matches. For illustrative purposes, in the top plot of the panel a of Figure
1, we report the number of tournaments played in each of the years covered by
our data set. With the exception of the period between $1968$ and $1970$, when
ATP was still in its infancy, about $75$ tournaments were played each year.
Two periods of larger popularity were registered around years $1980$ and
$1992$ when more than $90$ tournaments per year were played. The total number
of different players present in our data set is $3\,700$, and in the bottom
plot of panel a of Figure 1 we show how many players played at least one match
in each of the years covered by our analysis. In this case, the function is
less regular. On average, $400$ different players played in each of the years
between $1968$ and $1996$. Large fluctuations are anyway visible and a very
high peak in $1980$, when more than $500$ players participated in ATP
tournaments, is also present. Between $1996$ and $2000$, the number of players
decreased from $400$ to $300$ in an almost linear fashion. After that, the
number of participants in ATP tournaments started to be more constant with
small fluctuations around an average of about $300$ players.

###  II.2 Network representation

Figure 2: Top player network and scheme for a single tournament. In panel a,
we draw the subgraph of the contact network restricted only to those players
who have been number one in the ATP ranking. Intensities and widths are
proportional to the logarithm of the weight carried by each directed edge. In
panel b, we report a schematic view of the matches played during a single
tournament, while in panel c we draw the network derived from it.

We represent the data set as a network of contacts between tennis players.
This is a very natural representation of the system since a single match can
be viewed as an elementary contact between two opponents. Each time the player
$i$ plays and wins against player $j$, we draw a directed connection from $j$
to $i$ [$j\to i$, see Figure 2]. We adopt a weighted representation of the
contacts Barrat2004 , by assigning to the generic directed edge $j\to i$ a
weight $w_{ji}$ equal to the number of times that player $j$ looses against
player $i$. Our data are flexible and allow various levels of representation
by including for example only matches played in a certain period of time, on a
certain type of surface, etc. An example is reported in panel a of Figure 2
where the network of contacts is restricted only to the $24$ players having
been number one in the official ATP ranking. In general, networks obtained
from the aggregation of a sufficiently high number of matches have topological
complex features consistent with the majority of networked social systems so
far studied in literature Reka:RevModPhys2002 ; Newman2003 . Typical measures
revealing complex structure are represented by the probability density
functions of the in- and out-strengths of vertices Barrat2004 , both following
a clear power-law behavior [see Figure 1, panel b]. In our social system, this
means that most of the players perform a small number of matches (won or lost)
and then quit playing in major tournaments. On the other hand, a small set of
top players performs many matches against worse opponents (generally beating
them) and also many matches (won or lost) against other top players. This
picture is consistent with the so-called “Matthew effect” in career longevity
recently observed also in other professional sports petersen08 ; Petersen2011
.

###  II.3 Prestige score

The network representation can be used for ranking players. In our
interpretation, each player in the network carries a unit of “tennis prestige”
and we imagine that prestige flows in the graph along its weighted
connections. The process can be mathematically solved by determining the
solution of the system of equations

$P_{i}\;=\;\left(1-q\right)\,\sum_{j}\,P_{j}\,\frac{w_{ji}}{s_{j}^{out}}\;+\;\frac{q}{N}\;+\;\frac{1-q}{N}\,\sum_{j}\,P_{j}\,\delta\left(s_{j}^{out}\right)\;\;,$
(1)

valid for all nodes $i=1,\ldots,N$, with the additional constraint that
$\sum_{i}P_{i}=1$. $N$ indicates the total number of players (vertices) in the
network, while $s_{j}^{out}=\sum_{i}\,w_{ji}$ is the out-strength of the node
$j$ (i.e., the sum of the weight of all edges departing from vertex $j$).
$P_{i}$ is the “prestige score” assigned to player $i$ and represents the
fraction of the overall tennis prestige sitting, in the steady state of the
diffusion process, on vertex $i$. In Eqs. (1), $q\in\left[0,1\right]$ is a
control parameter which accounts for the importance of the various terms
contributing to the score of the nodes. The term
$\left(1-q\right)\,\sum_{j}\,P_{j}\,\frac{w_{ji}}{s_{j}^{out}}$ represents the
portion of score received by node $i$ in the diffusion process: vertices
redistribute their entire credit to neighboring nodes proportionally to the
weight of the connections linking to them. $\frac{q}{N}$ stands for a uniform
redistribution of tennis prestige among all nodes according to which each
player in the graph receives a constant and equal amount of credit. Finally
the term $\frac{1-q}{N}\,\sum_{j}\,P_{j}\,\delta\left(s_{j}^{out}\right)$
[with $\delta\left(\cdot\right)$ equal to one only if its argument is equal to
zero, and zero otherwise] serves as a correction in the case of existence of
dandling nodes (i.e., nodes with null out-strength), which otherwise would
behave as sinks in the diffusion process. Our prestige score is analogous to
the PageRank score Brin1 , originally formulated for ranking web pages and
more recently applied in different contexts.
In general topologies, analytical solutions of Eqs. (1) are hard to find. The
stationary values of the scores $P_{i}$s can be anyway computed recursively,
by setting at the beginning $P_{i}=1/N$ (but the results do not depend on the
choice of the initial value) and iterating Eqs. (1) until they converge to
values stable within a priori fixed precision.

####  II.3.1 Single tournament

Figure 3: Prestige score in a single tournament. Prestige score $P_{r}$ as a
function of the number of victories $r$ in a tournament with $\ell=7$ rounds
(Grand Slam). Black circles are obtained from Eqs. (7) and valid for $q=0$.
All other values of $q>0$ have been calculated from Eqs. (6): red squares
stand for $q=0.15$, blue diamonds for $q=0.5$, violet up-triangles for
$q=0.85$ and green down-triangles for $q=1$.

In the simplest case in which the graph is obtained by aggregating matches of
a single tournament only, we can analytically determine the solutions of Eqs.
(1). In a single tournament, matches are hierarchically organized in a binary
rooted tree and the topology of the resulting contact network is very simple
[see Figure 2, panels b and c]. Indicate with $\ell$ the number of matches
that the winner of the tournament should play (and win). The total number of
players present at the beginning of the tournament is $N=2^{\ell}$. The
prestige score is simply a function of $r$, the number of matches won by a
player, and can be denoted by $P_{r}$. We can rewrite Eqs. (1) as

$P_{r}=P_{0}\;+\;\left(1-q\right)\,\sum_{v=1}^{r}P_{v-1}\;\;,$ (2)

where $P_{0}=\frac{1-q}{N}\,P_{\ell}\;+\;\frac{q}{N}$ and $0\leq r\leq\ell$.
The score $P_{r}$ is given by the sum of two terms: $P_{0}$ stands for the
equal contribution shared by all players independently of the number of
victories; $\left(1-q\right)\,\sum_{v=1}^{r}P_{v-1}$ represents the score
accrued for the number of matches won. The former system of equations has a
recursive solution given by

$P_{r}\;=\;\left(2-q\right)P_{r-1}\;=\ldots\;=\;\left(2-q\right)^{r}\,P_{0}\;\;,$
(3)

which is still dependent on a constant that can be determined by implementing
the normalization condition

$\sum_{r=0}^{\ell}\,n_{r}\,P_{r}=1\;\;.$ (4)

In Eq. (4), $n_{r}$ indicates the number of players who have won $r$ matches.
We have $n_{r}=2^{\ell-r-1}$ for $0\leq r<\ell$ and $n_{\ell}=1$ and Eqs. (3)
and (4) allow to compute

$\begin{array}[]{ccc}\left(P_{0}\right)^{-1}=&\sum_{r=0}^{\ell-1}\,\left(2-q\right)^{r}\,2^{\ell-1-r}&+\;\left(2-q\right)^{\ell}\\\
&2^{\ell-1}\,\sum_{r=0}^{\ell-1}\,\left(\frac{2-q}{2}\right)^{r}&+\;\left(2-q\right)^{\ell}\\\
&2^{\ell-1}\,\frac{1-\left[\left(2-q\right)/2\right]^{\ell}}{\left[\left(2-q\right)/2\right]}&+\;\left(2-q\right)^{\ell}\\\
&\frac{2^{\ell}-\left(2-q\right)^{\ell}}{q}&+\;\left(2-q\right)^{\ell}\end{array}\;\;.$

In the former calculations, we have used the well known identity
$\sum_{r=0}^{v}\,x^{r}\,=\,\frac{1-x^{v+1}}{1-x}$, valid for any
$\left|x\right|<1$ and $v\geq 0$, which respectively means $0<q\leq 1$ and
$\ell>0$ in our case. Finally, we obtain

$P_{0}\;=\;\frac{q}{2^{\ell}\,+\,\left(2-q\right)^{\ell}\,\left(q-1\right)}\;\;,$
(5)

which together with Eqs. (3) provides the solution

$P_{r}\;=\;\frac{q\;\left(2-q\right)^{r}}{2^{\ell}\,+\,\left(2-q\right)^{\ell}\,\left(q-1\right)}\;\;.$
(6)

It is worth to notice that for $q=1$, Eqs. (6) correctly give
$P_{r}=2^{-\ell}$ for any $r$, meaning that, in absence of diffusion, prestige
is homogeneously distributed among all nodes. Conversely, for $q=0$ the
solution is

$P_{r}\;=\;\frac{2^{r}}{2^{\ell-1}\,\left(\ell+2\right)}\;\;.$ (7)

In Figure 3, we plot Eqs. (6) and (7) for various values of $q$. In general,
sufficiently low values of $q$ allow to assign to the winner of the tournament
a score which is about two order of magnitude larger than the one given to
players loosing at the first round. The score of the winner is an exponential
function of $\ell$, the length of the tournament. Grand Slams have for
instance length $\ell=7$ and their relative importance is therefore two or
four times larger than the one of other ATP tournaments, typically having
lengths $\ell=6$ or $\ell=5$.

##  III Results

Rank | Player | Country | Hand | Start | End
---|---|---|---|---|---
$1$ | Jimmy Connors | United States | L | $1970$ | $1996$
$2$ | Ivan Lendl | United States | R | $1978$ | $1994$
$3$ | John McEnroe | United States | L | $1976$ | $1994$
$4$ | Guillermo Vilas | Argentina | L | $1969$ | $1992$
$5$ | Andre Agassi | United States | R | $1986$ | $2006$
$6$ | Stefan Edberg | Sweden | R | $1982$ | $1996$
$7$ | Roger Federer | Switzerland | R | $1998$ | $2010$
$8$ | Pete Sampras | United States | R | $1988$ | $2002$
$9$ | Ilie Năstase | Romania | R | $1968$ | $1985$
$10$ | Björn Borg | Sweden | R | $1971$ | $1993$
$11$ | Boris Becker | Germany | R | $1983$ | $1999$
$12$ | Arthur Ashe | United States | R | $1968$ | $1979$
$13$ | Brian Gottfried | United States | R | $1970$ | $1984$
$14$ | Stan Smith | United States | R | $1968$ | $1985$
$15$ | Manuel Orantes | Spain | L | $1968$ | $1984$
$16$ | Michael Chang | United States | R | $1987$ | $2003$
$17$ | Roscoe Tanner | United States | L | $1969$ | $1985$
$18$ | Eddie Dibbs | United States | R | $1971$ | $1984$
$19$ | Harold Solomon | United States | R | $1971$ | $1991$
$20$ | Tom Okker | Netherlands | R | $1968$ | $1981$
$21$ | Mats Wilander | Sweden | R | $1980$ | $1996$
$22$ | Goran Ivanišević | Croatia | L | $1988$ | $2004$
$23$ | Vitas Gerulaitis | United States | R | $1971$ | $1986$
$24$ | Rafael Nadal | Spain | L | $2002$ | $2010$
$25$ | Raúl Ramirez | Mexico | R | $1970$ | $1983$
$26$ | John Newcombe | Australia | R | $1968$ | $1981$
$27$ | Ken Rosewall | Australia | R | $1968$ | $1980$
$28$ | Yevgeny Kafelnikov | Russian Federation | R | $1992$ | $2003$
$29$ | Andy Roddick | United States | R | $2000$ | $2010$
$30$ | Thomas Muster | Austria | L | $1984$ | $1999$
Table 1: Top $30$ players in the history of tennis. From left to right we indicate for each player: rank position according to prestige score, full name, country of origin, the hand used to play, and the years of the first and last ATP tournament played. Players having been at the top of ATP ranking are reported in boldface. Figure 4: Relation between prestige rank and other ranking techniques. In panel a, we present a scatter plot of the prestige rank versus the rank based on the number of victories (i.e., in-strength). Only players ranked in the top $30$ positions in one of the two lists are reported. Rank positions are calculated on the network corresponding to all matches played between $1968$ and $2010$. In panel b, a similar scatter plot is presented, but now only matches of year $2009$ are considered for the construction of the network. Prestige rank positions are compared with those assigned by ATP. Year | Prestige | ATP year-end | ITF
---|---|---|---
$1968$ | Rod Laver | - | -
$1969$ | Rod Laver | - | -
$1970$ | Rod Laver | - | -
$1971$ | Ken Rosewall | - | -
$1972$ | Ilie Năstase | - | -
$1973$ | Tom Okker | Ilie Năstase | -
$1974$ | Björn Borg | Jimmy Connors | -
$1975$ | Arthur Ashe | Jimmy Connors | -
$1976$ | Jimmy Connors | Jimmy Connors | -
$1977$ | Guillermo Vilas | Jimmy Connors | -
$1978$ | Björn Borg | Jimmy Connors | Björn Borg
$1979$ | Björn Borg | Björn Borg | Björn Borg
$1980$ | John McEnroe | Björn Borg | Björn Borg
$1981$ | Ivan Lendl | John McEnroe | John McEnroe
$1982$ | Ivan Lendl | John McEnroe | Jimmy Connors
$1983$ | Ivan Lendl | John McEnroe | John McEnroe
$1984$ | Ivan Lendl | John McEnroe | John McEnroe
$1985$ | Ivan Lendl | Ivan Lendl | Ivan Lendl
$1986$ | Ivan Lendl | Ivan Lendl | Ivan Lendl
$1987$ | Stefan Edberg | Ivan Lendl | Ivan Lendl
$1988$ | Mats Wilander | Mats Wilander | Mats Wilander
$1989$ | Ivan Lendl | Ivan Lendl | Boris Becker
$1990$ | Stefan Edberg | Stefan Edberg | Ivan Lendl
$1991$ | Stefan Edberg | Stefan Edberg | Stefan Edberg
$1992$ | Pete Sampras | Jim Courier | Jim Courier
$1993$ | Pete Sampras | Pete Sampras | Pete Sampras
$1994$ | Pete Sampras | Pete Sampras | Pete Sampras
$1995$ | Pete Sampras | Pete Sampras | Pete Sampras
$1996$ | Goran Ivanišević | Pete Sampras | Pete Sampras
$1997$ | Patrick Rafter | Pete Sampras | Pete Sampras
$1998$ | Marcelo Ríos | Pete Sampras | Pete Sampras
$1999$ | Andre Agassi | Andre Agassi | Andre Agassi
$2000$ | Marat Safin | Gustavo Kuerten | Gustavo Kuerten
$2001$ | Lleyton Hewitt | Lleyton Hewitt | Lleyton Hewitt
$2002$ | Lleyton Hewitt | Lleyton Hewitt | Lleyton Hewitt
$2003$ | Roger Federer | Andy Roddick | Andy Roddick
$2004$ | Roger Federer | Roger Federer | Roger Federer
$2005$ | Roger Federer | Roger Federer | Roger Federer
$2006$ | Roger Federer | Roger Federer | Roger Federer
$2007$ | Rafael Nadal | Roger Federer | Roger Federer
$2008$ | Rafael Nadal | Rafael Nadal | Rafael Nadal
$2009$ | Novak Djoković | Roger Federer | Roger Federer
$2010$ | Rafael Nadal | Rafael Nadal | Rafael Nadal
Table 2: Best players of the year. For each year we report the best player
according to our ranking scheme and those of ATP and ITF. Best year-end ATP
players are listed for all years from $1973$ on. ITF world champions have
started to be nominated since $1978$ only.

We set $q=0.15$ and run the ranking procedure on several networks derived from
our data set. The choice $q=0.15$ is mainly due to tradition. This is the
value originally used in the PageRank algorithm Brin1  and then adopted in the
majority of papers about this type of ranking procedures chen07 ; radicchi09 ;
west08 ; west10 . It should be stressed that $q=0.15$ is also a reasonable
value because it ensures a high relative score for the winner of the
tournament as stated in Eqs. (6).
In Table 1, we report the results obtained from the analysis of the contact
network constructed over the whole data set. The method is very effective in
finding the best players of the history of tennis. In our top $10$ list, there
are $9$ players having been number one in the ATP ranking. Our ranking
technique identifies Jimmy Connors as the best player of the history of
tennis. This could be a posteriori justified by the extremely long and
successful career of this player. Among all top players in the history of
tennis, Jimmy Connors has been undoubtedly the one with the longest and most
regular trend, being in the top $10$ of the ATP year-end ranking for $16$
consecutive years ($1973$-$1988$). Prestige score is strongly correlated with
the number of victories, but important differences are evident when the two
techniques are compared. Panel a of Figure 4 shows a scatter plot, where the
rank calculated according to our score is compared to the one based on the
number of victories. An important outlier is this plot is represented by the
Rafael Nadal, the actual number one of the ATP ranking. Rafael Nadal occupies
the rank position number $40$ according to the number of victories obtained in
his still young career, but he is placed at position number $24$ according to
prestige score, consistently with his high relevance in the recent history of
tennis. A similar effect is also visible for Björn Borg, whose career length
was shorter than average. He is ranked at position $17$ according to the
number of victories. Prestige score differently is able to determine the
undoubted importance of this player and, in our ranking, he is placed among
the best $10$ players of the whole history of professional tennis.
In general, players still in activity are penalized with respect to those who
have ended their careers. Prestige score is in fact strongly correlated with
the number of victories [see panel a of Figure 4] and still active players did
not yet played all matches of their career. This bias, introduced by the
incompleteness of the data set, can be suppressed by considering, for example,
only matches played in the same year. Table 2 shows the list of the best
players of the year according to prestige score. It is interesting to see how
our score is effective also here. We identify Rod Laver as the best tennis
player between $1968$ and $1971$, period in which no ATP ranking was still
established. Similar long periods of dominance are also those of Ivan Lendl
($1981-1986$), Pete Sampras ($1992-1995$) and Roger Federer ($2003-2006$). For
comparison, we report the best players of the year according to ATP (year-end
rank) and ITF (International Tennis Federation, www.itftennis.com) rankings.
In many cases, the best players of the year are the same in all lists.
Prestige rank seems however to have a higher predictive power by anticipating
the best player of the subsequent year according to the two other rankings.
John McEnroe is the top player in our ranking in $1980$ and occupies the same
position in the ATP and ITF lists one year later. The same happens also for
Ivan Lendl, Pete Sampras, Roger Federer and Rafael Nadal, respectively best
players of the years $1984$, $1992$, $2003$ and $2007$ according to prestige
score, but only one year later placed at the top position of ATP and ITF
rankings. The official ATP rank and the one determined on the basis of the
prestige score are strongly correlated, but small differences between them are
very interesting. An example is reported in panel b of Figure 4, where the
prestige rank calculated over the contact network of $2009$ is compared with
the ATP rank of the end of the same year (official ATP year-end rank as of
December $28$, $2009$). The top $4$ positions according to prestige score do
not corresponds to those of the ATP ranking. The best player of the year, for
example, is Novak Djoković instead of Roger Federer.
We perform also a different kind of analysis by constructing networks of
contacts for decades and for specific types of playing surfaces. According to
our score, the best players per decade are [Table 3 lists the top $30$ players
in each decade] : Jimmy Connors ($1971-1980$), Ivan Lendl ($1981-1990$), Pete
Sampras ($1991-2000$) and Roger Federer ($2001-2010$). Prestige score
identifies Guillermo Vilas as the best player ever in clay tournaments, while
on grass and hard surfaces the best players ever are Jimmy Connors and Andre
Agassi, respectively [see Table 4 for the list of the top $30$ players of a
particular playing surface].

##  IV Discussion

Tools and techniques of complex networks have wide applicability since many
real systems can be naturally described as graphs. For instance, rankings
based on diffusion are very effective since the whole information encoded by
the network topology can be used in place of simple local properties or pre-
determined and arbitrary criteria. Diffusion algorithms, like the one for
calculating the PageRank score Brin1 , were first developed for ranking web
pages and more recently have been applied to citation networks chen07 ;
radicchi09 ; west08 ; west10 . In citation networks, diffusion algorithms
generally outperform simple ranking techniques based on local network
properties (i.e., number of citations). When the popularity of papers is in
fact measured in terms of mere citation counts, there is no distinction
between the quality of the citations received. In contrast, when a diffusion
algorithm is used for the assessment of the quality of scientific
publications, then it is not only important that popular papers receive many
citations, but also that they are cited by other popular articles. In the case
of citation networks however, possible biases are introduced in the absence of
a proper classification of papers in scientific disciplinesradicchi08 . The
average number of publications and citations strongly depend on the popularity
of a particular topic of research and this fact influences the outcome of a
diffusion ranking algorithm. Another important issue in paper citation
networks is related to their intrinsic temporal nature: connections go only
backward in time, because papers can cite only older articles and not vice
versa. The anisotropy of the underlying network automatically biases any
method based on diffusion. Possible corrections can be implemented: for
example, the weight of citations may be represented by an exponential decaying
function of the age difference between citing and cited papers chen07 . Though
these corrections can be reasonable, they are ad hoc recipes and as such may
be considered arbitrary.
Here we have reported another emblematic example of a real social system
suitable for network representation: the graph of contacts (i.e., matches)
between professional tennis players. This network shows complex topological
features and as such the understanding of the whole system cannot be achieved
by decomposing the graph and studying each component in isolation. In
particular, the correct assessment of players’ performances needs the
simultaneously consideration of the whole network of interactions. We have
therefore introduced a new score, called “prestige score”, based on a
diffusion process occurring on the entire network of contacts between tennis
players. According to our ranking technique, the relevance of players is not
related to the number of victories only but mostly to the quality of these
victories. In this sense, it could be more important to beat a great player
than to win many matches against less relevant opponents. The results of the
analysis have revealed that our technique is effective in finding the best
players of the history of tennis. The biases mentioned in the case of citation
networks are not present in the tennis contact graph. Players do not need to
be classified since everybody has the opportunity to participate to every
tournament. Additionally, there is not temporal dependence because matches are
played between opponents still in activity and the flow does not necessarily
go from young players towards older ones. In general, players still in
activity are penalized with respect to those who already ended their career
only for incompleteness of information (i.e., they did not play all matches of
their career) and not because of an intrinsic bias of the system. Our ranking
technique is furthermore effective because it does not require any external
criteria of judgment. As term of comparison, the actual ATP ranking is based
on the amount of points collected by players during the season. Each
tournament has an a priori fixed value and points are distributed accordingly
to the round reached in the tournament. In our approach differently, the
importance of a tournament is self-determined: its quality is established by
the level of the players who are taking part of it.
In conclusion, we would like to stress that the aim of our method is not to
replace other ranking techniques, optimized and almost perfected in the course
of many years. Prestige rank represents only a novel method with a different
spirit and may be used to corroborate the accuracy of other well established
ranking techniques.

###### Acknowledgements.

We thank the Association of Tennis Professionals for making publicly available
the data set of all tennis matches played during last $43$ years. Helpful
discussions with Patrick McMullen are gratefully acknowledged as well.

| $1971-1980$ | $1981-1990$ | $1991-2000$ | $2001-2010$
---|---|---|---|---
Rank | Player | Country | Player | Country | Player | Country | Player | Country
$1$ | Jimmy Connors | United States | Ivan Lendl | United States | Pete Sampras | United States | Roger Federer | Switzerland
$2$ | Björn Borg | Sweden | John McEnroe | United States | Andre Agassi | United States | Rafael Nadal | Spain
$3$ | Ilie Năstase | Romania | Mats Wilander | Sweden | Michael Chang | United States | Andy Roddick | United States
$4$ | Guillermo Vilas | Argentina | Stefan Edberg | Sweden | Goran Ivanišević | Croatia | Lleyton Hewitt | Australia
$5$ | Arthur Ashe | United States | Jimmy Connors | United States | Yevgeny Kafelnikov | Russian Federation | Nikolay Davydenko | Russian Federation
$6$ | Brian Gottfried | United States | Boris Becker | Germany | Jim Courier | United States | Ivan Ljubičić | Croatia
$7$ | Manuel Orantes | Spain | Andrés Gómez | Ecuador | Richard Krajicek | Netherlands | Juan Carlos Ferrero | Spain
$8$ | Eddie Dibbs | United States | Yannick Noah | France | Thomas Muster | Austria | Novak Djoković | Serbia
$9$ | Harold Solomon | United States | Brad Gilbert | United States | Wayne Ferreira | South Africa | David Nalbandian | Argentina
$10$ | Stan Smith | United States | Tomáš Šmíd | Czech Republic | Thomas Enqvist | Sweden | Tommy Robredo | Spain
$11$ | Roscoe Tanner | United States | Henri Leconte | France | Boris Becker | Germany | David Ferrer | Spain
$12$ | Raúl Ramírez | Mexico | Tim Mayotte | United States | Stefan Edberg | Sweden | Fernando González | Chile
$13$ | Tom Okker | Netherlands | Anders Jarryd | Sweden | Sergi Bruguera | Spain | Andy Murray | Great Britain
$14$ | John Alexander | Australia | Miloslav Mečíř Sr. | Slovakia | Marc Rosset | Switzerland | Carlos Moyá | Spain
$15$ | Vitas Gerulaitis | United States | Kevin Curren | United States | Petr Korda | Czech Republic | Mikhail Youzhny | Russian Federation
$16$ | Ken Rosewall | Australia | Aaron Krickstein | United States | Todd Martin | United States | James Blake | United States
$17$ | John Newcombe | Australia | Guillermo Vilas | Argentina | Cédric Pioline | France | Tommy Haas | United States
$18$ | Wojtek Fibak | Poland | Joakim Nystrom | Sweden | Michael Stich | Germany | Fernando Verdasco | Spain
$19$ | Dick Stockton | United States | Emilio Sánchez | Spain | Àlex Corretja | Spain | Marat Safin | Russian Federation
$20$ | John McEnroe | United States | Johan Kriek | United States | Patrick Rafter | Australia | Tomás̆ Berdych | Czech Republic
$21$ | Adriano Panatta | Italy | Martin Jaite | Argentina | Magnus Gustafsson | Sweden | Juan Ignacio Chela | Argentina
$22$ | Jan Kodeš | Czech Republic | Jakob Hlasek | Switzerland | Andrei Medvedev | Ukraine | Radek Štěpánek | Czech Republic
$23$ | Jaime Fillol Sr. | Chile | Jimmy Arias | United States | Francisco Clavet | Spain | Andre Agassi | United States
$24$ | Robert Lutz | United States | Pat Cash | Australia | Marcelo Ríos | Chile | Robin Söderling | Sweden
$25$ | Marty Riessen | United States | Ramesh Krishnan | India | Greg Rusedski | Great Britain | Rainer Schüttler | Germany
$26$ | Rod Laver | Australia | José-Luis Clerc | Argentina | Fabrice Santoro | France | Feliciano López | Spain
$27$ | Tom Gorman | United States | Eliot Teltscher | United States | Magnus Larsson | Sweden | Tim Henman | Great Britain
$28$ | Vijay Amritraj | India | Thierry Tulasne | France | Tim Henman | Great Britain | Jarkko Nieminen | Finland
$29$ | Mark Cox | Great Britain | Scott Davis | United States | Alberto Berasategui | Spain | Mardy Fish | United States
$30$ | Onny Parun | New Zealand | Vitas Gerulaitis | United States | Albert Costa | Spain | Gastón Gaudio | Argentina
Table 3: Top $30$ players per decade. | Clay | Grass | Hard
---|---|---|---
Rank | Player | Country | Player | Country | Player | Country
$1$ | Guillermo Vilas | Argentina | Jimmy Connors | United States | Andre Agassi | United States
$2$ | Manuel Orantes | Spain | Boris Becker | Germany | Jimmy Connors | United States
$3$ | Thomas Muster | Austria | Roger Federer | Switzerland | Ivan Lendl | United States
$4$ | Ivan Lendl | United States | John Newcombe | Australia | Pete Sampras | United States
$5$ | Carlos Moyá | Spain | John McEnroe | United States | Roger Federer | Switzerland
$6$ | Eddie Dibbs | United States | Pete Sampras | United States | Stefan Edberg | Sweden
$7$ | José Higueras | Spain | Tony Roche | Australia | Michael Chang | United States
$8$ | Björn Borg | Sweden | Stefan Edberg | Sweden | John McEnroe | United States
$9$ | Ilie Năstase | Romania | Roscoe Tanner | United States | Andy Roddick | United States
$10$ | Andrés Gómez | Ecuador | Lleyton Hewitt | Australia | Lleyton Hewitt | Australia
$11$ | Àlex Corretja | Spain | Ken Rosewall | Australia | Brad Gilbert | United States
$12$ | Rafael Nadal | Spain | Arthur Ashe | United States | Jim Courier | United States
$13$ | José-Luis Clerc | Argentina | Stan Smith | United States | Brian Gottfried | United States
$14$ | Sergi Bruguera | Spain | Phil Dent | Australia | Thomas Enqvist | Sweden
$15$ | Mats Wilander | Sweden | Björn Borg | Sweden | Stan Smith | United States
$16$ | Albert Costa | Spain | Goran Ivanišević | Croatia | Boris Becker | Germany
$17$ | Gastón Gaudio | Argentina | Pat Cash | Australia | Wayne Ferreira | South Africa
$18$ | Juan Carlos Ferrero | Spain | Andy Roddick | United States | Ilie Năstase | Romania
$19$ | Harold Solomon | United States | Ivan Lendl | United States | Roscoe Tanner | United States
$20$ | Emilio Sánchez | Spain | Tim Henman | Great Britain | Tommy Haas | United States
$21$ | Adriano Panatta | Italy | Rod Laver | Australia | Rafael Nadal | Spain
$22$ | Félix Mantilla | Spain | Mark Edmondson | Australia | Tim Henman | Great Britain
$23$ | Francisco Clavet | Spain | John Alexander | Australia | Mats Wilander | Sweden
$24$ | Balázs Taróczy | Hungary | Hank Pfister | United States | Yevgeny Kafelnikov | Russian Federation
$25$ | Željko Franulović | Croatia | Wally Masur | Australia | Andy Murray | Great Britain
$26$ | Tomáš Šmíd | Czech Republic | Tim Mayotte | United States | Fabrice Santoro | France
$27$ | Jimmy Connors | United States | Vijay Amritraj | India | Harold Solomon | United States
$28$ | Raúl Ramirez | Mexico | Kevin Curren | United States | Ivan Ljubičić | Croatia
$29$ | Alberto Berasategui | Spain | Tom Okker | Netherlands | Marat Safin | Russian Federation
$30$ | Victor Pecci Sr. | Paraguay | Greg Rusedski | Great Britain | Aaron Krickstein | United States
Table 4: Top $30$ players of the history of tennis in tournaments played on
clay, grass and hard surfaces.

## References

  * (1) Castellano C, Fortunato S, Loreto V (2009) Statistical physics of social dynamics.  Rev Mod Phys 81: 591–646.
  * (2) Barabási AL (2005) The origin of bursts and heavy tails in human dynamics.  Nature 435: 207–211.
  * (3) Malmgren RD, Stouffer DB, Motter AE, Amaral LAN (2008) A poissonian explanation for heavy tails in e-mail communication.  Proc Natl Acad Sci USA 105: 18153–18158.
  * (4) Radicchi F (2009) Human activity in the web.  Phys Rev E 80: 026118.
  * (5) Wu Y, Zhou C, Xiao J, Kurths J, Schellnhuber HJ (2010) Evidence for a bimodal distribution in human communication.  Proc Natl Acad Sci USA 107: 18803–18808.
  * (6) Barabási AL, Albert R (1999) Emergence of scaling in random networks.  Science 286: 509-512.
  * (7) Onody RN, de Castro PA (2004) Complex network study of brazilian soccer players.  Phys Rev E 70: 037103.
  * (8) Duch J, Waitzman JS, Amaral LAN (2010) Quantifying the performance of individual players in a team activity.  PLoS ONE 5: e10937.
  * (9) Heuer A, Müller C, Rubner O (2010) Soccer: Is scoring goals a predictable poissonian process?  EPL 89: 38007.
  * (10) Girvan M, Newman MEJ (2002) Community structure in social and biological networks.  Proc Natl Acad Sci USA 99: 7821–7826.
  * (11) Ben-Naim E, Vazquez F, Redner S (2007) What is the most competitive sport?  J Korean Phys Soc 50: 124.
  * (12) Petersen AM, Jung WS, Stanley HE (2008) On the distribution of career longevity and the evolution of home-run prowess in professional baseball.  EPL 83: 50010.
  * (13) Sire C, Redner S (2009) Understanding baseball team standings and streaks.  Eur Phys J B 67: 473-481.
  * (14) Saavedra S, Powers S, McCotter T, Porter MA, Mucha PJ (2009) Mutually-antagonistic interactions in baseball networks.  Physica A 389: 1131–1141.
  * (15) Petersen AM, Jung WS, Yang JS, Stanley HE (2011) Quantitative and empirical demonstration of the Matthew effect in a study of career longevity.  Proc Natl Acad Sci USA 108: 18–23.
  * (16) Ben-Naim E, Redner S, Vazquez F (2007) Scaling in tournaments.  EPL 77: 30005.
  * (17) Skinner B (2010) The price of anarchy in basketball.  Journal of Quantitative Analysis in Sports 6: 3.
  * (18) Albert R, Jeong H, Barabási AL (2000) Error and attack tolerance in complex networks.  Nature 406: 378–382.
  * (19) Pastor-Satorras R, Vespignani A (2001) Epidemic spreading in scale-free networks.  Phys Rev Lett 86: 3200–3203.
  * (20) Arenas A, Díaz-Guilera A, Kurths J, Moreno Y, Zhou C (2008) Synchronization in complex networks.  Phys Rep 469: 93-153.
  * (21) Szabò G, Fáth G (2007) Evolutionary games on graphs.  Phys Rep 446: 97–216.
  * (22) Perc M, Szolnoki A (2010) Coevolutionary games - a mini review.  BioSystems 99: 109–125.
  * (23) Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine.  Comput Netw ISDN Syst 30: 107–117.
  * (24) de Solla Price DJ (1965) Networks of Scientific Papers.  Science 149: 510–515.
  * (25) Chen P, Xie H, Maslov S, Redner S (2007) Finding scientific gems with Google’s PageRank algorithm.  Journal of Informetrics 1: 8–15.
  * (26) Bergstrom CT, West J (2008) Assessing citations with the EigenfactorTM Metrics.  Neurology 71: 1850–1851.
  * (27) West J, Bergstrom T, Bergstrom CT (2010) Big Macs and Eigenfactor scores: Don’t let correlation coefficients fool you.  J Am Soc Inf Sci 61: 1800–1807.
  * (28) Radicchi F, Fortunato S, Markines B, Vespignani A (2009) Diffusion of scientific credits and the ranking of scientists.  Phys Rev E 80: 056103.
  * (29) Barrat A, Barthélemy M, Pastor-Satorras R, Vespignani A (2004) The architecture of complex weighted networks.  Proc Natl Acad Sci USA 101: 3747–3752.
  * (30) Albert R, Barabási AL (2002) Statistical mechanics of complex networks.  Rev Mod Phys 74: 47–97.
  * (31) Newman MEJ (2003) The structure and function of complex networks.  SIAM Review 45: 167–256.
  * (32) Radicchi F, Fortunato S, Castellano C (2008) Universality of citation distributions: Toward an objective measure of scientific impact.  Proc Natl Acad Sci USA 105: 17268–17272.