狠狠撸

Finding Nobel prize window by
PageRank

FUJITA Yuji, Turnstone Research Inst., Nihon Univ.

Graph and Network
● Graph theory
– Part of mathmatics
● Network science
– Inter-disciplinary study of
● Graph theory
● Physics
● Social science
● Informatics
● particular topics from finance, biology, ...

Graph theory
Date back to 1730's
● Objectives
– Lower dimensional topological structure
– Combinatorial and topological studies
● Topics
– Four colour theorem
– Invariants

From Wikipedia

Network science
● Objectives
– Statistics and dynamics
– Social, Financial, Technological themes
● Topics
– 6 degrees of separation
– Scale-free networks
– PageRank
Title:syms.eps
Creator:gnuplot 4.0 patchlevel 0
CreationDate:Sun Jan 13 23:04:28 2008

Bibliometrics
● Quantitative evaluation of (academic) documents
● Conventional approach: number of citation

● Citation network
– Node: paper Edge: citation
– directed graph
● More true metric: PageRank

Citation vs PageRank

Best cited do not have the best score

Top articles
Clinical Effects of an angiotensin-converting-enzyme inhibitor,
Medicine ramipril, on cardiovascular events in high-risk patients
Clinical Vitamin E supplementation and cardiovascular events in high-
Medicine risk patients
Immunology Cytotoxic T lymphocyte-associated antigen 4 plays an
essential role in the function of CD25(+)CD4(+) regulatory
cells that control intestinal inflammation
Immunology Immunologic self-tolerance maintained by CD25(+)CD4(+)
regulatory T cells constitutively expressing cytotoxic T
lymphocyte-associated antigen 4
Physics String theory and noncommutative geometry
Physics Large-N limit of non-commutative gauge theories
Molecular Smac, a mitochondrial protein that promotes cytochrome c-
Biology & dependent caspase activation by eliminating IAP inhibition
Genetics
Molecular Identification of DIABLO, a mammalian protein that promotes
Biology & apoptosis by binding to and antagonizing IAP proteins
Genetics
Molecular Systematic variation in gene expression patterns in human

Graph expression
● Embedding: drawing on sphere/space
● Matrix

PageRank overview
● Link from a great node is more important
? degree as a score
● But how can it be done? - the process can be
lost in a loop..

Figure from “The PageRank Citation Ranking: Bringing Order to the Web”

Finite state Markov chain
● Node: status, Transition matrix: moving along
the edge
– Row: linked (cited) vector
– Column: link (cite) vector
● Probability vector refreshed by multiplying the
transition matrix

Steady state gives PageRank
● Some Markov chain has a unique steady state
● Steady state given by eigenvector
– A vector such that Mx = ax
● Eigenvector given by linear algebra
– Widely known how to compute

Why PageRank works?
● Not all citations are equally significant
● Less citation can be a signal of even more
great work
– Fundamental work not cited directly
● Academic cascade

Meanings of citation
● Brainchild
● History
● Respect
● Identity

something more than <a>tag</a>

To reach the top
● Many great children
– Each child give birth to many works

= great scientific achievement

Limitations
● Prof. Yamanaka's work (CELL, 2006) has poor
PageRank score, which is a shame to say at
least.
● SPAM issues; not so serious as naiive citation
count

To practice
● Get citation data
– Product or scrape
● Transition matrix
– Random surfer model
● Iterate matrix-vector product operation
– Sparse matrix operation

Data
● Tomson-Reuter, Elsevier, …
● Scrape the web (arXive..)
● Common SQL server will hold the data
● NLP required

Transition matrix
● Not all transition matrix has unique
eigenvector
● Random surfer model: let the graph be
connected and get out of loop

+ =

Adaptation to papers
● Old paper cannot cite newer one
– Non-uniform random surfing
● Adjust decay rate

Sparse matrix
● Most of the elements are Zeros
● Compressed form reduces space and time

● libcsparse
– made by UFL people and others, distributed under
LGPL

Reference
L Page, S Brin, R Motwani, T The PageRank citation ranking: bringing order to
Winograd the web.
Dylan Walker1,2 , Huafeng Ranking Scientific Publications Using a Simple
Xie2,3 , Koon-Kiu Yan1,2 , Model of Network Traffic
Sergei Maslov2
P. Chen,1, ? H. Xie,2, 3, ? S. Finding Scientific Gems with Google
Maslov,3, ? and S. Redner1, §
Hajime BABA Google の秘密 - PageRank 徹底解説

Acknowledgment
● Mr. Kazuhisa Takei for ruby interface of
libcsparse in ffi
● Dr. Mari Jibu for citation data handling
● Dr. Wataru Souma for network scientific
suggestions and comments
● Dr. Yoshi Fujiwara for choosing this topic and
invitation
● Free software developers

About me
● 2010- Turnstone Research, Inst.
● 2011- Nihon Univ. researcher
● 2009-2010 finance sector
● 2007-2009 Network analysis at NiCT
● 2001-2007 Venture firm CEO
● 1994-2002 Discrete math graduate student

● Ski, climbing, bicycle, art

狠狠撸

finding nobel prize window by PageRank

More Related Content

finding nobel prize window by PageRank

Editor's Notes