Skip to content

Structural trust inference for social recommendation

Every year EURA NOVA proposes and leads Master thesis with Faculty of Science Engineering of Belgian Universities. In this post I will quickly come back on one of those master thesis organized with the Polytechnic School of Louvain-La-Neuve and I will give an high level overview of the Daire O’Doherty’s work.

Trust Inference

The objective is to define a method for building trust from structural graph properties. The idea is to start with a bipartite graph as the graph user-item represented by Figure 1.

Figure 1: a bipartite graph with a set if Users and Items, on which the users are connected to Items (1).
Figure 1: a bipartite graph with a set if Users and Items, on which the users are connected to Items (1).

In this kind of graph the users are not directly linked each other, instead they are linked to items. On those links, we can find rating information.

The trust is a measure of reliability defining the probability that two users will have same taste. Therefore, they can trust each other. The whole idea of this work is “can we define a structural graph analysis enabling to infer trust?”

In [1] Daire proposed an algorithm to build this trust from a bipartite graph by considering three main factors:

  1. The classic Jaccard index, a widely used measure to compare similarity and diversity of sample sets.

  1. The intuition that shared item by a lot of users is meaningless. Then, we need a distance between vertices in set of users in relation to the popularity of the vertices in set of items.


  1. A probability having the same role as the teleportation factor in Page Rank [2].

As a result the final formula of the Trust computation is defined by:


Using trust for recommendation

An interesting application of the trust computing is a better targeted recommendation. Therefore, a new kind of recommendation which takes into account the trust between users can be designed. In [3], Daire ans Salim proposed a new recommendation approach and compared his engine with traditional recommenders.

The master thesis can be downloaded here.


[1] Daire O’Doherty, Salim Jouili, and Peter Van Roy. Towards trust inference in bipartite social networks. In Proceedings of the Second ACM SIGMOD Workshop on Databases and Social Networks, DBSocial 2012, Scottsdale, USA, ACM, 2012.

[2] L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab, November 1999.

[3] Daire O’Doherty, Salim Jouili, and Peter Van Roy. Trust-based recommendation: an empirical analysis. In Submitted to: Proceedings of the Sixth ACM SIGKDD Workshop on  Social Network Mining and Analysis SNA-KDD, Beijing, China, ACM, 2012.


Releated Posts

Calibrate to Interpret

Trustworthy machine learning is driving a large number of the ML community works in order to improve ML acceptance and adoption. In this paper, we show a first link between uncertainty and explainability, by studying the relation between calibration and interpretation.
Read More

Mass Estimation of Planck Galaxy Clusters using Deep Learning

Galaxy cluster masses can be inferred indirectly using measurements from X-ray band, Sunyaev-Zeldovich (SZ) effect signal or optical observations. Unfortunately, all of them are affected by some bias. Alternatively, we provide an independent estimation of the cluster masses from the Planck PSZ2 catalogue of galaxy clusters using a machine-learning method.
Read More