$ remains high. \n",
" - Hence in the range $0.001"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"# In summary\n",
"- we find that the random network model does not capture the clustering of real networks. \n",
"- Instead real networks have a **much higher clustering coefficient** than expected for a random network of similar N and L. \n",
"- An extension of the random network model proposed by Watts and Strogatz [1998] addresses the coexistence of high and the small world property. \n",
"- It fails to explain, however, **why high-degree nodes have a smaller clustering coefficient than low-degree nodes**."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"\n",
"# REAL NETWORKS ARE NOT POISSON"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# BA模型 (1999)\n",
"\n",
"Barabasi (1999) Emergence of scaling in random networks.Science-509-12\n",
"\n",
"### Scaling-Free\n",
"\n",
"\n",
"\n",
"### The Preferential Attachment Model\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# 无标度的意义"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"度分布的n阶矩被定义为:\n",
"\n",
"$ = \\sum_{k_{min}}^{k_{max}}k^np_k = \\int_{k_{min}}^{k_{max}}k^np_kdk $ (1)\n",
"\n",
"低阶矩具有明确的统计意义:\n",
"\n",
"* n = 1的时候,一阶矩是$$,即平均度。\n",
"* n = 2的时候,二阶矩是$$,可以帮助计算方差 $ \\delta^2 = - ^{2} $,测量了度的离散程度(the spread in the degrees)。\n",
"* n = 3的时候,三阶矩是$$, 决定了度分布的偏度(skewness),测量了$p_k$围绕着$$的对称性。\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"对于无标度网络而言,满足幂律分布:\n",
"\n",
"$p(k) = Ck^{-\\gamma}$ (2)\n",
"\n",
"由公式(1)和(2)可以得到:\n",
"\n",
"$ = \\int_{k_{min}}^{k_{max}}k^np_kdk = C \\frac{k_{max}^{n- \\gamma +1} - k_{min}^{n - \\gamma +1}}{n - \\gamma + 1} $ (3)\n",
"\n",
"可以使用wolframalpha的积分计算器积分来进行简单验证,例如x^(n-r)dx从10到100积分 网页链接:http://www.wolframalpha.com/input/?i=integrate+x%5E%28n-r%29+dx+from+10+to+100"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"显然:\n",
"\n",
"* 当$n - \\gamma +1 <= 0$时,随着$k_{max}增加,$$k_{max}^{n- \\gamma +1} \\rightarrow 0$。所有满足$n <= \\gamma -1$的n阶矩都是有限的。\n",
"* 当$n - \\gamma +1 >0 $时,随着$k_{max}增加,$$k_{max}^{n- \\gamma +1} \\rightarrow \\infty$。所有满足$n > \\gamma -1$的n阶矩都是无极限的。\n",
"\n",
"对于无标度网络而言,一般幂参数$2 < \\gamma < 3$,所以:\n",
"\n",
"* 对于n = 1的情况,即一阶矩平均度$$是有限的。\n",
"\n",
"* 但对于n >= 2的情况,即$k^2$或$k^3$是无极限的。二阶和高阶矩无穷大是“无标度”的来源"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"# 无标度的意义\n",
"> ### 在网络中随机抽取一个节点的度可以显著的不同于平均度$$\n",
"\n",
"上图最为直接的描绘出了这种特点,即与正态分布等相比,`无标度网络下降的慢`。\n",
"\n",
"* 对于任何指数类型的分布,如泊松分布或高斯分布,随机选取一个节点的度在平均度附近,因此平均度就是这些网络的`尺度`。\n",
"\n",
"* 对于一个幂律分布而言,因为二阶矩发散,在网络中随机抽取一个节点的度可以显著的不同于平均度$$, 因此平均度不再是网络的尺度,称之为无标度。"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"\n",
"\n",
"# 对于不同的网络,平均度与标准差的取值"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"\n",
"\n",
"英国的天才 第一集 Genius of Britain: The Scientists Who Changed the World (2010) https://movie.douban.com/subject/4887415/\n",
"\n",
"# 微积分, 数学"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# 连续平均场\"Continuum Mean-Field\" \n",
"### \"Mean-Field\": many -> one\n",
"\n",
"> ## The complex interaction between a large number of components can be simplified into **a single averaged effect** of all the other individuals on any given one.\n",
"\n",
"### \"Continuum\": discrete -> Continuous\n",
"\n",
"A discrete variables that is \"smooth enough\", i.e. increase by one unit in each period, such as time steps [1], spatial jumps [2-3], and population, can be viewed as a continuous geometric structure. \n",
"\n",
"Any measure on this structure, like degree [1], number of unique locations visited [2], and distance [3], can be described by differential equations.\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## 模型设定\n",
"* 初始状态有$m_0$个节点\n",
"* 1. 增长原则:每次加入一个节点i (加入时间记为$t_i$), 每个节点的加入带来m条边,2m个度的增加\n",
"** 其中老节点分到的度数是m,新加入的那一个节点分到的度数为m\n",
"** 那么到时间t的时候,网络的总节点数是$m_0 + t$,网络的总度数为$2mt$。\n",
"* 2. 优先链接原则:每一次从m条边中占有一条边的概率正比于节点的度$k_i$\n",
"** 那么显然,加入的越早($t_i$越小)越容易获得更多的链接数。\n",
"** 从时间0开始,每一个时间步系统中的节点度$k_i$是不断增加的。\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## 度的增长/时间依赖性\n",
"$k_i$在一个时间步获得一个度的概率表示为$\\prod (k_i) $, 那么有:\n",
"\n",
"$\\prod (k_i) = \\frac{k_i}{\\sum k_i} = \\frac{k_i}{2mt}$\n",
"\n",
"> 也就是说,在时间点t,节点i获得一个度的概率(能力)是节点i的度占网络总度数的比值。\n",
"\n",
"一个时间步,$k_i$随t的变化率可以表达为:\n",
"\n",
"# $\\frac{\\partial k_i}{\\partial t} = \\Delta k \\prod (k_i) = m \\frac{k_i}{2mt} = \\frac{k_i}{2t}$\n",
"\n",
"# $\\frac{\\partial k_i}{k_i} = \\frac{\\partial t}{2t}$\n",
"\n",
"# $\\int \\frac{1}{k_i} d k_i = \\int \\frac{1}{2t} dt$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## 积分结果\n",
"\n",
"# $k_i = C (2t) ^ {-0.5}$ (1)\n",
"\n",
"此时,根据模型的初始条件,每个新加入节点获得的度是m:\n",
"\n",
"$k_i(t_i) = m $ 代入公式(1)\n",
"\n",
"可以得到$C = m(2t_i)^{-0.5}$ 公式(2)\n",
"\n",
"代入公式(1),得到:\n",
"\n",
"$k_i = m (\\frac{t}{t_i})^{0.5}$ 公式(3)\n",
"\n",
"对于一个节点i,其加入网络的时间$t_i$是固定的,我们可以观察其度$k_i$随着时间的幂律关系。\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## 累积概率分布\n",
"\n",
"当我们思考一个累积概率分布的时候,我们想要的是$k_i(t) < k$的概率:$P(k_i(t) < k) $\n",
"\n",
"由公式$k_i = m (\\frac{t}{t_i})^{0.5}$ 公式(3),可以知道:\n",
"\n",
"$P(k_i(t) < k) = P( m (\\frac{t}{t_i})^{0.5} < k ) = P( t_i > \\frac{m^2 t}{k^2} ) = 1 - P(t_i \\leqslant \\frac{m^2 t}{k^2} )$(4)\n",
"\n",
"在初始状态$ t = 0$, 有$m_0$个节点,那么$t_{m_0} = 0$\n",
"\n",
"假设我们将节点加入的时间步是均匀的,那么$t_i$的概率是一个常数:\n",
"\n",
"$P(t_i) = \\frac{1}{m_0 + t}$ 公式(5)\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### 均匀分布的性质\n",
"* 设连续型随机变量X的概率密度函数为 $f(x)=1/(b-a),a≤x≤b $, 则称随机变量X服从[a,b]上的均匀分布,记为X~U[a,b]。若[x1,x2]是[a,b]的任一子区间,则 $P{x_1≤x≤x_2}=(x_2-x_1) \\frac{1}{b-a}$\n",
"\n",
"根据均匀分布的性质,将公式(5)代入公式(4)得到:\n",
"\n",
"$P(k_i(t) < k) = 1- \\frac{m^2 t}{k^2} P(t_i) = 1 - \\frac{m^2 t}{k^2 (m_0 + t)} $ 公式(6)\n",
"\n",
"\n",
"对累积概率函数求微分,就可以到达概率密度函数:\n",
"\n",
"$P( k ) = \\frac{\\partial P(k_i(t) < k)}{\\partial k} = \\frac{2m^2 t}{m_0 + t} \\frac{1}{k^3}$ 公式(7)\n",
"\n",
"也就是说:$\\gamma = 3$, 与m无关。\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# 参考文献\n",
"- Barabasi 2016 Network Science. Cambridge\n",
"- Barabasi (1999) Emergence of scaling in random networks.Science-509-12.pdf\n",
"- Barabasi (1999) Mean-field theory for scale-free random networks. PA.pdf\n",
"- Albert & Barabasi (2002) Statistical mechanics of complex networks. RMP.pdf\n",
"- BA Model 计算传播百科 http://computational-communication.com/wiki/index.php?title=Mean_field_method#BA_Model\n",
"- Principle of Locality I: Hacking the Continuum Mean-Field Technique in Network Modeling http://www.jianshu.com/p/97f674267d3e\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"celltoolbar": "Slideshow",
"kernelspec": {
"display_name": "Python [conda env:anaconda]",
"language": "python",
"name": "conda-env-anaconda-py"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.5.4"
},
"latex_envs": {
"bibliofile": "biblio.bib",
"cite_by": "apalike",
"current_citInitial": 1,
"eqLabelWithNumbers": true,
"eqNumInitial": 0
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": false,
"sideBar": false,
"skip_h1_title": false,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {
"height": "1066px",
"left": "1954px",
"top": "198px",
"width": "504px"
},
"toc_section_display": false,
"toc_window_display": true
}
},
"nbformat": 4,
"nbformat_minor": 1
}