精华内容
下载资源
问答
  • 下面是求节点介数的代码,介数就是指经过一个点的最短路径的比例,在计算复杂网络中节点重要的时候会用到。 /*** 用来计算介数* 要计算所有的最短路径,用DIJ计算最短路径的时候我们可以发现一个规律:最后生成的...

    下面是求节点介数的代码,介数就是指经过一个点的最短路径的比例,在计算复杂网络中节点重要性的时候会用到。 /**

    * 用来计算介数

    * 要计算所有的最短路径,用DIJ计算最短路径的时候我们可以发现一个规律:最后生成的结果是最小生成树,而一棵树是可以用一个一维数组表示的。

    * 所以本代码在计算介数的时候具有和DIJ相同的时间复杂度。

    */

    public class Betweeness {

    private double[][] dis;

    private int N;

    Betweeness(double[][] dis)

    {

    this.dis = dis;

    this.N = dis.length;

    }

    /**

    * 根据返回的树来计算经过每个节点的最短路径的数目

    * @return

    */

    public double[] getBetweeness()

    {

    double[] b = new double[N];

    for(int start = 0; start < N; start++)

    {

    int[] path = getPath(start); // 保存树的结构

    int[] num = new int[N]; // 一个节点的路径的数目

    int[] used = new int[N]; // 0:初始-->1:有子节点 0--->2:把没有子节点的处理

    // 每次处理的时候找到没有子节点的点,然后将它的个数加到它的父节点中

    for(int i = 0; i < N; i++)

    {

    for(int j = 0; j < N; j++)

    {

    if(path[j] != -1 && used[path[j]] == 0)

    {

    used[path[j]] = 1;

    }

    }

    for(int j = 0; j < N; j++)

    {

    if(used[j] == 0 && path[j] >= 0)

    {

    num[path[j]] += 1 + num[j];

    used[j] = 2;

    }

    }

    for(int j = 0; j < N; j++)

    {

    if(used[j] == 1)

    {

    used[j] = 0;

    }

    }

    }

    for(int i = 0; i < N; i++)

    {

    b[i] += num[i];

    }

    }

    double sum = N*N - N;

    for(int i = 0; i < N; i++)

    {

    b[i] /= sum;

    }

    return b;

    }

    /**

    * 计算从start出发到各个节点的最短路径,返回这棵最小生成树

    * @param start

    * @return

    */

    public int[] getPath(int start)

    {

    int[] path = new int[N];

    boolean[] used = new boolean[N];

    double[] minDis = new double[N];

    for(int i = 0; i < N; i++)

    {

    path[i] = -1;

    minDis[i] = -1.0;

    }

    used[start] = true;

    minDis[start] = 0.0;

    for(int i = 1; i < N; i++)

    {

    for(int j = 0; j < N; j++)

    {

    if(used[j] == true || dis[start][j] < 0){

    continue;

    }

    if(dis[start][j] >= 0.0 && (minDis[j] < 0.0 || minDis[j] > minDis[start] + dis[start][j]))

    {

    path[j] = start;

    minDis[j] = minDis[start] + dis[start][j];

    }

    }

    start = -1;

    for(int j = 0; j < N; j++)

    {

    if(minDis[j] < 0.0 || used[j] == true)

    {

    continue;

    }

    if(start == -1 || minDis[start] > minDis[j])

    {

    start = j;

    used[start] = true;

    }

    }

    if(start == -1)

    {

    break;

    }

    }

    return path;

    }

    /

    public static void main(String[] main){

    double[][] dis = {{0, 1, 5, 2},

    {1, 0, 4, 6},

    {5, 4, 0, 3},

    {2, 6, 3, 0}};

    double[] b = new Betweeness(dis).getBetweeness();

    for(int i = 0; i < b.length; i++)

    {

    System.out.println(b[i]);

    }

    }

    }

    展开全文
  • 如何使用netwokx进行复杂网络的中心性分析? 这是本学期在大数据哲学与社会科学实验室做的第七次分享了。 第一次分享的是: 如何利用“wordcloud+jieba”制作中文词云? 第二次分享的是: 如何爬取知乎中问题的...

    如何使用netwokx进行复杂网络的中心性分析?

    这是本学期在大数据哲学与社会科学实验室做的第七次分享了。

    第一次分享的是:

    第二次分享的是:

    第三次分享的是:

    第四次分享的是:

    第五次分享的是:

    第六次分享的是:

    本次分享的是“如何使用netwokx进行复杂网络的中心性分析?”

    1. networkx概述

    networkx是用python语言编写的软件包,便于用户对复杂网络进行创建、操作和学习。

    利用networkx可以以标准化和非标准化的数据格式存储网络、生成多种随机网络和经典网络、分析网络结构、建立网络模型、设计新的网络算法、进行网络绘制等。

    使用pip安装当前版本的networkx:

    pip install networkx
    

    升级到最新版本,使用–upgrade标签:

    pip install --upgrde networkx
    

    查看本地networkx是否成功安装,可在命令提示符中输入:

    pip show networkx
    

    如果出现以下内容,则安装成功。

    Name: networkx
    Version: 2.5.1
    Summary: Python package for creating and manipulating graphs and networks
    Home-page: http://networkx.github.io/
    Author: Aric Hagberg
    Author-email: hagberg@lanl.gov
    License: UNKNOWN
    Location: c:\programdata\anaconda3\lib\site-packages
    Requires: decorator
    Required-by: scikit-image
    

    Github地址:

    https://github.com/networkx/networkx

    官方学习文档:

    https://networkx.github.io/documentation/latest/_downloads/networkx_reference.pdf

    2. 基本理论

    网络由节点(node)和连接它们的边(edge)构成。

    例如,微信好友的关系是相互的,如果我是你的好友,你也是我的好友。这样的网络称为无向网络(undirected graph/network)。但超链接并非如此,如果我的网站可以链接到维基百科,并不表示维基百科会链接到我的网站。这样的网络称为有向网络(directed graph/network)

    在图论和网络分析中,中心性(Centrality)是判断网络中节点重要性/影响力的指标。在社会网络分析中,一项基本的任务就是鉴定一群人中哪些人比其他人更有影响力,从而帮助我们理解他们在网络中扮演的角色。

    那么,什么样的节点是重要的呢?

    对节点重要性的解释有很多,不同的解释下判定中心性的指标也有所不同。

    通常在中心性的分析角度上有两种出发点:中心度和中心势。

    中心度:表示一个节点在网络中处于核心地位的程度;中心势:表示整个图的紧密程度。换句话说,度表示单个节点的性质,而势表示整个图的性质。

    2.1 点度中心性(degree centrality)

    在无向网络中,我们可以用一个节点的度数(相当于你的微信好友数)来衡量中心性。在微博中,刘德华的粉丝数9千多万,他的点度中心性就很高。

    这一指标背后的假设是:重要的节点就是拥有许多连接的节点。你的社会关系越多,你的影响力就越强。

    import networkx as nx
    import matplotlib.pyplot as plt
    
    G = nx.Graph()
    G.add_nodes_from(['A', 'B', 'C', 'D', 'E', 'F', 'G'])
    G.add_edges_from([('A', 'B'), ('A', 'C'), ('A', 'D'),
                      ('B', 'C'), ('B', 'D'), ('C', 'D'),
                      ('D', 'E'), ('D', 'F'), ('D', 'G'),
                      ('E', 'F'), ('E', 'G'), ('F', 'G')])
    
    pos = nx.spring_layout(G)
    nx.draw(G, pos, with_labels=True)
    plt.show()
    

    在上面的蝴蝶结网络中,节点 D D D的连接数是6,和网络中的所有人都建立了直接联系,其它节点的连接数都是3,因此节点 D D D的点度中心性最高。整个网络一共有7个节点,意味着每个人最多可以有6个社会关系。因此,节点 D D D的点度中心性是6/6=1,其它节点的点度中心性是3/6=0.5。

    d c ( v ) = d e g r e e ( v ) n − 1 dc(v)=\frac{degree(v)}{n-1} dc(v)=n1degree(v)

    2.2 中介中心性(betweenness centrality)

    网络中两个非相邻成员之间的相互作用依赖于其它成员,特别是两成员之间路径上的那些成员。他们对两个非相邻成员之间的相互作用具有控制和制约作用。Freeman (1979)认为中间成员对路径两端的成员具有“更大的人际关系影响”。因此,中介中心性的思想是:如果一个成员位于其它成员的多条最短路径上,那么该成员就是核心成员,就具有较大的中介中心性。

    计算网络中任意两个节点的所有最短路径,如果这些最短路径中很多条都经过了某个节点,那么就认为这个节点的中介中心性高,这个指标考察的是节点对于其它节点信息传播的控制能力。换句话说,就是这个节点相当于一个闸,和它相连的节点想要得到其它节点都得经过它。

    G = nx.Graph()
    G.add_nodes_from(['A', 'B', 'C', 'D', 'E', 'F', 'G'])
    G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'C'),
                      ('B', 'D'), ('D', 'E'), ('E', 'F'),
                      ('E', 'G'), ('F', 'G')])
    
    pos = nx.spring_layout(G)
    nx.draw(G, pos, with_labels=True)
    plt.show()
    

    假设我们要计算节点 D D D的中介中心性。

    首先,我们计算节点 D D D之外,所有节点对之间的最短路径有多少条,这里是15条(在6个节点中选择两个节点即节点对的个数)。

    然后,我们再看所有这些最短路径中有多少条经过节点 D D D,例如节点 A A A要想找到节点 E E E,必须经过节点 D D D。经过节点 D D D的最短路径有9条。

    最后,我们用经过节点 D D D的最短路径除以所有节点对的最短路径总数,这个比率就是节点 D D D的中介中心性。节点 D D D的中介中心性是9/15=0.6。

    b s ( v ) = ∑ s ≠ t ≠ v ∈ V d s t ( v ) d s t bs(v)=\sum_{s\neq t\neq v\in V}\frac{d_{st}(v)}{d_{st}} bs(v)=s=t=vVdstdst(v)

    • d s t dst dst表示 s s s t t t的最短路径条数。
    • d s t ( v ) dst(v) dst(v)表示从 s s s到t的最短路径中经过节点 v v v的条数。

    Maksim Tsvetovat&Alexander Kouznetsov在《社会网络分析》一书中有两个例子:

    • 鲍勃徘徊在两个女人之间,他贪恋爱丽丝的美丽和谈吐,亦无法舍弃卡若琳娜的乐天和无忧无虑。但他必须小心谨慎,生怕自己在其中任何一个人面前露馅,这样的关系充满了压力和焦虑。
    • 银行家以5%的利率接受A公司的存款,以7%的利率贷款给B公司,这样的关系给银行家带来了巨大的利益。它的前提是,市场中的A公司和B公司不能直接接触,或至少无法轻易地找到对方。

    鲍勃和银行家的故事尽管截然不同,但他们都处于一种被称为被禁止的三元组(forbidden triad)的关系中,需要确保三元组的末端不能直接联系。没有联系就像网络中出现了一个洞,因此也被称为结构洞

    2.3 接近中心性(closeness centrality)

    点度中心性仅仅利用了网络的局部特征,即节点的连接数有多少,但一个人连接数多,并不代表他/她处于网络的核心位置。接近中心性和中介中心性一样,都利用了整个网络的特征,即一个节点在整个结构中所处的位置。如果节点到图中其它节点的最短距离都很小,那么它的接近中心性就很高。相比中介中心性,接近中心性更接近几何上的中心位置。

    接近中心性反应某一节点与其它节点之间的接近程度。

    假设我们要计算节点 D D D的接近中心性,首先我们计算从节点 D D D到所有其它节点的最短距离。从图中可以判断,节点 D D D到所有其它节点的距离均为1,距离之和为6。因此,节点 D D D的接近中心性为(7-1)/6=1。分子为网络中节点总数减去1。也就是说,如果一个人可以直接跟网络中所有其他人联系,那么他/她的接近中心性就是1。对于其它节点,如节点 A A A的接近中心性为(7-1)/9=0.667。

    接近中心性高的节点一般扮演的是八婆的角色(gossiper)。他们不一定是名人,但是乐于在不同的人群之间传递消息。

    cc(v)=\frac{n-1}{\sum_{v\neq u}{d_{vu}}}
    

    2.4 特征向量中心性(eigenvector centrality)

    特征向量中心性的基本思想是,一个节点的中心性是相邻节点中心性的函数。也就是说,与你连接的人越重要,你也就越重要

    特征向量中心性和点度中心性不同,一个点度中心性高,即拥有很多连接的节点,特征向量中心性不一定高,因为所有的连接者有可能特征向量中心性很低。同理,特征向量中心性高并不意味着它的点度中心性高,它拥有很少但很重要的连接者也可以拥有高特征向量中心性。

    考虑下面的图,以及相应的 5 × 5 5\times 5 5×5的邻接矩阵(Adjacency Matrix), A A A

    邻接矩阵的含义是,如果两个节点没有直接连接,记为0,否则记为1。

    现在考虑 x x x,一个 5 × 1 5\times 1 5×1的向量,向量的值对应图中的每个点。在这种情况下,我们计算的是每个点的点度中心性(degree centrality),即以点的连接数来衡量中心性的高低。

    矩阵 A A A乘以这个向量的结果是一个 5 × 1 5\times 1 5×1的向量:

    A x = [ 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 ] [ 3 2 3 3 1 ] = [ 8 6 8 7 3 ] Ax= \begin{bmatrix} 0&1&1&1&0\\ 1&0&1&0&0\\ 1&1&0&1&0\\ 1&0&1&0&1\\ 0&0&0&1&0\\ \end{bmatrix}\begin{bmatrix} 3\\ 2\\ 3\\ 3\\ 1\\ \end{bmatrix}=\begin{bmatrix} 8\\ 6\\ 8\\ 7\\ 3\\ \end{bmatrix} Ax=011101010011010101010001032331=86873

    结果向量的第一个元素是用矩阵 A A A的第一行去“获取”每一个与第一个点有连接的点的值(连接数,点度中心性),也就是第2个、第3个和第4个点的值,然后将它们加起来。

    我们继续用矩阵 A A A乘以结果向量。如何理解呢?实际上,我们允许这一中心性数值再次沿着图的边界“扩散”。我们会观察到两个方向上的扩散(点既给予也收获相邻节点)。我们猜测,这一过程最后会达到一个平衡,特定点收获的数量会和它给予相邻节点的数量取得平衡。既然我们仅仅是累加,数值会越来越大,但我们最终会到达一个点,各个节点在整体中的比例会保持稳定。

    我们认为,图中的点存在一个数值集合,对于它,用矩阵 A A A去乘不会改变向量各个数值的相对大小。也就是说,它的数值会变大,但乘以的是同一个因子。用数学符号表示就是:

    x ( t + 1 ) = c A x ( t ) x(t+1)=cAx(t) x(t+1)=cAx(t)

    A x = λ x Ax=\lambda x Ax=λx

    满足这一属性的向量就是矩阵 A A A的特征向量。特征向量的元素就是图中每个点的特征向量中心性。

    3. 克拉克哈特风筝社交网络分析

    绘制克拉克哈特风筝社交网络

    import networkx as nx
    import matplotlib.pyplot as plt
    
    G = nx.krackhardt_kite_graph()
    pos = nx.spring_layout(G)
    
    nx.draw(G, pos, with_labels=True)
    plt.show()
    

    显示图的基本信息

    print(nx.nodes(G))
    # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    
    print(nx.number_of_nodes(G))  # 10
    print(nx.edges(G))
    # [(0, 1), (0, 2), (0, 3), (0, 5), (1, 3), (1, 4),
    # (1, 6), (2, 3), (2, 5), (3, 4), (3, 5), (3, 6),
    # (4, 6), (5, 6), (5, 7), (6, 7), (7, 8), (8, 9)]
    
    print(nx.number_of_edges(G))  # 18
    print(nx.adjacency_matrix(G))
    # (0, 1) 1
    # (0, 2) 1
    # (0, 3) 1
    # (0, 5) 1
    # (1, 0) 1
    # (1, 3) 1
    # (1, 4) 1
    # (1, 6) 1
    # (2, 0) 1
    # (2, 3) 1
    # (2, 5) 1
    # (3, 0) 1
    # (3, 1) 1
    # (3, 2) 1
    # (3, 4) 1
    # (3, 5) 1
    # (3, 6) 1
    # (4, 1) 1
    # (4, 3) 1
    # (4, 6) 1
    # (5, 0) 1
    # (5, 2) 1
    # (5, 3) 1
    # (5, 6) 1
    # (5, 7) 1
    # (6, 1) 1
    # (6, 3) 1
    # (6, 4) 1
    # (6, 5) 1
    # (6, 7) 1
    # (7, 5) 1
    # (7, 6) 1
    # (7, 8) 1
    # (8, 7) 1
    # (8, 9) 1
    # (9, 8) 1
    
    A = nx.to_numpy_matrix(G)
    print(A)
    # [[0. 1. 1. 1. 0. 1. 0. 0. 0. 0.]
    #  [1. 0. 0. 1. 1. 0. 1. 0. 0. 0.]
    #  [1. 0. 0. 1. 0. 1. 0. 0. 0. 0.]
    #  [1. 1. 1. 0. 1. 1. 1. 0. 0. 0.]
    #  [0. 1. 0. 1. 0. 0. 1. 0. 0. 0.]
    #  [1. 0. 1. 1. 0. 0. 1. 1. 0. 0.]
    #  [0. 1. 0. 1. 1. 1. 0. 1. 0. 0.]
    #  [0. 0. 0. 0. 0. 1. 1. 0. 1. 0.]
    #  [0. 0. 0. 0. 0. 0. 0. 1. 0. 1.]
    #  [0. 0. 0. 0. 0. 0. 0. 0. 1. 0.]]
    
    dic = dict((x, list(nx.neighbors(G, x))) for x in nx.nodes(G))
    print(dic)
    # {0: [1, 2, 3, 5], 1: [0, 3, 4, 6], 2: [0, 3, 5], 
    # 3: [0, 1, 2, 4, 5, 6], 4: [1, 3, 6], 5: [0, 2, 3, 6, 7], 
    # 6: [1, 3, 4, 5, 7], 7: [5, 6, 8], 8: [7, 9], 9: [8]}
    

    中心性分析

    deg_cen = nx.degree_centrality(G)
    print(deg_cen)
    # {0: 0.4444444444444444, 1: 0.4444444444444444, 2: 0.3333333333333333, 
    # 3: 0.6666666666666666, 4: 0.3333333333333333, 5: 0.5555555555555556, 
    # 6: 0.5555555555555556, 7: 0.3333333333333333, 8: 0.2222222222222222, 
    # 9: 0.1111111111111111}
    
    bet_cen = nx.betweenness_centrality(G)
    print(bet_cen)  #
    # {0: 0.023148148148148143, 1: 0.023148148148148143, 2: 0.0,
    # 3: 0.10185185185185183, # 4: 0.0, 5: 0.23148148148148148, 6: 0.23148148148148148,
    # 7: 0.38888888888888884, 8: 0.2222222222222222, 9: 0.0}
    
    clo_cen = nx.closeness_centrality(G)
    print(clo_cen)
    # {0: 0.5294117647058824, 1: 0.5294117647058824, 2: 0.5,
    # 3: 0.6, 4: 0.5, 5: 0.6428571428571429, 6: 0.6428571428571429,
    # 7: 0.6, 8: 0.42857142857142855, 9: 0.3103448275862069}
    
    eig_cen = nx.eigenvector_centrality(G)
    print(eig_cen)
    # {0: 0.35220898139203594, 1: 0.35220898139203594, 2: 0.2858347353163241, 
    # 3: 0.4810204881221006, 4: 0.2858347353163241, 5: 0.3976910106255469, 
    # 6: 0.3976910106255469, 7: 0.19586185175360382, 8: 0.04807477501420294, 
    # 9: 0.011164058575824238}
    

    4. 总结

    • 点度中心性:一个人的社会关系越多,他/她就越重要。
    • 中介中心性:如果一个成员处于其他成员的多条最短路径上,那么该成员就是核心成员。
    • 接近中心性:一个人跟所有其他成员的距离越近,他/她就越重要。
    • 特征向量中心性:与你连接的人社会关系越多,你就越重要。

    参考文献:

    • https://blog.csdn.net/yyl424525/article/details/103108506
    • https://blog.csdn.net/ztf312/article/details/107711916
    • https://blog.csdn.net/teacherfbj/article/details/106165429
    展开全文
  • 展开全部加权平均值即抄将各数值乘以相应的袭权数,然后加总bai求和得到du总体值,再除以总zhi的...例子:假设以下是小明某科的考试成绩:平时测验:80分 期中考试:90分 期末考试:95 分学校规定的学科综合成绩的计...

    展开全部

    加权平均值即抄将各数值乘以相应的袭权数,然后加总bai求和得到du总体值,再除以总zhi的单位数。dao

    加权平均值的大小不仅取决于总体中各单位的数值(变量值)的大小,而且取决于各数值出现的次数(频数),由于各数值出现的次数对其在平均数中的影响起着权衡轻重的作用,因此叫做权数。

    例子:

    假设以下是小明某科的考试成绩:

    平时测验:80分 期中考试:90分 期末考试:95 分

    学校规定的学科综合成绩的计算方式是:

    平时测验占比:20% 期中考试占比: 30% 期末考试占比: 50%

    (注:在这里,每个成绩所占的比重叫做权重)

    那么,加权平均值(综合成绩)

    扩展资料:

    意义:

    权重是一个相对的概念,是针对某一指标而言。

    某一指标的权重是指该指标在整体评价中的相对重要程度。权重表示在评价过程中,是被评价对象的不同侧面的重要程度的定量分配,对各评价因子在总体评价中的作用进行区别对待。

    事实上,没有重点的评价就不算是客观的评价。

    应用:

    加权平均数中的“权”的表现形式有多种,且由于权的变化,其结果就会大相径庭,他的这一特殊性,越来越受到人们的重视,应用也越来越广泛。

    展开全文
  • 概率论中几个有趣的例子

    千次阅读 2020-12-24 11:48:31
    转载】概率论中几个有趣的例子[ 2007-6-3 13:06:00 | By: Byron ]推荐作者: ni1985 (妮子||从东方席地卷来一团野火), 原发新水木Mathematics已经酝酿很长时间的本文终于出场了。写本文的主要目的:1 很多人看了我...

    转载】概率论中几个有趣的例子

    [ 2007-6-3 13:06:00 | By: Byron ]

    推荐

    作者: ni1985 (妮子||从东方席地卷来一团野火), 原发新水木Mathematics

    已经酝酿很长时间的本文终于出场了。

    写本文的主要目的:1 很多人看了我前面大量的历史日志后,对我的数学水平产生了怀疑;2 有高中的校友师妹咨询关于大学数学学习的问题;3 概率论是数学中一个重要而美的分支,可惜多数同学尚没有机会看到其冰山一角。

    本文的读者适用范围:最低标准是学过工科专业的高等数学和概率论,最高标准不清楚(也许水平比我高的人就不屑于读了)

    当我跟皇上提到要写这篇文章的想法时,我提到:试图用比较短的篇幅让只要有初等概率论基础的人,也能看懂,从而对较深的概率论的研究对象和有趣的结论有一个初步的了解,激发其进一步深入学习概率论的兴趣。皇上说:那可不容易,相当于一个毕业设计了。我觉得,确实如此,本文是基本失败还是基本成功,还要看读者的评价。

    要想引入本文的内容,首先从数学美的定义说起。关于数学美,我比较欣赏的有两种观点,一是Birkhoff 的观点,数学美=逻辑的复杂程度/表述的复杂程度;二是Von Neumann的观点,数学的活力依赖于与它有联系的科学分支的多寡与分支的活力。也许做应用的人更喜欢后者,但我是比较喜欢前者的。因此,我下面的主要内容就是介绍一些概率论中的基本例子,这些例子的表述是相当简单的,但得到这些例子的手段却比较复杂。我将试图把每个例子表述清楚,让只要有初等概率论基础的读者就知道在说什么,但对得到这些结果的证明过程则一律省略,只简要提出涉及的基本工具,但其中有些比较简单的细节会给大家留为习题。这些例子一律来自伟大的Durrett 的著作:Probability theory and examples——我认为最优秀的概率论教材。

    例1. Coupon collector问题:X1,X2,…是独立同分布,均匀的取自集合{1,…,n}的随机变量序列。大家把集合{1,…,n}想象为若干张扑克牌,每次我们等概率的取一张扑克牌,取完放回。

    ,意思就是手中取过k 种不同的扑克牌所需的次数。T(n)

    =t(n,n)表示取过所有扑克牌所需的次数。X(n,k)=t(n,k)-t(n,k-1),则X(n,k)服从参数是1-(k-1)/n的几何分布(思考题!),它的期望和方差可求,且容易发现X(n,1),…,X(n,n)相互独立,从而可以求出E T(n),Var T(n)(习题!) 。且去证明

    依概率趋近于0. (数学基础稍微深一些的同学都知道,L2收敛蕴含依概率收敛)最终得到一个漂亮的结论:

    依概率收敛于1.

    数学基础比较少的同学可以直接看这一行,我把这一行的实际意义说清楚:就是假设我们要收集的邮票有n 张,而每次别人给我们提供的邮票恰恰是等概率的,那么要想把n 张收集全,需要的时间依概率趋近于 nlogn 。 所以大家就可以发现,为什么我们想集齐比较少的邮票要比集齐多的邮票容易的多。

    作为更为深层次的读者,我要说的是,在随机变量收敛性问题的研究中,独立性和矩总是常见的关注对象。为什么我们非常喜欢方差这个概念呢?我想一个重要的性质就是:对于独立的随机变量,方差对和有分配律。于是二阶中心矩才会成为最重要的矩。通过对矩的估计把随机变量的收敛性问题,转化为实数序列的收敛性问题,最后完全是数学分析的东西,这种手段是屡屡使用的。

    例2 非对称的简单随机游动问题:

    , 独立同分布,

    . , 对于数学基础不太好的同学,我简单介绍一下这个问题的背景,其实很好理解。设有一个点在0时刻位于实轴的原点0处,它在每个时刻以概率p 向右跳跃一个单位长度,以概率q 向左跳跃一个单位长度,且跳跃的方向与以前每次跳跃的情况是独立的。

    我们有如下非常精彩的结论: 表示的是:n 时刻这个点所在的位置。

    1 , 的直观意思就是,这个点首次跳到x 的位置的时刻。那么对于任意的

    这里函数

    上面的这个等式的直观意义:a 是负半轴上一点,b 是正半轴上一点,点没到b 之前先到a 的概率被计算了出来。

    得到这个结论最快的方法就是用鞅论。鞅实在是一个漂亮的东西,而它的漂亮之处就在于它与停时结合在一起后的巨大威力。用N 表示

    中的较小值,则N 是停时。首先要说明的是N 小于无穷大。要得到这个结论,我掌握的有三种方法:

    (1)通过EN 小于无穷大,得到这个结论,这事实上是通过一个强的多的结论说明的,具体见Durrett 书181页。

    (2)通过鞅收敛定理,见Durrett 书275页。其中用了一个重要结论:一致有界的鞅序列必然一致可积(应该是很显然的吧,呵呵)。

    (3)通过马氏链的性质:对于一个有可列状态,不可约的马氏链,用F 表示状态空间的一个有限子集,设初始状态属于F, 用T 表示链首次离开F 的时间,则一定有T 小于无穷大。(可以作为本科生三年级应用随机过程的习题,证之!) 2 即首次到达b 点的平均时间是

    处理方法还是用鞅论,这里不再多说。

    关于用鞅论解决马氏链问题的例子,我还推荐数学基础比较高的同学阅读Durrett 书上的(1)M/G/1排队(282页,298页,309页) (2)生灭过程(295页,301页)

    本来我认为这两个例子是更加漂亮的,但考虑到数学基础一般的同学的阅读水平,就不写了。 例3 遍历定理的一个应用(Benford 定律)

    首先提一个问题:随机选取一个正整数,它的第一位数字是1 的概率是多少?

    很多同学会武断的回答:1/9.

    可是你忘记了问我一个问题:你是如何随机选取的?

    也许你会说:这还用问?就是等概率的选取呗。

    可是不要忘记,对于可列状态的状态空间,不存在一个概率测度,使得它在任意两个单点集上的概率相同!(思考题!)

    其实一个直观的想法是:我们考虑前n 个正整数中(均匀分布是可能的),首位数字是1的概率记为f(n),然后把f(n)的极限作为我上面所提问题的答案。

    可是随后会不幸的发现,极限是不存在的!

    于是作为习题,设前n个正整数中,首位数字是1的概率记为

    是1/9,且对于任意属于区间[1/9,5/9]的实数a ,都存在

    前n 个正整数中,首位数字是2的概率是

    题!) , 则

    的上极限是5/9,下极限的子序列,它的极限就是a 。类似的,记, 其上极限是10/27,下极限是1/18.(作为数学分析的习

    但是,当我们转而思考这样的等比序列,1,2,4,8,16,…记这个序列的前n 项中首位数字是1的概率为

    , 则

    是有极限的,且极限是

    . 一般地,对于任意一个非10的整数次幂的正整数q ,

    , 则

    的极考虑以1为首项,以q 为公比的等比数列,它的前n 项中首位数字是k 的概率为

    限是

    . (证明不可能在这里给出了,大家只管从结论中去欣赏概率论之美吧!) 这个结论是非常漂亮的!叙述是非常简单的,意义是非常直观的,但并不是容易猜到的,证明所需的背景——遍历定理又是极其深刻的。读来畅快淋漓!

    今年春天,陈大岳教授(陈大岳教授的书目和学习指南)对我说,在现代概率论的研究中,遍历定理显现

    的越发重要。当看到上面这个结论后,我初步认识到遍历定理内涵的深刻和丰富。

    以上仅选取三个概率论的基本例子,它们的结论的直观易懂与其所需理论背景的负责程度形成了鲜明的对比,体现了概率论作为一个数学分支的美妙。管中窥豹,可见一斑,希望能以此激发大家深入学习概率论的兴趣,使不同数学基础的同学都能有所收获。

    展开全文
  • 它体量虽轻,却能让网络以去中心化的方式在网络中协调流动部署,并保证可访问。 Liquidity ads 解决了通过闪电网络来接收支付的一个常见问题:从何处以及如何获得入账流动(inbound liquidity)。 实际上,...
  • UA MATH563 概率论的数学基础 中心极限定理25 随机变量特征函数的连续定理 Continuity Theorem 假设{μn},μ\{\mu_n\},\mu{μn​},μ是概率测度,{ϕn},ϕ\{\phi_n\},\phi{ϕn​},ϕ是他们的特征函数: μn⇒μ\...
  • 摘要这一篇是关于重要抽样(importance sampling)的介绍, 包括他的背景知识, 相关的数学转换和最后的例子.简介重要抽样(importance sampling)是一种近似的抽样方法, 他通过一些小的数学上的变化, 使得可以对一些...
  • 微服务之注册中心

    2021-05-26 17:13:08
    在微服务架构下,主要有三种角色:服务提供者(RPC Server)、服务消费者(RPC Client)和服务注册中心(Registry),三者的交互关系请看下面这张图,我来简单解释一下。 RPC Server 提供服务,在启动时,根据...
  • 解决reno家族全局同步的策略就是概率随机丢弃,避免所有流同时md,然而bbr却没法从数学上证明这种策略是公平的,至少我是证明不了。。。 周六早上3,4点钟自然醒,写篇意识流。 了解TCP Reno/CUBIC的都应该知道...
  • UA MATH563 概率论的数学基础 中心极限定理2 sigma代数的独立与随机变量的独立 这一讲我们在测度论的level对独立进行定义。
  • 中心极限定理的Matlab演示实验要求用Matlab验证中心极限定理实验原理中心极限定理是概率论中的一组定理。中心极限定理说明,大量相互独立的随机变量,其均值的分布以正态分布为极限。这组定理是数理统计学和误差分析...
  • 图算法 图的算法有很多,这里主要介绍三种最基本的算法:路径发现算法、中心性算法、社区发现算法。之所以说是“最基本”,是因为一方面它们是很多高级算法的底层基础,另一方面它们是我们拿到一个图进行探索时首先...
  • 业务中台数据一致方案

    千次阅读 多人点赞 2021-10-10 16:40:21
    但是随着应用规模的扩大,原本在单体应用中不是问题的问题,在微服务架构中可能就是比较严重的问题,本文所要探讨的服务之间的数据一致便是其中最具代表的问题。本文将结合常见的电商下单场景来说明业务中台数据...
  • 在分布式场景中,ZooKeeper 的应用非常广泛,比如数据发布和订阅、命名服务、配置中心、注册中心、分布式锁等。 ZooKeeper 提供了一个类似文件系统的数据模型,和基于 Watcher 机制的分布式事件通知,这些特性都依赖...
  • 在网络层面,5G无疑为音视频开发提供了有力的支持,网络通信的延时越低、带宽越高,音视频的开发领域就越具有多样,我们之前提到过的AR/VR、超高清音视频都是明显的例子。 5G服务的大规模推出恰逢实时视频流...
  • ​​​​​​摘要:其实对于节能,...国际惯例,先介(bai)绍(du)一(bai)下(ke)“数据中心”:数据中心是全球协作的特定设备网络,用来在 internet 网络基础设施上传递、加速、展示、计算、存储数据信息。一个
  • Dubbo是一个在国内比较流行的分布式框架,被大量的中小型互联网公司所采用,Dubbo是一个非常实用的框架,提供了比较完善的服务治理功能,而服务治理的实现主要依靠的就是注册中心。1 什么是注册中心注册中心可以说是...
  • 新版白话空间统计(22):中心要素

    千次阅读 2021-11-10 17:38:15
    同样,在空间统计中,也有很多这样的具有代表的概念,比如今天我们要说“中心要素”。 在经典统计学中,中位数表示从它开始,可以将整份数据分成上下两个部分,关键是这个数不能是被计算出来的,而是数据中的一个...
  • 我们先来看一个例子,以便理解为什么分布式架构中需要有注册中心。案例小明和小新住在同一家沃尔玛超市附近,他俩都办了会员,经常关注超市的一些优惠活动,元宵节快到了,沃尔玛准备搞一个元宵节特惠活动,需要通知...
  • 中心极限定理的解释和关键假设

    千次阅读 2021-08-11 09:04:56
    它还将帮助您更好地理解它的重要以及使用时的关键假设。 简单解释 中心极限定理指出,只要样本量足够大,任何分布的均值的抽样分布将是正态的。 让我们用一个更具体的例子将上面的定义与更简单的词分开。 假设有...
  • 数据中心概述【12】

    2021-03-19 15:44:47
    文章目录数据中心历史数据中心演进数据中心发展雏形-ENIAC数据中心虚拟化技术商业化-TRADICC/S结构计算模型与互联网模块化数据中心出现云数据中心数据中心基本组成模块数据中心说明数据中心分类数据中心的组成数据...
  • 服务注册中心是服务实现服务化管理的核心组件,类似于目录服务的作用,主要用来存储服务信息,譬如提供者 url 串、路由信息等。服务注册中心是微服务架构中最基础的设施之一。注册中心可以说是微服务架构中的...
  • TiDB 5.0 发布在即,在这个大版本更新中提升 TiDB 集群的跨中心部署能力是我们重要的一个着力点。其中,新的分布式本地事务能力及其对应的授时服务改造是基础且又重要的一环。本文将会从 TiDB 现有的授时服务出发,...
  • R语言:描述分析

    千次阅读 2021-07-29 15:57:37
    R语言:描述分析 (一)R内置的分布 (二)集中趋势的分析 实例:2007.01-2012.09时间段中国人寿股票价格 (三)离散趋势的分析 (四)数据的分布分析 (五)图形分析及R实现 1.直方图和密度函数图 2.QQ图 3.茎叶...
  • Nacos 注册中心的设计原理详解

    千次阅读 2021-03-23 17:06:55
    图 5 Nacos 一致协议 负载均衡 负载均衡严格的来说,并不算是传统注册中心的功能。一般来说服务发现的完整流程应该是先从注册中心获取到服务的实例列表,然后再根据自身的需求,来选择其中的部分实例或者按照一定...
  • 缺点不明显:转换器一般要求与业务数据无关,因此通用强,应最大可能的复用 下面示例二将帮你解决通过复用已有能力方式达到Person -> String的目的。 示例二:使用Printer,有中间转换 基于示例一,若要实现Person...
  • 对比学习 kafka 的内部逻辑结构、集群原理、一致实现以及重平衡协议
  • 但是英伟达现在有一项非常坑爹的政策,如果在数据中心使用CUDA,那么只允许使用Tesla GPU而不能用GTX或RTX GPU。 由于担心法律问题,研究机构和大学经常被迫购买低价比的Tesla GPU。然而,Tesla与GTX和RTX相比并...
  • 双线内插值算法

    2021-08-01 15:20:04
      在图像的仿射变换中,很多地方需要用到插值运算,常见的插值运算包括最邻近插值,双线插值,双三次插值,兰索思插值等方法,OpenCV提供了很多方法,其中,双线插值由于折中的插值效果和运算速度,运用比较...
  • 是选择停止可用达到强一致还是保留可用选择最终一致。通常选择后者。 其中 zookeeper 和 eureka分别是注册中心CP AP 的两种的实践。他们都提供服务注册中心的功能。建议使用AP。不强求数据的强一致,达成...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 203,375
精华内容 81,350
关键字:

中心性的例子