进一步探索Kemeny常数的一个上限
Robert E Kooij1,2, Johan L A Dubbeldam1
1Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, 2628 CD Delft, The Netherlands.
Entropy (Basel, Switzerland)
|April 26, 2025
概括
凯梅尼常数在马尔科夫链中至关重要,现在可以在大型网络中使用从拉普拉斯图中获得的新型上限来有效近似. 这种方法为复杂的图形分析提供了显著的加速.
科学领域:
- 图形理论是指图形的理论.
- 马尔科夫链是一种马尔科夫链.
- 网络分析 网络分析
背景情况:
- 凯梅尼常数是马尔科夫链分析中的一个关键指标,传统上是使用平均第一次通道时间来计算的.
- 计算凯梅尼常数的现有方法对于大图来说在计算上变得不可行.
研究的目的:
- 开发一种计算效率高的方法来近似凯梅尼常数.
- 用图表拉普拉西安的伪反向来确定凯梅尼常数的尖上限.
- 为了验证这个边界对特定图形类的紧密性及其对现实世界网络的适用性.
主要方法:
- 使用图形拉普拉斯矩阵的伪反向表达凯梅尼常数.
- 导出和分析Kemeny常数的一个尖的上限.
- 在双面和通用风车图表上测试边界的紧密性.
- 在真实世界的网络数据上执行数值模拟.
主要成果:
- 导出的上界被证明对某些图形类来说很紧,概括了以前的发现.
- 数值结果表明,边界为现实世界网络中的Kemeny常数提供了良好的近似值.
- 对于高达100K节点的图形,实现了高达30的加速度因子.
- 该近似方法可以对超过500K个节点的网络进行Kemeny常数的估计,在这些网络中,精确的计算是难以处理的.
结论:
- 拉普拉斯的伪反向提供了一个强大的工具,用于限制Kemeny的常量.
- 这种方法显著提高了分析大型网络的计算效率.
- 该方法提供了一个实用的方法来估计Kemeny的常数,当准确的计算是不可行的.
相关概念视频
The Equilibrium Binding Constant and Binding Strength
12.7K
The equilibrium binding constant (Kb) quantifies the strength of a protein-ligand interaction. Kb can be calculated as follows when the reaction is at equilibrium:
12.7K
EDTA: Conditional Formation Constant
647
Each EDTA molecule has six binding sites: four carboxyl groups and two amino groups. The fully protonated form of EDTA is represented as H6Y2+. However, it can exist in different forms, H5Y+, H4Y, H3Y−, H2Y2−, and HY3−, depending on the pH of the solution. In very basic solutions with pH > 10.17, the fully deprotonated form, Y4−, is the predominant species that readily complexes with metal ions in a 1:1 ratio.
For the equilibrium reaction of the metal with the...
For the equilibrium reaction of the metal with the...
647
Euler's Formula to Columns with Other End Conditions
407
Euler's formula is very important in the field of structural engineering, providing a foundation for understanding the critical loading conditions of pin-ended columns. This formula links the modulus of elasticity, the moment of inertia of the cross-section, and the column's length, offering a precise calculation of the critical load at which a column is prone to buckling.
407
Kendall's Tau Test
518
Kendall's tau test, also known as the Kendall rank coefficient test, is a nonparametric method for assessing association between two variables. This test is particularly useful for identifying significant correlations when the distributions of the sample and population are unknown. Developed in 1938 by the British statistician Sir Maurice George Kendall, the tau coefficient (denoted as τ) serves as a rank correlation coefficient, with values ranging from -1 to +1.
A τ value...
A τ value...
518
Kendall's Coefficient of Concordance
169
Kendall's Coefficient of Concordance (W), also known as Kendall's W, is a non-parametric statistical measure used to assess the agreement or concordance between multiple raters or judges when they rank a set of items. It is often used when you have ordinal data (ranks) and you want to see if there is consistency or consensus among the raters. It is widely applied in research areas such as psychology, medicine, and social sciences, where multiple judges are asked to rank or rate subjects...
169
Structure of Benzene: Kekulé Model
8.2K
In 1865, August Kekule suggested the structure of benzene according to the structural theory of organic chemistry based on the three assertions—formula of benzene is C6H6, all the hydrogens of benzene are equivalent, and each carbon must have four bonds due to its tetravalency.
He proposed that benzene has a cyclic structure of six carbon atoms attached to one hydrogen atom each, with three alternating pi bonds.
He proposed that benzene has a cyclic structure of six carbon atoms attached to one hydrogen atom each, with three alternating pi bonds.
8.2K


