2018年5月24日，美国南加州大学滕尚华教授在静园五院为图灵班的同学带来了题为“Personalized PageRank Matrices: Structures and Algorithmic Implications”的特邀报告。

　　PageRank是社会网络计算中对节点中心度的一个经典度量。滕老师首先利用一个图诱导的马尔可夫转移给出了PageRank的直接定义，用形式化的数学语言表示了这个定义。接着，将定义式做了简单巧妙的变换，展示了PageRank的本质其实是对于未来多次转移的线性组合，以此揭示PageRank在实际应用中，作为中心度度量，相比于其它的中心度更为有效的原因。

　　在计算难度层面，对于实际中的社会网络，图往往是稀疏的，因而直接使用Taylor展开进行计算就能达到约为线性的速度。然而在大数据时代，有时线性时间的算法也不能令人满意，于是滕老师给同学们提出了一个挑战，即能否给出一个近似算法，对图各个节点按PageRank的大小作近似的划分，并且这个算法甚至不需要利用所有边的信息，以计算精度换时间，达到比线性更快的平均速度。

报告摘要：

In this (blackboard) talk, I will discuss some basic algebraic properties of personalized PageRank matrices, formulated by a family of Markov processes over graphs. I will focus on their applications to two fundamental concepts in network analysis: centrality and clusterability. I will also discuss several efficient algorithms for and based on personalized PageRank.

报告人简介：

Dr. Shang-Hua Teng has twice won the prestigious Gödel Prize in theoretical computer science, first in 2008, for developing the theory of smoothed analysis , and then in 2015, for designing the groundbreaking nearly-linear time Laplacian solver for network systems. Both are joint work with Dan Spielman of Yale --- his long-time collaborator. Smoothed analysis is fundamental for modeling and analyzing practical algorithms, and the Laplacian paradigm has since led to several breakthroughs in network analysis, matrix computation, and optimization. Citing him as, ``one of the most original theoretical computer scientists in the world'', the Simons Foundation named Teng a 2014 Simons Investigator, for pursuing long-term curiosity-driven fundamental research. He and his collaborators also received the best paper award at ACM Symposium on Theory of Computing (STOC) for what's considered to be the ``first improvement in 10 years'' of a fundamental optimization problem --- the computation of maximum flows and minimum cuts in a network. In addition, he is known for his joint work with Xi Chen and Xiaotie Deng that characterized the complexity for computing an approximate Nash equilibrium in game theory, and his joint papers on market equilibria in computational economics. He and his collaborators also pioneered the development of well-shaped Dalaunay meshing algorithms for arbitrary three-dimensional geometric domains, which settled a long-term open problem in numerical simulation, also a fundamental problem in computer graphics. Software based on this development was used at the University of Illinois for the simulation of advanced rockets. Teng is also interested in mathematical board games. With his former Ph.D. student Kyle Burke, he designed and analyzed a game called Atropos , which is played on the Sperner's triangle and based on the beautiful, celebrated Sperner's Lemma. In 2000 at UIUC, Teng was named on the List of Teachers Ranked as Excellent by Their Students for his class, ``Network Security and Cryptography''. He has worked and consulted for Microsoft Research, Akamai, IBM Almaden Research Center, Intel Corporation, Xerox PARC, and NASA Ames Research Center, for which he received fifteen patents for his work on compiler optimization, Internet technology, and social network.