eigentrust

Contents

eigentrust#

graph_tool.centrality.eigentrust(g, trust_map, vprop=None, norm=False, epsilon=1e-06, max_iter=0, ret_iter=False)[source]#

Calculate the eigentrust centrality of each vertex in the graph.

Parameters:
gGraph

Graph to be used.

trust_mapEdgePropertyMap

Edge property map with the values of trust associated with each edge. The values must lie in the range [0,1].

vpropVertexPropertyMap, optional (default: None)

Vertex property map where the values of eigentrust must be stored.

normbool, optional (default: False)

Norm eigentrust values so that the total sum equals 1.

epsilonfloat, optional (default: 1e-6)

Convergence condition. The iteration will stop if the total delta of all vertices are below this value.

max_iterint, optional (default: None)

If supplied, this will limit the total number of iterations.

ret_iterbool, optional (default: False)

If true, the total number of iterations is also returned.

Returns:
eigentrustVertexPropertyMap

A vertex property map containing the eigentrust values.

See also

betweenness

betweenness centrality

pagerank

PageRank centrality

trust_transitivity

pervasive trust transitivity

Notes

The eigentrust [kamvar-eigentrust-2003] values \(t_i\) correspond the following limit

\[\mathbf{t} = \lim_{n\to\infty} \left(C^T\right)^n \mathbf{c}\]

where \(c_i = 1/|V|\) and the elements of the matrix \(C\) are the normalized trust values:

\[c_{ij} = \frac{\max(s_{ij},0)}{\sum_{j} \max(s_{ij}, 0)}\]

The algorithm has a topology-dependent complexity.

Parallel implementation.

If enabled during compilation, this algorithm will run in parallel using OpenMP. See the parallel algorithms section for information about how to control several aspects of parallelization.

References

[kamvar-eigentrust-2003]

S. D. Kamvar, M. T. Schlosser, H. Garcia-Molina “The eigentrust algorithm for reputation management in p2p networks”, Proceedings of the 12th international conference on World Wide Web, Pages: 640 - 651, 2003, DOI: 10.1145/775152.775242 [sci-hub, @tor]

[adamic-polblogs]

L. A. Adamic and N. Glance, “The political blogosphere and the 2004 US Election”, in Proceedings of the WWW-2005 Workshop on the Weblogging Ecosystem (2005). DOI: 10.1145/1134271.1134277 [sci-hub, @tor]

Examples

>>> g = gt.collection.data["polblogs"]
>>> g = gt.GraphView(g, vfilt=gt.label_largest_component(g))
>>> w = g.new_edge_property("double")
>>> w.a = np.random.random(len(w.a)) * 42
>>> t = gt.eigentrust(g, w)
>>> gt.graph_draw(g, pos=g.vp["pos"], vertex_fill_color=t,
...               vertex_size=gt.prop_to_size(t, mi=5, ma=15),
...               vcmap=matplotlib.cm.gist_heat,
...               vorder=t, output="polblogs_eigentrust.pdf")
<...>
../_images/polblogs_eigentrust.png

Eigentrust values of the a political blogs network of [adamic-polblogs], with random weights attributed to the edges.#

Contents