# Mobile Edge Computing for the Metaverse

Chang Liu, Yitong Wang, Jun Zhao The authors are all with Nanyang
Technological University, Singapore. Email<EMAIL_ADDRESS>
###### Abstract

The Metaverse has emerged as the next generation of the Internet. It aims to
provide an immersive, persistent virtual space where people can live, learn,
work and interact with each other. However, the existing technology is
inadequate to guarantee high visual quality and ultra-low latency service for
the Metaverse players. Mobile Edge Computing (MEC) is a paradigm where
proximal edge servers are utilized to perform computation-intensive and
latency-sensitive tasks like image processing and video analysis. In MEC, the
large amount of data is processed by edge servers closest to where it is
captured, thus significantly reducing the latency and providing almost real-
time performance. In this paper, we integrate fundamental elements (5G and 6G
wireless communications, Blockchain, digital twin and artificial intelligence)
into the MEC framework to facilitate the Metaverse. We also elaborate on the
research problems and applications in the MEC-enabled Metaverse. Finally, we
provide a case study to establish a thorough knowledge of the user utility
maximization problem in a real-world scenario and gain some insights about
trends in potential research directions.

###### Index Terms:

Mobile Edge Computing, Metaverse, Wireless Communication, Blockchain, Digital
Twin.

##  I Introduction

The Metaverse is a computer-generated environment that fluidly combines
physical reality with digital virtuality with a variety of consumer and
business applications. As a universal and immersive virtual world for users to
create content, interact with each other and own digital assets, the Metaverse
is believed to be the next iteration of the internet. The potential of this
internet evolution is attracting the attention of large groups of online game
makers and social network companies [1, 2], even making companies like
Facebook pivot towards the Metaverse to stay competitive. Unlike typical video
games, which are entirely contained within a single ecosystem, the Metaverse
is an open world for users to coexist. To experience a different existence in
virtuality that is a metaphor for the users’ actual realities, each individual
user in the Metaverse has her/his own avatar, which functions similarly to the
user’s physical person. The technological enablers, particularly in the areas
of mobile edge computing (MEC) and augmented and virtual reality (AR/VR) make
the launch and quick uptake of the Metaverse platform possible [3].

Mobile Edge Computing. Mobile Edge Computing (MEC), as an emerging computing
paradigm, efficiently tackles the stringent constraints of communication and
computation. Compared with conventional computing paradigms especially cloud
computing, MEC proposed by the European Telecommunications Standard Institute
(ETSI) introduces a novel strategy of task offloading. Instead of delivering
the tasks to the central cloud servers, computation-intensive tasks of MEC are
offloaded to the MEC servers that are placed on the edge of networks (e.g.
base stations), which has a significant impact on reducing transmission delays
and energy consumption of devices.

Metaverse. Facebook’s rebranding of its company as “Meta” and Omniverse
developed by NVIDIA in the Metaverse system mark the next step in the
Metaverse’s evolution into the spotlight. This emerging ecosystem of services
could significantly improve individuals’ daily life in the virtual universe in
terms of education, industries, and healthcare, where the inconvenience of
living with an epidemic quarantine caused by COVID-19 can be tackled by the
service applications in the Metaverse. As a universe of ternary-world
interactions (i.e. physical world, human world, and digital world), Metaverse
can provide a fully immersive world for people as digital avatars to interact
between the physical and virtual worlds. More importantly, hyper
spatiotemporal, self-sustaining, and interoperability are the inherent
attributes of Metaverse as a result of the convergence of digital twin (DT),
virtual reality (VR), augmented reality (AR), blockchain, and non-fungible
token (NFT).

MEC-enabled Metaverse. The convergence of mobile edge computing and the
Metaverse meets both user-side and system-side requirements. For the user
side, the edge servers close to the users are able to respond faster to the
tasks sent by the devices. As Metaverse is based on a mass of virtual scenes
and sensor data transmission based on mixed reality, mobile edge computing is
able to meet the latency requirements of Metaverse service applications and
solve the symptoms such as dizziness and vomiting of users due to high
latency. Context-aware immersive content can also be delivered to improve the
experience of users. Specifically, context-aware contents are distributed and
cached in MEC servers based on the current users’ contextual preferences, such
as current fields of views (FOVs), view angles, and interacting actions. For
the system side, MEC offloads tasks that would have been processed locally to
the edge server, solving the problem of insufficient computing resources and
battery life on local devices. A large amount of 2D/3D scene data from
Metaverse applications can be cached in the edge server, solving the
limitations of local device caching storage while reducing the total bandwidth
required for immersive streaming and interaction.

Comparison with other work. There are several studies on the Metaverse
communication paradigms design and review. Yu _et al._ [4] provide a review on
6G mobile-edge empowered Metaverse, investigating the real-world deployment
contexts of these technologies and proving that MEC with intelligent
reflecting surfaces (IRS) can improve the energy efficiency and throughput in
the Metaverse. However, their study focuses on the 6G networks and enabling
technologies. Our paper places emphasis on the MEC technologies that can
empower the Metaverse. Musamih _et al._ [5] discuss the opportunities of the
Metaverse in healthcare such as medical education and training, medical
marketing and healthcare supply chain, as well as the enabling technologies.
In contrast, our paper provides insights into several Metaverse applications
and enabling technologies. The paper [6] proposes a system that combines
digital twins (DT) with other cutting-edge technologies, including the 6G
communication network, blockchain, and AI. It focuses on sustaining continuous
end-to-end Metaverse services, while our paper gives an overview of the
enabling technologies, applications and research problems in MEC-enabled
Metaverse.

Figure 1: The framework of MEC-enabled Metaverse system. Figure 2: The
applications of MEC-enabled Metaverse.

##  II Enabling technologies for MEC-enabled Metaverse

In this section, the technologies that empower the Metaverse with MEC are
discussed. We give an overview of how 5G and 6G wireless communication,
blockchain, digital twin and artificial intelligence can be developed to
support MEC-enabled Metaverse. Fig 1 illustrates the framework of the MEC-
enabled Metaverse system. The wireless communication technologies and
blockchain lay the infrastructure for the Metaverse system. The virtualization
engine includes digital twin and artificial intelligence. Mobile devices such
as AR/VR equipment serve as the user interface.

###  II-A 5G and 6G Wireless Communication

In contrast to the conventional 5th wireless communication network, the
emerging 6G network is critical to meet the constraints in terms of delay,
reliability, and application scenarios. Detailed comparisons are as follows:

5G: Based on the 5G attributes standardized by the Internet Telecommunication
Union (ITU), three main 5G-based application scenarios are derived, including
eMBB (enhanced Mobile Broadband), URLLC (Ultra Reliable Low Latency
Communications), and mMTC (Massive Machine-Type Communications). 5G, as a new
type of network, is the generation of the global wireless standard after 4G,
designed to increase data transmission speeds, reduce latency and support more
users, devices and services, while improving network efficiency. However, with
the proliferation of communication devices and communication data volumes, as
well as the evolution of communication scenarios, 5G will likely no longer
meet some of the stringent requirements.

6G: As distinct from 5G, the most inherent attribute of 6G is mobile broadband
reliable low latency communication (MBRLLC)[7]. 6G, as a mobile communication
system featuring “connected intelligence”, will provide more complete network
coverage and a more secure communication network. In addition, 6G offers
significant improvements in various metrics, such as a peak transmission rate
of 1Tbit/s, which will enhance the performance of existing and future
communication applications. Furthermore, holographic communication and high-
fidelity human-computer interaction scenarios are further driving the rapid
development of 6G. In short, the vision of 6G is to provide users with a more
diverse and intelligent communication network based on realizing semantic
communication[8].

###  II-B Blockchain

As a representative technology of decentralization, Blockchain can secure data
of users in the Metaverse, improve transparency of transactions and prevent
single point of failure (SPoF). The convergence of Blockchain and Metaverse
can further improve the scalability and interoperability by using sharding
technology and cross-chain technology to divide the whole Metaverse into
multiple shards [9]. At the same time, Blockchain plays a key role in edge
resource allocation by providing access control and identification of various
services in the virtual world. In conclusion, Blockchain, as a key technology
in the edge universe, can influence the improvement of various performances in
the Metaverse, including computing offloading, resource allocation, and edge
intelligence.

###  II-C Digital Twin

Digital twin is a vital technology for projecting real-world scenes, objects
and users into the virtual world. Specifically, digital twin, which makes full
use of data such as physical models, sensor updates and operational histories,
integrates multi-disciplinary, multi-physical quantity, multi-scale and multi-
probability simulation processes and completes the mapping in virtual space,
thus reflecting the full life-cycle process of the corresponding physical
equipment.

###  II-D Artificial Intelligence

Rendering the various scenarios of the large-scale Metaverse is inseparable
from artificial intelligence (AI) technology. Specifically, the multilingual
environment and personalised application services in the Metaverse are offered
on the basis of massive data inference. AI technology also has a crucial role
in enhancing the performance of the Metaverse system. For example, to meet
variable and previously unknown time budgets, deep neural network (DNN) can be
applied in the vision transformer backbones to improve the accuracy and speed
of the system. Deep learning algorithm can also be adopted to identify the
type (faithful or malicious) of edge servers to improve the security and
convergence of the state-of-the-art systems[10].

##  III Research problems in MEC-enabled Metaverse

Although the tremendous development of the above mentioned technologies, some
problems still occur when large-scale MEC-enabled Metaverse system is deployed
in the real world. In this section, we will identify and discuss the research
problems in MEC-enabled Metaverse.

###  III-A Resource allocation

Optimal allocation schemes of resources not only substantially enhance the
computational performance of the system but also enable adaptation to new
Metaverse service applications in the future. Resource allocation problems can
be divided into two categories: communication resource allocation and
computation resource allocation. For communication resource allocation, how to
allocate FDMA bandwidth resources, TDMA time resources, and NOMA power
resources emerges as the main concern, where FDMA, TDMA, and NOMA are short
for frequency-division, time-division, and non-orthogonal multiple access,
respectively. In particular, NOMA power allocation has gained more attention
due to the fact that NOMA is the preferred alternative technology for 5G. For
computation resource allocation, offloading decisions have a significant
impact on it. Due to the different computing resources of VR devices and edge
servers, computing tasks locally and offloading tasks to the edge servers are
two preferred methods. But both approaches need to address the tradeoff
between latency and resources. Thus, the novel device-edge association
allocation of edge computation resources is progressively gaining focus in
research.

###  III-B Mobility

High fidelity and smooth scenes as users change their field of views (FOV) and
physical position are essential factors in maintaining an immersive experience
for users. However, seamless and stable services are subject to resource
allocation and traditional optimization will have much computational
complexity. To address mobility, deep reinforcement learning can be used and
provides seamless services. For example, the prediction model uses past head
movements to predict the users’ position in the 360 degree view, which
accurately provides the users with the next view of the screen. Furthermore,
predicting the users’ future location based on their physical motion can
facilitate the advanced allocation of various resources.

###  III-C Security

The security and privacy issues of the Metaverse are two issues that need to
be addressed since the Metaverse is built on blockchain-empowered economic
ecosystems [11]. For security issues, the following aspects are described.
Data security, as users trade goods, shares and other virtual funds in the
virtual world, their virtual assets and transaction passwords must be secured
from potential attackers. In addition, the user’s activities in the Metaverse
must be protected from hackers by the transmission of communication data and
feedback from the server. Therefore, better authentication schemes and post-
quantum cryptography are the dominant techniques to resist attackers. User
security, in the virtual world, collaboration among attackers will lead to
digital avatars in the Metaverse receiving physical harm, for example,
robbery, rape, etc. In the real world, attackers can commit data theft from
the users’ devices, leading to the prying of information about their real-
world habitat and belongings.

###  III-D Privacy

With regard to the privacy of users, service providers collect various human
biological data from users to personalise their service provision, which can
further lead to privacy breaches. For example, the users’ eye information,
including pupil spacing and pupil size, can be obtained by collecting eye
tracking data. The users’ sensitivity to colour and colour blindness can be
determined by the users’ reaction time to images of different colours. The
users’ nationality and native language can be identified by the user’s
reaction time to different languages. The performance and price range of the
devices worn by the users can be judged by the RTT for different resolution
animations. This data may be vital for companies to derive the attention span
of users in order to market their products better, but if leaked, the users’
personal privacy will also be stolen, or worse, attackers will steal or fake
the users’ identities to live in the Metaverse[12].

As a result, a number of techniques and risk assessment architectures to
resist attackers should be pursued to defend users against the various threats
they receive. The convergence of federated learning and homomorphic encryption
can effectively improve the robustness of the system while protecting the
privacy of the user.

##  IV Applications of MEC-enabled Metaverse

The Metaverse has a wide range of applications in the society and in the
industry as illustrated in Fig 2. In this section, we describe several
Metaverse applications with great potential.

###  IV-A Smart Manufacturing

The development of the Metaverse has not only taken people’s daily lives from
the real world to the virtual world but has also brought various industrial
manufacturing activities into the virtual world. With the help of various
VR/AR devices, people can even perform industrial activities that cannot be
done in the real world, thus realising the “industrial Metaverse”.
Specifically, professional surgeons can wear Microsoft Hololens 2 to perform
preoperative simulations of high-risk surgical procedures and analyse any
possible adverse effects on the patient during surgery. Automotive parts
manufacturers can wear Microsoft Hololens 2 to perform the manufacturing and
commissioning of high precision parts within the Metaverse, which not only
saves the cost of failed part manufacturing but also maximises the performance
of vehicles in the physical world.

###  IV-B Smart City

The form of the smart city of the future will gradually change into a virtual
city. The Metaverse platform is an alternative to the smart cities of the
future, enabling various social activities such as healthcare, economy,
education and entertainment in a virtual world based on the convergence of
various technologies, including Internet of Things (IoT), Blockchain, AI, VR,
and AR[13]. Yet, before the virtual city can be realised, the issue of how to
plan the functioning of the city and the rights and interests of the people
involved will have to be considered. For example, people can use AR technology
to make furniture choices and match decorating styles and tones through AR
devices. People will also be able to hold business and academic meetings in
Metaverse while communicating face-to-face in a virtual world, solving the
drawback of currently only being able to hold meetings on a 2D plane.

###  IV-C Play-to-Earn Games

With the aid of revolutionary technologies such as Blockchain, a great change
is taking place in the game industry. The decentralized nature of the
Metaverse allows players to gain real-world rewards from the time and effort
they put into the game [3]. This evolution of the game industry is known as
“Play to Earn” (P2E). In P2E games, players can log in to complete the game or
battle with other plays to earn or create digital assets. The most popular
digital assets are cryptocurrencies and Non-Fungible Tokens (NFTs). In
decentralized marketplaces, players are allowed to trade the NFTs with others
in the game, and carry them to other digital experiences. The brand-new, free-
market and internet-based economy makes it increasingly prevalent that people
spend more time on digital activities.

##  V A Case Study of MEC-enabled Metaverse

In this section, we will provide a case study of MEC-enabled Metaverse.

Mobile and wearable technology, such as AR glasses, headsets, and smartphones,
is now the most appealing and popular Metaverse interfaces because they enable
easy player movement. However, the Metaverse applications’ real-time
interactive nature and their high demands on a seamless experience are too
heavy for mobile devices on account of the following two aspects:

  * •

Limited Computation Resource: To render a digital world which is physically
accurate in the Metaverse, massive computation resources will be consumed. For
instance, operating a typical AAA game today (such as Fortnite) takes multiple
trillion floating point operations per second, and the need to generate
completely immersive Metaverse experiences is anticipated to increase by two
orders of magnitude. Even the most fundamental image and video processing
tasks, such as real-time object detection, can become quite computationally
complicated and time-consuming when used in increasingly sophisticated virtual
environments [14, 15]. However, the computational capacity of graphics and
chipsets in the mobile devices such as AR glasses and headsets is not enough
to handle sophisticated tasks. The most advanced all-in-one VR hardware,
Oculus quest 2, is able to deliver VR service without a linked PC with its
strong Qualcomm Snapdragon XR2 chipset [16]. The standalone VR experience
comes at the expense of lower frame rates and hence less detailed VR sceneries
because its computing power is still limited when compared to a PC or edge
server. As a result, the user experience might suffer from insufficient
processing resources if user activities incur delay [17].

  * •

Limited Communication Resource: The Metaverse is developed to support user
interactions within the virtual world as well as with other users. To this
end, it requires keeping track of the dynamic state information about physical
devices and the integration of live streams and digital assets, as well as the
dissemination of the processed streams. Specifically, in the Metaverse, the
raw data collected by the sensors on the user side is transmitted to the
server, and the processed information will be transmitted to the users again.
The substantial amount of data that needs to be transmitted increases the
network traffic between Metaverse users and the servers. For example, the
video traffic in the Metaverse, already makes up 80% of all Internet traffic
today and is expected to expand at a 37% compound annual growth rate over the
next ten years, exceeding the present data use by about 24 times [18].

The practice of offloading the computationally difficult work to a cloud
server is a widely-used solution to the problem of mobile devices’ limited
computing resources. A Metaverse Service Provider (MSP) edge server will often
communicate the gaming environment in graphical form to the players in a
typical Metaverse game scenario. The players will take in the visual data and
react. Players’ states will alter in response to the player’s appropriate
actions. The MSP edge server will then receive these modifications and process
them there. However, due to the limited communication resource, transmission
delay between the players and MSP edge servers will be increased when high-
definition graphics data is transmitted. In the Metaverse applications over
MEC, communication effectiveness is essential to provide players with an
immersive gaming experience. Virtual objects might move out of place if there
is a significant amount of latency, which could affect players’ reactions and
the outcome of the profits they make in the game as a whole. This delay may
also negatively affect players’ health and dizziness, which will affect how
they play the game.

Intuitively, the delay can be mitigated if one could decrease the size of
transmission data. Graphics will be of lower quality nevertheless if data is
scarce. It might also hinder visuals, which would affect the gaming experience
and cause difficulties in detecting the game’s settings. In this case, players
are more likely to play poorly, which results in fewer game tokens. As shown
above, there is a clear trade-off between the amount of tokens a player might
be able to earn and the volume of data being exchanged. A further method to
decrease service latency and boost token profits is to optimize the user-
server association approach in addition to optimizing the data size
communicated between player devices and edge servers. The varied geographic
distribution of users often causes workload imbalances between edges, which
leads to certain edge servers being overused and others being underused. Due
to this imbalance, the overall performance of the entire Metaverse service
system is reduced. It is crucial to develop a user-server association strategy
in order to address this issue.

Figure 3: The latency and earning when weight parameter $\omega=2$.

In this case study, we formulate an optimization problem to optimize the
transmission data size by controlling the resolution, and the user-server
association. First, in order to measure the profits and describe how the
service can affect the token earnings a player can make, we propose an
increasing and concave resolution-impacted earning function. Through this
function, a larger transmission data size will increase the visibility of the
player, thus bringing higher profits to the player. If the transmission data
size decreases, visual experience will be degraded, which might provide
particular difficulties to the player, including making sense of the gaming
scene. In this case, the tokens the player can earn are supposed to decrease.
However, with the concave nature of the function, the marginal revenues will
decrease when more data is transmitted.

To achieve a balance between the profits players can make and the latency
players experience, we propose to maximize the utility of the players, which
is defined as the weighted sum of profits and latency as follows:

$\displaystyle\text{Utility}=\text{Profits}-\omega\cdot\text{Total Latency}.$

The weight parameter $\omega$ can be adjusted according to different
preferences on latency. It allows us to capture the trade-off between the
profits and the latency. The user-server association variables are integers
while the transmission data size can be continuous. Thus, the problem is a
mixed-integer nonlinear programming which is considered to be NP-hard. In
addition, the nonlinearity in the objective function makes the problem hard to
solve. In order to tackle the problem, we propose to use alternating
optimization to optimize the transmission data size and user-server
association iteratively. For the transmission data size optimization, it is
proved to be a convex optimization problem which can be solved by standard
convex optimization software such as CVX in Matlab. For the user-to-server
optimization, it is a non-convex problem which can not be solved by convex
optimization tools. Thus, it is transformed into a quadratically constrained
quadratic programming (QCQP) and we utilize the semidefinite relaxation (SDR)
technique to solve the user-to-server problem and get a sub-optimal solution.
To verify the performance of the proposed algorithm, we simulate a system with
20 MSP edge servers and 100 Metaverse players. A uniform distribution of
Metaverse players’ uplink transmission speeds ranges from 1 to 5 Mbps, while a
uniform distribution of their downlink transmission rates ranges from 10 to 20
Mbps. By measuring the latency with regard to different weight parameters
$\omega=2$ and $\omega=4$, we evaluate the proposed methodology. The magnitude
of latency’s impact on the system is indicated by the value of $\omega$. The
overall profits of users are then assessed for various minimum downlink data
sizes. We compare the proposed algorithm with three different algorithms: the
“Optimal Earning” targets at making maximum profits while ignoring the
players’ delay experience. The “Optimal Latency” minimizes only the latency to
acquire the ideal delay experience. The “Random” algorithm chooses random
user-to-server association and transmission data size. Our proposed algorithm
is presented by “Optimal Latency+Earning”. The average earning amount is
scaled to fall between 0 and 1.

In Fig. 3, the weight parameter $\omega$ is set to be 2. It can be seen that
the “Optimal Earning” achieves the maximum profits at the expense of the
highest latency. The “Optimal Latency” strategy maintains the lowest latency
while acquiring little token earning. Compared with “Optimal Earning”, the
proposed “Optimal Latency+Earning” reduces the latency by 50% while obtaining
75% of its token earning. In comparison to “Random”, the proposed strategy
reduces the latency by 30% and increases the earning by 16%.

Figure 4: The latency and earning when weight parameter $\omega=4$.

In Fig. 4, the weight parameter $\omega$ is specified to be 4. It indicates
that more attention is placed on latency. It can be observed that our
technique generates fewer profits when $\omega=2$. It means the system
exchanges latency for profits. The “Optimal Latency” approach maintains low
latency continuously since it only seeks to reduce total latency. As a result,
it consistently picks the smallest downlink data size and earns little tokens.
The proposed “Optimal Latency+Earning” achieves only 36% latency of “Random”
strategy but obtains 81% of its token earning.

##  VI Discussions

The deployment and application of the Metaverse are still at an early stage. A
large number of practical problems are there when large-scale Metaverse
applications are developed. Many challenges come from the high requirement on
user-oriented experience with limited network resources and the heterogeneity
of different traffic patterns.

###  VI-A Hierarchical Edge-Cloud-Enabled Metaverse

The network framework that is used widely today assumes a central cloud server
as a Metaverse service provider where the delivery of service is easy.
However, incorporating the concept of mobile edge computing, a three-layer
hierarchical framework enables the edge server and cloud server to collaborate
to provide Metaverse service. Low bandwidth demands, data storage locally and
low latency Metaverse applications are made possible by the edge servers.
Although an edge-based system enjoys a low delay, the number of devices it can
access is limited. When it involves a machine learning process, the limited
number of participating devices will degrade the system’s overall performance.
While the cloud server can access more devices to train a more accurate model,
an edge-cloud-enabled hierarchical Metaverse system can achieve a balance of
the trade-off between latency and learning performance. Further studies are
necessary on the design of an edge-cloud-enabled hierarchical Metaverse
system, including how to design the offloading strategy and how to associate
the players with edge servers and the cloud.

###  VI-B Metaverse with Augmented Reality (AR), Virtual Reality (VR) or Mixed
Reality (MR)

Augmented reality (AR), virtual reality (VR) and mixed reality (MR) are all
combined into the much larger idea of the Metaverse. The phrase that most
people are acquainted with is probably virtual reality. A 3D virtual
environment created by a computer that either simulates the actual world or an
invented one is referred to as VR. A physical environment is seen in real-time
with its aspects enhanced by digital sensory input like music, images, films,
or GPS information. In other words, AR overlays the physical world by enabling
users to view the real world through the displays of their phones or tablets.
MR, also known as hybrid reality, is the blending of the virtual and real
worlds to create a new setting where real-time interactions between virtual
and real-world items are possible. Many unanswered concerns remain about the
future operation of the Metaverse. Undoubtedly, AR, VR and XR are crucial to
the development of the Metaverse. It is necessary to facilitate the growth, in
order to ensure long-standing connectivity and smooth virtual experiences for
users.

##  VII Conclusion

This paper provides an investigation on the MEC-enabled Metaverse. MEC
utilizes the Metaverse edge server which is close to a particular data source
to provide real-time data processing service. It could significantly reduce
the latency, optimize the wireless communication bandwidth utilization and
ensure an immersive user experience for Metaverse players. This article gives
an overview of the enabling technologies, research problems and MEC-enabled
Metaverse applications. A case study is provided where the transmission data
size and user-to-server association are optimized to maximize users’ utility.
Finally, the paper discusses some future research challenges and directions
that may arise when a large-scale MEC-enabled Metaverse system is deployed in
the presence of limited network resources and heterogeneous traffic patterns.

## References

  * [1] M. Bobrowsky, “Big tech seeks its next fortune in the metaverse,” 2021. [Online]. Available: https://www.wsj.com/articles/big-tech-seeks-its-next-fortune-in-the-metaverse-11636459200
  * [2] S. Kraus, D. K. Kanbach, P. M. Krysta, M. M. Steinhoff, and N. Tomini, “Facebook and the creation of the metaverse: radical business model innovation or incremental transformation?” _International Journal of Entrepreneurial Behavior & Research_, 2022.
  * [3] L.-H. Lee, T. Braud, P. Zhou, L. Wang, D. Xu, Z. Lin, A. Kumar, C. Bermejo, and P. Hui, “All one needs to know about metaverse: A complete survey on technological singularity, virtual ecosystem, and research agenda,” _arXiv preprint arXiv:2110.05352_ , 2021.
  * [4] J. Yu, A. Alhilal, P. Hui, and D. H. Tsang, “6g mobile-edge empowered metaverse: Requirements, technologies, challenges and research directions,” _arXiv preprint arXiv:2211.04854_ , 2022.
  * [5] A. Musamih, I. Yaqoob, K. Salah, R. Jayaraman, Y. Al-Hammadi, M. Omar, and S. Ellahham, “Metaverse in healthcare: Applications, challenges, and future directions,” _IEEE Consumer Electronics Magazine_ , 2022.
  * [6] M. Aloqaily, O. Bouachir, F. Karray, I. Al Ridhawi, and A. El Saddik, “Integrating digital twin and advanced intelligent technologies to realize the metaverse,” _IEEE Consumer Electronics Magazine_ , 2022.
  * [7] W. Saad, M. Bennis, and M. Chen, “A Vision of 6G Wireless Systems: Applications, trends, Technologies, and Open Research Problems,” _IEEE network_ , vol. 34, no. 3, pp. 134–142, 2019.
  * [8] E. C. Strinati and S. Barbarossa, “6G Networks: Beyond Shannon towards Semantic and Goal-Oriented Communications,” _Computer Networks_ , vol. 190, p. 107930, 2021.
  * [9] M. Xu, W. C. Ng, W. Y. B. Lim, J. Kang, Z. Xiong, D. Niyato, Q. Yang, X. S. Shen, and C. Miao, “A full dive into realizing the edge-enabled metaverse: Visions, enabling technologies, and challenges,” _IEEE Communications Surveys & Tutorials_, 2022.
  * [10] A. Asheralieva and D. Niyato, “Secure and Efficient Coded Multi-Access Edge Computing with Generalized Graph Neural Networks,” _IEEE Transactions on Mobile Computing_ , pp. 1–1, 2022.
  * [11] W. Y. B. Lim, Z. Xiong, D. Niyato, X. Cao, C. Miao, S. Sun, and Q. Yang, “Realizing the metaverse with edge intelligence: A match made in heaven,” _arXiv preprint arXiv:2201.01634_ , 2022.
  * [12] V. Nair, G. M. Garrido, and D. Song, “Going Incognito in the Metaverse,” _arXiv preprint arXiv:2208.05604_ , 2022.
  * [13] Z. Allam, A. Sharifi, S. E. Bibri, D. S. Jones, and J. Krogstie, “The metaverse as a virtual form of smart cities: Opportunities and challenges for environmental, economic, and social sustainability in urban futures,” _Smart Cities_ , vol. 5, no. 3, pp. 771–801, 2022.
  * [14] Z.-Q. Zhao, P. Zheng, S.-t. Xu, and X. Wu, “Object detection with deep learning: A review,” _IEEE transactions on neural networks and learning systems_ , vol. 30, no. 11, pp. 3212–3232, 2019.
  * [15] Y. Cai, J. Llorca, A. M. Tulino, and A. F. Molisch, “Compute-and data-intensive networks: The key to the metaverse,” _arXiv preprint arXiv:2204.02001_ , 2022.
  * [16] Qualcomm, “Oculus quest 2: How snapdragon xr2 powers the next generation of vr,” 2020. [Online]. Available: https://www.qualcomm.com/news/onq/2020/10/oculus-quest-2-how-snapdragon-xr2-powers-next-generation-vr
  * [17] L. H. Lee, T. Braud, F. H. Bijarbooneh, and P. Hui, “Ubipoint: towards non-intrusive mid-air interaction for hardware constrained smart glasses,” in _Proceedings of the 11th ACM Multimedia Systems Conference_ , 2020, pp. 190–201.
  * [18] “Metaverse: A guide to the next-gen internet connections series technology, media and telecoms,” 2022. [Online]. Available: https://www.credit-suisse.com/media/assets/corporate/docs/about-us/media/media-release/2022/03/metaverse-14032022.pdf

## Biographies

Chang Liu is currently pursuing a Ph.D. degree with School of Computer Science
and Engineering, Nanyang Technological University. His research interests
include federated learning and Metaverse.

Yitong Wang is currently pursuing a Ph.D. degree with School of Computer
Science and Engineering, Nanyang Technological University. His research
interests include mobile edge computing.

Jun Zhao (S’10-M’15) is currently an Assistant Professor in the School of
Computer Science and Engineering at Nanyang Technological University (NTU) in
Singapore. His research interests include blockchain, edge/fog computing, and
Metaverse.


A Tale of Two Limits: An Extremal Pagerank ProblemJ. Farnan and F. Kenter

# A Tale of Two Limits: An Extremal Pagerank Problem††thanks: Submitted to the
editors April 8, 2021. This work was funded in part by the NSF-DMS-1720225

and Franklin H. J. Kenter  Joseph Farnan United States Naval Academy,
Annapolis, MD<EMAIL_ADDRESS>Franklin H. J. Kenter United
States Naval Academy, Annalpols, MD<EMAIL_ADDRESS>
# A Tale of Two Limits, An Extremal Pagerank Problem

and Franklin H. J. Kenter  Joseph Farnan United States Naval Academy,
Annapolis, MD<EMAIL_ADDRESS>Franklin H. J. Kenter United
States Naval Academy, Annalpols, MD<EMAIL_ADDRESS>
###### Abstract

For a directed graph, the Pagerank algorithm emulates a random walker on the
graph that occasionally “jumps” to a random vertex based on a jumping
parameter $\alpha$. Upon completion, the algorithm generates a stochastic
vector whose entries correspond to the limiting probability that the walker
will be at that vertex. This vector is a right eigenvector of a corresponding
Markov trasition matrix. Undoubtedly, this vector can drastically change based
upon the jumping parameter $\alpha$.

In this article, we investigate the maximum possible discrepancy for different
Pagerank vectors on the same unweighted directed (perhaps with loops) graph as
measured by the 2-norm. We show that the limsup of this discrepancy can be as
large as $\sqrt{\frac{67}{50}}$ using a very specific construction. (For
contrast, the norm of the difference for any two stochastic vectors is at most
$\sqrt{2}$.) Interestingly, on this construction this discrepancy occurs when
$\alpha=1$ and when $\alpha$ is very close to 1.

###### keywords:

directed graphs, Pagerank algorithm, spectral graph theory, extremal spectral
graph theory

05C35, 05C50, 05C81

##  1 Introduction

###  1.1 Overview

One way to rank the relative importance of vertices on a directed graph
(network) is to use the Pagerank algorithm. The Pagerank algorithm was
developed by Page and Brin to address the conundrum between quantity versus
quality in the context of webpages [2], as a webpage could be considered
influential either because it is linked to by many sites or by a few, high-
quality sites. For instance, many space-enthusiasts may link to a NASA,
indicating its authority. In turn, NASA may link to a revered astrophysicist
on its own, indicating its endorsement.

Pagerank and similar network algorithms have been developed for other
contexts. In the of a sports league, the graph could have teams be the
vertices and the directed edges represent a team losing against the other
team. Previous work has utilized this idea of to rank NCAA College Football
teams where it is often the case that some teams perform very well but with
weaker opponents [3]. In social media, the graph would have users of vertices
and the directed edges represent one user following or mentioning one another.
In [6], the PageRank algorithm is used to provide an alternative measure of
influence of Twitter users beyond simply counting the number of retweets. That
is, who retweets our message is just as important as how many times it is
retweeted.

Consider a directed graph, $G$. For our purposes and throughout, $G$ may have
loops and bidirectional edges (i.e., there is an arc from $i$ to $j$ and
another arc from $j$ to $i$). However, there will be no duplicate arcs (i.e.,
there is at most one arc from $i$ to $j$). The Pagerank algorithm produces a
vector of length $n$ (the number of vertices in $G$), denoted $\pi$, where
each entry measures on the proportion of the time we would encounter each
vertex by simply wandering around the graph randomly and occasionally jump
around. Hence, the Pagerank vector is a stochastic vector.

To begin calculating the Pagerank vector, consider a directed graph $G$ and
choose an $\alpha$ to be your jumping parameter, $0<\alpha<1$. The parameter
$\alpha$ will determine the proportion of the time we will follow an arc in
our random process. Intuitively, $\alpha$ balances the impact of arcs from
high-quality vertices and high quantities of arcs. Once $\alpha$ is chosen,
randomly pick a vertex of $G$ uniformly at random to start, denoted $v$. Then,
with probability $\alpha$, choose an out-neighbor of $v$, uniformly at random,
and walk to that vertex; and with probability $1-\alpha$, jump to an another
random vertex chosen uniformly at random. If $v$ has no out neighbors, then
simply jump to a random vertex, chosen uniformly at random. Take the vertex we
are on and declare that the new $v$ and repeat. The Pagerank vector is the
limiting probability of finding ourselves at each vertex after an arbitrarily
large number of steps. Intuitively, the more often we visit a vertex, the more
important it is and the higher the (Page)rank it has!

For a given directed graph $G$ and $\alpha$, we define the Pagerank vector
with jumping parameter $\alpha$

$(\pi_{\alpha})_{i}=\lim_{t\to\infty}P(\text{being at vertex }i\text{ at step
}t)$

for each vertex $i$.

The Pagerank can be interpreted using linear algebra in the context of Markov
chains where the probability transition matrix for a directed graph $G$,
$\mathbf{R}$, is given by

$\mathbf{R}_{ij}=\begin{cases}\frac{\alpha}{{deg}^{out}_{j}}+\frac{1-\alpha}{n}~{}\text{
if }~{}{deg}^{out}_{j}\neq 0\\\ \frac{1}{n}~{}\text{otherwise}\end{cases}$

Where $deg_{j}^{out}$ is the number of out neighbors of j. In which case, the
Pagerank vector $\pi$ is a right eigenvector of $\mathbf{R}$ with eigenvalue 1

$\mathbf{R}\pi=\pi$

and is the stationary distribution of the random walk.

The existence and uniqueness of $\pi$ guaranteed by the Perron-Frobenius
Theorem for all $0\leq\alpha<1$ (see, for example, [4]). For $\alpha=1$,
$\pi_{\alpha}$ is well-defined provided $G$

  * •

is aperiodic (i.e., the greatest common divisor of the length of all cycles is
1),

  * •

is weakly connected and

  * •

there is a unique maximal induced subgraph that is strongly connected (perhaps
with just a vertex with a single loop).

For simplicity, we will typically drop one of the subscripts of the Pagerank
vector. We note that in this paper we will use subscripts to both the value of
$\alpha$ and which vertex is being spoken of. For instance, we write
$\pi_{\alpha=1}$ to refer to the entire Pagerank vector when $alpha=1$ but
also we write $\pi_{A}$ to denote to entry of the Pagerank vector
corresponding to the vertex $A$; in the later case, the context of $\alpha$
will be clear.

###  1.2 Problem Statement

Even on the same graph, choosing different values for $\alpha$ can result in
substantially different Pagerank vectors. For example, when $\alpha=0$, the
walker always jumps, in which case $\pi_{\alpha}$ is the uniform vector:
$(1/n,1/n,\ldots,1/n)$ where $n$ is the number of vertices in $G$. On the
other extreme, when $\alpha=1$, the walker always follows the arcs (unless
they are stuck), so naturally, vertices with more in-arcs will be visited more
often. In this situation, it is possible that $\pi_{\alpha}$ is concentrated
at one vertex. This leads to the question: For the same graph, how different
can these rankings be? Our main problem is to determine the maximum difference
between Pagerank vector with one $\alpha$ and a Pagerank with a different
$\alpha$ but on the same graph. Formally we ask:

######  Problem 1.1.

How large can

$||\pi_{\alpha_{1}}-\pi_{\alpha_{2}}||_{2}$

be over all directed graphs $G$ and $\alpha_{1}$, $\alpha_{2}$ with
$0\leq\alpha_{1},\alpha_{2}\leq 1$? Here, $\pi_{\alpha_{1}}$ is the Pagerank
vector produced on the graph $G$ with jumping constant $\alpha_{1}$, and
$\pi_{\alpha_{2}}$ is the ranking values returned by the Pagerank algorithm
for the graph $G$ with jumping constant different $\alpha_{2}$.

We focus on the 2-norm as it is the traditional norm, though we briefly
discuss the problem for other norms in Section 3 which we leave as an open
problem for the reader.

As we will discover, this problem is difficult because it requires carefully
constructed examples with precisely chosen parameters $\alpha_{1}$ and
$\alpha_{2}$. While we do not answer this problem explicitly, we provide a
construction that provides an extremal value of $\sqrt{\frac{67}{50}}$.
Surprisingly, to achieve this, we use $\alpha_{1}=1$ and $\alpha_{2}$ very
close to 1. We believe $\sqrt{\frac{67}{50}}$ to be best possible.

###  1.3 Previous Similar Work

Based on the linear-algebraic interpretation of Pagerank mentioned previously,
this problem is fundamentally one about the principal eigenvector of graph-
theoretic matrices. Indeed, problems of a similar nature have been considered
before. For an irreducible nonnegative matrix, the principal ratio is the
ratio between the maximum and minimum entries of the principal eigenvector.
For Markov transition matrices of simple directed graphs, Askoy, Chung, and
Peng show that the principal ratio of a random walk can be superexponentially
small [1]. For the adjacency matrix of undirected graphs, Tait proved that the
“kite graph” (a complete graph with a long path) acheives the maximum
principal ratio [9].

###  1.4 Important facts and properties of PageRank

To get our feet wet, here are some important properties of Pagerank vectors we
use.

######  Fact 1.2.

For $\alpha=0$, $\pi_{\alpha}=(1/n,1/n,\ldots,1/n)^{\prime}$.

Where $n$ is the number of vertices in the graph. What this says is that, in
practice, one should choose an $\alpha$ away from 0 so that the resulting
values vertices are more differentiated. Indeed, the original $\alpha$ for the
Pagerank algorithm was $\alpha=0.85$ [2].

In the context of maximizing $\|\pi_{\alpha=1}-\pi_{\alpha=x}\|_{2}$, this
suggests that we would want to choose $\alpha$’s away from 0. Our the extremal
choices for $\alpha$ are closer to 1.

Also, in practice, people usually avoid choosing an $\alpha$ close to 1
because accurately computing $\pi_{\alpha\approx 1}$ numerically is
challenging using methods such as the power method [7]. Our graphical plots
fail to show the true behavior near $\alpha=1$ because when $k$ is large,
these numerical methods are not accurate enough! See for example figure 2

######  Fact 1.3.

$||\pi||_{2}\leq 1$.

###### Proof.

$||\pi||_{2}\leq||\pi||_{1}=1$.

######  Fact 1.4.

$||\pi_{\alpha}||_{\infty}\leq 1$ or in other words, $max(\pi_{i})\leq 1$.

######  Fact 1.5.

$||\pi_{\alpha_{1}}-\pi_{\alpha_{2}}||_{\infty}\leq 1$.

###### Proof.

$||\pi_{\alpha_{1}}-\pi_{\alpha_{2}}||_{\infty}\leq|max(|\pi_{\alpha_{1}}|,|\pi_{\alpha_{2}}|)|_{\infty}\leq
1$.

######  Fact 1.6.

$||\pi_{1}-\pi_{2}||_{2}\leq\sqrt{2}$

###### Proof.

$||\pi_{1}-\pi_{2}||_{2}\leq\sqrt{||\pi_{1}||_{1}+||\pi_{2}||_{1}}\leq\sqrt{2}$.
The first inequality holds because the $\pi$s are non-negative.

This last bound is important because it provides an upper bound for how high
$\|\pi_{\alpha=1}-\pi_{\alpha=x}\|_{2}$ can be. While we are unable to achieve
$\sqrt{2}\approx 1.4142$, we are not too far from it:
$\sqrt{\frac{67}{50}}\approx 1.1576$.

##  2 Main Result

######  Theorem 2.1.

For any $\delta>0$, there exists an unweighted directed graph and
$\alpha_{1}=1$ and $\alpha_{2}$ with

$\|\pi_{\alpha_{1}}-\pi_{\alpha_{2}}\|\geq\sqrt{\frac{67}{50}}-\delta.$

In particular, for the Pagerank vectors on the directed graph on $\Gamma(k)$
(defined in the next subsection),

$\lim_{k\to\infty}\|\pi_{\alpha_{1}=1}-\pi_{\alpha_{2}=1-1/k}\|=\sqrt{\frac{67}{50}}.$

This answer is very interesting in several ways. First, the answer depends on
the number of vertices in the graph in the sense that increasing the number of
vertices in the graph enabled an slightly increased value of
$||\pi_{\alpha_{1}}-\pi_{\alpha_{2}}||_{2}$. In this paper, we will show that
$\displaystyle\lim_{k\to\infty}||\pi_{\alpha_{1}}-\pi_{\alpha_{2}}||_{2}$
(where $k+3$ is number of vertices in the graph for very large $k$) goes to a
certain size, but implicit in this is that increasing the number of vertices
in the graph will allow a value closer to the limit. Also, the extremal
difference occurs approximately when $\alpha=1$ and $1>\alpha\geq 1-1/k$.
Figure 2 plots $\|\pi_{\alpha=1}-\pi_{\alpha=x}\|_{2}$ for a particular
construction we give in the next section. The graph is beyond deceiving! When
$x=1$, the value for $\|\pi_{\alpha=1}-\pi_{\alpha=x}\|_{2}=0$, but a large
enough graph, the maximum value is achieved very very close to $x=1$!

We believe the value $\sqrt{\frac{67}{50}}$ is the best possible:

######  Conjecture 2.2.

For _any_ unweighted directed graph (perhaps with loops and perhaps bidirected
arcs) and two jumping constants $\alpha_{1}$ and $\alpha_{2}$, we have,

$\|\pi_{\alpha_{1}}-\pi_{\alpha_{2}}\|<\sqrt{\frac{67}{50}}.$

We will give our reasoning and intuition for this conjecture in Section 3

###  2.1 Our Construction, $\Gamma(k)$

Our construction is a long “ladder” with $k+3$ vertices:
$C_{1},C_{2},B_{1},\ldots,B_{k},$ and $A$. It is illustrated in graph Figure 1
and is constructed as follows. Vertex $C_{1}$ has an arc to itself and to
$C_{2}$. $C_{2}$ has an arc back to $C_{1}$, a loop to itself and a path to
$B_{1}$. $B_{1}$ has an arc back to $C_{1}$ and $C_{2}$, and an arc to
$B_{2}$. Likewise, for all $i<k$, $B_{i}$, has arcs back to both $C_{1}$ and
$C_{2}$ and an arc to $B_{i+1}$. Then, $B_{k}$ which has an arc back to
$C_{1}$ and $C_{2}$ and to a vertex $A$. However, vertex $A$ only has a loop
to itself.

This construction will end up concentrating the random walkers either in $A$
or in $C_{1}$ and $C_{2}$, depending on the value of the jumping constant
$\alpha$.

When $\alpha=1$, the random walker will always follow the arcs. The walker
will climb up and fall down “the ladder”, but inevitably, they will eventually
make it to $A$ and become stuck. Therefore, when $\alpha=1$ we have
$\pi_{A}=1$.

On the other hand, for other, carefully chosen, values of $\alpha$ close to 1,
the random walker will frequently “fall down” to $C_{1}$ and $C_{2}$. In which
case, it is next to impossible for the walker to get to $A$. And even if the
walker gets to $A$, since $\alpha<1$, the walker is able to avoid becoming
stuck. Within the proof of Theorem 2.1, we show that $\pi_{A}\to 0$ as
$k\to\infty$ for $\alpha=1-1/k$.

$A$$B_{k}$$\cdots$$B_{1}$$C_{2}$$C_{1}$
Figure 1: Construction of the family of graphs used in the proof of Theorem
2.1

###  2.2 Proof of Theorem 2.1

Our proof is outlined as follows. We will start by explicitly computing
$\pi_{\alpha_{1}=1}$ for $\Gamma(k)$ for any $k>0$. We then compute
$\pi_{\alpha_{2}=1-1/k}$ and show that $\pi_{C_{1}}$ and
$\pi_{C_{2}}\to\frac{2}{5}$ as $k\to\infty$. We then analyze $\pi_{B_{i}}$ and
show that $\sum_{i}\pi_{B_{i}}^{2}$ can be approximated by a geometric series
in terms of $\pi_{C_{2}}$. As a result, we will have that as $k\to\infty$,
$\|\pi_{\alpha_{1}=1}-\pi_{\alpha_{2}=1-1/k}\|_{2}^{2}\to 67/50$.

####  2.2.1 Computing $\pi_{\alpha=1}$

######  Lemma 2.3.

When $\alpha=1$, $\pi_{A}=1$, and $\pi_{v}=0$ for any vertex $v\neq A$.

######  Proof 2.4.

The loop at $A$ ensures that when $\alpha=1$, a “random-walker” must follow
their way to $A$ and remain there. Therefore, $\pi_{A}$ has a value of 1 at
vertex $A$ and 0 at all other vertices.

Now, the more difficult task, of carefully computing $\pi_{\alpha_{2}=1-1/k}$
remains.

####  2.2.2 Computing $\pi_{A}$ when $\alpha=1-1/k$

We will show that as $k\to\infty$,

$\pi_{C_{1}}\to\frac{2}{5},\quad\pi_{C_{2}}\to\frac{2}{5},\text{ and
}\quad\pi_{A}\to 0.$

Our main technique for computing $\pi_{v}$ is to consider change with each
time step for sufficiently large $t$. We let
$\Delta\pi_{v}=\sum_{u}\left(\mathbf{R}_{v,u}\pi_{u}\right)-\pi{v}$.
Effectively, $\Delta\pi_{v}$ is “rate in” - “rate out”.

######  Lemma 2.5.

For any vertex $v$, the stationary distribution obeys $\Delta\pi_{v}=0$.

$\square$
We can apply the previous lemma to compute $\pi_{A}$.

For a random walker to reach $A$ there are 4 disjoint possibilities:

  * •

$k$ steps ago, the random walker was at $C_{2}$ and did not jump within the
intervening $k$ steps from $C_{2}$ to A.

  * •

1 step ago, the walker was at $A$ and then they took the loop back to $A$.

  * •

$k-i$ steps ago, the walker jumped to $B_{i}$ and the made it up the “ladder”
to $A$ without jumping again, or

  * •

the walker could have directly jumped to $A$.

Therefore, we have

$\Delta\pi_{A}=\left(\left(1-\frac{1}{k}\right)^{k}\pi_{C_{2}}(1/3)^{k}+\left(1-\frac{1}{k}\right)\pi_{A}+\sum_{i=1}^{k}\frac{\frac{1}{k}(1/3)^{k-i}\left(1-\frac{1}{k}\right)^{k-i}}{3+k}\right)-\pi_{A}.$

The first term accounts for the first possibility. The second term accounts
for the second possibility. The sum accounts for the last two possibilities.
Finally, $-\pi_{A}$ falls from the definition of $\Delta\pi_{A}$ and contains
all of the walkers leaving $A$ even if they come back.

This simplifies to

$\Delta\pi_{A}=\left(\left(1-\frac{1}{k}\right)^{k}\pi_{C_{2}}(1/3)^{k}+-\frac{1}{k}\pi_{A}+\sum_{i=1}^{k}\frac{\frac{1}{k}(1/3)^{k-i}(1-\frac{1}{k})^{k-i}}{3+k}\right).$

Claim:

$\pi_{A}\to 0\text{ as }k\to\infty$

######  Proof 2.6.

For the stationary distribution,

$\Delta\pi_{A}=(1-\frac{1}{k})^{k}\pi_{C_{2}}(1/3)^{k}-\pi_{A}/k+\sum_{i=1}^{k}\frac{\frac{1}{k}(1/3)^{k-i}(1-\frac{1}{k})^{k}}{3+k}.$

Observe that the series

$\sum_{i=1}^{k}\left(\frac{1/k~{}(1/3)^{k-i}(1-1/k)^{k}}{3+k}\right).$

is a finite geometric series that’s bounded above by its infinite sum which is

$\frac{3/k}{2(3+k)}.$

And solving for $\pi_{A}$ we have

$\pi_{A}<\frac{(1-1/k)^{k}\pi_{C_{2}}(1/3)^{k}}{1/k}+\frac{3}{2(3+k)}.$

Since $0\leq\pi_{C_{2}}\leq 1$ and $1/k>0$, we can simplify the above equation

(2.1)
$\pi_{A}<\frac{(1-1/k)^{k}(1/3)^{k}}{1/k}+\frac{3}{2(3+k)}<\frac{(1/3)^{k}}{1/k}+\frac{3}{2(3+k)}=\frac{k}{3^{k}}+\frac{3}{2(k+1)}.$

Therefore, as $k\to\infty$, $\pi_{A}\to 0$

####  2.2.3 Relating $\pi_{C_{1}}$, $\pi_{C_{2}}$ and $\sum_{i}\pi_{B_{i}}$
when $\alpha=1-1/k$

Claim:

$\pi_{C_{1}}=\pi_{C_{2}}$

and

$\pi_{C_{1}}=\frac{1/k}{3+k}+(1-1/k)\cdot\frac{\sum_{i=1}^{k}\pi_{B_{i}}}{3}+\pi_{C_{1}}/3+(1-1/k)\cdot\pi_{C_{1}}/2$

and hence

$\pi_{C_{2}}=\frac{1/k}{3+k}+(1-1/k)\cdot\frac{\sum_{i=1}^{k}\pi_{B_{i}}}{3}+\pi_{C_{2}}/3+(1-1/k)\cdot\pi_{C_{2}}/2$

######  Proof 2.7.

Now, consider $\Delta\pi_{C_{1}}$ and $\Delta\pi_{C_{2}}.$ For $C_{1}$, the
vertex at the bottom of the chain of vertices, we have

$\Delta\pi_{C_{1}}=\frac{1/k}{3+k}+(1-1/k)\cdot\frac{\sum_{i=1}^{k}\pi_{B_{i}}}{3}+\pi_{C_{2}}/3+(1-1/k)\cdot\pi_{C_{1}}/2-\pi_{C_{1}}$

This follows similarly to the case for $A$ and $\pi_{A}$ previously. The first
term is represents mass jumping from some vertex to $C_{1}$; the second term
is the probability mass that is at $B_{i}$ and returns to $C_{1}$; the third
term is the mass from $C_{2}$ that goes back to $C_{1}$; the fourth term is
the probability that $C_{1}$ gets from its self loop; and the fifth term is
everything leaving $C_{1}$.

For $\Delta\pi_{C_{1}}=0$, we have

$\pi_{C_{1}}=\frac{1/k}{3+k}+(1-1/k)\cdot\frac{\sum_{i=1}^{k}\pi_{B_{i}}}{3}+\pi_{C_{2}}/3+(1-1/k)\cdot\pi_{C_{1}}/2$

Similarly for $\pi_{C_{2}}$, we have

$\Delta\pi_{C_{2}}=\frac{1/k}{3+k}+(1-1/k)\cdot\frac{\sum_{i=1}^{k}\pi_{B_{i}}}{3}+(1-1/k)\cdot\pi_{C_{2}}/3+(1-1/k)\cdot\pi_{C_{1}}/2-\pi_{C_{2}}$

and

(2.2)
$\pi_{C_{2}}=\frac{1/k}{3+k}+(1-1/k)\cdot\frac{\sum_{i=1}^{k}\pi_{B_{i}}}{3}+(1-1/k)\cdot\pi_{C_{2}}/3+(1-1/k)\cdot\pi_{C_{1}}/2$

The symmetry for the equations for $\pi_{C_{1}}$ and $\pi_{C_{2}}$ give that

$\pi_{C_{1}}=\pi_{C_{2}}$

Now, let us relate $\pi_{C_{2}}$ to the $\pi_{B_{i}}$.

We can substitute $\pi_{C_{2}}$ in for $\pi_{C_{1}}$ in the equation for
$\pi_{C_{2}}$

$\pi_{C_{2}}=\frac{1/k}{3+k}+(1-1/k)\cdot\frac{\sum_{i=1}^{k}\pi_{B_{i}}}{3}+(1-1/k)\cdot\pi_{C_{2}}/3+(1-1/k)\cdot(\pi_{C_{2}})/2$
(2.3)
$\pi_{C_{2}}=\frac{1/k}{3+k}+(1-1/k)\cdot\frac{\sum_{i=1}^{k}\pi_{B_{i}}}{3}+\frac{(1-1/k)\cdot\pi_{C_{2}}\cdot
5}{6}$

Finally, let us each consider the $\pi_{B_{i}}$.

$\Delta\pi_{B_{i}}=\frac{1/k}{3+k}+(1-1/k)\cdot\frac{\pi_{B_{i-1}}}{3}-\pi_{B_{i}}$

And thus for the stationary distribution,

$\pi_{B_{i}}=\frac{1/k}{3+k}+(1-1/k)\cdot\frac{\pi_{B_{i-1}}}{3}$

And also for $B_{1}$,

$\pi_{B_{1}}=\frac{1/k}{3+k}+(1-1/k)\cdot\frac{\pi_{C_{2}}}{3}$

$\pi_{B_{i}}>(1-1/k)\frac{\pi_{B_{i-1}}}{3}$

and

$\pi_{B_{1}}>(1-1/k)\frac{\pi_{C_{2}}}{3}.$

So by induction,

(2.4) $\pi_{B_{i}}>(1-1/k)^{i}\frac{\pi_{C_{2}}}{3^{i}}$

and

$\sum_{i=1}^{k}\pi_{B_{i}}>\sum_{i=1}^{k}(1-1/k)^{i}\frac{\pi_{C_{2}}}{3^{i}}=\frac{(\pi_{C_{2}}-\pi_{C_{2}}(\frac{1-1/k}{3})^{k})}{(1-\frac{1-1/k}{3})}$

This equation comes from viewing the previous equations as a finite geometric
series.

####  2.2.4 Showing $\pi_{C_{1}},\pi_{C_{2}}\to\frac{2}{5}$

We will now evaluate the limit with our choice $\alpha=1-\frac{1}{k}$. We
already know that as $k\to\infty$, $\pi_{A}\to 0$; now we show that
$\pi_{C_{1}}\to 2/5$, $\pi_{C_{2}}\to 2/5$.

Claim:

$\pi_{C_{1}}=\pi_{C_{2}}\to\frac{2}{5}$

######  Proof 2.8.

We will show that $\lim_{k\to\infty}\pi_{C_{2}}\leq\frac{2}{5}$ and that
$\lim_{k\to\infty}\pi_{C_{2}}\geq\frac{2}{5}$

Let’s start with

$\pi_{C_{1}}+\pi_{C_{2}}+\pi_{A}+\sum_{i=1}^{k}\pi_{B_{i}}=1.$

and so

$\lim_{k\to\infty}\left[\pi_{C_{1}}+\pi_{C_{2}}+\pi_{A}+\sum_{i=1}^{k}\pi_{B_{i}}\right]=1.$

By (2.2) we can substitute

$\displaystyle\pi_{C_{1}}$ $\displaystyle=$ $\displaystyle\pi_{C_{2}}$

into the above:

$\lim_{k\to\infty}\left[2\pi_{C_{2}}+\pi_{A}+\sum_{i=1}^{k}\pi_{B_{i}}\right]=1.$

and by distributing the limits:

$2\left[\lim_{k\to\infty}\pi_{C_{2}}\right]+\left[\lim_{k\to\infty}\pi_{A}\right]+\left[\lim_{k\to\infty}\sum_{i=1}^{k}\pi_{B_{i}}\right]=1.$

Since $\pi_{A}\to 0$, We can find the total ranking as

$\sum_{i=1}^{k}\pi_{B_{i}}+\pi_{C_{1}}+\pi_{C_{2}}\to 1.$

To find an upper bound for $\pi_{C_{2}}$ we can sum the Pagerank values in
$C_{2}$, $C_{1}$ and the value of the $\pi_{B_{i}}$s that comes from $C_{2}$.
This gives us:

$1>\pi_{C_{1}}+\frac{((\pi_{C_{2}}-\pi_{C_{2}}\cdot(\frac{1-1/k}{3})^{k})}{(1-\frac{1-1/k}{3})}$

By taking the limit of both sides

$\
\lim_{k\to\infty}1\geq\lim_{k\to\infty}\left[\pi_{C_{1}}+\frac{(\pi_{C_{2}}-\pi_{C_{2}}\cdot(\frac{1-1/k}{3})^{k}}{(1-\frac{1-1/k}{3})}\right]$

$1\geq\lim_{k\to\infty}\left[\pi_{C_{1}}\right]+\lim_{k\to\infty}\left[\frac{(\pi_{C_{2}}-\pi_{C_{2}}\cdot(\frac{1-1/k}{3})^{k}}{(1-\frac{1-1/k}{3})}\right]$

Splitting the fraction and substituting $\pi_{C_{2}}$ in for $\pi_{C_{1}}$

$1>\lim_{k\to\infty}(\pi_{C_{2}})+\left[\lim_{k\to\infty}\frac{\pi_{C_{2}}}{(1-\frac{1-1/k}{3})}\right]-\lim_{k\to\infty}\left[\frac{\pi_{C_{2}}\cdot(\frac{1-1/k}{3})^{k}}{(1-\frac{1-1/k}{3})}\right]$

Taking the limits

$1\geq\lim_{k\to\infty}\pi_{C_{2}}+\lim_{k\to\infty}\frac{\pi_{C_{2}}}{\frac{2}{3}}-0$

And so by solving for $\lim_{k\to\infty}\pi_{C_{2}}$,

$2/5\geq\lim_{k\to\infty}\pi_{C_{2}}$

We now find a lower bound for $\pi_{C_{2}}$.

Let’s start with (2.2):

$\pi_{C_{2}}=\frac{1/k}{3+k}+(1-1/k)\cdot\frac{\sum_{i=1}^{k}\pi_{B_{i}}}{3}+\frac{(1-1/k)\cdot\pi_{C_{2}}\cdot
5}{6}$

By removing the first term,

$\pi_{C_{2}}>(1-1/k)\frac{\sum_{i=1}^{k}\pi_{B_{i}}}{3}+\frac{5(1-1/k)\pi_{C_{2}}}{6})$

Combining the $\pi_{C_{2}}$ terms,

$\pi_{C_{2}}-\frac{\pi_{C_{2}}\cdot
5}{6}+\frac{5\pi_{C_{2}}}{6k}>(1-1/k)\cdot\frac{\sum_{i=1}^{k}\pi_{B_{i}}}{3}$

Simplifying

$\frac{\pi_{C_{2}}}{6}+\frac{5\pi_{C_{2}}}{6k}>(1-1/k)\cdot\frac{\sum_{i=1}^{k}\pi_{B_{i}}}{3}$

Therefore,

(2.5)
$\sum_{i=1}^{k}\pi_{B_{i}}<\left(\frac{\pi_{C_{2}}}{6}+\frac{5\pi_{C_{2}}}{6k}\right)\cdot\frac{3}{(1-1/k)}$

By applying this,

$\pi_{C_{1}}+\pi_{C_{2}}+\pi_{A}+\sum_{i=1}^{k}\pi_{B_{i}}=1$

$\displaystyle 1$ $\displaystyle<$
$\displaystyle\pi_{C_{2}}+\pi_{C_{2}}+\frac{k}{3^{k}}+\frac{1}{2k}$
$\displaystyle+\left(\frac{\pi_{C_{2}}}{6}+\frac{5\pi_{C_{2}}}{6k}\right)\frac{3}{(1-1/k)}$

Which will help us to find $\pi_{C_{2}}$ since

$\displaystyle 1$ $\displaystyle<$
$\displaystyle\pi_{C_{2}}+\pi_{C_{2}}+\frac{\pi_{C_{2}}}{2(1-1/k)}+\frac{k}{3^{k}}+\frac{1}{2k}+\frac{5\pi_{C_{2}}}{2k-2}$

Or solving for $\pi_{C_{2}}$,

$\pi_{C_{2}}>\frac{2}{5}-\frac{\pi_{C_{2}}}{2}(\frac{k}{k-1}-1)-\frac{k}{3^{k}}-\frac{1}{2k}-\frac{5\pi_{C_{2}}}{2k-2}$

Let
$d=\frac{\pi_{C_{2}}}{2}(\frac{k}{k-1}-1)+\frac{k}{3^{k}}+\frac{1}{2k}+\frac{5\pi_{C_{2}}}{2k-2}$.
We do this because as $k\to\infty,d\to 0$ and because
$\pi_{C_{2}}>\frac{2}{5}-d$ which implies:

$\lim_{k\to\infty}\pi_{C_{1}}=\lim_{k\to\infty}\pi_{C_{2}}=\frac{2}{5}$

####  2.2.5 Computing $\|\pi_{\alpha=1-1/k}\|^{2}$

To compute $\|\pi_{\alpha=1-1/k}\|^{2}$, we are not necessarily concerned with
what $\sum_{i=1}^{k}\pi_{B_{i}}$ is equal to, rather we are more concerned
about what $\sum_{i=1}^{k}\pi_{B_{i}}^{2}$ is equal to.

Using the fact that $\pi_{C_{1}}=\pi_{C_{2}}$ and $\pi_{C_{2}}\to 2/5$ and
$\pi_{C_{2}}+\sum_{i=1}^{k}\pi_{B_{i}}$ goes to a geometric series we now have
the following,

######  Lemma 2.9.

$\lim_{k\to\infty}\|\pi_{\alpha=1-1/k}\|_{2}^{2}\to\frac{17}{50}$

######  Proof 2.10.

As before, we will provide an lower bound and then an upper bound for
$\lim_{k\to\infty}\|\pi_{\alpha=1-1/k}\|_{2}^{2}.$

Let us begin with the lower bound.

$\displaystyle\|\pi_{\alpha=1-1/k}\|_{2}^{2}$ $\displaystyle=$
$\displaystyle\pi_{A}^{2}+\pi_{C_{1}}^{2}+\pi_{C_{2}}^{2}+\sum_{i}^{k}\pi_{B_{i}}^{2}$
$\displaystyle>$
$\displaystyle\pi_{A}^{2}+\pi_{C_{1}}^{2}+\pi_{C_{2}}^{2}+\sum_{i=1}^{k}(1-1/k)^{i}\frac{\pi_{C_{2}}}{3^{i}}$
$\displaystyle=$
$\displaystyle\pi_{A}^{2}+\pi_{C_{1}}^{2}+\frac{\pi_{C_{2}}^{2}-\pi_{C_{2}}^{2}(\frac{1-1/k}{3})^{2k}}{1-\left(\frac{1-1/k}{3}\right)^{2}}$

Where the first inequality follows from (2.4). The second equality applies the
finite geometric series.

So by applying the limit on both sides, we have

$\displaystyle\lim_{k\to\infty}\|\pi_{\alpha=1-1/k}\|_{2}^{2}$
$\displaystyle\geq$
$\displaystyle\lim_{k\to\infty}\left(\pi_{A}^{2}+\pi_{C_{1}}^{2}+\frac{\pi_{C_{2}}^{2}-\pi_{C_{2}}^{2}(\frac{1-1/k}{3})^{2k}}{1-\left(\frac{1-1/k}{3}\right)^{2}}\right)$
$\displaystyle=$
$\displaystyle\lim_{k\to\infty}\pi_{A}^{2}+\lim_{k\to\infty}\pi_{C_{1}}^{2}+\lim_{k\to\infty}\frac{\pi_{C_{2}}^{2}-\pi_{C_{2}}^{2}(\frac{1-1/k}{3})^{2k}}{1-\left(\frac{1-1/k}{3}\right)^{2}}$
$\displaystyle=$ $\displaystyle 0+\frac{4}{25}+\frac{4\cdot 9}{25\cdot 8}$

To find an upper bound, we only need an upper bound for the $\pi_{B_{i}}$. We
can observe that

$\pi_{B_{i}}=(1/3)^{i}\pi_{C_{2}}\left(1-\frac{1}{k}\right)^{i}+\sum_{n=1}^{i-1}\frac{(1/3)^{i-n}(1-\frac{1}{k})^{i-n}\cdot\frac{1}{k})}{3+k}.$

The first term above contains all of the probability mass that has gone
through $C_{2}$ since it last jumped and the second term contains the
probability mass that has not (i.e., it jumped onto vertex $B_{j}$ for $j<i$).

By overestimating the second term of the equation above with an infinite
geometric series, it is bounded by $\frac{3/k}{2(3+k)}$. Ergo

$\pi_{B_{i}}<(1/3)^{i}\pi_{C_{2}}\left(1-\frac{1}{k}\right)^{i}+\frac{3/k}{2(3+k)}.$

However, we are concerned about $\pi_{B_{i}}^{2}$ so by expanding we have

$\pi_{B_{i}}^{2}<(1/3)^{2i}\pi_{C_{2}}^{2}(1-1/k)^{2i}+(1/3)^{i}\pi_{C_{2}}(1-1/k)^{i}\frac{3/k}{2(3+k)}+\left(\frac{3/k}{2(3+k)}\right)^{2}.$

Since $(1/3)^{i}\pi_{C_{2}}(1-1/k)^{i}<1$ we know that

$\pi_{B_{i}}^{2}<(1/3)^{2i}\pi_{C_{2}}^{2}(1-1/k)^{2i}+\frac{3/k}{2(3+k)}+(\frac{3/k}{2(3+k)})^{2}.$

So

$\displaystyle\|\pi_{\alpha=1-1/k}\|_{2}^{2}$ $\displaystyle=$
$\displaystyle\pi_{C_{1}}^{2}+\left(\pi_{C_{2}}^{2}+\sum_{i=1}^{k}\pi_{B_{i}}^{2}\right)+\pi_{A}^{2}.$
$\displaystyle<$
$\displaystyle\pi_{C_{1}}^{2}+\left(\pi_{C_{2}}^{2}+\sum_{i=1}^{k}\left[(1/3)^{2i}\pi_{C_{2}}^{2}(1-1/k)^{2i}+\frac{3/k}{2(3+k)}+(\frac{3/k}{2(3+k)})^{2}\right]\right)+\pi_{A}^{2}.$
$\displaystyle=$
$\displaystyle\pi_{C_{1}}^{2}+\left(\pi_{C_{2}}^{2}+\sum_{i=1}^{k}(1/3)^{2i}\pi_{C_{2}}^{2}(1-1/k)^{2i}\right)+k\frac{3/k}{2(3+k)}+k(\frac{3/k}{2(3+k)})^{2}+\pi_{A}^{2}.$
$\displaystyle<$
$\displaystyle\pi_{C_{1}}^{2}+\frac{\pi_{C_{2}}^{2}}{1-(1/9)}+k\left(\frac{3/k}{2(3+k)}+\left(\frac{3/k}{2(3+k)}\right)^{2}\right)+\pi_{A}^{2}.$

where the first inequality follows using the previous estimate of
$\pi_{B_{i}}$, the second inequality follows from overestimating the geometric
sum as an infinite series.

So by applying the limit, we have

$\lim_{k\to\infty}\|\pi_{\alpha=1-1/k}\|_{2}^{2}\leq\lim_{k\to\infty}\left[\frac{4}{25}+\frac{4\cdot
9}{25\cdot 8}+\frac{3}{2(3+k)}+\frac{9/k}{4(3+k)^{2}}+\pi_{A}^{2}\right]$

which goes to

$\frac{4}{25}+\frac{4\cdot 9}{25\cdot 8}=\frac{17}{50}$

as $k\to\infty$.

####  2.2.6 Computing $\|\pi_{\alpha=1}-\pi_{\alpha=1-1/k}\|_{2}$

Since when $\alpha=1$ vertex $\pi_{A}=1$, and $\alpha=1-1/k$, $\pi_{A}\to 0$,
the sum

$\|\pi_{\alpha=1}-\pi_{\alpha=1-1/k}\|_{2}=\sum_{i=1}(\pi_{\alpha=1,v}-\pi_{\alpha=1-1/k,v})^{2}$

has either $\pi_{\alpha=1,v}\to 0$ or $\pi_{\alpha=1-1/k,v}\to 0$, so

$\lim_{k\to\infty}\|\pi_{\alpha=1-1/k}-\pi_{\alpha=1}\|^{2}=\lim_{k\to\infty}\|\pi_{\alpha=1-1/k}\|^{2}+\lim_{k\to\infty}\|\pi_{\alpha=1}\|^{2}.$

We have

$\lim_{k\to\infty}\|\pi_{\alpha=1-1/k}-\pi_{\alpha=1}\|\to\sqrt{\|\pi_{\alpha=1-1/k}\|^{2}+\|\pi_{\alpha=1}\|^{2}}\to\sqrt{\frac{17}{50}+1}=\sqrt{\frac{67}{50}}$

$\triangle$

Indeed the deceiving graph from Figure 2 shows
$\|\pi_{\alpha=1-1/k}-\pi_{\alpha=1}\|\to\sqrt{\frac{67}{50}}\approx 1.1575$
as $\alpha\to 1$.

Figure 2: A plot of $x=\alpha$ versus $y=||\pi_{\alpha={1}}-\pi_{\alpha=x}||$
using the construction from Theorem 2.1, $\Gamma(k)$, for sufficiently large
$k$. The resolution of the plot is unable to capture that
$|\pi_{\alpha={1}}-\pi_{\alpha=x}||\to 0$ as $x\to 1$.

##  3 The Open Problem

Originally, in this study, our construction had only one “$C$” vertex. This
would lead to a limiting value of
$\sqrt{\frac{4}{3}}=\sqrt{1+\left(\frac{1}{2}\right)^{2}+\left(\frac{1}{2^{2}}\right)^{2}+\ldots}\approx
1.15470$ which is just a tad less than $\sqrt{\frac{67}{50}}\approx 1.15758$.

This would seem to suggest that adding more “$C$” vertices (which we call the
set C) would be beneficial as in Figure 3. This would result in a larger total
probability mass among the $C_{i}$. However, splitting the probability mass
among more vertices would result in a smaller 2-norm when squaring. For
instance, if $\pi_{\alpha_{1}}$ was concentrated at one vertex whereas
$\pi_{\alpha_{2}}$ was concentrated on more than two other vertices equally,
the resulting difference would be at most
$\sqrt{1+3\frac{1}{3^{2}}}=\sqrt{\frac{4}{3}}$, which is worse than our
result.

$A$$B_{k}$$\cdots$$B_{1}$$C_{i}$$\cdots$$C_{1}$ Figure 3: A more general
construction with more $C$ vertices. The optimal value of
$\|\pi_{\alpha_{1}}-\pi_{\alpha_{2}}\|$ occurs for two $C$ vertices.

Consider a similar construction to the path we had earlier but with a varying
number of vertices in $C$. This general construction is the same as the
previous version except we can add a fixed amount of vertices that are copies
(in that they have the same in-arcs and out-arcs) of $C_{1}$ except they do
not have an arc to $B_{1}$ and they have an arc to and from every other vertex
in $C$.

We will give an informal argument why having two vertices in $C$ is the best
for this more general construction. As in the proofs above, for $\alpha$ close
to (but not equal to) $1$, the probability mass always sums to $1$ and
approximately forms a geometric series, so we have

$1\approx(m-1)\pi_{C_{i}}+\frac{\pi_{C_{i}}}{1-\frac{1}{m+1}}$

where $\pi_{C_{i}}$ is the Pagerank each vertex in any such vertex in $C$ and
$m$ is the number of such vertices. By solving for $\pi_{C_{i}}$ we have

$\pi_{C_{i}}\approx\frac{m}{1+m^{2}}.$

Based on this result, we can make a formula for $\|\pi\|_{2}^{2}$

$\displaystyle\|\pi\|_{2}^{2}$ $\displaystyle\approx$ $\displaystyle
m\pi_{C_{i}}^{2}+\sum_{i=1}^{k}\pi_{B_{i}}^{2}$ $\displaystyle\approx$
$\displaystyle
m\pi_{C_{i}}^{2}+\sum_{i=1}^{k}\frac{1}{(m+1)^{2i}}\pi_{C_{i}}^{2}$
$\displaystyle\approx$
$\displaystyle\pi_{C_{i}}^{2}\left[m-1+\frac{1}{1-\frac{1}{(1+m)^{2}}}\right]$
$\displaystyle=$
$\displaystyle\frac{m^{2}}{\left(m^{2}+1\right)^{2}}\left[m-1+\frac{1}{1-\frac{1}{(1+m)^{2}}}\right]$
$\displaystyle=$
$\displaystyle\frac{m^{4}+2m^{3}+m}{(m+2)\left(m^{2}+1\right)^{2}}$

As a result, we have that

$\|\pi_{\alpha_{1}}-\pi_{\alpha_{2}}\|\approx\sqrt{1+\frac{m^{4}+2m^{3}+m}{(m+2)\left(m^{2}+1\right)^{2}}}$

This function reaches a maximum of approximately $\sqrt{1.360390}$ at
approximately $m=1.445036$, but since this problem only accepts discrete
answers the optimum is either at $m=1$ or $m=2$. For $m=1$ we have
$\sqrt{\frac{4}{3}}$, and for $m=2$, we have $\sqrt{\frac{67}{50}}$ slightly
higher as shown in Figure 4.

Figure 4:  Plot of
$f(x)=\sqrt{1+\frac{x^{4}+2x^{3}+x}{(x+2)\left(x^{2}+1\right)^{2}}}$ with the
values for $x=1,2,\ldots$ indicated. For positive integral values $f(x)$ is
maximized at $x=2$ indicating that 2 “C” vertices provides for an optimal
construction.

We can also ask about the supremum values of
$\|\pi_{\alpha_{1}}-\pi_{\alpha_{2}}\|_{p}$ for different $p\geq 1$ Our
construction achieves the supremum values for both the $1$\- and the
$\infty$-norms, The maximum that can be possibly achieved for the $\infty$
norm for the difference between two Pagerank vectors is 1, and these
constructions achieve that because when $\alpha=1$, $\pi_{A}=1$ and when
$\alpha=1-1/k$, $\pi_{A}\to 0$. Similarly, the maximum that can be possibly
achieved for the $1$-norm for the difference between two Pagerank vectors is
2, and our constructions achieve that because when $\alpha=1$, $\pi_{A}=1$ and
when $\alpha=1-1/k$, $\pi_{A}\to 0$ and so the probability mass is distributed
among the other vertices and so $\|\pi_{\alpha_{1}}-\pi_{\alpha_{2}}\|_{1}\to
1$. However, it is remains unclear if our construction is optimal for
$1<p<\infty$.

We would hope the argument above is convincing that $\sqrt{\frac{67}{50}}$ is
perhaps the best possible for the 2-norm, but this is far from a proof! In
fact, it highlights why optimization is difficult for discrete combinatorial
objects. There is much work on optimizing a graph based on eigenvalues and/or
eigenvectors [1, 8, 9], and even among them, there are several cases where the
optimal graph follows a canonical construction in small cases but becomes
different in larger cases [5].

## References

  * [1] S. Aksoy, F. Chung, and X. Peng, Extreme values of the stationary distribution of random walks on directed graphs, Advances in Applied Mathematics, 81 (2016), pp. 128–155.
  * [2] S. Brin and L. Page, The anatomy of a large-scale hypertextual web search engine, Computer networks and ISDN systems, 30 (1998), pp. 107–117.
  * [3] T. Callaghan, P. J. Mucha, and M. A. Porter, Random walker ranking for ncaa division ia football, The American Mathematical Monthly, 114 (2007), pp. 761–777.
  * [4] R. A. Horn and C. R. Johnson, Matrix analysis, Cambridge university press, 2012.
  * [5] A. Kostochka and N. Prince, On ks, t-minors in graphs with given average degree, Discrete mathematics, 308 (2008), pp. 4435–4445.
  * [6] H. Kwak, C. Lee, H. Park, and S. Moon, What is twitter, a social network or a news media?, in Proceedings of the 19th international conference on World wide web, 2010, pp. 591–600.
  * [7] A. N. Langville and C. D. Meyer, Google’s PageRank and beyond: The science of search engine rankings, Princeton university press, 2011.
  * [8] M. Tait, The colin de verdiere parameter, excluded minors, and the spectral radius, Journal of Combinatorial Theory, Series A, 166 (2019), pp. 42–58.
  * [9] M. Tait and J. Tobin, Three conjectures in extremal spectral graph theory, Journal of Combinatorial Theory, Series B, 126 (2017), pp. 137–161.