diff env/lib/python3.9/site-packages/networkx/algorithms/centrality/eigenvector.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/algorithms/centrality/eigenvector.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,229 @@
+"""Functions for computing eigenvector centrality."""
+
+from math import sqrt
+
+import networkx as nx
+from networkx.utils import not_implemented_for
+
+__all__ = ["eigenvector_centrality", "eigenvector_centrality_numpy"]
+
+
+@not_implemented_for("multigraph")
+def eigenvector_centrality(G, max_iter=100, tol=1.0e-6, nstart=None, weight=None):
+    r"""Compute the eigenvector centrality for the graph `G`.
+
+    Eigenvector centrality computes the centrality for a node based on the
+    centrality of its neighbors. The eigenvector centrality for node $i$ is
+    the $i$-th element of the vector $x$ defined by the equation
+
+    .. math::
+
+        Ax = \lambda x
+
+    where $A$ is the adjacency matrix of the graph `G` with eigenvalue
+    $\lambda$. By virtue of the Perron–Frobenius theorem, there is a unique
+    solution $x$, all of whose entries are positive, if $\lambda$ is the
+    largest eigenvalue of the adjacency matrix $A$ ([2]_).
+
+    Parameters
+    ----------
+    G : graph
+      A networkx graph
+
+    max_iter : integer, optional (default=100)
+      Maximum number of iterations in power method.
+
+    tol : float, optional (default=1.0e-6)
+      Error tolerance used to check convergence in power method iteration.
+
+    nstart : dictionary, optional (default=None)
+      Starting value of eigenvector iteration for each node.
+
+    weight : None or string, optional (default=None)
+      If None, all edge weights are considered equal.
+      Otherwise holds the name of the edge attribute used as weight.
+
+    Returns
+    -------
+    nodes : dictionary
+       Dictionary of nodes with eigenvector centrality as the value.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(4)
+    >>> centrality = nx.eigenvector_centrality(G)
+    >>> sorted((v, f"{c:0.2f}") for v, c in centrality.items())
+    [(0, '0.37'), (1, '0.60'), (2, '0.60'), (3, '0.37')]
+
+    Raises
+    ------
+    NetworkXPointlessConcept
+        If the graph `G` is the null graph.
+
+    NetworkXError
+        If each value in `nstart` is zero.
+
+    PowerIterationFailedConvergence
+        If the algorithm fails to converge to the specified tolerance
+        within the specified number of iterations of the power iteration
+        method.
+
+    See Also
+    --------
+    eigenvector_centrality_numpy
+    pagerank
+    hits
+
+    Notes
+    -----
+    The measure was introduced by [1]_ and is discussed in [2]_.
+
+    The power iteration method is used to compute the eigenvector and
+    convergence is **not** guaranteed. Our method stops after ``max_iter``
+    iterations or when the change in the computed vector between two
+    iterations is smaller than an error tolerance of
+    ``G.number_of_nodes() * tol``. This implementation uses ($A + I$)
+    rather than the adjacency matrix $A$ because it shifts the spectrum
+    to enable discerning the correct eigenvector even for networks with
+    multiple dominant eigenvalues.
+
+    For directed graphs this is "left" eigenvector centrality which corresponds
+    to the in-edges in the graph. For out-edges eigenvector centrality
+    first reverse the graph with ``G.reverse()``.
+
+    References
+    ----------
+    .. [1] Phillip Bonacich.
+       "Power and Centrality: A Family of Measures."
+       *American Journal of Sociology* 92(5):1170–1182, 1986
+       <http://www.leonidzhukov.net/hse/2014/socialnetworks/papers/Bonacich-Centrality.pdf>
+    .. [2] Mark E. J. Newman.
+       *Networks: An Introduction.*
+       Oxford University Press, USA, 2010, pp. 169.
+
+    """
+    if len(G) == 0:
+        raise nx.NetworkXPointlessConcept(
+            "cannot compute centrality for the null graph"
+        )
+    # If no initial vector is provided, start with the all-ones vector.
+    if nstart is None:
+        nstart = {v: 1 for v in G}
+    if all(v == 0 for v in nstart.values()):
+        raise nx.NetworkXError("initial vector cannot have all zero values")
+    # Normalize the initial vector so that each entry is in [0, 1]. This is
+    # guaranteed to never have a divide-by-zero error by the previous line.
+    nstart_sum = sum(nstart.values())
+    x = {k: v / nstart_sum for k, v in nstart.items()}
+    nnodes = G.number_of_nodes()
+    # make up to max_iter iterations
+    for i in range(max_iter):
+        xlast = x
+        x = xlast.copy()  # Start with xlast times I to iterate with (A+I)
+        # do the multiplication y^T = x^T A (left eigenvector)
+        for n in x:
+            for nbr in G[n]:
+                w = G[n][nbr].get(weight, 1) if weight else 1
+                x[nbr] += xlast[n] * w
+        # Normalize the vector. The normalization denominator `norm`
+        # should never be zero by the Perron--Frobenius
+        # theorem. However, in case it is due to numerical error, we
+        # assume the norm to be one instead.
+        norm = sqrt(sum(z ** 2 for z in x.values())) or 1
+        x = {k: v / norm for k, v in x.items()}
+        # Check for convergence (in the L_1 norm).
+        if sum(abs(x[n] - xlast[n]) for n in x) < nnodes * tol:
+            return x
+    raise nx.PowerIterationFailedConvergence(max_iter)
+
+
+def eigenvector_centrality_numpy(G, weight=None, max_iter=50, tol=0):
+    r"""Compute the eigenvector centrality for the graph G.
+
+    Eigenvector centrality computes the centrality for a node based on the
+    centrality of its neighbors. The eigenvector centrality for node $i$ is
+
+    .. math::
+
+        Ax = \lambda x
+
+    where $A$ is the adjacency matrix of the graph G with eigenvalue $\lambda$.
+    By virtue of the Perron–Frobenius theorem, there is a unique and positive
+    solution if $\lambda$ is the largest eigenvalue associated with the
+    eigenvector of the adjacency matrix $A$ ([2]_).
+
+    Parameters
+    ----------
+    G : graph
+      A networkx graph
+
+    weight : None or string, optional (default=None)
+      The name of the edge attribute used as weight.
+      If None, all edge weights are considered equal.
+
+    max_iter : integer, optional (default=100)
+      Maximum number of iterations in power method.
+
+    tol : float, optional (default=1.0e-6)
+       Relative accuracy for eigenvalues (stopping criterion).
+       The default value of 0 implies machine precision.
+
+    Returns
+    -------
+    nodes : dictionary
+       Dictionary of nodes with eigenvector centrality as the value.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(4)
+    >>> centrality = nx.eigenvector_centrality_numpy(G)
+    >>> print([f"{node} {centrality[node]:0.2f}" for node in centrality])
+    ['0 0.37', '1 0.60', '2 0.60', '3 0.37']
+
+    See Also
+    --------
+    eigenvector_centrality
+    pagerank
+    hits
+
+    Notes
+    -----
+    The measure was introduced by [1]_.
+
+    This algorithm uses the SciPy sparse eigenvalue solver (ARPACK) to
+    find the largest eigenvalue/eigenvector pair.
+
+    For directed graphs this is "left" eigenvector centrality which corresponds
+    to the in-edges in the graph. For out-edges eigenvector centrality
+    first reverse the graph with ``G.reverse()``.
+
+    Raises
+    ------
+    NetworkXPointlessConcept
+        If the graph ``G`` is the null graph.
+
+    References
+    ----------
+    .. [1] Phillip Bonacich:
+       Power and Centrality: A Family of Measures.
+       American Journal of Sociology 92(5):1170–1182, 1986
+       http://www.leonidzhukov.net/hse/2014/socialnetworks/papers/Bonacich-Centrality.pdf
+    .. [2] Mark E. J. Newman:
+       Networks: An Introduction.
+       Oxford University Press, USA, 2010, pp. 169.
+    """
+    import numpy as np
+    import scipy as sp
+    from scipy.sparse import linalg
+
+    if len(G) == 0:
+        raise nx.NetworkXPointlessConcept(
+            "cannot compute centrality for the null graph"
+        )
+    M = nx.to_scipy_sparse_matrix(G, nodelist=list(G), weight=weight, dtype=float)
+    eigenvalue, eigenvector = linalg.eigs(
+        M.T, k=1, which="LR", maxiter=max_iter, tol=tol
+    )
+    largest = eigenvector.flatten().real
+    norm = np.sign(largest.sum()) * sp.linalg.norm(largest)
+    return dict(zip(G, largest / norm))