Upload folder using huggingface_hub

17c6d62 verified over 1 year ago

9.51 kB

"""
Subraph centrality and communicability betweenness.
"""

import networkx as nx
from networkx.utils import not_implemented_for

__all__ = [
    "subgraph_centrality_exp",
    "subgraph_centrality",
    "communicability_betweenness_centrality",
    "estrada_index",
]


@not_implemented_for("directed")
@not_implemented_for("multigraph")
@nx._dispatchable
def subgraph_centrality_exp(G):
    r"""Returns the subgraph centrality for each node of G.
    Subgraph centrality  of a node `n` is the sum of weighted closed
    walks of all lengths starting and ending at node `n`. The weights
    decrease with path length. Each closed walk is associated with a
    connected subgraph ([1]_).
    Parameters
    ----------
    G: graph
    Returns
    -------
    nodes:dictionary
        Dictionary of nodes with subgraph centrality as the value.
    Raises
    ------
    NetworkXError
        If the graph is not undirected and simple.
    See Also
    --------
    subgraph_centrality:
        Alternative algorithm of the subgraph centrality for each node of G.
    Notes
    -----
    This version of the algorithm exponentiates the adjacency matrix.
    The subgraph centrality of a node `u` in G can be found using
    the matrix exponential of the adjacency matrix of G [1]_,
    .. math::
        SC(u)=(e^A)_{uu} .
    References
    ----------
    .. [1] Ernesto Estrada, Juan A. Rodriguez-Velazquez,
       "Subgraph centrality in complex networks",
       Physical Review E 71, 056103 (2005).
       https://arxiv.org/abs/cond-mat/0504730
    Examples
    --------
    (Example from [1]_)
    >>> G = nx.Graph(
    ...     [
    ...         (1, 2),
    ...         (1, 5),
    ...         (1, 8),
    ...         (2, 3),
    ...         (2, 8),
    ...         (3, 4),
    ...         (3, 6),
    ...         (4, 5),
    ...         (4, 7),
    ...         (5, 6),
    ...         (6, 7),
    ...         (7, 8),
    ...     ]
    ... )
    >>> sc = nx.subgraph_centrality_exp(G)
    >>> print([f"{node} {sc[node]:0.2f}" for node in sorted(sc)])
    ['1 3.90', '2 3.90', '3 3.64', '4 3.71', '5 3.64', '6 3.71', '7 3.64', '8 3.90']
    """
    # alternative implementation that calculates the matrix exponential
    import scipy as sp

    nodelist = list(G)  # ordering of nodes in matrix
    A = nx.to_numpy_array(G, nodelist)
    # convert to 0-1 matrix
    A[A != 0.0] = 1
    expA = sp.linalg.expm(A)
    # convert diagonal to dictionary keyed by node
    sc = dict(zip(nodelist, map(float, expA.diagonal())))
    return sc


@not_implemented_for("directed")
@not_implemented_for("multigraph")
@nx._dispatchable
def subgraph_centrality(G):
    r"""Returns subgraph centrality for each node in G.
    Subgraph centrality  of a node `n` is the sum of weighted closed
    walks of all lengths starting and ending at node `n`. The weights
    decrease with path length. Each closed walk is associated with a
    connected subgraph ([1]_).
    Parameters
    ----------
    G: graph
    Returns
    -------
    nodes : dictionary
       Dictionary of nodes with subgraph centrality as the value.
    Raises
    ------
    NetworkXError
       If the graph is not undirected and simple.
    See Also
    --------
    subgraph_centrality_exp:
        Alternative algorithm of the subgraph centrality for each node of G.
    Notes
    -----
    This version of the algorithm computes eigenvalues and eigenvectors
    of the adjacency matrix.
    Subgraph centrality of a node `u` in G can be found using
    a spectral decomposition of the adjacency matrix [1]_,
    .. math::
       SC(u)=\sum_{j=1}^{N}(v_{j}^{u})^2 e^{\lambda_{j}},
    where `v_j` is an eigenvector of the adjacency matrix `A` of G
    corresponding to the eigenvalue `\lambda_j`.
    Examples
    --------
    (Example from [1]_)
    >>> G = nx.Graph(
    ...     [
    ...         (1, 2),
    ...         (1, 5),
    ...         (1, 8),
    ...         (2, 3),
    ...         (2, 8),
    ...         (3, 4),
    ...         (3, 6),
    ...         (4, 5),
    ...         (4, 7),
    ...         (5, 6),
    ...         (6, 7),
    ...         (7, 8),
    ...     ]
    ... )
    >>> sc = nx.subgraph_centrality(G)
    >>> print([f"{node} {sc[node]:0.2f}" for node in sorted(sc)])
    ['1 3.90', '2 3.90', '3 3.64', '4 3.71', '5 3.64', '6 3.71', '7 3.64', '8 3.90']
    References
    ----------
    .. [1] Ernesto Estrada, Juan A. Rodriguez-Velazquez,
       "Subgraph centrality in complex networks",
       Physical Review E 71, 056103 (2005).
       https://arxiv.org/abs/cond-mat/0504730
    """
    import numpy as np

    nodelist = list(G)  # ordering of nodes in matrix
    A = nx.to_numpy_array(G, nodelist)
    # convert to 0-1 matrix
    A[np.nonzero(A)] = 1
    w, v = np.linalg.eigh(A)
    vsquare = np.array(v) ** 2
    expw = np.exp(w)
    xg = vsquare @ expw
    # convert vector dictionary keyed by node
    sc = dict(zip(nodelist, map(float, xg)))
    return sc


@not_implemented_for("directed")
@not_implemented_for("multigraph")
@nx._dispatchable
def communicability_betweenness_centrality(G):
    r"""Returns subgraph communicability for all pairs of nodes in G.
    Communicability betweenness measure makes use of the number of walks
    connecting every pair of nodes as the basis of a betweenness centrality
    measure.
    Parameters
    ----------
    G: graph
    Returns
    -------
    nodes : dictionary
        Dictionary of nodes with communicability betweenness as the value.
    Raises
    ------
    NetworkXError
        If the graph is not undirected and simple.
    Notes
    -----
    Let `G=(V,E)` be a simple undirected graph with `n` nodes and `m` edges,
    and `A` denote the adjacency matrix of `G`.
    Let `G(r)=(V,E(r))` be the graph resulting from
    removing all edges connected to node `r` but not the node itself.
    The adjacency matrix for `G(r)` is `A+E(r)`,  where `E(r)` has nonzeros
    only in row and column `r`.
    The subraph betweenness of a node `r`  is [1]_
    .. math::
         \omega_{r} = \frac{1}{C}\sum_{p}\sum_{q}\frac{G_{prq}}{G_{pq}},
         p\neq q, q\neq r,
    where
    `G_{prq}=(e^{A}_{pq} - (e^{A+E(r)})_{pq}`  is the number of walks
    involving node r,
    `G_{pq}=(e^{A})_{pq}` is the number of closed walks starting
    at node `p` and ending at node `q`,
    and `C=(n-1)^{2}-(n-1)` is a normalization factor equal to the
    number of terms in the sum.
    The resulting `\omega_{r}` takes values between zero and one.
    The lower bound cannot be attained for a connected
    graph, and the upper bound is attained in the star graph.
    References
    ----------
    .. [1] Ernesto Estrada, Desmond J. Higham, Naomichi Hatano,
       "Communicability Betweenness in Complex Networks"
       Physica A 388 (2009) 764-774.
       https://arxiv.org/abs/0905.4102
    Examples
    --------
    >>> G = nx.Graph([(0, 1), (1, 2), (1, 5), (5, 4), (2, 4), (2, 3), (4, 3), (3, 6)])
    >>> cbc = nx.communicability_betweenness_centrality(G)
    >>> print([f"{node} {cbc[node]:0.2f}" for node in sorted(cbc)])
    ['0 0.03', '1 0.45', '2 0.51', '3 0.45', '4 0.40', '5 0.19', '6 0.03']
    """
    import numpy as np
    import scipy as sp

    nodelist = list(G)  # ordering of nodes in matrix
    n = len(nodelist)
    A = nx.to_numpy_array(G, nodelist)
    # convert to 0-1 matrix
    A[np.nonzero(A)] = 1
    expA = sp.linalg.expm(A)
    mapping = dict(zip(nodelist, range(n)))
    cbc = {}
    for v in G:
        # remove row and col of node v
        i = mapping[v]
        row = A[i, :].copy()
        col = A[:, i].copy()
        A[i, :] = 0
        A[:, i] = 0
        B = (expA - sp.linalg.expm(A)) / expA
        # sum with row/col of node v and diag set to zero
        B[i, :] = 0
        B[:, i] = 0
        B -= np.diag(np.diag(B))
        cbc[v] = float(B.sum())
        # put row and col back
        A[i, :] = row
        A[:, i] = col
    # rescale when more than two nodes
    order = len(cbc)
    if order > 2:
        scale = 1.0 / ((order - 1.0) ** 2 - (order - 1.0))
        cbc = {node: value * scale for node, value in cbc.items()}
    return cbc


@nx._dispatchable
def estrada_index(G):
    r"""Returns the Estrada index of a the graph G.
    The Estrada Index is a topological index of folding or 3D "compactness" ([1]_).
    Parameters
    ----------
    G: graph
    Returns
    -------
    estrada index: float
    Raises
    ------
    NetworkXError
        If the graph is not undirected and simple.
    Notes
    -----
    Let `G=(V,E)` be a simple undirected graph with `n` nodes  and let
    `\lambda_{1}\leq\lambda_{2}\leq\cdots\lambda_{n}`
    be a non-increasing ordering of the eigenvalues of its adjacency
    matrix `A`. The Estrada index is ([1]_, [2]_)
    .. math::
        EE(G)=\sum_{j=1}^n e^{\lambda _j}.
    References
    ----------
    .. [1] E. Estrada, "Characterization of 3D molecular structure",
       Chem. Phys. Lett. 319, 713 (2000).
       https://doi.org/10.1016/S0009-2614(00)00158-5
    .. [2] José Antonio de la Peñaa, Ivan Gutman, Juan Rada,
       "Estimating the Estrada index",
       Linear Algebra and its Applications. 427, 1 (2007).
       https://doi.org/10.1016/j.laa.2007.06.020
    Examples
    --------
    >>> G = nx.Graph([(0, 1), (1, 2), (1, 5), (5, 4), (2, 4), (2, 3), (4, 3), (3, 6)])
    >>> ei = nx.estrada_index(G)
    >>> print(f"{ei:0.5}")
    20.55
    """
    return sum(subgraph_centrality(G).values())

	"""
	Subraph centrality and communicability betweenness.
	"""

	import networkx as nx
	from networkx.utils import not_implemented_for

	__all__ = [
	"subgraph_centrality_exp",
	"subgraph_centrality",
	"communicability_betweenness_centrality",
	"estrada_index",
	]


	@not_implemented_for("directed")
	@not_implemented_for("multigraph")
	@nx._dispatchable
	def subgraph_centrality_exp(G):
	r"""Returns the subgraph centrality for each node of G.

	Subgraph centrality of a node `n` is the sum of weighted closed
	walks of all lengths starting and ending at node `n`. The weights
	decrease with path length. Each closed walk is associated with a
	connected subgraph ([1]_).

	Parameters
	----------
	G: graph

	Returns
	-------
	nodes:dictionary
	Dictionary of nodes with subgraph centrality as the value.

	Raises
	------
	NetworkXError
	If the graph is not undirected and simple.

	See Also
	--------
	subgraph_centrality:
	Alternative algorithm of the subgraph centrality for each node of G.

	Notes
	-----
	This version of the algorithm exponentiates the adjacency matrix.

	The subgraph centrality of a node `u` in G can be found using
	the matrix exponential of the adjacency matrix of G [1]_,

	.. math::

	SC(u)=(e^A)_{uu} .

	References
	----------
	.. [1] Ernesto Estrada, Juan A. Rodriguez-Velazquez,
	"Subgraph centrality in complex networks",
	Physical Review E 71, 056103 (2005).
	https://arxiv.org/abs/cond-mat/0504730

	Examples
	--------
	(Example from [1]_)
	>>> G = nx.Graph(
	... [
	... (1, 2),
	... (1, 5),
	... (1, 8),
	... (2, 3),
	... (2, 8),
	... (3, 4),
	... (3, 6),
	... (4, 5),
	... (4, 7),
	... (5, 6),
	... (6, 7),
	... (7, 8),
	... ]
	... )
	>>> sc = nx.subgraph_centrality_exp(G)
	>>> print([f"{node} {sc[node]:0.2f}" for node in sorted(sc)])
	['1 3.90', '2 3.90', '3 3.64', '4 3.71', '5 3.64', '6 3.71', '7 3.64', '8 3.90']
	"""
	# alternative implementation that calculates the matrix exponential
	import scipy as sp

	nodelist = list(G) # ordering of nodes in matrix
	A = nx.to_numpy_array(G, nodelist)
	# convert to 0-1 matrix
	A[A != 0.0] = 1
	expA = sp.linalg.expm(A)
	# convert diagonal to dictionary keyed by node
	sc = dict(zip(nodelist, map(float, expA.diagonal())))
	return sc


	@not_implemented_for("directed")
	@not_implemented_for("multigraph")
	@nx._dispatchable
	def subgraph_centrality(G):
	r"""Returns subgraph centrality for each node in G.

	Subgraph centrality of a node `n` is the sum of weighted closed
	walks of all lengths starting and ending at node `n`. The weights
	decrease with path length. Each closed walk is associated with a
	connected subgraph ([1]_).

	Parameters
	----------
	G: graph

	Returns
	-------
	nodes : dictionary
	Dictionary of nodes with subgraph centrality as the value.

	Raises
	------
	NetworkXError
	If the graph is not undirected and simple.

	See Also
	--------
	subgraph_centrality_exp:
	Alternative algorithm of the subgraph centrality for each node of G.

	Notes
	-----
	This version of the algorithm computes eigenvalues and eigenvectors
	of the adjacency matrix.

	Subgraph centrality of a node `u` in G can be found using
	a spectral decomposition of the adjacency matrix [1]_,

	.. math::

	SC(u)=\sum_{j=1}^{N}(v_{j}^{u})^2 e^{\lambda_{j}},

	where `v_j` is an eigenvector of the adjacency matrix `A` of G
	corresponding to the eigenvalue `\lambda_j`.

	Examples
	--------
	(Example from [1]_)
	>>> G = nx.Graph(
	... [
	... (1, 2),
	... (1, 5),
	... (1, 8),
	... (2, 3),
	... (2, 8),
	... (3, 4),
	... (3, 6),
	... (4, 5),
	... (4, 7),
	... (5, 6),
	... (6, 7),
	... (7, 8),
	... ]
	... )
	>>> sc = nx.subgraph_centrality(G)
	>>> print([f"{node} {sc[node]:0.2f}" for node in sorted(sc)])
	['1 3.90', '2 3.90', '3 3.64', '4 3.71', '5 3.64', '6 3.71', '7 3.64', '8 3.90']

	References
	----------
	.. [1] Ernesto Estrada, Juan A. Rodriguez-Velazquez,
	"Subgraph centrality in complex networks",
	Physical Review E 71, 056103 (2005).
	https://arxiv.org/abs/cond-mat/0504730

	"""
	import numpy as np

	nodelist = list(G) # ordering of nodes in matrix
	A = nx.to_numpy_array(G, nodelist)
	# convert to 0-1 matrix
	A[np.nonzero(A)] = 1
	w, v = np.linalg.eigh(A)
	vsquare = np.array(v) ** 2
	expw = np.exp(w)
	xg = vsquare @ expw
	# convert vector dictionary keyed by node
	sc = dict(zip(nodelist, map(float, xg)))
	return sc


	@not_implemented_for("directed")
	@not_implemented_for("multigraph")
	@nx._dispatchable
	def communicability_betweenness_centrality(G):
	r"""Returns subgraph communicability for all pairs of nodes in G.

	Communicability betweenness measure makes use of the number of walks
	connecting every pair of nodes as the basis of a betweenness centrality
	measure.

	Parameters
	----------
	G: graph

	Returns
	-------
	nodes : dictionary
	Dictionary of nodes with communicability betweenness as the value.

	Raises
	------
	NetworkXError
	If the graph is not undirected and simple.

	Notes
	-----
	Let `G=(V,E)` be a simple undirected graph with `n` nodes and `m` edges,
	and `A` denote the adjacency matrix of `G`.

	Let `G(r)=(V,E(r))` be the graph resulting from
	removing all edges connected to node `r` but not the node itself.

	The adjacency matrix for `G(r)` is `A+E(r)`, where `E(r)` has nonzeros
	only in row and column `r`.

	The subraph betweenness of a node `r` is [1]_

	.. math::

	\omega_{r} = \frac{1}{C}\sum_{p}\sum_{q}\frac{G_{prq}}{G_{pq}},
	p\neq q, q\neq r,

	where
	`G_{prq}=(e^{A}_{pq} - (e^{A+E(r)})_{pq}` is the number of walks
	involving node r,
	`G_{pq}=(e^{A})_{pq}` is the number of closed walks starting
	at node `p` and ending at node `q`,
	and `C=(n-1)^{2}-(n-1)` is a normalization factor equal to the
	number of terms in the sum.

	The resulting `\omega_{r}` takes values between zero and one.
	The lower bound cannot be attained for a connected
	graph, and the upper bound is attained in the star graph.

	References
	----------
	.. [1] Ernesto Estrada, Desmond J. Higham, Naomichi Hatano,
	"Communicability Betweenness in Complex Networks"
	Physica A 388 (2009) 764-774.
	https://arxiv.org/abs/0905.4102

	Examples
	--------
	>>> G = nx.Graph([(0, 1), (1, 2), (1, 5), (5, 4), (2, 4), (2, 3), (4, 3), (3, 6)])
	>>> cbc = nx.communicability_betweenness_centrality(G)
	>>> print([f"{node} {cbc[node]:0.2f}" for node in sorted(cbc)])
	['0 0.03', '1 0.45', '2 0.51', '3 0.45', '4 0.40', '5 0.19', '6 0.03']
	"""
	import numpy as np
	import scipy as sp

	nodelist = list(G) # ordering of nodes in matrix
	n = len(nodelist)
	A = nx.to_numpy_array(G, nodelist)
	# convert to 0-1 matrix
	A[np.nonzero(A)] = 1
	expA = sp.linalg.expm(A)
	mapping = dict(zip(nodelist, range(n)))
	cbc = {}
	for v in G:
	# remove row and col of node v
	i = mapping[v]
	row = A[i, :].copy()
	col = A[:, i].copy()
	A[i, :] = 0
	A[:, i] = 0
	B = (expA - sp.linalg.expm(A)) / expA
	# sum with row/col of node v and diag set to zero
	B[i, :] = 0
	B[:, i] = 0
	B -= np.diag(np.diag(B))
	cbc[v] = float(B.sum())
	# put row and col back
	A[i, :] = row
	A[:, i] = col
	# rescale when more than two nodes
	order = len(cbc)
	if order > 2:
	scale = 1.0 / ((order - 1.0) ** 2 - (order - 1.0))
	cbc = {node: value * scale for node, value in cbc.items()}
	return cbc


	@nx._dispatchable
	def estrada_index(G):
	r"""Returns the Estrada index of a the graph G.

	The Estrada Index is a topological index of folding or 3D "compactness" ([1]_).

	Parameters
	----------
	G: graph

	Returns
	-------
	estrada index: float

	Raises
	------
	NetworkXError
	If the graph is not undirected and simple.

	Notes
	-----
	Let `G=(V,E)` be a simple undirected graph with `n` nodes and let
	`\lambda_{1}\leq\lambda_{2}\leq\cdots\lambda_{n}`
	be a non-increasing ordering of the eigenvalues of its adjacency
	matrix `A`. The Estrada index is ([1]_, [2]_)

	.. math::
	EE(G)=\sum_{j=1}^n e^{\lambda _j}.

	References
	----------
	.. [1] E. Estrada, "Characterization of 3D molecular structure",
	Chem. Phys. Lett. 319, 713 (2000).
	https://doi.org/10.1016/S0009-2614(00)00158-5
	.. [2] José Antonio de la Peñaa, Ivan Gutman, Juan Rada,
	"Estimating the Estrada index",
	Linear Algebra and its Applications. 427, 1 (2007).
	https://doi.org/10.1016/j.laa.2007.06.020

	Examples
	--------
	>>> G = nx.Graph([(0, 1), (1, 2), (1, 5), (5, 4), (2, 4), (2, 3), (4, 3), (3, 6)])
	>>> ei = nx.estrada_index(G)
	>>> print(f"{ei:0.5}")
	20.55
	"""
	return sum(subgraph_centrality(G).values())