graph_tool.centrality.eigentrust

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

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.

If enabled during compilation, this algorithm runs in parallel.

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")
<...>

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