__init__.py 23.8 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
#! /usr/bin/env python
2
# -*- coding: utf-8 -*-
Tiago Peixoto's avatar
Tiago Peixoto committed
3
#
4
5
# graph_tool -- a general graph manipulation python module
#
Tiago Peixoto's avatar
Tiago Peixoto committed
6
# Copyright (C) 2007-2011 Tiago de Paula Peixoto <tiago@skewed.de>
Tiago Peixoto's avatar
Tiago Peixoto committed
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

21
"""
22
23
``graph_tool.centrality`` - Centrality measures
-----------------------------------------------
24
25

This module includes centrality-related algorithms.
26
27
28
29
30
31
32
33
34
35
36

Summary
+++++++

.. autosummary::
   :nosignatures:

   pagerank
   betweenness
   central_point_dominance
   eigentrust
37
   trust_transitivity
38
39
40

Contents
++++++++
41
42
"""

Tiago Peixoto's avatar
Tiago Peixoto committed
43
44
45
from .. dl_import import dl_import
dl_import("import libgraph_tool_centrality")

46
from .. import _prop, ungroup_vector_property
Tiago Peixoto's avatar
Tiago Peixoto committed
47
48
import sys
import numpy
Tiago Peixoto's avatar
Tiago Peixoto committed
49
50

__all__ = ["pagerank", "betweenness", "central_point_dominance", "eigentrust",
51
           "trust_transitivity"]
Tiago Peixoto's avatar
Tiago Peixoto committed
52

Tiago Peixoto's avatar
Tiago Peixoto committed
53

54
55
def pagerank(g, damping=0.85, pers=None, weight=None, prop=None, epsilon=1e-6,
             max_iter=None, ret_iter=False):
56
57
58
59
60
    r"""
    Calculate the PageRank of each vertex.

    Parameters
    ----------
61
    g : :class:`~graph_tool.Graph`
62
        Graph to be used.
63
    damping : float, optional (default: 0.85)
64
        Damping factor.
65
66
67
68
69
    pers : :class:`~graph_tool.PropertyMap`, optional (default: None)
        Personalization vector. If omitted, a constant value of :math:`1/N`
        will be used.
    weight : :class:`~graph_tool.PropertyMap`, optional (default: None)
        Edge weights. If omitted, a constant value of 1 will be used.
70
    prop : :class:`~graph_tool.PropertyMap`, optional (default: None)
71
        Vertex property map to store the PageRank values.
Tiago Peixoto's avatar
Tiago Peixoto committed
72
    epsilon : float, optional (default: 1e-6)
73
74
75
76
77
78
79
80
81
        Convergence condition. The iteration will stop if the total delta of all
        vertices are below this value.
    max_iter : int, optional (default: None)
        If supplied, this will limit the total number of iterations.
    ret_iter : bool, optional (default: False)
        If true, the total number of iterations is also returned.

    Returns
    -------
82
83
    pagerank : :class:`~graph_tool.PropertyMap`
        A vertex property map containing the PageRank values.
84
85
86
87
88

    See Also
    --------
    betweenness: betweenness centrality
    eigentrust: eigentrust centrality
89
    trust_transitivity: pervasive trust transitivity
90
91
92

    Notes
    -----
Tiago Peixoto's avatar
Tiago Peixoto committed
93
94
    The value of PageRank [pagerank-wikipedia]_ of vertex v, :math:`PR(v)`, is
    given iteratively by the relation:
95
96

    .. math::
97

98
99
        PR(v) = \frac{1-d}{N} + d \sum_{u \in \Gamma^{-}(v)}
                \frac{PR (u)}{d^{+}(u)}
100
101
102
103

    where :math:`\Gamma^{-}(v)` are the in-neighbours of v, :math:`d^{+}(w)` is
    the out-degree of w, and d is a damping factor.

104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
    If a personalization property :math:`p(v)` is given, the definition becomes:

    .. math::

        PR(v) = (1-d)p(v) + d \sum_{u \in \Gamma^{-}(v)}
                \frac{PR (u)}{d^{+}(u)}

    If edge weights are also given, the equation is then generalized to:

    .. math::

        PR(v) = (1-d)p(v) + d \sum_{u \in \Gamma^{-}(v)}
                \frac{PR (u) w_{u\to v}}{d^{+}(u)}

    where :math:`d^{+}(u)=\sum_{y}A_{u,y}w_{u\to y}` is redefined to be the sum
    of the weights of the out-going edges from u.

    The implemented algorithm progressively iterates the above equations, until
Tiago Peixoto's avatar
Tiago Peixoto committed
122
    it no longer changes, according to the parameter epsilon. It has a
123
124
125
126
127
128
    topology-dependent running time.

    If enabled during compilation, this algorithm runs in parallel.

    Examples
    --------
129
    >>> from numpy.random import random, poisson, seed
130
    >>> seed(42)
131
    >>> g = gt.random_graph(100, lambda: (poisson(3), poisson(3)))
132
    >>> pr = gt.pagerank(g)
133
    >>> print pr.a
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
    [ 0.00782362  0.01642353  0.00420484  0.0038825   0.0015      0.01145378
      0.00514203  0.00593481  0.00743705  0.00785063  0.00446447  0.00440222
      0.00684158  0.00463226  0.00518308  0.0056288   0.01207045  0.00617264
      0.00958574  0.00817165  0.01041552  0.00508079  0.0015      0.00249411
      0.00842537  0.00293099  0.00873296  0.001755    0.003371    0.00817938
      0.00406813  0.00576584  0.01188752  0.00674565  0.00758134  0.00855306
      0.00975204  0.00823918  0.00209855  0.00753858  0.0015      0.001925
      0.00593262  0.00603431  0.00977679  0.00707922  0.00529399  0.01048882
      0.001755    0.0111949   0.0032813   0.01591077  0.00407595  0.01015827
      0.00383036  0.01024311  0.00714593  0.00379142  0.00955729  0.001925
      0.00737848  0.00352088  0.00654273  0.00676324  0.00353259  0.0015
      0.00809045  0.00864939  0.00626611  0.00632213  0.00939761  0.0015
      0.00584767  0.0077272   0.00688094  0.01010526  0.01071083  0.00550524
      0.0045327   0.00577072  0.00337711  0.00637928  0.01295484  0.0015
      0.00265875  0.003245    0.00203456  0.00969993  0.00908983  0.00759961
      0.00428542  0.00674196  0.0043264   0.01339053  0.00570051  0.00253539
      0.01464169  0.00505055  0.01919599  0.01413612]

    Now with a personalization vector, and edge weights:

    >>> w = g.new_edge_property("double")
    >>> w.a = random(g.num_edges())
    >>> p = g.new_vertex_property("double")
    >>> p.a = random(g.num_vertices())
    >>> p.a /= p.a.sum()
    >>> pr = gt.pagerank(g, pers=p, weight=w)
    >>> print pr.a
    [ 0.01693559  0.01316915  0.00369907  0.00245658  0.00092715  0.01380721
      0.00703909  0.00407121  0.00816254  0.00880131  0.0035886   0.0050914
      0.00815843  0.00624021  0.0069828   0.00647311  0.01260669  0.00884083
      0.01324534  0.01103024  0.01417902  0.00309344  0.00250025  0.00153889
      0.00969556  0.00491575  0.00552323  0.00300698  0.00327355  0.00829017
      0.00274335  0.00440865  0.01436394  0.00671045  0.00788395  0.01092875
      0.0126331   0.00789263  0.00422443  0.00745144  0.00148972  0.00198663
      0.00476339  0.00800871  0.01468149  0.00971962  0.00446663  0.01333257
      0.00085768  0.01044298  0.00286075  0.02119469  0.00406517  0.01317145
      0.00280023  0.0143227   0.00867722  0.00234863  0.01180399  0.00298827
      0.0049022   0.00532752  0.00603759  0.00766617  0.00293739  0.00238803
      0.00863735  0.01110095  0.00660816  0.00170262  0.00884469  0.00300867
      0.00441168  0.00630793  0.00424727  0.00906709  0.0135949   0.00890726
      0.00267835  0.00615783  0.0045653   0.00720592  0.00996495  0.0009367
      0.00233309  0.00265909  0.00211686  0.01277934  0.01284484  0.00625721
      0.00487027  0.00852522  0.00403389  0.01817233  0.00573321  0.0038696
      0.00932334  0.00515806  0.01601592  0.0167547 ]
178
179
180

    References
    ----------
181
182
    .. [pagerank-wikipedia] http://en.wikipedia.org/wiki/Pagerank
    .. [lawrence-pagerank-1998] P. Lawrence, B. Sergey, M. Rajeev, W. Terry,
183
       "The pagerank citation ranking: Bringing order to the web", Technical
184
       report, Stanford University, 1998
185
186
187
    .. [Langville-survey-2005] A. N. Langville, C. D. Meyer, "A Survey of
       Eigenvector Methods for Web Information Retrieval", SIAM Review, vol. 47,
       no. 1, pp. 135-161, 2005, :DOI:`10.1137/S0036144503424786`
188
189
190
191
    """

    if max_iter == None:
        max_iter = 0
Tiago Peixoto's avatar
Tiago Peixoto committed
192
193
194
    if prop == None:
        prop = g.new_vertex_property("double")
    ic = libgraph_tool_centrality.\
195
196
197
            get_pagerank(g._Graph__graph, _prop("v", g, prop),
                         _prop("v", g, pers), _prop("e", g, weight),
                         damping, epsilon, max_iter)
Tiago Peixoto's avatar
Tiago Peixoto committed
198
199
200
201
202
    if ret_iter:
        return prop, ic
    else:
        return prop

Tiago Peixoto's avatar
Tiago Peixoto committed
203

204
205
206
207
208
209
def betweenness(g, vprop=None, eprop=None, weight=None, norm=True):
    r"""
    Calculate the betweenness centrality for each vertex and edge.

    Parameters
    ----------
210
    g : :class:`~graph_tool.Graph`
211
        Graph to be used.
212
    vprop : :class:`~graph_tool.PropertyMap`, optional (default: None)
213
        Vertex property map to store the vertex betweenness values.
214
    eprop : :class:`~graph_tool.PropertyMap`, optional (default: None)
215
        Edge property map to store the edge betweenness values.
216
    weight : :class:`~graph_tool.PropertyMap`, optional (default: None)
217
218
219
220
221
222
        Edge property map corresponding to the weight value of each edge.
    norm : bool, optional (default: True)
        Whether or not the betweenness values should be normalized.

    Returns
    -------
Tiago Peixoto's avatar
Tiago Peixoto committed
223
224
    vertex_betweenness : A vertex property map with the vertex betweenness values.
    edge_betweenness : An edge property map with the edge betweenness values.
225
226
227
228
229
230

    See Also
    --------
    central_point_dominance: central point dominance of the graph
    pagerank: PageRank centrality
    eigentrust: eigentrust centrality
231
    trust_transitivity: pervasive trust transitivity
232
233
234
235
236

    Notes
    -----
    Betweenness centrality of a vertex :math:`C_B(v)` is defined as,

237
238
    .. math::

239
240
241
242
243
244
245
246
247
        C_B(v)= \sum_{s \neq v \neq t \in V \atop s \neq t}
                \frac{\sigma_{st}(v)}{\sigma_{st}}

    where :math:`\sigma_{st}` is the number of shortest geodesic paths from s to
    t, and :math:`\sigma_{st}(v)` is the number of shortest geodesic paths from
    s to t that pass through a vertex v.  This may be normalised by dividing
    through the number of pairs of vertices not including v, which is
    :math:`(n-1)(n-2)/2`.

248
    The algorithm used here is defined in [brandes-faster-2001]_, and has a
249
250
251
252
253
254
255
    complexity of :math:`O(VE)` for unweighted graphs and :math:`O(VE + V(V+E)
    \log V)` for weighted graphs. The space complexity is :math:`O(VE)`.

    If enabled during compilation, this algorithm runs in parallel.

    Examples
    --------
256
257
    >>> from numpy.random import poisson, seed
    >>> seed(42)
258
    >>> g = gt.random_graph(100, lambda: (poisson(3), poisson(3)))
259
    >>> vb, eb = gt.betweenness(g)
260
    >>> print vb.a
Tiago Peixoto's avatar
Tiago Peixoto committed
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
    [  2.65012897e-02   1.04414799e-01   2.73374899e-02   1.52782183e-02
       0.00000000e+00   2.74548352e-02   3.54680121e-02   3.72671558e-02
       2.39732112e-02   2.34942149e-02   2.97950758e-02   4.08351383e-02
       4.31702840e-02   1.90317902e-02   3.66879750e-02   8.65571818e-03
       0.00000000e+00   3.74046494e-02   4.22428130e-02   2.10503176e-02
       1.39558854e-02   8.40349783e-03   0.00000000e+00   4.45784374e-03
       3.38671970e-02   1.72390157e-02   4.82232543e-02   1.03071532e-04
       1.42200266e-02   4.82793598e-02   1.82020235e-02   0.00000000e+00
       7.04969679e-02   2.31267158e-02   6.42817952e-02   3.71139131e-02
       3.81618985e-02   4.06231715e-02   2.16376594e-03   2.44758076e-02
       0.00000000e+00   6.86198722e-03   1.36132952e-02   1.73886977e-02
       2.30213129e-02   4.44999980e-02   0.00000000e+00   1.40589569e-02
       0.00000000e+00   4.74213177e-02   2.65427674e-02   1.05684330e-01
       6.30552365e-03   2.86320444e-02   4.50079022e-03   7.76843152e-02
       2.88642900e-02   3.52207159e-02   2.01852506e-02   9.26784855e-04
       4.35733012e-02   1.84745904e-02   1.35102237e-02   2.69638287e-02
       1.88247064e-02   0.00000000e+00   2.03784688e-02   4.14981678e-02
       1.79538495e-02   1.12983577e-02   3.23765203e-02   0.00000000e+00
       3.99771399e-02   2.85164571e-03   2.18967289e-02   3.96111705e-02
       3.40096863e-02   1.72800650e-02   1.36861815e-02   0.00000000e+00
       1.19328203e-02   1.71726485e-02   0.00000000e+00   0.00000000e+00
       6.33251858e-03   4.64324980e-03   1.33084980e-03   9.89021626e-02
       3.52934995e-02   2.96267777e-02   1.73480268e-02   3.07545000e-02
       2.47891161e-02   3.32486832e-02   7.45403501e-03   1.46792267e-02
       0.00000000e+00   3.35642472e-02   8.78597450e-02   3.94517740e-02]
286
287
288

    References
    ----------
289
290
    .. [betweenness-wikipedia] http://en.wikipedia.org/wiki/Centrality#Betweenness_centrality
    .. [brandes-faster-2001] U. Brandes, "A faster algorithm for betweenness
Tiago Peixoto's avatar
Tiago Peixoto committed
291
       centrality", Journal of Mathematical Sociology, 2001, :doi:`10.1080/0022250X.2001.9990249`
292
    """
Tiago Peixoto's avatar
Tiago Peixoto committed
293
294
295
296
297
298
299
300
301
302
303
304
305
    if vprop == None:
        vprop = g.new_vertex_property("double")
    if eprop == None:
        eprop = g.new_edge_property("double")
    if weight != None and weight.value_type() != eprop.value_type():
        nw = g.new_edge_property(eprop.value_type())
        g.copy_property(weight, nw)
        weight = nw
    libgraph_tool_centrality.\
            get_betweenness(g._Graph__graph, _prop("e", g, weight),
                            _prop("e", g, eprop), _prop("v", g, vprop), norm)
    return vprop, eprop

Tiago Peixoto's avatar
Tiago Peixoto committed
306

Tiago Peixoto's avatar
Tiago Peixoto committed
307
def central_point_dominance(g, betweenness):
308
309
310
311
312
313
    r"""
    Calculate the central point dominance of the graph, given the betweenness
    centrality of each vertex.

    Parameters
    ----------
314
    g : :class:`~graph_tool.Graph`
315
        Graph to be used.
316
    betweenness : :class:`~graph_tool.PropertyMap`
317
318
319
320
321
        Vertex property map with the betweenness centrality values. The values
        must be normalized.

    Returns
    -------
322
323
    cp : float
        The central point dominance.
324
325
326
327
328
329
330
331

    See Also
    --------
    betweenness: betweenness centrality

    Notes
    -----
    Let :math:`v^*` be the vertex with the largest relative betweenness
332
    centrality; then, the central point dominance [freeman-set-1977]_ is defined
333
334
    as:

335
336
    .. math::

337
338
339
340
341
342
343
344
345
        C'_B = \frac{1}{|V|-1} \sum_{v} C_B(v^*) - C_B(v)

    where :math:`C_B(v)` is the normalized betweenness centrality of vertex
    v. The value of :math:`C_B` lies in the range [0,1].

    The algorithm has a complexity of :math:`O(V)`.

    Examples
    --------
346
347
    >>> from numpy.random import poisson, seed
    >>> seed(42)
348
    >>> g = gt.random_graph(100, lambda: (poisson(3), poisson(3)))
349
350
    >>> vb, eb = gt.betweenness(g)
    >>> print gt.central_point_dominance(g, vb)
Tiago Peixoto's avatar
Tiago Peixoto committed
351
    0.0813233725942
352
353
354

    References
    ----------
355
    .. [freeman-set-1977] Linton C. Freeman, "A Set of Measures of Centrality
Tiago Peixoto's avatar
Tiago Peixoto committed
356
357
       Based on Betweenness", Sociometry, Vol. 40, No. 1,  pp. 35-41, 1977,
       `http://www.jstor.org/stable/3033543 <http://www.jstor.org/stable/3033543>`_
358
359
    """

Tiago Peixoto's avatar
Tiago Peixoto committed
360
    return libgraph_tool_centrality.\
361
           get_central_point_dominance(g._Graph__graph,
Tiago Peixoto's avatar
Tiago Peixoto committed
362
363
                                       _prop("v", g, betweenness))

364

Tiago Peixoto's avatar
Tiago Peixoto committed
365
def eigentrust(g, trust_map, vprop=None, norm=False, epsilon=1e-6, max_iter=0,
Tiago Peixoto's avatar
Tiago Peixoto committed
366
               ret_iter=False):
367
368
369
370
371
    r"""
    Calculate the eigentrust centrality of each vertex in the graph.

    Parameters
    ----------
372
    g : :class:`~graph_tool.Graph`
373
        Graph to be used.
374
    trust_map : :class:`~graph_tool.PropertyMap`
375
        Edge property map with the values of trust associated with each
376
        edge. The values must lie in the range [0,1].
377
378
379
380
    vprop : PropertyMap, optional (default: None)
        Vertex property map where the values of eigentrust must be stored.
    norm : bool, optional (default: false)
        Norm eigentrust values so that the total sum equals 1.
Tiago Peixoto's avatar
Tiago Peixoto committed
381
    epsilon : float, optional (default: 1e-6)
382
383
384
385
386
387
388
389
390
        Convergence condition. The iteration will stop if the total delta of all
        vertices are below this value.
    max_iter : int, optional (default: None)
        If supplied, this will limit the total number of iterations.
    ret_iter : bool, optional (default: False)
        If true, the total number of iterations is also returned.

    Returns
    -------
391
    eigentrust : A vertex property map containing the eigentrust values.
392
393
394
395
396

    See Also
    --------
    betweenness: betweenness centrality
    pagerank: PageRank centrality
397
    trust_transitivity: pervasive trust transitivity
398
399
400

    Notes
    -----
401
    The eigentrust [kamvar-eigentrust-2003]_ values :math:`t_i` correspond the
402
403
    following limit

404
405
    .. math::

406
407
408
409
410
        \mathbf{t} = \lim_{n\to\infty} \left(C^T\right)^n \mathbf{c}

    where :math:`c_i = 1/|V|` and the elements of the matrix :math:`C` are the
    normalized trust values:

411
412
    .. math::

413
414
415
416
417
418
419
420
421
422
        c_{ij} = \frac{\max(s_{ij},0)}{\sum_{j} \max(s_{ij}, 0)}

    The algorithm has a topology-dependent complexity.

    If enabled during compilation, this algorithm runs in parallel.

    Examples
    --------
    >>> from numpy.random import poisson, random, seed
    >>> seed(42)
423
    >>> g = gt.random_graph(100, lambda: (poisson(3), poisson(3)))
424
425
    >>> trust = g.new_edge_property("double")
    >>> trust.get_array()[:] = random(g.num_edges())*42
426
    >>> t = gt.eigentrust(g, trust, norm=True)
427
    >>> print t.get_array()
Tiago Peixoto's avatar
Tiago Peixoto committed
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
    [ 0.02100449  0.01735932  0.00227182  0.00342703  0.          0.01739914
      0.00658874  0.00592764  0.00879695  0.01483758  0.00390145  0.00939709
      0.01038803  0.00896039  0.0080222   0.00583084  0.01510505  0.01106463
      0.02048866  0.0179936   0.02196625  0.00604554  0.          0.00038504
      0.01704679  0.00431482  0.00538866  0.          0.00163772  0.02009726
      0.00254747  0.00440903  0.02305541  0.01061566  0.00583414  0.01521545
      0.01894677  0.00941793  0.00259066  0.00454916  0.          0.
      0.00411855  0.01005776  0.029152    0.01500648  0.00797009  0.02057446
      0.          0.02100182  0.00519358  0.02503401  0.00368714  0.02176737
      0.00111934  0.02763714  0.00615445  0.00163793  0.01998869  0.
      0.00831816  0.00692008  0.00439715  0.01287125  0.00534507  0.
      0.00805071  0.02094972  0.00622514  0.00285397  0.01009464  0.
      0.00360911  0.00653993  0.00800227  0.01521205  0.02901848  0.01693622
      0.00323205  0.00748302  0.00443795  0.0076314   0.01147831  0.
      0.00129362  0.00173367  0.00188625  0.02110825  0.01349257  0.00956502
      0.00694694  0.01780551  0.00344632  0.02869166  0.00388418  0.0016279
      0.01691452  0.00783781  0.02795918  0.03327071]
445
446
447

    References
    ----------
448
    .. [kamvar-eigentrust-2003] S. D. Kamvar, M. T. Schlosser, H. Garcia-Molina
449
450
       "The eigentrust algorithm for reputation management in p2p networks",
       Proceedings of the 12th international conference on World Wide Web,
Tiago Peixoto's avatar
Tiago Peixoto committed
451
       Pages: 640 - 651, 2003, :doi:`10.1145/775152.775242`
452
453
    """

Tiago Peixoto's avatar
Tiago Peixoto committed
454
455
    if vprop == None:
        vprop = g.new_vertex_property("double")
456
457
    i = libgraph_tool_centrality.\
           get_eigentrust(g._Graph__graph, _prop("e", g, trust_map),
Tiago Peixoto's avatar
Tiago Peixoto committed
458
                          _prop("v", g, vprop), epsilon, max_iter)
459
460
461
462
463
464
465
466
    if norm:
        vprop.get_array()[:] /= sum(vprop.get_array())

    if ret_iter:
        return vprop, i
    else:
        return vprop

Tiago Peixoto's avatar
Tiago Peixoto committed
467

468
def trust_transitivity(g, trust_map, source=None, target=None, vprop=None):
469
    r"""
470
471
    Calculate the pervasive trust transitivity between chosen (or all) vertices
    in the graph.
472
473
474

    Parameters
    ----------
475
    g : :class:`~graph_tool.Graph`
476
        Graph to be used.
477
    trust_map : :class:`~graph_tool.PropertyMap`
478
479
        Edge property map with the values of trust associated with each
        edge. The values must lie in the range [0,1].
Tiago Peixoto's avatar
Tiago Peixoto committed
480
    source : :class:`~graph_tool.Vertex` (optional, default: None)
481
        Source vertex. All trust values are computed relative to this vertex.
482
        If left unspecified, the trust values for all sources are computed.
Tiago Peixoto's avatar
Tiago Peixoto committed
483
    target : :class:`~graph_tool.Vertex` (optional, default: None)
484
485
486
        The only target for which the trust value will be calculated. If left
        unspecified, the trust values for all targets are computed.
    vprop : :class:`~graph_tool.PropertyMap` (optional, default: None)
487
488
        A vertex property map where the values of transitive trust must be
        stored.
489
490
491

    Returns
    -------
492
493
494
495
496
497
498
499
    trust_transitivity : :class:`~graph_tool.PropertyMap` or float
        A vertex vector property map containing, for each source vertex, a
        vector with the trust values for the other vertices. If only one of
        `source` or `target` is specified, this will be a single-valued vertex
        property map containing the trust vector from/to the source/target
        vertex to/from the rest of the network. If both `source` and `target`
        are specified, the result is a single float, with the corresponding
        trust value for the target.
500

501
502
503
504
505
506
507
508
    See Also
    --------
    eigentrust: eigentrust centrality
    betweenness: betweenness centrality
    pagerank: PageRank centrality

    Notes
    -----
Tiago Peixoto's avatar
Tiago Peixoto committed
509
    The pervasive trust transitivity between vertices i and j is defined as
510

511
512
    .. math::

513
514
        t_{ij} = \frac{\sum_m A_{m,j} w^2_{G\setminus\{j\}}(i\to m)c_{m,j}}
                 {\sum_m A_{m,j} w_{G\setminus\{j\}}(i\to m)}
515

516
517
518
    where :math:`A_{ij}` is the adjacency matrix, :math:`c_{ij}` is the direct
    trust from i to j, and :math:`w_G(i\to j)` is the weight of the path with
    maximum weight from i to j, computed as
Tiago Peixoto's avatar
Tiago Peixoto committed
519

520
521
    .. math::

522
       w_G(i\to j) = \prod_{e\in i\to j} c_e.
523

524
525
    The algorithm measures the transitive trust by finding the paths with
    maximum weight, using Dijkstra's algorithm, to all in-neighbours of a given
526
    target. This search needs to be performed repeatedly for every target, since
527
528
529
530
531
532
533
    it needs to be removed from the graph first. For each given source, the
    resulting complexity is therefore :math:`O(N^2\log N)` for all targets, and
    :math:`O(N\log N)` for a single target. For a given target, the complexity
    for obtaining the trust from all given sources is :math:`O(kN\log N)`, where
    :math:`k` is the in-degree of the target. Thus, the complexity for obtaining
    the complete trust matrix is :math:`O(EN\log N)`, where :math:`E` is the
    number of edges in the network.
534
535
536
537
538
539
540

    If enabled during compilation, this algorithm runs in parallel.

    Examples
    --------
    >>> from numpy.random import poisson, random, seed
    >>> seed(42)
541
    >>> g = gt.random_graph(100, lambda: (poisson(3), poisson(3)))
542
    >>> trust = g.new_edge_property("double")
543
    >>> trust.a = random(g.num_edges())
544
    >>> t = gt.trust_transitivity(g, trust, source=g.vertex(0))
545
    >>> print t.a
Tiago Peixoto's avatar
Tiago Peixoto committed
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
    [ 1.          0.09649648  0.01375374  0.09864347  0.          0.52668732
      0.02655169  0.05771735  0.25651251  0.13071344  0.1258206   0.13065921
      0.12051013  0.13754053  0.26727787  0.06951245  0.38774441  0.25343023
      0.21297027  0.59232433  0.10843174  0.02810649  0.          0.04000351
      0.13784095  0.06125175  0.04156937  0.          0.05771925  0.04967184
      0.11251086  0.25172931  0.1982562   0.28225643  0.05339001  0.10629504
      0.04440744  0.05815895  0.097983    0.03333347  0.          0.
      0.10845473  0.13751647  0.27567139  0.03946153  0.25063883  0.0755547   0.
      0.25167962  0.33205973  0.08237051  0.12983804  0.02587608  0.09694727
      0.16435599  0.09445501  0.07402817  0.06425702  0.          0.22420236
      0.11284837  0.05567628  0.0561254   0.36563496  0.          0.09358333
      0.06315609  0.3853858   0.01338133  0.08506159  0.          0.23226712
      0.0841518   0.07274848  0.17553984  0.14032908  0.15737553  0.13703351
      0.25035262  0.03570828  0.04341688  0.11955905  0.          0.01757771
      0.04990193  0.10457395  0.41668972  0.04546921  0.04404905  0.24922167
      0.09752267  0.03872946  0.26113888  0.04677363  0.03220735  0.03928181
      0.08696124  0.21697483  0.1388346 ]

    References
    ----------
    .. [richters-trust-2010] Oliver Richters, Tiago P. Peixoto, "Trust
       transitivity in social networks", :arXiv:`1012.1358`, 2010

569
    """
Tiago Peixoto's avatar
Tiago Peixoto committed
570
571

    if vprop == None:
572
        vprop = g.new_vertex_property("vector<double>")
573

574
575
576
577
    if target == None:
        target = -1
    else:
        target = g.vertex_index[target]
578

579
580
581
582
583
    if source == None:
        source = -1
    else:
        source = g.vertex_index[source]

584
    libgraph_tool_centrality.\
585
586
587
588
            get_trust_transitivity(g._Graph__graph, source, target,
                                   _prop("e", g, trust_map),
                                   _prop("v", g, vprop))
    if target != -1 or source != -1:
589
        vprop = ungroup_vector_property(vprop, [0])[0]
590
    if target != -1 and source != -1:
591
        return vprop.a[target]
592
    return vprop