For a random walk on a network, the mean first-passage time from a node i to another node j chosen stochastically, according to the equilibrium distribution of Markov chain representing the random walk is called the Kemeny constant, which is closely related to the navigability on the network. Thus, the configuration of a network that provides optimal or suboptimal navigation efficiency is a question of interest. It has been proved that complete graphs have the exact minimum Kemeny constant over all graphs. In this paper, by using another method we first prove that complete graphs are the optimal networks with a minimum Kemeny constant, which grows linearly with the network size. Then, we study the Kemeny constant of a class of sparse networks that exhibit remarkable scale-free and fractal features as observed in many real-life networks, which cannot be described by complete graphs. To this end, we determine the closed-form solutions to all eigenvalues and their degeneracies of the networks. Employing these eigenvalues, we derive the exact solution to the Kemeny constant, which also behaves linearly with the network size for some particular cases of networks. We further use the eigenvalue spectra to determine the number of spanning trees in the networks under consideration, which is in complete agreement with previously reported results. Our work demonstrates that scale-free and fractal properties are favorable for efficient navigation, which could be considered when designing networks with high navigation efficiency.

Download full-text PDF

Source
http://dx.doi.org/10.1063/1.4768665DOI Listing

Publication Analysis

Top Keywords

kemeny constant
20
complete graphs
12
optimal suboptimal
8
networks
8
efficient navigation
8
random walk
8
navigation efficiency
8
minimum kemeny
8
linearly network
8
network size
8

Similar Publications

Computational thinking (CT) is a set of problem-solving skills with high relevance in education and work contexts. The present paper explores the role of key cognitive factors underlying CT performance in non-programming university students. We collected data from 97 non-programming adults in higher education in a supervised setting.

View Article and Find Full Text PDF

The recent trend in using network and graph structures to represent a variety of different data types has renewed interest in the graph partitioning (GP) problem. This interest stems from the need for general methods that can both efficiently identify network communities and reduce the dimensionality of large graphs while satisfying various application-specific criteria. Traditional clustering algorithms often struggle to capture the complex relationships within graphs and generalize to arbitrary clustering criteria.

View Article and Find Full Text PDF
Article Synopsis
  • * Research in Italy's central Apennines measures how different heat flow and crust thickness influence carbon fluxes from weathering, metamorphism, and carbonate melting.
  • * Findings indicate that at certain depths and heat levels, emissions from the crust greatly exceed those from near-surface weathering, suggesting tectonic processes play a crucial role in regulating the inorganic carbon cycle.
View Article and Find Full Text PDF

Biogeochemical reactions modulate the chemical composition of the oceans and atmosphere, providing feedbacks that sustain planetary habitability over geological time. Here, we mathematically evaluate a suite of biogeochemical processes to identify combinations of reactions that stabilize atmospheric carbon dioxide by balancing fluxes of chemical species among the ocean, atmosphere, and geosphere. Unlike prior modeling efforts, this approach does not prescribe functional relationships between the rates of biogeochemical processes and environmental conditions.

View Article and Find Full Text PDF

Variational kinetic clustering of complex networks.

J Chem Phys

March 2023

Department of Physics and Astronomy, University College London, WC1E 6BT London, United Kingdom.

Efficiently identifying the most important communities and key transition nodes in weighted and unweighted networks is a prevalent problem in a wide range of disciplines. Here, we focus on the optimal clustering using variational kinetic parameters, linked to Markov processes defined on the underlying networks, namely, the slowest relaxation time and the Kemeny constant. We derive novel relations in terms of mean first passage times for optimizing clustering via the Kemeny constant and show that the optimal clustering boundaries have equal round-trip times to the clusters they separate.

View Article and Find Full Text PDF

Want AI Summaries of new PubMed Abstracts delivered to your In-box?

Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!