Network essence: PageRank completion and centrality-conforming Markov chains

DOI10.1007/978-3-319-44479-6_31zbMATH Open1423.68062arXiv1708.07906OpenAlexW2753129555MaRDI QIDQ4604398FDOQ4604398

Authors: Shang-Hua Teng 

Publication date: 26 February 2018

Published in: A Journey Through Discrete Mathematics (Search for Journal in Brave)

Abstract: Jiv{r}'i Matouv{s}ek (1963-2015) had many breakthrough contributions in mathematics and algorithm design. His milestone results are not only profound but also elegant. By going beyond the original objects --- such as Euclidean spaces or linear programs --- Jirka found the essence of the challenging mathematical/algorithmic problems as well as beautiful solutions that were natural to him, but were surprising discoveries to the field. In this short exploration article, I will first share with readers my initial encounter with Jirka and discuss one of his fundamental geometric results from the early 1990s. In the age of social and information networks, I will then turn the discussion from geometric structures to network structures, attempting to take a humble step towards the holy grail of network science, that is to understand the network essence that underlies the observed sparse-and-multifaceted network data. I will discuss a simple result which summarizes some basic algebraic properties of personalized PageRank matrices. Unlike the traditional transitive closure of binary relations, the personalized PageRank matrices take "accumulated Markovian closure" of network data. Some of these algebraic properties are known in various contexts. But I hope featuring them together in a broader context will help to illustrate the desirable properties of this Markovian completion of networks, and motivate systematic developments of a network theory for understanding vast and ubiquitous multifaceted network data.

Full work available at URL: https://arxiv.org/abs/1708.07906

Recommendations

• On the localization of the personalized PageRank of complex networks
• On some analytical properties of a general PageRank algorithm
• The mathematics of Google: the PageRank algorithm
• PageRank for networks, graphs, and Markov chains
• Sharp estimates for the personalized multiplex PageRank

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Biographies, obituaries, personalia, bibliographies (01A70) History of computer science (68-03) Internet topics (68M11)

Cites Work

• Social choice and individual values
• Title not available (Why is that?)
• Title not available (Why is that?)
• Non-cooperative games
• Equilibrium points in n -person games
• Title not available (Why is that?)
• Probabilistic graphical models.
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• A new status index derived from sociometric analysis
• Consistent community detection in multi-relational data through restricted multi-layer stochastic blockmodel
• Scalable Algorithms for Data and Network Analysis
• Networks. An introduction.
• The centrality of groups and classes
• Title not available (Why is that?)
• Cores of convex games
• Title not available (Why is that?)
• Title not available (Why is that?)
• The geometry of graphs and some of its algorithmic applications
• Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
• Spectral sparsification of graphs
• Title not available (Why is that?)
• Random walks in a convex body and an improved volume algorithm
• The complexity of computing a Nash equilibrium
• Title not available (Why is that?)
• A Nearly-m log n Time Solver for SDD Linear Systems
• College Admissions and the Stability of Marriage
• Title not available (Why is that?)
• A subexponential bound for linear programming
• Title not available (Why is that?)
• The centrality index of a graph
• Settling the complexity of computing two-player Nash equilibria
• Separators for sphere-packings and nearest neighbor graphs
• Efficient computation of the Shapley value for game-theoretic network centrality
• A Generalization of Radon's Theorem
• Spectral partitioning works: planar graphs and finite element meshes
• Graph limits and parameter testing
• Title not available (Why is that?)
• The catline for deep regression
• Synchronization in Network Structures: Entangled Topology as Optimal Architecture for Network Design
• A unified framework for approximating and clustering data
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• Regression depth and center points.
• Geometric Separators for Finite-Element Meshes
• Geometric Mesh Partitioning: Implementation and Experiments
• Using PageRank to Locally Partition a Graph
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• An axiomatic approach to community detection
• An axiomatic approach to personalized ranking systems
• Finding endogenously formed communities
• Local Computation of PageRank Contributions
• Approximate undirected maximum flows in \(O(m\operatorname{polylog}(n))\) time

Cited In (3)

• Ranking nodes in general networks: a Markov multi-chain approach
• PageRank for networks, graphs, and Markov chains
• Title not available (Why is that?)

Uses Software

• MESHPART

This page was built for publication: Network essence: PageRank completion and centrality-conforming Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604398)