Title: Network Essence: PageRank Completion and Centrality-Conforming Markov Chains,
Abstract: Jiří Matouš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.