Approximations for Kemeny’s Constant for Several Families of Graphs and Real-World Networks
Speaker: Rob Kooij
Abstract: The linear relation between Kemeny’s constant, a graph metric directly linked with random walks, and the effective graph resistance in a regular graph has been an incentive to calculate Kemeny’s constant for various networks. In this paper we consider complete bipartite graphs, (generalized) windmill graphs and tree networks with large diameter and give exact expressions of Kemeny’s constant. For nonregular graphs we propose two approximations for Kemeny’s constant by adding to the effective graph resistance term a linear term related to the degree heterogeneity in the graph. These approximations are exact for complete bipartite graphs, but show some discrepancies for generalized windmill and tree graphs. However, we show that a recently obtained upper-bound for Kemeny’s constant in based on the pseudo inverse Laplacian gives the exact value of Kemeny’s constant for generalized windmill graphs. Next, we have evaluated Kemeny’s constant, its two approximations and its upper bound, for 243 moderate sized real-world networks. This evaluation reveals that the upper bound is tight, with average relative error of only 0.73%. In most cases the upper bound clearly outperforms the other two approximations.
For the upper bound based on the pseudo inverse of the Laplacian, we show that for a certain class of bimodal networks with diameter two, the upper bound is also tight. This generalizes previous results for bipartite and (generalized) windmill graphs. Moreover, we show numerically that also for large real-world networks this bound can be used to find good numerical approximations for Kemeny’s constant. For certain graphs consisting of up to 100K nodes, we find a speed up of a factor 30 can be achieved, depending on the accuracy of the approximation. For networks consisting of over 500K nodes the approximation can be used to estimate values for Kemeny’s constant, where exact calculation is no longer feasible within reasonable computation time.
Location: Building 28: Turing room 0.E420
Time: 10.30-11.15
Network Reliability: Approximation, Upper Bounds, and Applications to Network Robustness
Speaker: Xinhan Liu
Abstract: This research discusses the reliability of a graph in which the links are perfectly reliable but the nodes may fail with certain probability ppp. Calculating graph reliability is an NP-Hard problem. We introduce an efficient and accurate Monte Carlo method and a stochastic approximation for the node reliability polynomial based solely on the degree distribution. We provide the formulas for the node reliability polynomial of both Erdős–Rényi graphs and Random Geometric graphs. The phase transition in the node reliability of Erdős–Rényi graphs is also discussed. Additionally, we propose two increasingly accurate upper bounds for the node reliability polynomial solely based on the graph’s degree distributions. The advantages and disadvantages of these two upper bounds are thoroughly compared. Beyond the computation of node reliability polynomials, we also estimate the number of cut sets and present a solution to the reliability-based network enhancement problem.
Location: Building 28: Turing room 0.E420
Time: 11.15-11.35
Diffusion Backbones of Temporal Higher-Order Networks
Speaker: Shilun Zhang
Abstract: Temporal higher-order networks have recently been used to represent complex systems of time-evolving interactions among groups of individuals. Recent studies investigated the impact of properties of temporal higher-order networks on the behavior of dynamical processes. However, it remains unexplored how a specific group of individuals contributes to the process. In this work, we consider the Susceptible-Infected threshold process on temporal higher-order networks derived from human face-to-face interactions. We propose the diffusion backbone as a weighted higher-order network, where the weight of each hyperlink denotes the contribution of the hyperlink to the diffusion process. Then, we illustrate dependency of the backbone on the infection probability and threshold. Finally, we design centrality metrics for hyperlinks to predict the ranking of hyperlinks by their weights in the backbone.
Location: Building 28: Turing room 0.E420
Time: 11.35-11.55