---- > [!definition] Definition. ([[PageRank centrality]]) > Let $G$ be a [[network]] of $n$ nodes with [[adjacency matrix]] $A$. The **PageRank centrality** $x_{i}$ of a node $i$ is the $i^{th}$ entry of the [[vector]] $\b x:= (I_{n} - AD^{-1}\b x)^{-1} \b 1,$ > where $D$ is [[diagonal]] with $D_{ii}:=\max(k_{i}^{\text{out}}, 1)$. ($k_{i}^{\text{out}}$ is the [[degree|out-degree]]) of node $i$.) > [!justification] Conceptual Motivation. > The [[Katz centrality]] has one potentially undesirable feature: If a node with high Katz centrality has edges pointing to many others then all of those others also get high centrality. A high-centrality node pointing to one million others gives all one million of them high centrality. One could argue that this is not always appropriate. In many cases it means less if a node is only one among many that are pointed to. The centrality gained by virtue of receiving an edge from a prestigious node is diluted by being shared with so many others. For instance, websites like Amazon or eBay link to the web pages of thousands of manufacturers and sellers; if I’m selling something on Amazon it might link to me. Amazon is an important website, and would have high centrality by any sensible measure, but should I therefore be considered important by association? Most people would say not: I am only one of many that Amazon links to and its contribution to the centrality of my page will get diluted as a result. (Newman p.165) > [!justification] Mathematical Motivation. > In light of the above, we define a variant of [[Katz centrality]] in which the [[centrality]] a node derives from its [[network]] neighbors is proportional to their [[centrality]] *divided by their [[degree|out-degree]]*. Naively, we say $x_{i}=\alpha \sum_{j=1}^{n}A_{ij} \frac{x_{j}}{k_{j}^{\text{out}}} + \beta,$ > where $\alpha, \beta >0$ are [[hyperparameter]]s. ($A_{ij}$ just acts as an [[indicator random variable]] for whether an edge exists between nodes $i$ and $j$). But this gives problems when $k_{j}^{\text{out}}=0$. Of course, it is clear that a node with no outgoing edges should contribute zero to the [[centrality]] of any other node, which we can contrive by artificially setting $k_{j}^{\text{out}}=1$ for all such nodes. The [[matrix]] form of this would be $\b x = \alpha A D ^{-1} \b x + \beta \b 1,$ > where $D$ is [[diagonal]] with elements $\max(k_{i}^{\text{out}},1)$. Rearranging we find $\b x = \beta (I - \alpha A D^{-1})^{-1} \b 1$ > and similar to with [[Katz centrality]] we see that $\beta$ can just be set to $1$ as a convention without affecting much of anything. ---- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```