精华内容
下载资源
问答
  • 图上的广义K均值是一种利用诸如PageRank,谐波中心度等中心性度量的方法,在有向图和无向图上获得类似k均值的聚类算法。 该算法是可生成的,适用于图形,网格,点云甚至度量空间。 该算法的详细信息在论文中进行了...
  • 文章目录点度中心性(degree centrality)中介中心性(betweenness centrality)接近中心性(closeness centrality)特征向量中心性(eigenvector centrality)有向图与PageRank小结 网络由节点(node)和连接它们...

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

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

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

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

    点度中心性(degree centrality)

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

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

    图1:使用networkx绘制的蝴蝶结网络

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

    中介中心性(betweenness centrality)

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

    计算网络中任意两个节点的所有最短路径,如果这些最短路径中很多条都经过了某个节点,那么就认为这个节点的中介中心性高。回到上面的蝴蝶结网络,假设我们要计算节点D的中介中心性。

    首先,我们计算节点D之外,所有节点对之间的最短路径有多少条,这里是15条(在6个节点中选择两个节点即节点对的个数)。
    然后,我们再看所有这些最短路径中有多少条经过节点D,例如节点A要想找到节点E,必须经过节点D。经过节点D的最短路径有9条。
    最后,我们用经过节点D的最短路径除以所有节点对的最短路径总数,这个比率就是节点D的中介中心性。节点D的中介中心性是9/15=0.6。

    如果说点度中心性发现的是网络中的“名人”,那么中介中心性的现实意义是什么呢?

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

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

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

    当网络中众多成员的接触或低成本接触都依赖我时,我就对其他成员有了控制和制约作用。我可以利用这种关系控制信息的流动,套取巨大的利益。当然,这样的关系也充满着压力和紧张。诚如Maksim Tsvetovat&Alexander Kouznetsov所言,商人的成功,不仅取决于他们对不对称信息的利用和经营能力,也需要对创造和维持套利机会带来的压力的高度容忍。

    接近中心性(closeness centrality)

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

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

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

    特征向量中心性(eigenvector centrality)

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

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

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

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

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

    矩阵A乘以这个向量的结果是一个5x1的向量:

    A×x=(11101100111010110001)(32331)=(0×3+1×2+1×3+1×3+0×11×3+0×2+1×3+0×3+0×11×3+1×2+0×3+1×3+0×11×3+0×2+1×3+0×3+1×10×3+0×2+1×3+0×3+0×1)=[86873] \mathbf{A} \times \mathbf{x}=\left(\begin{array}{cccc}{-1} & {1} & {1} & {0} \\ {1} & {-1} & {0} & {0} \\ {1} & {1} & {-1} & {0} \\ {1} & {0} & {1} & {-1} \\ {0} & {0} & {0} & {1}\end{array}\right)\left(\begin{array}{l}{3} \\ {2} \\ {3} \\ {3} \\ {1}\end{array}\right)=\left(\begin{array}{c}{0 \times 3+1 \times 2+1 \times 3+1 \times 3+0 \times 1} \\ {1 \times 3+0 \times 2+1 \times 3+0 \times 3+0 \times 1} \\ {1 \times 3+1 \times 2+0 \times 3+1 \times 3+0 \times 1} \\ {1 \times 3+0 \times 2+1 \times 3+0 \times 3+1 \times 1} \\ {0 \times 3+0 \times 2+1 \times 3+0 \times 3+0 \times 1}\end{array}\right)=\left[\begin{array}{c}{8} \\ {6} \\{8} \\ {7} \\ {3}\end{array}\right]
    结果向量的第一个元素是用矩阵A的第一行去“获取”每一个与第一个点有连接的点的值(连接数,点度中心性),也就是第2个、第3个和第4个点的值,然后将它们加起来。

    换句话说,邻接矩阵做的事情是将相邻节点的求和值重新分配给每个点。这样做的结果就是“扩散了”点度中心性。你的朋友的朋友越多,你的特征向量中心性就越高。

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

    现在把所有点的数值构成的向量用更一般的形式表示:

    [11101100111010110001][x1x2x3x4x5]=[0x1+1x2+1x3+1x4+0x51x1+0x2+1x3+0x4+0x51x1+1x2+0x3+1x4+0x51x1+0x2+1x3+0x4+1x50x1+0x2+0x3+1x4+0x5] \left[\begin{array}{ccccc}{-} & {1} & {1} & {1} & {0} \\ {1} & {-} & {1} & {0} & {0} \\ {1} & {1} & {-} & {1} & {0} \\ {1} & {0} & {1} & {-} & {1} \\ {0} & {0} & {0} & {1} & {-}\end{array}\right]\left[\begin{array}{l}{x_{1}} \\ {x_{2}} \\ {x_{3}} \\ {x_{4}} \\ {x_{5}}\end{array}\right]=\left[\begin{array}{c}{0 \cdot x_{1}+1 \cdot x_{2}+1 \cdot x_{3}+1 \cdot x_{4}+0 \cdot x_{5}} \\ {1 \cdot x_{1}+0 \cdot x_{2}+1 \cdot x_{3}+0 \cdot x_{4}+0 \cdot x_{5}} \\ {1 \cdot x_{1}+1 \cdot x_{2}+0 \cdot x_{3}+1 \cdot x_{4}+0 \cdot x_{5}} \\ {1 \cdot x_{1}+0 \cdot x_{2}+1 \cdot x_{3}+0 \cdot x_{4}+1 \cdot x_{5}} \\ {0 \cdot x_{1}+0 \cdot x_{2}+0 \cdot x_{3}+1 \cdot x_{4}+0 \cdot x_{5}}\end{array}\right]
    我们认为,图中的点存在一个数值集合,对于它,用矩阵A去乘不会改变向量各个数值的相对大小。也就是说,它的数值会变大,但乘以的是同一个因子。用数学符号表示就是:

    Mx=λx \mathbf{M} \mathbf{x}=\lambda \mathbf{x}

    M×(x1x2xn)=(λx1λx2λxn) \mathbf{M} \times\left(\begin{array}{c}{x_{1}} \\ {x_{2}} \\ {\cdots} \\ {x_{n}}\end{array}\right)=\left(\begin{array}{c}{\lambda x_{1}} \\ {\lambda x_{2}} \\ {\cdots} \\ {\lambda x_{n}}\end{array}\right)
    满足这一属性的向量就是矩阵M的特征向量。特征向量的元素就是图中每个点的特征向量中心性。

    特征向量中心性的计算需要读者具备矩阵乘法和特征向量的知识,但不影响这里读者对特征向量中心性思想的理解,不再赘述。

    有向图与PageRank

    PageRank是衡量有向网络中节点重要性的指标。

    我们将万维网抽象成有向图:(1)每个网页抽象成一个节点,假设有A、B、C、D四个节点;(2)用户通过超链接在网页之间跳转,这种跳转是有方向的(directed),从网页A跳转到网页B不代表可以从网页B链接到网页A,这种节点之间的有方向的连接被抽象成有方向的边。整个网络构成一个有向图。

    你可以很轻易地找到最受欢迎的网页。但是,PageRank的思想认为,指标最好还需要考虑到指向你的那些网页。也就是说,来自受欢迎的网页的跳转应该重于不太受欢迎的网页的跳转。这就是PageRank思想的精华,Google就是利用这一思想来给网站排名的。这里的思想依据和特征向量中心性其实是一致的。

    首先,我们假设用户停留在一个页面时,跳转到每个链接页面的概率是相同的。例如,用户停留在页面A,他可以跳转到B、C、D三个页面,我们假设用户跳转到每个页面的概率相同,也就是说用户跳转到每个页面的概率均为1/3。我们可以用下面的转移矩阵(Transition Matrix)来表示整个有向图的情况:

    M=[01/201/21/3001/21/31/2001/3010] M=\left[\begin{array}{cccc}{0} & {1 / 2} & {0} & {1 / 2} \\ {1 / 3} & {0} & {0} & {1 / 2} \\ {1 / 3} & {1 / 2} & {0} & {0} \\ {1 / 3} & {0} & {1} & {0}\end{array}\right]

    假设有向图中有n个节点,那么M就是一个n行n列的矩阵,其中的第i行第j列代表从页面j跳转到页面i的概率。例如,M矩阵的第一行代表从ABCD跳转到页面A的概率。

    然后,我们设每个页面的初始rank为1/4,4个页面的初始rank构成向量v:

    v=[1/41/41/41/4] v=\left[\begin{array}{c}{1 / 4} \\ {1 / 4} \\ {1 / 4} \\ {1 / 4}\end{array}\right]
    用M第一行乘以向量v,得到的就是页面A最新rank的合理估计:01/4+1/21/4+01/4+1/21/4=1/40*1/4+1/2*1/4+0*1/4+1/2*1/4=1/4。Mv的结果就是ABCD四个页面的新rank:

    Mv=[1/45/245/241/3] M v=\left[\begin{array}{c}{1 / 4} \\ {5 / 24} \\ {5 / 24} \\ {1 / 3}\end{array}\right]
    然后用M再乘以新的rank向量,又会产生一个新的rank向量。迭代这一过程,Mv结果各个值的相对大小会保持稳定。也就是说,其结果等于用一个标量乘以v。

    满足这一属性的向量就是矩阵M的特征向量。这里的结果会收敛在[1/4, 1/4, 1/5, 1/4],这就是A、B、C、D最后的PageRank。这一结果表明,相比于网页C, ABD更为重要。

    上述方程式假设上网者一定是通过网页上的链接进行跳转的,但实际上,上网者在每一步都有可能在地址栏随机输入一个网址,跳转到其他页面,而不是点击网页上的链接。或者,上网者可能到达一个没有任何链出页面的网页,这时他会随机到另外的页面进行浏览。

    想象有两个网页的简单例子,网页A链接到B,但B无法链接到A。转移矩阵如下:

    M=[0010] M=\left[\begin{array}{ll}{0} & {0} \\ {1} & {0}\end{array}\right]
    不断迭代,最后我们得到的是一个0矩阵:

    Mv=[0010][1212]=[012] M v=\left[\begin{array}{ll}{0} & {0} \\ {1} & {0}\end{array}\right]\left[\begin{array}{l}{\frac{1}{2}} \\ {\frac{1}{2}}\end{array}\right]=\left[\begin{array}{l}{0} \\ {\frac{1}{2}}\end{array}\right]
    考虑到B比A重要,这一结果是不合理的,它认为A和B同等重要。为了解决这个问题,我们引入 “心灵运输”(Teleportation) 的概念。它意味着上网者每一步都有可能随机输入一个网址(心灵运输),跳转到其他页面(这意味着每一步,网络上的每个网页都有一定的概率被访问到,它的概率为(1-d)/N,即上网者心灵运输的概率乘以每个网页被访问的概率),而不是点击网页上的链接。

    我们假设上网者在任何页面继续向下浏览的概率为d=0.85。d也被称为阻尼系数(damping factor)。1-d=0.15就是上网者停止点击,随机跳到新网址的概率,即心灵运输的概率。设网页总数为N,那么跳转到任一网页的概率为N。因此,调整后的方程式如下:

    v=dMv+e1dN v^{\prime}=d M v+e \frac{1-d}{N}
    其中的e为单位矩阵,这样才能与方程式的前半部分相加。

    v=0.8×[0010][1212]+0.2×[1212]=[11012] v^{\prime}=0.8 \times\left[\begin{array}{ll}{0} & {0} \\ {1} & {0}\end{array}\right]\left[\begin{array}{l}{\frac{1}{2}} \\ {\frac{1}{2}}\end{array}\right]+0.2 \times\left[\begin{array}{l}{\frac{1}{2}} \\ {\frac{1}{2}}\end{array}\right]=\left[\begin{array}{c}{\frac{1}{10}} \\ {\frac{1}{2}}\end{array}\right]
    不断迭代后,两个网页的rank会收敛为:

    [11012]0.10.18][0.350.64] \left.\left[\begin{array}{c}{\frac{1}{10}} \\ {\frac{1}{2}}\end{array}\right] \begin{array}{l}{0.1} \\ {0.18}\end{array}\right] \cdots \left[\begin{array}{l}{0.35} \\ {0.64}\end{array}\right]

    小结

    • 点度中心性:一个人的社会关系越多,他/她就越重要
    • 中介中心性:如果一个成员处于其他成员的多条最短路径上,那么该成员就是核心成员
    • 接近中心性:一个人跟所有其他成员的距离越近,他/她就越重要
    • 特征向量中心性:与你连接的人社会关系越多,你就越重要
    • PageRank:来自受欢迎的网页的跳转应该重于不太受欢迎的网页的跳转
    展开全文
  • 设计一个算法求图的中心点,设v是有向图G的一个顶点,把v的偏心定义为Max{从w到v最短距离|w属于V(G)}如果v是有向图中最小偏心的顶点,则称顶点v是G的中心
  • R和中心度、中心势

    2018-10-31 13:54:00
    最近用R画论文里的弦图,恰好借的书里着重写了中心度等问题...有向图内点度中心度=点入度,即直接指向该店的点的总数 有向图外点度中心度=点出度,该点所直接指向的点的总数 绝对法的问题在于无法衡量不等规模的...

    最近用R画论文里的弦图,恰好借的书里着重写了中心度等问题。

    网上流行一套密歇根大学社交计算的教程。但是前两年看了好几遍总是搞不清,即便是记公式也是收效不大。不妨按照书上总结一下。

    绝对法:

    无向图点度中心度=点度数,即与该点相连的点的度数

    有向图内点度中心度=点入度,即直接指向该店的点的总数

    有向图外点度中心度=点出度,该点所直接指向的点的总数

     

    绝对法的问题在于无法衡量不等规模的图。因此使用相对法:

    无向图点度中心度:点度数/(n-1)

    有向图内点度中心度:点入度/(n-1)

    有向图外点度中心度:点出度/(n-1)

    此外还有接近中心度、中间中心度两种中心度的定义。由中心度又可以推导出中心势。首先计算出网络中的最大中心度数值,然后计算出最大中心度和其他任何点中心度的差值。最后用该总和除以各个差值总和的最大可能值。

    转载于:https://www.cnblogs.com/ubiwind/p/9882602.html

    展开全文
  • SNA(社会网络分析)——三种中心度总结

    万次阅读 多人点赞 2017-11-11 16:35:41
    度中心度表示与该点直接相连的点的个数,无向图为(n-1),有向图为(入度,出度)。分为绝对和相对。 点度中心势表示网络图的整体中心性。体现整体网的集中程度。星形网络图核心点点度中心度为n-1,其余点为1,...

    一 简介

           社会网络分析中,中心度表示点的中心度,中心势表示整个网络的中心度(趋势)。中心度常用的有三种,点度中心度、中间中心度和接近中心度。

    二 三种中心度

    点度中心度表示与该点直接相连的点的个数,无向图为(n-1),有向图为(入度,出度)。分为绝对和相对。

    点度中心势表示网络图的整体中心性。体现整体网的集中程度。星形网络图核心点点度中心度为n-1,其余点为1,中心势为1;完备图每个点中心度都是n-1,中心势为0。

    中间中心度表示该点的“中间人”程度,即媒介程度。分为相对和绝对。计算方法为其他任何两点的测地线,以及过该点的测地线数目之比。(测地线表示两点之间的最短距离)

    中间中心势表示整个网的中间性。星形网的中间中心势为1,环形网的中间中心势为0。星形网核心点可以控制其他所有点的交往,中间中心度最大。而其余点在网的边缘,无法控制其他点的交往,故中间中心度为0。

    接近中心度表示一种对不受他人控制的测度。通俗讲就是一个点和所有其他点的接近性程度。分为绝对和相对。计算方法是该点与其他所有点的测地线距离之和。(绝对)

    接近中心势表示整体网的接近集中趋势。同点度中心势类似,星形网接近中心势为1,环形和完备图接近中心势为0。

    三 计算公式汇总

      度数中心性 中间中心性 接近中心性
    绝对点度中心度
    相对点度中心度(标准化)
    图的中心势

    注:以上公式都是针对无向图,如果是有向图则根据定义相应修改公式即可

    四 算法实现

           这几个中心度的计算中,点度中心度最为简单,就是邻接矩阵的行和列代表出度和入度,然后对每个元素进行计算即可。比较难的是中间中心度和接近中心度,因为涉及测地线的计算。我稍微找了一下网上关于这方面的算法,没有找到,所以就自己想了一下,觉得想出解决方法了。首先我们要知道一个知识点,就是“矩阵之积”在SNA中的含义。

           在SNA中,矩阵的乘法是非常重要的。它可以用来研究图中“途径”的个数。简单来说,邻接矩阵一次方(即邻接矩阵本身)表示一个行动者到另一个行动者之间存在多少条距离为1的途径;同理,邻接矩阵的平方表示。。到。。存在多少条距离为2的途径,以此类推。那么,当一个矩阵的某一个行动者到另一个行动者的途径,第一次由0突变为非0时,就是这两个行动者的“距离”(最短距离,即测地线)的产生!

           那么我们就可以先实现接近中心度的算法:简单描述为计算邻接矩阵的乘积(对角线初始为0,因为一个点到它本身不存在一条距离为1的途径),记录下每次乘后的矩阵以及乘前的矩阵,进行每个元素的比较,如果由0->非0,则在测地线长度矩阵中保存对应位置的值为邻接矩阵的次数,如二次方就记为2,三次方就记为3,表示该位置的两个点的测地线长度为2或3。同时,还要在测地线条数矩阵中保存测地线的条数(求中间中心度需要用到)。直到测地线矩阵中所有的值都求出后停止矩阵相乘。

           利用测地线长度矩阵,我们可以求出绝对接近中心度,即矩阵每一行进行求和,相对中心度和中心势按公式也好求。

           那么如何求中间中心性?这个算法的主要问题就是如何求每条测地线途经的点!我们又没必要使用最短路径算法来计算这样一个有规律的图,而且最短路径算法计算量大,最重要的是这个算法最终给出的是一条路径,如果测地线有多条,那就无法解决这个问题。

           那么问题如何解决?我们可以使用测地线条数矩阵和邻接矩阵来实现!描述如下:遍历测地线条数矩阵,对于每一个点首先可以得到中心度的分母,即测地线的条数。然后以测地线的长度为循环次数,对邻接矩阵进行以下操作:从起点开始,列出为相邻的节点,并保存到向量中,此为一次循环,接下来以相邻节点为起点,继续列出相邻节点,存入向量中,此为二次循环,直到循环结束。循环过程中,如果回到循环的点,则不存入向量,起点本身也排除。这样本质就是列出了所有途径的树。至于这个树怎么实现,我自己想了一个,到时候再发个帖子。感兴趣的朋友可以关注一下。

           这样我们根据树的层数判断距离然后从终点反推到起点,得到路径判断是否经过判断节点即可。统计经过判断节点的数量,就是中间中心度的分子。这样三个中间性指标都可以求出。

           以上是自己今天学习的一些总结和想法,供各位参考。如有错误,请指正!谢谢。

           转载请注明本贴网址!

    展开全文
  • 通过生成矩阵实现度的计算度中心性计算,注意:有向图度中心性合并计算(入度+入度)/(节点总数-1) 关键是找好节点与位置的对应关系!同时考虑好矩阵一行的计算M[1]与一列M[:,1]的写法 import networkx as nx ...

    通过生成矩阵实现度的计算度中心性计算,注意:有向图的度中心性合并计算(入度+入度)/(节点总数-1)

    关键是找好节点与位置的对应关系!同时考虑好矩阵一行的计算M[1]与一列M[:,1]的写法

    import networkx as nx
    import numpy as np
    from  matplotlib import pyplot as plt
    def nodedegree(G):   #计算有向图出度中心性及无向图的度中心性
        N = list(G.nodes())
        M = nx.to_numpy_matrix(G, nodelist=N)    #计算矩阵行:np.sum(M[1])与列:np.sum(M[:,1])
        d={}
        for i in N:
            t=N.index(i)   #返回节点i在列表中的位置,对应矩阵中元素
            d[i]=(np.sum(M[t]))/(len(N)-1)        #度中心性计算方法是度除节点数-1
        return d
    
    
    if __name__ == "__main__":
        G=nx.DiGraph()
        with open('E:\\kt\\kkkk.txt') as f:  #数据集根据位置取
            # n, m = f.readline().split()
            for line in f:
                u, v = map(int, line.split())
                try:
                    G[u][v]['weight'] += 1
                except:
                    G.add_edge(u,v, weight=1)
        print(nodedegree(G))
        # pos = nx.spring_layout(G)  # 此语句可以不要,图形固定,否则会变化
        # nx.draw(G, pos, node_color='r', node_size=400, with_labels=True, alpha=0.9)
        # plt.show(G)
    

    数据集样式
    1 2
    1 3
    1 4
    2 4
    3 9
    4 9
    2 9
    9 1

    展开全文
  • 节点中心度MATLAB实现

    2018-07-24 09:00:59
    节点是指和该节点相关联的边的条数,又称关联。 特别地,对于有向图, 节点的入度 是指进入该节点的边的条数; 节点的出度是指从该节点出发的边的条数。
  • 1. Centrality 1).度中心性 在社会网络中,对于具有更多连接关系的结点,度中心性度量方法认为他们具有...在有向图中,既可以利用入度或者初度,也可以将2者相结合起来作为度中心性值: Cd(vi) = diin(声望) Cd(...
  • CSS高度和宽度

    2020-03-23 17:24:50
    CSS假定每个元素都会生成一个或多个矩形框,这称为元素框,各元素框中心有一个内容区。内容区周围可选的内边距、边框和外边距。如下: 注:1. 元素背景显示的区域是 内容区+内边距 ** 2. 边框和内边距的宽度不...
  • 中心性(centrality)

    2020-11-24 00:32:14
    参考资料 《社会媒体挖掘》 中心性(centrality)用来度量结点在网络中的重要性。对于单个结点或由多个结点组成的群体都可以定义中心性。...针对有向图中心性既可以是入度(视为声望)Cd(vi)=di
  • 略去简单的概念,如:有向图与无向图,节点,边,加权图,无向图的度,有向图的入度、出度,各种中心度等 重点总结较难的概念: 图的连通分量: 图片来自《算法导论》 该无向图有三个连通分量 如果一个无向图只有一...
  • 角度说明:在全景图中心点的位置为0,右至最右边是180°,左最左边是-180° 如疑问或需帮助,可与我联系Q168387321 my web: www.flashme.cn 声明:文件内360全景图片仅仅为演示文件,不可挪做其它样板间使用...
  • 一个圆的角度为360,首先计算饼状中的对象多少个,每个对象所占有的角度多少,设定饼状外接圆的半径,外接圆的圆心位置; 根据每一个角度和半径,获取东西、南北的移动距离,使用的函数为半径*sin...
  • 2) 首先偏移Z轴(屏幕方向一个固定距离),然后绕原来中心点旋转一个角度,这里8张图,每张递增45 3) 新建另外一个层,存放两个按钮 3.图片360旋转: 1) 在CS文件中新建一个StoryBorad对象,创8幅顺时针...
  • 心性的计算 临近节点(Neighbourhood) 集中系数(Clustering Coefficient):节点的集中系数 == 其临近的节点中边相连的节点数/...度中心性(Degree Centrality):计算一个节点的边数,度中心性关注单个节点。...
  • QT 绘图函数

    2012-12-21 17:16:03
    Qt中每一个窗口都一个坐标系,默认的,窗口左上角为坐标原点,然后水平右依次增大,水平左依次减小,垂直下依次增大,垂直向上依次减小。原点即为(0,0)点,然后以像素为单位增减。 例如: void Dialog::...
  • 题意: 给出n个结点的简单无向图,每个点的度数均为3。...一个鸡爪当中,一个中心点,即为3的点,还有3个边缘点。 每条边都连接了一个中心点和一个边缘点,于是就是二分图判定。 1 #include<i...
  • 选择海报层,按CTRL+T,调出变形框,选择扭曲命令,将变形框右下角的控点页面中心拖拽。海报会出现相应的扭曲效果。直到你觉得合适,确定变形(15)。这种方法,虽然不是很精确,但已能满足一般要求的图像。 ...
  • 做的不是很好希望大家多多交流,问题的可以提出。 下面上传效果 上面的菜单键变化为两种,一种是拖动的转变,还有就是点击的转变。 下面看一下分析 1.由菜单键到返回键转变,以180为周期。旋转中心...
  • 这个城市可以抽象成一张 n 个节点,节点之间 m 条双向道路连接的无向图,每条道路的⻓都为 1 。 经过侦查,C 国情报部部⻓ GGB 惊讶地发现,这座看起来不起眼的城市竟然是 D 国的军事中心。因此 GGB 决定在这...
  • 这个城市可以抽象成一张 n 个节点,节点之间 m 条双向道路连接的无向图,每条道路的⻓都为 1 。 经过侦查,C 国情报部部⻓ GGB 惊讶地发现,这座看起来不起眼的城市竟然是 D 国的军事中心。因此 GGB 决定在这...
  • 这个城市可以抽象成一张n(n≤1000)个节点,节点之间m条双向道路连接的无向图,每条道路的⻓都为1。 经过侦查,C国情报部部⻓GGB惊讶地发现,这座看起来不起眼的城市竟然是D国的军事 中心。因此GGB决定在这个...
  • 第五章 中心性——权力的量化分析 ...有向图中某点的相对点度中心度:该点的入度和出度和/(图中点总数-1)的2倍 如果计算得到某点的的相对点度中心度为0,该点是孤点,如果是1,该点是核心点。 以上仅仅是通...
  • Time Limits: 1500 ms Memory Limits: 262144 ...这个城市可以抽象成一张 n 个节点,节点之间 m 条双向道路连接的无向图,每条道路的⻓都为 1 。 经过侦查,C 国情报部部⻓ GGB 惊讶地发现,这座看起来不起眼...
  • 正如“世界*佳高层建筑奖”颁奖词所言:“‘上海中心’不仅成为上海的*新象征,世界展示现代化大都市形象,也为建筑科技创新与文化身份认同相结合指出了新方向。”   目  录:   前言 解码中国建筑新高度 ...
  • 12、企业和个人管理中心和前台找工作、找简历等功能分离,提高用户体验; 13、个人注册提供邮箱、手机和用户名等三种注册途径; 14、采集功能新增对智联的企业和职位采集; 15、新增微信接口,申请微信公共服务...

空空如也

空空如也

1 2 3 4 5 ... 15
收藏数 297
精华内容 118
关键字:

有向图度中心度