二十世纪,科学研究的特点是分析的方法,还原论的方法:物理学(牛顿力学、量子力学、电子论、半导体),化学(量子分子论),生物(双螺旋结构);建筑工程(应力应变分析),……
二十一世纪(二十世纪末),系统成为主要的研究对象,整合成为主要方法。普列高津的耗散结构理论,哈肯的协同学,混沌和复杂系统理论,系统生物学 … …
当分析为主要的研究方法时,人类关注如何将系统“分析”、“分解”,揭开系统的细部,了解是什么元素或部件组成了系统,却忽视或破坏了这些元素是如何组合成系统的。而整合的方法在于了解细部以后,研究“如何组合”的问题。这种方法导致复杂网络结构的研究。
网络连接结构错综复杂、极其混乱,同时又蕴含着丰富的结构:社区、基序、聚集性、生成规律性等等,而且网络连接结构可能是随时间变化的,例如,WWW上每天都不停地有页面和链接的产生和删除。
网络中的节点可能是具有分岔和混沌等复杂非线 性行为的动力系统。例如,基因网络中每个节点都具有复杂的时间演化行为。而且,一个网络中可能存在多种不同类型的节点。例如,控制哺乳动物中细胞分裂的生化网络就包含各种各样的基质和酶。
当关联失去时这类特性会在节点处消失或改变。例如,耦合神经元重复地被同时激活,那么它们之间的连接就会加强,这被认为是记忆和学习的基础。
一篇是美国康奈尔(Cornell)大学理论和应用力学系的博士生Watts及其导师、非线性动力学专家Strogatz教授于1998年6月在Nature杂志上发表的题为《“小世界”网络的集体动力学》(Collective Dynamics of ‘Small-World’ Networks)的文章;
另一篇是美国Notre Dame大学物理系的Barabāsi教授及其博士生Albert于1999年10月在Science杂志上发表的题为《随机网络中标度的涌现》(Emergence of Scaling in Random Networks)的文章。
这两篇文章分别揭示了复杂网络的小世界特征和无标度性质,并建立了相应的模型以阐述这些特性的产生机理。
节点$i$的度$k_i$定义为与该节点连接的其他节点的数目。
直观上看,一个节点的度越大就意味着这个节点在某种意义上越重要.
在简单图中,设节点$v$的邻集为$N(v)$, $|N(v)|=k_i$,则节点$v$的聚类系数定义为这$k_i$个节点之间存在边数$E_i$与总的可能边数$k_i(k_i-1)/2$之比,即:$C_i=2E_i/k_i(k_i-1)$。 该值表明了节点$v$的邻点间关系的密切程度。
所有节点$i$的聚类系数$C_i$的平均值。$C=0$网络中所有节点都是孤立点,$C=1$网络中任意节点间都有边相连。 网络节点间联系的密切程度, 体现网络的凝聚力。
点介数:网络中通过该节点的最短路径的条数。
边介数:网络中通过该边的最短路径的条数。
反映了节点或边的作用和影响力。如果一对节点间共有$B$条不同的最短路径,其中有$b$条经过节点$i$,那么节点$i$对这对节点的介数的贡献为$b/B$。把节点$i$对所有节点对的贡献累加起来再除以节点对总数,就可得到节点i的介数。类似的,边的介数定义为所有节点对的最短路径中经过该边的数量比例。
介数越大,说明经过该节点(边)的最短路径越多。在信息传播过程中,通过该节点(边)的信息量就越大,于是就越容易发生拥塞。 研究表明,节点介数与度之间有很强的相关性,不同类型的网络,其介数分布也大不一样。
一个图的k-核:反复去掉图中度小于等于$k$的节点后,所剩余的子图。
若一个节点存在于k-核,而在(k+1)-核中被去掉,则此节点核数为k,例:所有度为1的节点的核数必为0
节点核数中的最大值称为网络图的核数
节点核数可以表明节点在核中的深度;即便一个节点的度数很高,它的核数也可能很小。例如:包含N个节点的星型网络的中心节点的度数为N-1,但它的核数为0
目前刻划复杂网络的统计量有很多,例:聚类系数,平均路径长度,平均度,介数,核数等。
这个要从搜索引擎的发展讲起。最早的搜索引擎采用的是 分类目录的方法,即通过人工进行网页分类并整理出高质量的网站。那时 Yahoo 和国内的 hao123 就是使用的这种方法。 后来网页越来越多,人工分类已经不现实了。搜索引擎进入了文本检索的时代,即计算用户查询关键词与网页内容的相关程度来返回搜索结果。这种方法突破了数量的限制,但是搜索结果不是很好。因为总有某些网页来回地倒腾某些关键词使自己的搜索排名靠前。 后来,谷歌的两位创始人,佩奇 (Larry Page) 和布林 (Sergey Brin) 开始了对网页排序问题的研究。他们的借鉴了学术界评判学术论文重要性的通用方法,那就是看论文的引用次数。由此想到网页的重要性也可以根据这种方法来评价。于是PageRank的核心思想就诞生了,非常简单:
如果一个网页被很多其他网页链接到的话说明这个网页比较重要,也就是PageRank值会相对较高
如果一个PageRank值很高的网页链接到一个其他的网页,那么被链接到的网页的PageRank值会相应地因此而提高
$PageRank$算法总的来说就是预先给每个网页一个$PR$值,由于$PR$值物理意义上为一个网页被访问概率,所以一般是$1/N$, 其中$N$为网页总数。另外,一般情况下,所有网页的$PR$值的总和为$1$。如果不为$1$的话也不是不行,最后算出来的不同网页之间$PR$值的大小关系仍然是正确的,只是不能直接地反映概率了。
预先给定$PR$值后,通过下面的算法不断迭代,直至达到平稳分布为止。
互联网中的众多网页可以看作一个有向图。下图是一个简单的例子:图中的节点表示网页,如果网页A有链接到网页B,则存在一条有向边A->B: 这个例子中只有四个网页,如果当前在$A$网页,那么悠闲的上网者将会各以$1/3$的概率跳转到$B、C、D$,这里的3表示$A$有3条出链,如果一个网页有$k$条出链,那么跳转任意一个出链上的概率是$1/k$,同理$D$到$B$、$C$的概率各为$1/2$,而$B$到$C$的概率为0。一般用转移矩阵表示上网者的跳转概率,如果用$n$表示网页的数目,则转移矩阵$M$是一个$n*n$的方阵;如果网页$j$有$k$个出链,那么对每一个出链指向的网页$i$,有$M[i][j]=1/k$,而其他网页的$M[i][j]=0$;上面示例图对应的转移矩阵如下:
\begin{equation} M={ \left[ \begin{array}{cccc} 0 & 1/2 & 1 & 0\\ 1/3 & 0 & 0 & 1/2\\ 1/3 & 0 & 0 & 1/2\\ 1/3 & 1/2 & 0 & 0 \end{array} \right ]} \end{equation}初始时,假设上网者在每一个网页的概率都是相等的,即$1/n$,于是初始的概率分布就是一个所有值都为$1/n$的$N$维列向量$V_0$,用$V_0$去右乘转移矩阵$M$,就得到了第一步之后上网者的概率分布向量$V_1$。下面是$V_1$的计算过程:
\begin{equation} V_1 = MV_0 ={ \left[ \begin{array}{cccc} 0 & 1/2 & 1 & 0\\ 1/3 & 0 & 0 & 1/2\\ 1/3 & 0 & 0 & 1/2\\ 1/3 & 1/2 & 0 & 0 \end{array} \right ] \left[ \begin{array}{cccc} 1/4\\ 1/4\\ 1/4\\ 1/4 \end{array} \right ]= \left[ \begin{array}{cccc} 9/24\\ 5/24\\ 5/24\\ 5/24 \end{array} \right ]} \end{equation}注意矩阵M中$M[i][j]$不为0表示用一个链接从$j$指向$i$,$M$的第一行乘以$V_0$,表示累加所有网页到网页$A$的概率即得到$9/24$。得到了$V_1$后,再用$V_1$去右乘$M$得到$V_2$,一直下去,最终$V$会收敛,即$V_n=MV_{(n-1)}$,上面的图示例,不断的迭代,最终 $V=[3/9,2/9,2/9,2/9]^T$
\begin{equation} { \left[ \begin{array}{cccc} 1/4\\ 1/4\\ 1/4\\ 1/4 \end{array} \right ] \left[ \begin{array}{cccc} 9/24\\ 5/24\\ 5/24\\ 5/24 \end{array} \right ] \left[ \begin{array}{cccc} 15/48\\ 11/48\\ 11/48\\ 11/48 \end{array} \right ] \left[ \begin{array}{cccc} 11/32\\ 7/32\\ 7/32\\ 7/32 \end{array} \right ] ... \left[ \begin{array}{cccc} 3/9\\ 2/9\\ 2/9\\ 2/9 \end{array} \right ]} \end{equation}上述上网者的行为是一个马尔科夫过程的实例,要满足收敛,需要具备一个条件: 图是强连通的,即从任意网页可以到达其他的任意网页
但是互联网上的网页不满足强连通的特性,因为有一些网页不指向任何网页,如果按照上面的计算,上网者到达这样的网页后便走投无路,导致前面累计得到的转移概率被清零,这样下去,最终的得到的概率分布向量所有元素几乎都为0。假设我们把上面图中C到A的链接丢掉,C变成了一个终止点,得到下面这个图:
对应的转移矩阵为
\begin{equation} M={ \left[ \begin{array}{cccc} 0 & 1/2 & 0 & 0\\ 1/3 & 0 & 0 & 1/2\\ 1/3 & 0 & 0 & 1/2\\ 1/3 & 1/2 & 0 & 0 \end{array} \right ]} \end{equation}连续迭代下去,最终所有元素都为$0$:
\begin{equation} { \left[ \begin{array}{cccc} 1/4\\ 1/4\\ 1/4\\ 1/4 \end{array} \right ] \left[ \begin{array}{cccc} 3/24\\ 5/24\\ 5/24\\ 5/24 \end{array} \right ] \left[ \begin{array}{cccc} 5/48\\ 7/48\\ 7/48\\ 7/48 \end{array} \right ] \left[ \begin{array}{cccc} 21/288\\ 31/288\\ 31/288\\ 31/288 \end{array} \right ] ... \left[ \begin{array}{cccc} 0\\ 0\\ 0\\ 0 \end{array} \right ]} \end{equation}另外一个问题就是陷阱问题,即有些网页不存在指向其他网页的链接,但存在指向自己的链接。比如下面这个图:
上网者跑到C网页后,再也不能从C中出来,将最终导致概率分布值全部转移到C上来,这使得其他网页的概率分布值为0,从而整个网页排名就失去了意义。
对应的转移矩阵为
\begin{equation} M={ \left[ \begin{array}{cccc} 0 & 1/2 & 0 & 0\\ 1/3 & 0 & 0 & 1/2\\ 1/3 & 0 & 1 & 1/2\\ 1/3 & 1/2 & 0 & 0 \end{array} \right ]} \end{equation}连续迭代下去,最终所有元素都为$0$:
\begin{equation} { \left[ \begin{array}{cccc} 1/4\\ 1/4\\ 1/4\\ 1/4 \end{array} \right ] \left[ \begin{array}{cccc} 3/24\\ 5/24\\ 11/24\\ 5/24 \end{array} \right ] \left[ \begin{array}{cccc} 5/48\\ 7/48\\ 29/48\\ 7/48 \end{array} \right ] \left[ \begin{array}{cccc} 21/288\\ 31/288\\ 205/288\\ 31/288 \end{array} \right ] ... \left[ \begin{array}{cccc} 0\\ 0\\ 1\\ 0 \end{array} \right ]} \end{equation}我们认为上网者,总是随机的选择网页,当走到一个终结网页或者一个陷阱网页时(比如两个示例中的$C$),不会被困在原地,而是会在浏览器的地址栏随机输入一个地址,当然这个地址可能又是原来的网页,但这里给了他一个逃离的机会。为此我们对算法进行改进,每一步,上网者可能都不想看当前网页了,不看当前网页也就不会点击上面的链接,而是在地址栏输入另外一个地址,而在地址栏输入而跳转到各个网页的概率是$1/n$。假设上网者每一步查看当前网页的概率为$a$,那么他从浏览器地址栏跳转的概率为$(1-a)$,于是原来的迭代公式转化为:
$$V = aMV+(1-a)e$$根据上式来计算带有陷阱节点的网页图的最终的概率分布:
\begin{equation} V = aMV+(1-a)e = 0.8 \times \left[ \begin{array}{cccc} 0 & 1/2 & 0 & 0\\ 1/3 & 0 & 0 & 1/2\\ 1/3 & 0 & 1 & 1/2\\ 1/3 & 1/2 & 0 & 0 \end{array} \right ] \left[ \begin{array}{cccc} 1/4\\ 1/4\\ 1/4\\ 1/4 \end{array} \right ]+0.2 \times \left[ \begin{array}{cccc} 1/4\\ 1/4\\ 1/4\\ 1/4 \end{array} \right ]= \left[ \begin{array}{cccc} 9/60\\ 13/60\\ 25/60\\ 13/60 \end{array} \right ] \end{equation}import matplotlib.pyplot as plt
import networkx as nx
G=nx.barabasi_albert_graph(30,3)
layout = nx.spring_layout(G)
plt.figure(figsize=(15,8))
plt.subplot(121)
nx.draw(G, pos=nx.shell_layout(G), node_color='y')
pr=nx.pagerank(G,alpha=0.85)
plt.subplot(122)
nx.draw(G, pos=nx.shell_layout(G), node_size=[x * 18000 for x in pr.values()],node_color='r',with_labels=True)
plt.show()