这是我学习斯坦福大学课程的一个个人笔记，记录的是个人感觉有趣的东西。会从2015年7月3日开始每天攒一点点。希望在正式入职阿里之前完成。如有任何疑问，欢迎留言或者托梦。

Week 1

Note1_centrality、constraint

家族联姻网络，betweenness最高的家族是Medici，在当时拥有的财富和权利比其他家族更多。我们还可以用constraint来量化：

$$constraint(Medici) = 4*(1/6)^2+2*(1/6+1/6*1/3)^2 = 0.21$$

$$constraint(Strozzi) = 2*(1/4+1/4*1/3)^2 + (1/4+2*1/4*1/3)^2 + (1/4)^2 = 0.46$$

$$constraint(Guadagni) = 4*(1/4)^2 = 0.25$$

从constaint来看，影响力排名为：Medici > Guadagni > Strozzi，与betweenness反映的一致。 从Closeness来看，影响力排名为：Medici > Guadagni > Strozzi，与betweenness反映的一致。

$$Closeness = (n-1)/(\sum_j{l_{i,j}})$$ $$Closeness(Medici) = 14/25$$ $$Closeness(Strozzi) = 14/32$$ $$Closeness(Guadagni) = 14/26$$

Note2_直径、Tree、ER图、Six Degrees of Separation

先计算tree的直径。如上图所示，从绿色节点开始向外连边（拓展），每个节点有4个邻居。拓展l步（最长的路径/直径是2l）后图中除去root的节点数目是$d+d(d-1)+...+d(d-1)^{l-1} = d((d-1)^l-1)/(d-2) \approx (d-1)^l \approx d^l$，因此如果一个点要与其他$n-1$个节点可达的话，大约需要$l = log(n)/log(d)$步。即在包含有$n$个节点的tree中，假设节点度为$d$，那么该网络直径的数量级为$log(n)/log(d)$

在tree的基础上通过改变连边的概率和增加环 变为 E-R图：包含有有$n$个节点的E-R图中，节点的平均度为$d$，以一定概率$p$产生连边（二项分布）。证明：当$d(n) > (1 + \epsilon)log(n)$ 且 $d(n)/n \rightarrow 0$时，E-R的直径数量级也是$log(n)/log(d)$。证明如下：

根据Chernoff Bounds原理有$Pr(d/3 \leq d_i \leq 3d) \geq 1-e^{-d}$，所有节点度都满足的概率为$Pr(d/3 \leq d_{all} \leq 3d) \geq (1-e^{-d})^n$。当$d(n) > (1 + \epsilon)log(n)$，且$n$很大时时，上式变为：$Pr(d/3 \leq d_{all} \leq 3d) > (1-(1/n)^{1+\epsilon})^n \rightarrow exp(-n^{-\epsilon}) \rightarrow 1$。因此$log(n)/log(3d) < l < log(n)/log(d/3)$。当$d$足够大时，有$l = log(n)/log(d)$。

针对环的问题，其实影响不大，因为：随着$l$的增加，新的节点以指数级增长，扩展$k$步后，仍有$n-d^k$个节点未被扩展，当$k < log(n)/log(d)$ 时，$n-d^k$ 远大于 $d^k$，在网络直径计算中，与新增的节点相比现有节点中存在的环可以忽略不计。

当前全世界有70亿人，只要每个人平均认识50个人，那么全世界的任意两个人之间一般只隔着5个人，即通过6步介绍即可建立联系。 E-R图可以解释六度分隔的现象，$log(7000000000)/log(50) = 5.79$。当然后来被更合理地改进(rewired保证高聚类系数)，但是其思想影响了大半个世纪之久。

Note3_无标度与分形，从不同尺度上观察网络的结构类似

Note4_现实网络的聚集系数要高于E-R网络

Week 2

Note1_现实网络的聚集系数要高于E-R网络

Note2_Eigenvector centrality

这部分与薛定谔方程的联系要再想想。

Eigenvector centrality is one method of computing the "centrality" of each node in a graph. The assumption is that each node's centrality is the sum of the centrality values of the nodes that it is connected to. The nodes are drawn with a radius proportional to their centrality. The adjacency matrix and centrality matrix for the solution are shown. The centrality matrix is an eigenvector of the adjacency matrix such that all of its elements are positive.

From HITS to Eigenvector

HITS 将节点属性分为authority（入边）和hubs（出边）。因为大部分的页面既有inlinks，又有outlinks，所以这些页面同时具有Authority和Hub的属性。HITS算法的核心，就是根据一个有向结构图，计算得到每个节点的authority和hub值。

迭代算法：

1. 假设每个节点i都有一个authority值 $x_i$ 和 一个hub值 $y_i$；
2. 初始化的时候，给每个节点一个authority和hub的默认值，比如都是1；
3. 于是在下一次迭代的时候，新的authority值 $x_i$ 就等于节点i的inlinks对应节点的hub值之和

算法向量化：

定义邻接矩阵$L$,authority向量为$\vec x$，hub向量为$\vec y$，有：

$$\vec x^{k} = L^T \vec y^{k-1}$$

$$\vec y^k = L \vec x^k$$

$$k = k+1$$

$$\vec x , \vec y 归一化，防止溢出$$

上面的公式又可以写为：

$$\vec x^{k} = L^T L \vec x^{k-1}$$

$$\vec y^{k} = L L^T \vec y^{k-1}$$

因此$\vec x 与 \vec y$最终就是矩阵L在column-normalization下的最大特征值对应的特征向量。

Pagerank vs (HITS)SVD

虽然大部分的文献中，都将PageRank解释成是基于”Random Surfer“模型，在随机游走的过程中，经常被访问到的page比很少被访问到的page更加的重要。但从随机的角度更难理解PageRank的计算公式。其实换个角度看，PageRank和HITS非常的类似。例如下面这张图：

节点X有两个inlinks，分别来自节点A，B。A除了指向X以外，还指向了其它3个节点，而B还指向了其它的2个节点。那么节点X的PageRank的值就等于： PR(X) = PR(A) / 4 + PR(B) / 3 这个公式已经非常近似于HITS中计算Authority的方法，例如X的Authority等于： Autority(X) = Hub(A) + Hub(B) 这两个公式的区别，就在于HITS仅仅是一个求和，而PageRank相加的是概率。

Pagerank和HITS类似，首先将Graph表示成一个矩阵，只是不再是邻接矩阵，而是 转移概率矩阵 ：

概率转移矩阵是一个随机矩阵（stochastic matrix），理想情况下，每一列之和等于1。当加入了random jump之后，变形后的matrix（irreducible）依然可以用特征向量求解节点重要性。

PageRank computes (a variant of) eigenvector centrality, ,while the SVD apparently leads to the Hyperlink-Induced Topics Search (HITS) algorithm.

Mathematically speaking, the PageRank is the dominant eigenvector of the (modified) adjacency matrix - as explained on the Wikipedia page - while HITS gives the dominant singular vector of the adjacency matrix. Both are defined by the global network of webpages and links between them, and both can be computed by only considering the node graph locally. So at first sight, I think that the computational cost is roughly equal.

Week 3

长尾未必是powerlaw，powerlaw的生成模型是100%根据preference（优先链接）的，而现实网络中朋友的交往也会存在着随机性。下图展示了4个网络在hybrid model上的拟合系数：

a接近1时，是泊松分布，a接近0时是powerlaw分布。可见，fat tails并非都是powerlaw。