Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / centrality / eigenvector.py @ 5cef0f13

History | View | Annotate | Download (8.47 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2004-2019 by
3
#    Aric Hagberg <hagberg@lanl.gov>
4
#    Dan Schult <dschult@colgate.edu>
5
#    Pieter Swart <swart@lanl.gov>
6
#    All rights reserved.
7
#    BSD license.
8
#
9
# Authors:
10
#     Aric Hagberg <aric.hagberg@gmail.com>
11
#     Pieter Swart <swart@lanl.gov>
12
#     Sasha Gutfraind <ag362@cornell.edu>
13
"""Functions for computing eigenvector centrality."""
14
from __future__ import division
15

    
16
from math import sqrt
17

    
18
import networkx as nx
19
from networkx.utils import not_implemented_for
20

    
21
__all__ = ['eigenvector_centrality', 'eigenvector_centrality_numpy']
22

    
23

    
24
@not_implemented_for('multigraph')
25
def eigenvector_centrality(G, max_iter=100, tol=1.0e-6, nstart=None,
26
                           weight=None):
27
    r"""Compute the eigenvector centrality for the graph `G`.
28

29
    Eigenvector centrality computes the centrality for a node based on the
30
    centrality of its neighbors. The eigenvector centrality for node $i$ is
31
    the $i$-th element of the vector $x$ defined by the equation
32

33
    .. math::
34

35
        Ax = \lambda x
36

37
    where $A$ is the adjacency matrix of the graph `G` with eigenvalue
38
    $\lambda$. By virtue of the Perron–Frobenius theorem, there is a unique
39
    solution $x$, all of whose entries are positive, if $\lambda$ is the
40
    largest eigenvalue of the adjacency matrix $A$ ([2]_).
41

42
    Parameters
43
    ----------
44
    G : graph
45
      A networkx graph
46

47
    max_iter : integer, optional (default=100)
48
      Maximum number of iterations in power method.
49

50
    tol : float, optional (default=1.0e-6)
51
      Error tolerance used to check convergence in power method iteration.
52

53
    nstart : dictionary, optional (default=None)
54
      Starting value of eigenvector iteration for each node.
55

56
    weight : None or string, optional (default=None)
57
      If None, all edge weights are considered equal.
58
      Otherwise holds the name of the edge attribute used as weight.
59

60
    Returns
61
    -------
62
    nodes : dictionary
63
       Dictionary of nodes with eigenvector centrality as the value.
64

65
    Examples
66
    --------
67
    >>> G = nx.path_graph(4)
68
    >>> centrality = nx.eigenvector_centrality(G)
69
    >>> sorted((v, '{:0.2f}'.format(c)) for v, c in centrality.items())
70
    [(0, '0.37'), (1, '0.60'), (2, '0.60'), (3, '0.37')]
71

72
    Raises
73
    ------
74
    NetworkXPointlessConcept
75
        If the graph `G` is the null graph.
76

77
    NetworkXError
78
        If each value in `nstart` is zero.
79

80
    PowerIterationFailedConvergence
81
        If the algorithm fails to converge to the specified tolerance
82
        within the specified number of iterations of the power iteration
83
        method.
84

85
    See Also
86
    --------
87
    eigenvector_centrality_numpy
88
    pagerank
89
    hits
90

91
    Notes
92
    -----
93
    The measure was introduced by [1]_ and is discussed in [2]_.
94

95
    The power iteration method is used to compute the eigenvector and
96
    convergence is **not** guaranteed. Our method stops after ``max_iter``
97
    iterations or when the change in the computed vector between two
98
    iterations is smaller than an error tolerance of
99
    ``G.number_of_nodes() * tol``. This implementation uses ($A + I$)
100
    rather than the adjacency matrix $A$ because it shifts the spectrum
101
    to enable discerning the correct eigenvector even for networks with
102
    multiple dominant eigenvalues.
103

104
    For directed graphs this is "left" eigenvector centrality which corresponds
105
    to the in-edges in the graph. For out-edges eigenvector centrality
106
    first reverse the graph with ``G.reverse()``.
107

108
    References
109
    ----------
110
    .. [1] Phillip Bonacich.
111
       "Power and Centrality: A Family of Measures."
112
       *American Journal of Sociology* 92(5):1170–1182, 1986
113
       <http://www.leonidzhukov.net/hse/2014/socialnetworks/papers/Bonacich-Centrality.pdf>
114
    .. [2] Mark E. J. Newman.
115
       *Networks: An Introduction.*
116
       Oxford University Press, USA, 2010, pp. 169.
117

118
    """
119
    if len(G) == 0:
120
        raise nx.NetworkXPointlessConcept('cannot compute centrality for the'
121
                                          ' null graph')
122
    # If no initial vector is provided, start with the all-ones vector.
123
    if nstart is None:
124
        nstart = {v: 1 for v in G}
125
    if all(v == 0 for v in nstart.values()):
126
        raise nx.NetworkXError('initial vector cannot have all zero values')
127
    # Normalize the initial vector so that each entry is in [0, 1]. This is
128
    # guaranteed to never have a divide-by-zero error by the previous line.
129
    nstart_sum = sum(nstart.values())
130
    x = {k: v / nstart_sum for k, v in nstart.items()}
131
    nnodes = G.number_of_nodes()
132
    # make up to max_iter iterations
133
    for i in range(max_iter):
134
        xlast = x
135
        x = xlast.copy()  # Start with xlast times I to iterate with (A+I)
136
        # do the multiplication y^T = x^T A (left eigenvector)
137
        for n in x:
138
            for nbr in G[n]:
139
                w = G[n][nbr].get(weight, 1) if weight else 1
140
                x[nbr] += xlast[n] * w
141
        # Normalize the vector. The normalization denominator `norm`
142
        # should never be zero by the Perron--Frobenius
143
        # theorem. However, in case it is due to numerical error, we
144
        # assume the norm to be one instead.
145
        norm = sqrt(sum(z ** 2 for z in x.values())) or 1
146
        x = {k: v / norm for k, v in x.items()}
147
        # Check for convergence (in the L_1 norm).
148
        if sum(abs(x[n] - xlast[n]) for n in x) < nnodes * tol:
149
            return x
150
    raise nx.PowerIterationFailedConvergence(max_iter)
151

    
152

    
153
def eigenvector_centrality_numpy(G, weight=None, max_iter=50, tol=0):
154
    r"""Compute the eigenvector centrality for the graph G.
155

156
    Eigenvector centrality computes the centrality for a node based on the
157
    centrality of its neighbors. The eigenvector centrality for node $i$ is
158

159
    .. math::
160

161
        Ax = \lambda x
162

163
    where $A$ is the adjacency matrix of the graph G with eigenvalue $\lambda$.
164
    By virtue of the Perron–Frobenius theorem, there is a unique and positive
165
    solution if $\lambda$ is the largest eigenvalue associated with the
166
    eigenvector of the adjacency matrix $A$ ([2]_).
167

168
    Parameters
169
    ----------
170
    G : graph
171
      A networkx graph
172

173
    weight : None or string, optional (default=None)
174
      The name of the edge attribute used as weight.
175
      If None, all edge weights are considered equal.
176

177
    max_iter : integer, optional (default=100)
178
      Maximum number of iterations in power method.
179

180
    tol : float, optional (default=1.0e-6)
181
       Relative accuracy for eigenvalues (stopping criterion).
182
       The default value of 0 implies machine precision.
183

184
    Returns
185
    -------
186
    nodes : dictionary
187
       Dictionary of nodes with eigenvector centrality as the value.
188

189
    Examples
190
    --------
191
    >>> G = nx.path_graph(4)
192
    >>> centrality = nx.eigenvector_centrality_numpy(G)
193
    >>> print(['{} {:0.2f}'.format(node, centrality[node]) for node in centrality])
194
    ['0 0.37', '1 0.60', '2 0.60', '3 0.37']
195

196
    See Also
197
    --------
198
    eigenvector_centrality
199
    pagerank
200
    hits
201

202
    Notes
203
    -----
204
    The measure was introduced by [1]_.
205

206
    This algorithm uses the SciPy sparse eigenvalue solver (ARPACK) to
207
    find the largest eigenvalue/eigenvector pair.
208

209
    For directed graphs this is "left" eigenvector centrality which corresponds
210
    to the in-edges in the graph. For out-edges eigenvector centrality
211
    first reverse the graph with ``G.reverse()``.
212

213
    Raises
214
    ------
215
    NetworkXPointlessConcept
216
        If the graph ``G`` is the null graph.
217

218
    References
219
    ----------
220
    .. [1] Phillip Bonacich:
221
       Power and Centrality: A Family of Measures.
222
       American Journal of Sociology 92(5):1170–1182, 1986
223
       http://www.leonidzhukov.net/hse/2014/socialnetworks/papers/Bonacich-Centrality.pdf
224
    .. [2] Mark E. J. Newman:
225
       Networks: An Introduction.
226
       Oxford University Press, USA, 2010, pp. 169.
227
    """
228
    import scipy as sp
229
    from scipy.sparse import linalg
230
    if len(G) == 0:
231
        raise nx.NetworkXPointlessConcept('cannot compute centrality for the'
232
                                          ' null graph')
233
    M = nx.to_scipy_sparse_matrix(G, nodelist=list(G), weight=weight,
234
                                  dtype=float)
235
    eigenvalue, eigenvector = linalg.eigs(M.T, k=1, which='LR',
236
                                          maxiter=max_iter, tol=tol)
237
    largest = eigenvector.flatten().real
238
    norm = sp.sign(largest.sum()) * sp.linalg.norm(largest)
239
    return dict(zip(G, largest / norm))
240

    
241

    
242
# fixture for nose tests
243
def setup_module(module):
244
    from nose import SkipTest
245
    try:
246
        import scipy
247
    except:
248
        raise SkipTest("SciPy not available")