Source code for networkx.algorithms.centrality.percolation

"""渗透中心性度量。"""

import networkx as nx
from networkx.algorithms.centrality.betweenness import (
    _single_source_dijkstra_path_basic as dijkstra,
)
from networkx.algorithms.centrality.betweenness import (
    _single_source_shortest_path_basic as shortest_path,
)

__all__ = ["percolation_centrality"]




@nx._dispatchable(node_attrs="attribute", edge_attrs="weight")
def percolation_centrality(G, attribute="percolation", states=None, weight=None):
    r"""计算节点的渗透中心性。

节点 $v$ 在给定时间的渗透中心性定义为通过该节点的“渗透路径”的比例。

该度量根据节点的拓扑连接性及其渗透状态量化节点的相对影响。

节点的渗透状态用于描述网络渗透场景（例如在个人社交网络中的感染传播、计算机网络上的计算机病毒传播或城镇网络上的疾病传播）随时间的变化。在这个度量中，渗透状态通常表示为0.0到1.0之间的十进制数。

当所有节点处于相同的渗透状态时，该度量等同于介数中心性。

Parameters
----------
G : 图
  一个 NetworkX 图。

attribute : None 或 字符串, 可选 (默认='percolation')
  用于渗透状态的节点属性名称，如果 `states` 为 None 则使用。如果节点未设置该属性，则该节点的状态将设置为默认值1。如果所有节点都没有该属性，则所有节点将设置为1，中心性度量将等同于介数中心性。

states : None 或 字典, 可选 (默认=None)
  指定节点的渗透状态，节点为键，状态为值。

weight : None 或 字符串, 可选 (默认=None)
  如果为 None，则所有边的权重视为相等。否则，保留用作权重的边属性名称。边的权重被视为两端之间的长度或距离。

Returns
-------
nodes : 字典
  包含节点及其渗透中心性值的字典。

See Also
--------
betweenness_centrality

Notes
-----
该算法来自 Mahendra Piraveenan, Mikhail Prokopenko 和 Liaquat Hossain [1]_
成对依赖关系通过 [2]_ 计算和累积

对于加权图，边权重必须大于零。零边权重可以在节点对之间产生无限数量的等长路径。

References
----------
.. [1] Mahendra Piraveenan, Mikhail Prokopenko, Liaquat Hossain
   Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes
   during Percolation in Networks
   http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0053095
.. [2] Ulrik Brandes:
   A Faster Algorithm for Betweenness Centrality.
   Journal of Mathematical Sociology 25(2):163-177, 2001.
   https://doi.org/10.1080/0022250X.2001.9990249
"""
    percolation = dict.fromkeys(G, 0.0)  # b[v]=0 for v in G

    nodes = G

    if states is None:
        states = nx.get_node_attributes(nodes, attribute, default=1)

    # sum of all percolation states
    p_sigma_x_t = 0.0
    for v in states.values():
        p_sigma_x_t += v

    for s in nodes:
        # single source shortest paths
        if weight is None:  # use BFS
            S, P, sigma, _ = shortest_path(G, s)
        else:  # use Dijkstra's algorithm
            S, P, sigma, _ = dijkstra(G, s, weight)
        # accumulation
        percolation = _accumulate_percolation(
            percolation, S, P, sigma, s, states, p_sigma_x_t
        )

    n = len(G)

    for v in percolation:
        percolation[v] *= 1 / (n - 2)

    return percolation



def _accumulate_percolation(percolation, S, P, sigma, s, states, p_sigma_x_t):
    delta = dict.fromkeys(S, 0)
    while S:
        w = S.pop()
        coeff = (1 + delta[w]) / sigma[w]
        for v in P[w]:
            delta[v] += sigma[v] * coeff
        if w != s:
            # percolation weight
            pw_s_w = states[s] / (p_sigma_x_t - states[w])
            percolation[w] += delta[w] * pw_s_w
    return percolation