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