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.
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.
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  Daire proposed an algorithm to build this trust from a bipartite graph by considering three main factors:
- The classic Jaccard index, a widely used measure to compare similarity and diversity of sample sets.
- 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.
- A probability having the same role as the teleportation factor in Page Rank .
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 , Daire ans Salim proposed a new recommendation approach and compared his engine with traditional recommenders.
The master thesis can be downloaded here.
 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.
 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.
 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.