紧密中心性 - CSDN
精华内容
参与话题
  • 紧密中心性(closeness centrality)

    万次阅读 2017-04-16 14:43:49
    closeness centrality:某个节点到达其他节点的难易程度,也就是到其他所有结点距离的平均值的倒数。 公式: 例题及实现 : from igraph import Graph as IGraph ...for line in f.readlines():

    closeness centrality:某个节点到达其他节点的难易程度,也就是到其他所有结点距离的平均值的倒数。

    公式:


    例题及实现 :


    from igraph import Graph as IGraph
    
    f = open('/Users/tangweize/Desktop/net.data')
    edges = []
    for line in f.readlines():
       u, v = [i for i in line.strip().split(',')]
       edges.append((u, v))
    
    print(edges)
    ''''[('1', '2'), ('1', '3'), ('2', '3'), ('3', '7'), ('4', '5'), ('4', '6'), ('5', '6'),
    ('6', '7'), ('7', '8'), ('8', '9'), ('9', '10'), ('9', '11'), 
    ('10', '11'), ('8', '12'), ('12', '13'), ('12', '14'), ('13', '14')]'''
    
    f.close()
    g = IGraph.TupleList(edges, directed=False, vertex_name_attr='name')
    
    path = g.get_shortest_paths("7")
    names = g.vs['name']
    
    cc = 0;
    for p in path:
        cc += len(p) + 1
    
    print("closeness centrality = ", (len(path)-1)/float(cc))


    
    

    
    

    或者直接调用igraph里面的closeness

    from igraph import Graph as IGraph
    
    f = open('/Users/tangweize/Desktop/net.data')
    edges = []
    for line in f.readlines():
       u, v = [i for i in line.strip().split(',')]
       edges.append((u, v))
    
    print(edges)
    ''''[('1', '2'), ('1', '3'), ('2', '3'), ('3', '7'), ('4', '5'), ('4', '6'), ('5', '6'),
    ('6', '7'), ('7', '8'), ('8', '9'), ('9', '10'), ('9', '11'),
    ('10', '11'), ('8', '12'), ('12', '13'), ('12', '14'), ('13', '14')]'''
    
    f.close()
    g = IGraph.TupleList(edges, directed=False, vertex_name_attr='name')
    
    ccvs = []
    for p in zip(g.vs, g.closeness()):
        ccvs.append({"name" :p[0]["name"], "cc":p[1]})
    
    sorted(ccvs, lambda k:k["cc"], reversed = True)[:10]
    
    
    
    
    
    
    
    
    
    






    展开全文
  • 《图算法》第五章 中心性算法-2

    千次阅读 2019-08-28 17:15:52
    紧密性中心性是一种检测节点通过子图传播信息有效性的方法。该方法度量是节点与所有其他节点的距离近的程度。高紧密中心性的节点与所有其他节点的距离最短。 在所有节点对的最短路径计算的基础上,紧密中心性算法,...

    紧密中心性(Closeness Centrality)

    紧密性中心性是一种检测节点通过子图传播信息有效性的方法。该方法度量是节点与所有其他节点的距离近的程度。高紧密中心性的节点与所有其他节点的距离最短。

    在所有节点对的最短路径计算的基础上,紧密中心性算法,计算一个节点到所有其他节点的距离之和。然后将得到的和求倒数,以确定该节点的紧密性中心性得分。节点的紧密中心性用以下的公式来计算:
    在这里插入图片描述
    在这个公式中

    • u是一个节点。
    • n是图中的节点数。
    • d(u,v)是另一个节点V和U之间的最短路径距离。

    更常见的是将该分数归一化,使该得分代表最短路径的平均长度,而不是它们的总和。这种调整允许比较不同大小图节点的紧密性中心性。
    归一化后的紧密中心性公式如下:
    在这里插入图片描述
    紧密中心性算法的使用场景

    当你需要知道哪个节点传播的东西最快时,应使用紧密中心性。在紧密中心性算法中,使用加权关系的话,会特别有助于评估交流和行为分析中的交互速度。
    示例用例包括:

    • 发现对控制和获取组织内重要信息和资源处于非常有利位置的个人。这方面的一项研究是V. E. Krebs的“Mapping Networks of Terrorist Cells”。
    • 作为一种启发式方法,用于估计电信和包裹交付中的到达时间,在交付过程中,内容通过最短路径流向预先定义的目标。它还被用来揭示通过所有最短路径同时传播的情况,例如通过当地社区传播的感染。在S. P. Borgatti的 “Centrality and Network Flow”中找到更多细节。
    • 可以应用在基于基于图的关键字提取过程,比如评估文档中单词的重要性。这一过程由F. Boudin在“A Comparison of Centrality Measures for Graph-Based Keyphrase Extraction”中有描述。

    紧密性中心性在连通图上效果最好。当该公式应用于一个不连通图时,两个节点之间的距离是无限的,两个节点之间没有路径。这意味着,当我们计算所有节点到那个节点的距离并求和时,我们将得到一个无限大的紧密中心性分数。在下一个示例之后将给出原始公式的变体,用来避免这种情况。

    Apache Spark上的紧密中心性算法

    Apache Spark没有提供一个紧密中心性的内置算法,但是我们可以用aggregateMessages框架来实现,这个框架在最短路径算法部分已经介绍过了。
    在我们创建函数之间,我们需要导入将会用到的包。

    from graphframes.lib import AggregateMessages as AM
    from pyspark.sql import functions as F
    from pyspark.sql.types import *
    from operator import itemgetter
    

    我们创建几个稍后会被引用到的自定义函数(user-defined function)

    def collect_paths(paths):
        return F.collect_set(paths)
    collect_paths_udf = F.udf(collect_paths, ArrayType(StringType()))
    paths_type = ArrayType(
        StructType([StructField("id", StringType()), StructField("distance", IntegerType())]))
    def flatten(ids):
        flat_list = [item for sublist in ids for item in sublist]
        return list(dict(sorted(flat_list, key=itemgetter(0))).items())
    flatten_udf = F.udf(flatten, paths_type)
    def new_paths(paths, id):
        paths = [{"id": col1, "distance": col2 + 1} for col1,
        col2 in paths if col1 != id]
        paths.append({"id": id, "distance": 1})
        return paths
    new_paths_udf = F.udf(new_paths, paths_type)
    def merge_paths(ids, new_ids, id):
        joined_ids = ids + (new_ids if new_ids else [])
        merged_ids = [(col1, col2) for col1, col2 in joined_ids if col1 != id]
        best_ids = dict(sorted(merged_ids, key=itemgetter(1), reverse=True))
        return [{"id": col1, "distance": col2} for col1, col2 in best_ids.items()]
    merge_paths_udf = F.udf(merge_paths, paths_type)
    def calculate_closeness(ids):
        nodes = len(ids)
        total_distance = sum([col2 for col1, col2 in ids])
        return 0 if total_distance == 0 else nodes * 1.0 / total_distance
        closeness_udf = F.udf(calculate_closeness, DoubleType())
    closeness_udf = F.udf(calculate_closeness, DoubleType())
    

    以下代码是计算每个节点的紧密中心性

    vertices = g.vertices.withColumn("ids", F.array())
    cached_vertices = AM.getCachedDataFrame(vertices)
    g2 = GraphFrame(cached_vertices, g.edges)
    for i in range(0, g2.vertices.count()):
        msg_dst = new_paths_udf(AM.src["ids"], AM.src["id"])
        msg_src = new_paths_udf(AM.dst["ids"], AM.dst["id"])
        agg = g2.aggregateMessages(F.collect_set(AM.msg).alias("agg"),
                    sendToSrc=msg_src, sendToDst=msg_dst)
        res = agg.withColumn("newIds", flatten_udf("agg")).drop("agg")
        new_vertices = (g2.vertices.join(res, on="id", how="left_outer")
                .withColumn("mergedIds", merge_paths_udf("ids", "newIds",
                "id")).drop("ids", "newIds")
                .withColumnRenamed("mergedIds", "ids"))
        cached_new_vertices = AM.getCachedDataFrame(new_vertices)
        g2 = GraphFrame(cached_new_vertices, g2.edges)
    (g2.vertices
    .withColumn("closeness", closeness_udf("ids"))
    .sort("closeness", ascending=False)
    .show(truncate=False))
    

    结果如下。Alice、Doug和David是图中连接最紧密的节点,得分为1.0,这意味着每个节点都直接连接到图中其部分的所有节点。

    +-------+-----------------------------------------------------------------+------------------+
    |id     |ids                                                              |closeness         |
    +-------+-----------------------------------------------------------------+------------------+
    |Alice  |[[Bridget, 1], [Doug, 1], [Charles, 1], [Michael, 1], [Mark, 1]] |1.0               |
    |Doug   |[[Bridget, 1], [Charles, 1], [Michael, 1], [Mark, 1], [Alice, 1]]|1.0               |
    |David  |[[James, 1], [Amy, 1]]                                           |1.0               |
    |Bridget|[[Doug, 1], [Charles, 2], [Michael, 1], [Mark, 2], [Alice, 1]]   |0.7142857142857143|
    |Michael|[[Bridget, 1], [Doug, 1], [Charles, 2], [Mark, 2], [Alice, 1]]   |0.7142857142857143|
    |James  |[[David, 1], [Amy, 2]]                                           |0.6666666666666666|
    |Amy    |[[James, 2], [David, 1]]                                         |0.6666666666666666|
    |Charles|[[Bridget, 2], [Doug, 1], [Michael, 2], [Mark, 2], [Alice, 1]]   |0.625             |
    |Mark   |[[Bridget, 2], [Doug, 1], [Charles, 2], [Michael, 2], [Alice, 1]]|0.625             |
    +-------+-----------------------------------------------------------------+------------------+
    

    图5-5说明了即使David在密友群中只有几个联系,但他在他的群体中,也是重要的。换句话说,这个分数表示每个用户在其子图(能连通的到的子图)中与其他用户之间的亲密程度,而不一定全图。
    在这里插入图片描述
    图5-5.紧密中心性的可视化

    Neo4j上的紧密中心性

    Neo4j上用如下的公式来实现紧密中心性算法。
    在这里插入图片描述
    在这个公式中,

    • u是一个节点
    • n是在当前组件(component)内节点数量
    • d(u,v)是其他节点v和u之间的最短路径。
      运行如下查询,将会计算图中每个节点的紧密中心性。
    CALL algo.closeness.stream("User", "FOLLOWS")
    YIELD nodeId, centrality
    RETURN algo.getNodeById(nodeId).id, centrality
    ORDER BY centrality DESC
    

    以下是运行的结果

    +--------------------------------------------------+
    | algo.getNodeById(nodeId).id | centrality         |
    +--------------------------------------------------+
    | "Alice"                     | 1.0                |
    | "Doug"                      | 1.0                |
    | "David"                     | 1.0                |
    | "Bridget"                   | 0.7142857142857143 |
    | "Michael"                   | 0.7142857142857143 |
    | "Amy"                       | 0.6666666666666666 |
    | "James"                     | 0.6666666666666666 |
    | "Charles"                   | 0.625              |
    | "Mark"                      | 0.625              |
    +--------------------------------------------------+
    

    我们得到了与Spark算法相同的结果,但是,和以前一样,分数代表了他们在子图中与其他人的紧密程度,而不是整个图。
    在这里插入图片描述
    在严格意义上的紧密性中心性算法中,我们图中的所有节点都会得到无穷大的分数,因为每个节点至少有一个它无法到达的其他节点。不过,实现每个断开的组件(component,局部连通的图)的得分通常会更有用。

    理想情况下,我们希望在整个图中得到一个中心性的整体认识,在接下来的两个部分中,我们将学习实现紧密中心性算法的一些变体,它们将实现这一点。

    紧密中心性的变体:Wasserman & Faust

    Stanley Wasserman和Katherine Faust提出了一个改进的公式,用于计算具有多个无相互连接的子图的紧密中心性。他们的书Social Network Analysis: Methods and Applications中详细介绍了他们的公式。此公式的结果是可到达组中节点的分数与可到达节点的平均距离之比。
    公式如下:
    在这里插入图片描述
    在这个公式中

    • u是一个节点
    • N是所有节点的数量
    • n是u所在的组件上的节点数量
    • d(u,v)是在其他节点v和u之间的最短路径

    为了能够使用这个公式,我们可以通过传递参数{improved:true}给紧密中心性算法。

    以下查询使用Wasserman & Faust紧密中心性算法:

    CALL algo.closeness.stream("User", "FOLLOWS", {improved: true})
    YIELD nodeId, centrality
    RETURN algo.getNodeById(nodeId).id AS user, centrality
    ORDER BY centrality DESC
    

    运行的结果如下:

    +---------------------------------+
    | user      | centrality          |
    +---------------------------------+
    | "Alice"   | 0.5                 |
    | "Doug"    | 0.5                 |
    | "Bridget" | 0.35714285714285715 |
    | "Michael" | 0.35714285714285715 |
    | "Charles" | 0.3125              |
    | "Mark"    | 0.3125              |
    | "David"   | 0.125               |
    | "Amy"     | 0.08333333333333333 |
    | "James"   | 0.08333333333333333 |
    +---------------------------------+
    

    如图5-6所示,结果现在更能代表节点与整个图的紧密性。较小子图(David、Amy和James)成员的得分已被降低,现在他们的得分是所有用户中最低的。这很有意义,因为它们是最孤立的节点。这个公式对于检测节点在整个图中的重要性更有用,而不是在它自己的子图中。
    在这里插入图片描述
    图5-6.紧密性中心性的可视化
    在下一节中,我们将学习和谐中心性算法,它使用另一个公式来计算紧密性,从而获得类似的结果。

    紧密中心性变体:和谐中心性
    和谐中心性(也称为值化中心性)是紧密中心性的一种变体,被发明来解决不连通图的问题。在《Harmony in a Small World》一书中,M. Marchiori和 V. Latora提出了这个概念,作为一个平均最短路径的实用表示。
    在计算每个节点的接近度得分时,它不是求一个节点到所有其他节点的距离之和,而是求这些距离的倒数。这意味着无穷大的值变得无关紧要。基础的和谐中心性算法使用以下公式:
    在这里插入图片描述
    在公式中

    • u是一个节点
    • n是图中的节点数
    • d(u,v)是在其他节点v和u之间的最短路径

    与紧密中心性一样,我们也可以用以下公式计算归一化和谐中心性:
    在这里插入图片描述
    在这个共识中,无穷大被很干净利索地处理掉了。

    Neo4j上的和谐中心性

    用如下的查询来执行和谐中心性算法。

    CALL algo.closeness.harmonic.stream("User", "FOLLOWS")
    YIELD nodeId, centrality
    RETURN algo.getNodeById(nodeId).id AS user, centrality
    ORDER BY centrality DESC
    

    该Procedure的运行结果如下:

    +------------------------+
    | user      | centrality |
    +------------------------+
    | "Alice"   | 0.625      |
    | "Doug"    | 0.625      |
    | "Bridget" | 0.5        |
    | "Michael" | 0.5        |
    | "Charles" | 0.4375     |
    | "Mark"    | 0.4375     |
    | "David"   | 0.25       |
    | "Amy"     | 0.1875     |
    | "James"   | 0.1875     |
    +------------------------+
    

    该算法的结果与原始的紧密性中心性算法不同,但与Wasserman和Faust改进算法的结果相似。当处理具有多个连接组件的图时,可以使用任一算法。

    中介中心性(Betweenness Centrality)

    有时,系统中最重要的齿轮不是最明显的动力最高的齿轮。有时反而是一些中间环节把对资源或信息流控制最大的群体或经纪人联系起来。中介中心性是一种检测节点对图中信息或资源流的影响程度的方法。它通常用于查找充当从图的一部分到另一部分的桥梁型节点。

    中介中心性算法首先计算连接图中每对节点之间的最短(权重)路径。每个节点都会根据这些通过该节点的最短路径的数量得到一个分数。经过节点的最短路径越多,该节点的得分越高。

    当Linton C. Freeman在1971年的论文A Set of Measures of Centrality Based on Betweenness中介绍这个概念后,中介中心性被认为是“三个截然不同的直观的中心性概念”之一。

    桥和控制点

    网络中的桥可以是节点或关系。在一个非常简单的图中,您可以通过查找节点或关系来找到它们,如果删除这些节点或关系,将导致图的一部分断开连接。然而,由于这种简单情形在典型的图并不是实际发生,实际情况会更复杂,我们需要使用中介中心性算法来评估在一个群体中某个节点的中介特性。

    如果一个节点位于这些节点之间的每一条最短路径上,则它被认为是其他两个节点的关键,如图5-7所示。
    在这里插入图片描述
    图5-7.关键节点位于两个节点之间的每一条最短路径上。所以,创建更多的最短路径,会减少这个关键节点的数量,并减少风险。

    关键节点(pivotal node)在连接其他节点时起着重要作用。如果删除关键节点,则各节点对的新的最短路径将更长或更昂贵。这可以作为评估单一脆弱性点的考虑因素。

    计算中介中心性

    中介中心性是将最短路径通过如下公式计算后累加的结果。
    在这里插入图片描述
    在公式中

    1. u是一个节点
    2. p是节点s和t之间最短路径的数量
    3. p(u)是s和t之间通过u的最短路径的数量
      图5-8显示了计算出中介中心性的步骤
      在这里插入图片描述
      图5-8. 计算中介中心性的基本概念

    这是计算过程:

    1. 对于每个节点,找到通过它的所有最短路径。 B、C、E没有最短路径,并被赋值为0。

    2. 对于步骤1中的每个最短路径,计算其在该对可能最短路径总数中的百分比。(两点间可能有多条最短路径)

    3. 将步骤2中的所有值相加,以找到节点的中间中心性得分。图5-8中的表说明了节点D的步骤2和3。

    4. 对每个节点重复该过程。

    中介中心性算法的使用场景

    中介中心性适用于现实网络中的各种问题。我们使用它来发现瓶颈、控制点和漏洞。
    示例用例包括:

    • 识别不同组织中的影响因素。有权势的个人不一定在管理岗位上,但可以出现在“中介性岗位”上,这能够通过中介中心性来找到。消除这些影响者会严重破坏组织的稳定。如果该组织是犯罪组织,这可能被认为是一种很有效的执法方式;另一种场景下,但是如果企业失去了被低估的关键员工,这可能是一场灾难。更多细节见C. Morselli和J. Roy的Brokerage Qualifications in Ringing Operations。
    • 发现电网等网络中的关键转移点。与直觉相反,移除特定的桥梁或者关键节点,实际上可以通过使得干扰因素孤岛化而提高整体的鲁棒性。研究细节包含在R. Sol.等人的“Robustness of the European Power Grids Under Intentional Attack”中。
    • 通过为目标人物提供推荐引擎,帮助微博用户在Twitter上传播他们的影响力。这一方法在S. Wu等人的一篇论文“Making Recommendations in a Microblog to Improve the Impact of a Focal User”中进行了描述。

    在这里插入图片描述
    中介中心性假设节点之间的所有通信都是沿着最短路径以相同的概率进行的,这在现实生活中情况并不相同。因此,它并没有给我们一个在全图中最有影响力的节点的概览,而只是提供了一个很好的表示方法。 Mark Newman在《Networks: An Introduction 》(Oxford University Press, p186)中有介绍。

    Neo4j上的中介中心性

    Spark没有中介中心性的内置算法,因此我们将使用Neo4j来演示此算法。调用以下过程将计算图中每个节点的中介中心性:

    CALL algo.betweenness.stream("User", "FOLLOWS")
    YIELD nodeId, centrality
    RETURN algo.getNodeById(nodeId).id AS user, centrality
    ORDER BY centrality DESC
    

    运行这个procedure可以得到如下的结果:

    +------------------------+
    | user      | centrality |
    +------------------------+
    | "Alice"   | 10.0       |
    | "Doug"    | 7.0        |
    | "Mark"    | 7.0        |
    | "David"   | 1.0        |
    | "Bridget" | 0.0        |
    | "Charles" | 0.0        |
    | "Michael" | 0.0        |
    | "Amy"     | 0.0        |
    | "James"   | 0.0        |
    +------------------------+
    

    如图5-9所示,Alice是这个网络的主要中介节点,但Mark和Doug并不落后。在较小的子图中,所有最短的路径都经过David,因此他对于这些节点之间的信息流很重要。
    在这里插入图片描述
    图5-9.中介中心性的可视化

    在这里插入图片描述
    对于更大的图来说,精确的中心性计算是不实际的,因为已知最快的精确计算所有节点中间数的算法的运行时间与节点数和关系数的乘积成正比。我们可能希望先过滤后留下子图,并使用子图来(在下一节中描述)处理所有节点的子集。

    我们可以将两个断开连接的图组件连接在一起,方法是引入一个名为Jason的新用户,该用户关注两个组件的用户人员,而且被两个组件的人所关注。

    WITH ["James", "Michael", "Alice", "Doug", "Amy"] AS existingUsers
    MATCH (existing:User) WHERE existing.id IN existingUsers
    MERGE (newUser:User {id: "Jason"})
    MERGE (newUser)<-[:FOLLOWS]-(existing)
    MERGE (newUser)-[:FOLLOWS]->(existing)
    

    如果我们重新运行算法,我们将看到这个输出:

    +--------------------------------+
    | user      | centrality         |
    +--------------------------------+
    | "Jason"   | 44.33333333333333  |
    | "Doug"    | 18.333333333333332 |
    | "Alice"   | 16.666666666666664 |
    | "Amy"     | 8.0                |
    | "James"   | 8.0                |
    | "Michael" | 4.0                |
    | "Mark"    | 2.1666666666666665 |
    | "David"   | 0.5                |
    | "Bridget" | 0.0                |
    | "Charles" | 0.0                |
    +--------------------------------+
    

    Jason的得分最高,因为这两组用户之间的交流将通过他。可以说Jason是两组用户之间的本地桥梁,如图5-10所示。
    在这里插入图片描述
    在我们继续下一节之前,让我们通过删除Jason和他的关系:

    MATCH (user:User {id: "Jason"}) DETACH DELETE user
    
    展开全文
  • 作者:何燕杰 ... 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。...度中心性(degree) 设想一下,你在微信上有个账号,那么是不是意味着微信好友数量越多,那么你的社交圈子越
    作者:何燕杰
    链接:https://www.zhihu.com/question/22610633/answer/143644471
    来源:知乎
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    ps:写在这里只是为了方便以后忘记后理解。

    度中心性(degree)

    设想一下,你在微信上有个账号,那么是不是意味着微信好友数量越多,那么你的社交圈子越广?(假设都是真实好友,不考虑微商神马的奇葩情况)比如我有20个好友,那么意味着20个结点与我相连。如果你有50个好友,那么意味着你的点度中心度比我高,社交圈子比我广。这个就是点度中心性的概念。

    当然,刚才这个情况是无向图的情形,如果是有向图,需要考虑的出度和入度的问题。

    在刚才的基础上拓展一下,假如我们要比较你在微博和微信上的点度中心度,刚才的方法是否适用?如果说使用微信与微博的人数差不多,那么的确可以。但是如果说用户数量不一样呢?那么我们需要考虑到去规模化的问题,这就是标准化的点度中心性的理念。

    接近中心性(closeness)

    对于了解图论的朋友而言,最短路这个概念一定不陌生。我们设想一个实际生活中的场景,比如你要建一个大型的娱乐商场,你可能会希望周围的顾客到达这个商场的距离都可以尽可能地短。这个就涉及到接近中心性的概念,接近中心性的值为路径长度的倒数。

    接近中心性需要考量每个结点到其它结点的最短路的平均长度。也就是说,对于一个结点而言,它距离其它结点越近,那么它的中心度越高。一般来说,那种需要让尽可能多的人使用的设施,它的接近中心度一般是比较高的。

    中介中心性(betweenness)

    这个度量很有意思。这个有点像是我们身边那种社交达人,我们认识的不少朋友可能都是通过他/她认识的,这个人起到了中介的作用。

    中介中心性指的是一个结点担任其它两个结点之间最短路的桥梁的次数。一个结点充当“中介”的次数越高,它的中介中心度就越大。如果要考虑标准化的问题,可以用一个结点承担最短路桥梁的次数除以所有的路径数量。


    百度百科解释:

    度中心性(Degree Centrality)是在网络分析中刻画节点中心性(Centrality)的最直接度量指标。一个节点的节点度越大就意味着这个节点的度中心性越高,该节点在网络中就越重要。


    接近中心性(Closeness Centrality)。反映在网络中某一节点与其他节点之间的接近程度。将一个节点到所有其他节点的最短路径距离的累加起来的倒数表示接近性中心性。即对于一个节点,它距离其他节点越近,那么它的接近性中心性越大。


    中介中心性/中间中心性(Between Centrality) 。以经过某个节点的最短路径数目来刻画节点重要性的指标。


    特征向量中心性(Eigenvector Centrality)。一个节点的重要性既取决于其邻居节点的数量(即该节点的度),也取决于其邻居节点的重要性。



    展开全文
  • 网络分析中,经常会用到中心性这个概念。通常在中心性的分析角度上有两种出发点:中心度和中心势。 &amp;amp;amp;amp;amp;npsb;&amp;amp;amp;amp;amp;npsb;中心度表示一个节点在网络中处于核心地位的程度;...

    网络分析中,经常会用到中心性这个概念。通常在中心性的分析角度上有两种出发点:中心度和中心势。
      中心度表示一个节点在网络中处于核心地位的程度;中心势表示整个图的紧密程度。换句话说,度表示单个节点的性质,而势表示整个图的性质。
    目前有四种中心性的分析方法,分别是:度中心性(degree centrality),间接中心性(betweenness centrality),紧密中心性(closeness centrality),特征向量中心性(eigenvector centrality)。对于每种分析方法都有度和势两种指标。

    1、度中心性(degree centrality)

    网络中,一个节点与其他很多节点发生直接联系,那么这个节点就处于中心地位。即节点的关系越广,相邻节点越多,那么这个节点也就越重要。可以通过节点的 入度来表示DC。

    计算:
    a) 对于有n个节点的图G=(V,E),节点v的度中心性DC就是返回这个节点的入度数。那么当不同的图在做比较时就需要对度中心性进行标准化,这时可以除以这个点v有可能的最大连接数V-1,其中V表示节点个数。
    在这里插入图片描述
    b)整个图的中心势:
    一张图的度中心性需要以单个点的DC最高的点为核心来计算,这里我们将这个点记为n*,它的中心度为DC(n*)。中心势的计算为DC(n*)与其他各点的差值的总和。如果需要标准化的话,在除以最大可能的相连情况(V-1)(V-2)。这个计算结果反应了度中心性最高的点和其他点的差距,差距越大,表示权力越集中。在这里插入图片描述

    2、间接中心性(betweenness centrality)

    间接中心性是指某节点出现在其他节点之间的最短路径的个数。如果这个节点的间接中心性高,那么它对整个图的转移会有很大的影响,考察的是节点对于其他节点信息传播的控制能力。换句话说,就是这个节点相当远一个闸,和它相连的节点想要得到其他节点都得经过它。

    计算:
    求解的过程可以分为三部分:
      1、计算每对节点(s,t)之间的最短路径,需要得到具体的路径信息
      2、对各个节点判断该节点是否在最短路径上
      3、最后将刚刚的判断进行累加得到从s到t的最短路径镜柜该节点的数量,公式如下所示,其中,dst表示s到t的最短路径数,dst()是从s到t的最短路径中经过节点的数量。
    在这里插入图片描述
    若需要进行标准化,在如上公式基础上,除以(n-1)(n-2)

    3、紧密中心性(closeness centrality)

    紧密中心性反应某一节点与其他节点之间的接近程度。如果一个节点离其他节点越近,那么他传播信息的时候也就越不需要依赖他人。一个节点到网络中各点的距离都很短,那么这个点就不会受制于其他点。

    计算:
    这个点的紧密中心性 基于该节点到网络中其他所有节点的最短路径之和。如果进行归一化,那么就是求这个节点到其他所有节点的平均最短距离。一个节点的平均最短距离(di)越小,那么该节点的紧密中心性越大。di越小,意味着节点vi更接近网络中的其他节点,于是把di的倒数定义为节点vi的紧密中心性,即CC(i)。
    在这里插入图片描述
    在这里插入图片描述
    如果节点vi和vj之间没有路径可达,则定义dij=无穷大,则其倒数为0.

    4 、特征向量中心性(eigenvector centrality)

    一个节点的重要性既取决于其邻居节点的数量(即该节点的度),也取决于其邻居节点的重要性,记xi为节点vi的重要性度量值,则:
    在这里插入图片描述
    其中,c为一个比例常数,记x=[x1,x2,x3,…,xn]T,经过多次迭代到达稳态时,可以写成如下的矩阵形式:
    在这里插入图片描述
    这里表示x是矩阵A的特征值c-1对应的特征向量,也可表示为如下形式:
    在这里插入图片描述
    计算:
    一个节点的特征向量中心性与其临近节点的中心性得分的总和成正比。与重要的节点连接的节点更重要,有少量有影响的联系人的节点其中心性可能超过拥有大量平庸的联系人的节点。
    1、计算图的成对临近矩阵的特征分解
    2、选择有最大特征值的特征向量
    3、第i个节点的中心性等于特征向量中的第i元素

    另外PageRank算法是特征向量中心性的一个变种。

    展开全文
  • 网络分析(Network Analysis)入门篇(一) 网络节点的性质

    万次阅读 多人点赞 2018-08-13 16:29:22
    网络分析是数据挖掘中重要的一部分,涉及到的知识和图论有一定的联系,这里讲到的网络分析更倾向于社交网络分析,可以是人与人之间的好友关系,电子邮件的发送关系,也可以推广到互联网网站之间的关系等等。...
  • 社交网络分析:网络中心性

    千次阅读 2016-08-29 12:49:14
    原文地址:社交网络分析:网络中心性作者:酸嘢本文为Social Network Analysis学习笔记,课程地址为https://www.coursera.org/course/sna。 对于中心性(centrality)的不同观点 在下面每一个网络中,X都相对Y具有更...
  • 1.买钢笔,一般要依据质量、颜色、实用、价格等方面的因素来选择某一只钢笔。 2.我们如果想要给一些问题的指标设定权重,而又减弱主观因素在里面。 对于这些问题我们都可以使用AHP算法,让结果尽量接近实际。AHP...
  • 聚类算法评价指标

    万次阅读 2016-09-03 17:34:10
    一、Compactness(紧密性)(CP)  CP计算 每一个类 各点到聚类中心的平均距离  CP越低意味着类内聚类距离越近  缺点:没有考虑类间效果 二、Separation(间隔性)(SP)  SP计算 各聚类中心两两之间平均距离  SP...
  • 模块中组成元素结合的越紧密,模块的内聚就越高,模块的独立也就越高。理想的内聚要求模块的功能应明确、单一,即一个模块只做一件事情。模块的内聚和耦合是两个相互对立且又密切相关的概念。耦合也叫块...
  • 每个模块之间相互联系的紧密程度,模块之间联系越紧密,则耦合越高,模块的独立就越差!反之同理; 一个模块中各个元素之间的联系的紧密程度,如果各个元素(语句、程序段)之间的联系程度越高,则内聚越高,...
  • 本节介绍两个算法,因为Harmonic Centrality algorithm是紧密中心性的变体,故两个算法放在一起介绍。 一.紧密中心度介绍  一个节点的紧密中心性度量它与所有其他节点的平均距离(反比距离)。紧密度得分高的节点...
  • 社会网络分析的主要内容

    万次阅读 2017-09-22 12:25:47
    一、中心性分析——权力的量化研究 目的:在什么意义上说一个行动者有权力?一个子群体有权力? 指标:点或群体的中心度(centrality)和网络的中心势(centralization) 内容:  “中心性”是社会网络分析的重点之...
  • 相关性和显著分析

    千次阅读 2020-01-03 15:33:00
    相关分析用于研究定量数据之间的关系情况,包括是否有关系,以及关系紧密程度等。 1、如果呈现出显著(结果右上角有*号,此时说明有关系;反之则没有关系);有了关系之后,关系的紧密程度直接看相关系数大小即可...
  • 中心性(Centrality)是社交网络分析(Social network analysis, SNA)中常用的一个概念,用以表达社交网络中每个点或者每个人在整个网络中与其他点或其他人之间的关联程度。比如,想知道某个人在网络社交圈中处于哪...
  • 模块独立与高内聚低耦合

    千次阅读 2013-09-23 09:29:13
    模块独立程度的度量标准 1)耦合 不同模块之间的互联程度的度量 2)内聚 模块内部彼此结合的紧密程度的度量 ...模块之间联系越紧密,其耦合就越强,模块的独立则越差。模块间耦合高低取决于模块
  • CEBP

    千次阅读 2009-05-02 21:40:00
    Forrester是这么定义的:通过UC技术,紧密地集成业务流程和应用软件,使得在业务交易处理过程中,在客户、供应商、员工之间可以并发或连续地通信。 通信支持的业务流程可以加快决策、提供更好地客户服务,驱动业务...
  • 1) AABB 包围盒: AABB 包围盒是与坐标轴对齐的包围盒, 简单性好, 紧密性较差(尤其对斜对角方向放置的瘦长形对象, 采用AABB, 将留下很大的边角空隙, 导致大量没必要的包围盒相交测试)。当物体旋转之后需对AABB 进行...
  • 模块的7种内聚类型

    千次阅读 2019-03-31 15:17:46
    一个模块内部各元素之间的紧密程度越高,则其内聚越高,模块独立越好。模块内聚类型主要有以下几类: 偶然内聚或巧合内聚:指一个模块内的各处理元素之间没有任何联系。 逻辑内聚:指模块内执行若干个逻辑上...
  • java设计原则——高内聚低耦合

    千次阅读 2017-05-16 18:38:21
    高内聚低耦合二者的定义如下: 内聚:又称块内联系。指模块的功能强度的度量,即一个...模块之间联系越紧密,其耦合就越强,模块的独立则越差。模块间耦合高低取决于模块间接口的复杂、调用的方式及传递的信息
  • 1.DevOps简介

    万次阅读 2018-01-19 08:01:24
    目的: 为了按时交纳产品与服务,开发和运营工作必须紧密合作 1.简介 1)开发,技术运营和质量保障(QA)三者的交集 2)传统的软件组织将开发,IT运营和质量保障设为分离的部门 按照从前的工作方式,开发和部
1 2 3 4 5 ... 20
收藏数 195,925
精华内容 78,370
热门标签
关键字:

紧密中心性