Course link:CS224W: Machine Learning with Graphs
Course video:[Course] Stanford CS224W: Map Machine Learning (2019 Autumn | English)

web (Internet) can essentially see as a Direct Graph, nodes are various web pages, and are hyperlinks between web pages.

For such a direction, we consider two questions:

• given node$v$, which nodes can be reached$v$？
• From node$v$Which nodes can be reached?

For the first point, we use a collection I n ( v ) = { w ∣ w  can reach  v } In(v)=\{w| w \text{ can reach }v\} In(v)={
w∣w can reach v}Come, for example, the following picture, I n ( A ) = { A , B , C , E , G } In(A)=\{A,B,C,E,G\} In(A)={
A,B,C,E,G}. For the second point, we use a collection O u t ( v ) = { w ∣ v  can reach  w } Out(v)=\{w|v \text{ can reach } w\} Out(v)={
w∣v can reach w}to indicate, that is, O u t ( A ) = { A , B , C , D , F } Out(A)=\{A,B,C,D,F\} Out(A)={
A,B,C,D,F}。

Any direction (web) can be represented by the two types below:

type	style	Description
Strongly Connected strong connection chart		Any nodes can be reached through a path, that is, I n ( A ) = O u t ( A ) = { A , B , C , D , E } In(A)=Out(A)=\{A,B,C,D,E\} In(A)=Out(A)={ A,B,C,D,E}。
Direct ACYCLIC Graph (DAG) has a ringless diagram		There is no ring circuit, node$u$can reach the node$v$, but nodes$v$Can’t reach the node$u$。

So, we can pay attention to the complex networkStrongly Connected Component (SCC). SCC is actually a collection of points$S$, in the collection

There are paths between any two points in any intention of$S$, and ensure that other SCC collection does not include this collection$S$。

For example, the scc of the above figure includes: {a, b, c, g}, {d}, {e}, {f}.

Any orientation of any orientation is the direction without a loop.The following is a proof–

So how do we find nodes

What about the strong connection of$v$? We know by defining,$In(v)$is all can reach the node$v$node collection,$Out(v)$is all nodes$v$The node collection that can be reached, then the node

The component of$v$is$Out(v)\bigcap In(v)=Out(v,G)\bigcap Out(v,G^{\prime })$, of which$G^{\prime }$Yes

The reversal of the$G$edge. We can use the depth of the graph to priority search (DFS)/breadth priority search (BFS) to get$Out(v,G)$and$Out(v,G^{\prime })$。

Use BFS algorithm to calculate$In(v)$and$Out(v)$, the number of nodes visited is relatively different. (The BFS Either Visits Many Nodes or Very Few)

Through the experiment, it was found that on the web network, for a random node$v$Let’s talk about it,$Out(v)\approx 100\text{ million (50\% nodes)}$, and$In(v)\approx 100\text{ million (50\% nodes)}$; Its great strong connection components include 56 Million nodes, which is about 28%of all nodes.

In this way, the calculation diagram of the web can be represented in the following form:

The starting point of

Pagerank is that the nodes in the network are not equally important). We will introduce the following link analysis methods to calculate the importance of nodes in the graph:

• PageRank
• Personalized PageRank
• Random Walk with Restarts

Obviously, the importance of nodes can be reflected through its link -Page is more important if it has more links. Of course, these links can be reflected in two aspects: In-COMING Links and Out-Going Links. At the same time, the importance of node external links can also reflect its own importance. Links from Important Pages Count More -this is a recursive problem.

In general:

The importance ofA “vote” from an important page is worth more.

Each node will be passed to its external link node on average. Set nodes

The important degree of$i$is$r_i$, there is$d_i$Out-links, then the important degree it passed to these nodes is$\frac{r_i}{d_i}$. For example, the node in the figure$j$important level$r_j=\frac{r_i}{3}+\frac{r_k}{4}$。

, that is,A page is important if it is pointed to by other important pages. At the same time, we can define nodes

Ranking of$j$:

$$r_j=\sum _{i\to j}\frac{r_i}{d_i}$$

among them$d_i$is node

Out degree.$i$

Let’s give an example:

We can get Flow Equation:

$$\begin{array}{rl}{r}_y& =\frac{r_y}{2}+\frac{r_a}{2}\\ r_a& =\frac{r_y}{2}+r_m\\ r_m& =\frac{r_a}{2}\end{array}$$

Here is three unknown, three equations, can solve related parameters.

We can write the above Flow Equation as a matrix form:

$$r=M\cdot r,r_j=\sum _{i\to j}\frac{r_i}{d_i}$$

among them$M$is a column random matrix. Set nodes$j$‘s output is$d_j$, if$j\to i$, then$M_{ij}=\frac{1}{d_j}$, that is, the matrix

The column and 1 of$M$are 1.

$r_i$is the webpage

The important degree of$i$,${\sum }_i{r}_i=1$。

Suppose someone is browsing the web, at time

At$t$, he was browsing the web$i$; at time

At$t+1$, this person will choose the webpage randomly$i$external link$j$Access; then when surfing online, the above process will be repeated.

So, set the orientation$p(t)$indicates the state probability,$p(t{)}_i$indicates at time$t$Located on the webpage

The probability of$i$; that is,$p(t)$is based on the probability distribution of webpages.

So, in time$t+1$,$p(t+1)=M\cdot p(t)$. if$p(t+1)=M\cdot p(t)=p(t)$, so we call it$p(t)$is a stamentary distribution of a random Walk.

Because Flow Equation is written as a matrix form$r=M\cdot r$, so$r$is a matrix$M$Feature vector. We can solve the method of ** power iteration (Power Iteration) **$r$。

Power Iteration

Suppose there is one with$N$The web map of the node, where the node is the page and the hyperlink. Power iteration is a simple solution$r$iteration scheme, you can allocate an initial$r$value, repeat the following steps until convergence (${\sum }_i|r^{(t+1)-r^t}{|}_1<\epsilon$）。

• Initialization-$r^{(0)}=[\frac{1}{N},\cdots ,\frac{1}{N}{]}^T$。
• iteration-$r^{(t+1)}=M\cdot r^{(t)}$，$r_j^{(t+1)}={\sum }_{i\to j}\frac{r_i^{(t)}}{d_i}$。
• iteration termination conditions-$|r^{(t+1)-r^t}{|}_1<\epsilon$。

But can this algorithm be converged? Does its convergence results meet our expectations? Is convergence reasonable?

Actually, there are two problems in this algorithm:

(1) SOME PAGES Are DEAD ENDS -Some pages have no external links.

Solution:

（2）Spider traps——(all out-links are within the group)。

Spider Traps solution:

Therefore, we can get the Pagerank equation–

$$r_j=\sum _{i\to j}\beta \frac{r_i}{d_i}+(1-\beta )\frac{1}{N}$$

Write into matrix form:

$$r=A\cdot r$$

among them$A$is Google Matrix,$A=\beta M+(1-\beta )[\frac{1}{N}{]}_{N\times N}$. here$\beta$usually take 0.8,0.9.

The following is an example:

The calculation process of

Pagesk is mainly matrix multiplication$r^{new}=A\cdot r^{old}$. But there is a problem that when the number of nodes is large, it takes a lot of memory.

We can re -organize the form of the PageRANK equation:

$$r=\beta M\cdot r+[\frac{1-\beta }{N}{]}_N$$

Here, matrix$M$is a sparse matrix, and$[\frac{1-\beta }{N}{]}_N$is a dense matrix. Therefore, in order to facilitate calculations, we calculate in each round of iteration$r^{new}=\beta M\cdot r^{old}$, and then$r^{new}$Based on a constant value$(1-\beta )/N$。