Context-Aware Recommender Systems for Opportunistic Environments

(1)

UNIVERSITÁ DIPISA

DOTTORATO DI RICERCA ININGEGNERIA DELL’INFORMAZIONE

C

ONTEXT

-A

WARE

R

ECOMMENDER

S

YSTEMS FOR

OPPORTUNISTIC

ENVIRONMENTS

DOCTORALTHESIS

Author

Mattia Giovanni Campana

Tutor (s)

Dr. Enrico Gregori, Dr. Franca Delmastro

Reviewer (s)

Prof. Gaia Maselli, Prof. Salil Kanhere

The Coordinator of the PhD Program

Prof. Marco Luise

Pisa, October 2018 Cycle XXXI

(2)

(3)

“Trust in progress, which is always right, even when it is wrong, because it is motion, life, struggle, and hope.” Filippo Tommaso Marinetti

(4)

(5)

Acknowledgements

F

IRSTLY, I would like to express my sincere gratitude to my advisor Dr. Franca Del-mastro for the continuous support during my Ph.D. study and related research, for her patience and motivation. She always gave me the freedom to choose the research topics on my own, and guided me in every aspect of my study. She helped me throughout the research and writing of this thesis. I could not have imagined having a better advisor and mentor for my Ph.D.

Besides my advisor, I am also grateful to Prof. Elena Pagani and Dr. Valerio Arn-aboldi for enlightening me the first glance of research. They encouraged me to continue my studies, and I had the opportunity to learn a lot from them. I would also like to thank the reviewers Prof. Gaia Maselli and Prof. Salil Kanhere for their insightful comments and encouragement.

My sincere thanks also go to Prof. Pan Hui and Dr. Dimitris Chatzopoulos from the Hong Kong University of Science and Technology, who provided me the invaluable opportunity to join their great research team as an intern. I will never forget the time spent together, and I truly hope to have the opportunity to work again with them in the future.

Last but not least, I thank my fellow labmates Flavio Dimartino, Mustafa Toprack (aka Musty), Kilian Ollivier (aka Kiky), and Vahid Zolfaghari for the stimulating dis-cussions, the meaningless conversations, the hundreds of cigarettes and coffees shared together, and for all the fun we have had in the last years. A special thanks goes to Laura for all the good time spent together. There are only a few people I will never forget, and she is definitely one of them.

(6)

(7)

Summary

C

ONNECTEDsmart devices are now pervasive and they represent an important part

of our daily lives. The widespread diffusion of these devices greatly contributes to the rapid expansion and evolution of the Internet at its edges, where personal mobile devices follow the behaviour of their human users and can interact with other smart objects located in the surroundings. This phenomenon paves the way towards the emergence of a new and more human-centric Internet paradigm called Internet of People (IoP), in which humans and their personal mobile devices are not seen merely as end users of applications, but they become active elements of the whole network.

According to IoP, data transmission leverages on both the Internet core and direct communications among devices in proximity. Indeed, mobile devices can opportunis-tically exploit both the mobility of their human users and their physical contacts to discover and share information among each other by using self-organising wireless net-works, without relying on any centralised infrastructure. Moreover, humans and their personal devices can leverage direct communications also to share their computational resources and to establish new physical and virtual relationships with other people and devices. In this thesis, we generally refer to Opportunistic Environments as the combi-nation of all the aforementioned characteristics of the envisioned future Internet, where mobile devices opportunistically exploit their smart features and the surrounding envi-ronment to provide personalised services to their human users.

One of the most critical challenges in the opportunistic environment is the identifi-cation of the relevant information for the user. In fact, in this scenario, users can poten-tially access a massive quantity of data coming from either remote servers or devices in proximity. Moreover, the actual utility of the discovered contents typically depends on the current situation in which the user is involved. Traditional approaches for data dissemination in self-organising networks are based on publish/subscribe mechanisms, assuming that user’s preferences are well-defined a priori in content categories and her device should collect all the contents related to these categories. However, in the real world, users’ interests are not static, but they change over time and they often depend on the situation in which the user is currently involved and the other people in the nearby. In this scenario, mobile devices must be able to act as avatars of their respective

(8)

hu-man users by exploring congested cyber landscapes and filtering the available contents according to their preferences and contexts.

In this dissertation, we design and analyse a new human-centric approach to iden-tify relevant contents for the users in opportunistic environments, based on the use of Context-Aware Recommender Systems(CARS). CARS represent a specific type of Rec-ommender Systems that exploits information related to the user context to provide more accurate and personalised recommendations, based on the situation in which the user is currently involved. CARS for centralised architectures has been widely studied in the literature, and several solutions have been proposed during the last years to address different target domains by exploiting various context information. On the other hand, their use in highly distributed environments is still in its infancy, and ad-hoc solutions that fit the unique characteristics of the opportunistic scenario are required. The main difference between CARS for centralised and distributed environments relies on the knowledge they can use to provide recommendations to the user. While centralised CARS are able to access a complete knowledge about both users and items to suggest, distributed CARS can rely only on the local knowledge of each device, represented by the available contents generated by the local user and those advertised by other devices in proximity through direct communications. Moreover, in this scenario, CARS must be lightweight and efficient in terms of response time. This is due to the fact that they must be executed on devices with limited resources and, more important, opportunis-tic contacts have limited and unpredictable duration, during which mobile devices can exchange their knowledge and the recommended contents.

Therefore, the development of CARS in opportunistic environments must be sup-ported by additional components able to establish opportunistic communications among mobile devices in order to discover new contents in the environment, and to model and recognise the user context to further personalise the provided recommendations. To this aim, we propose a middleware solution that implements all the necessary features to provide personalised recommendations and services to mobile users, where CARS represent the main component of the whole architecture.

This thesis provides several contributions in the research area. As a first step, we propose a novel CARS called PopuLarity ItEm-based Recommender System (PLIERS) that exploits user-defined tags as a practical way to characterise both the user’s context and her items in order to provide contextual recommendations in a centralised sce-nario. Then, we leverage on PLIERS’s principles to define a new solution specifically designed for opportunistic environments, called Pervasive PLIERS (p-PLIERS). It rep-resents a general framework for identifying useful and interesting contents in highly distributed scenarios, relying only on the exchange of single devices knowledge during proximity contacts and through direct wireless communications.

To this aim, we propose Wi-Fi Direct Group Manager (WFD-GM), a novel context-aware networking protocol based on the Wi-Fi Direct standard to establish self-forming direct communications among mobile devices. The main goal of WFD-GM is the autonomous configuration and management of Wi-Fi Direct communication groups, without relying on the manual intervention of the human user. In this way, our protocol enables the creation of self-forming wireless networks on commercial mobile devices and allows p-PLIERS to evaluate contents discovered in the opportunistic environment. Finally, we define a lightweight approach to model and infer the user context directly

(9)

on mobile devices, without the need of relying on remote computational resources (e.g., cloud architecture). Our approach leverages on machine learning techniques to recog-nise the user’s context by combining the sensing capabilities of mobile devices with information related to the user’s activities and social interactions, both in the physical and virtual worlds. In addition, a sensing framework called ContextKit has been de-veloped to monitor context data from mobile devices and collect real-world datasets to define and evaluate new CARS for opportunistic environments, and to support the development of new context-aware applications.

(10)

(11)

List of publications

International Journals

1. Arnaboldi Valerio, Campana Mattia Giovanni, Delmastro Franca, Pagani Elena. (2017). A personalized recommender system for pervasive social networks. Per-vasive and Mobile Computing. (Vol.36, pp. 3-24). Elsevier.

2. Campana Mattia Giovanni, Delmastro Franca. (2017). Recommender Systems for Online and Mobile Social Networks: A survey. Online Social Networks and Media. (Vol. 3, pp. 75-97). Elsevier.

International Conferences/Workshops with Peer Review

1. Campana Mattia Giovanni, Chatzopoulos Dimitris, Delmastro Franca, Hui Pan. (2018, October). Lightweight Modeling of User Context Combining Physical and Virtual Sensor Data. In Proceedings of UbiComp/ISWC’18 Adjunct. ACM 2. Arnaboldi Valerio, Campana Mattia Giovanni, Delmastro Franca. (2017,

Octo-ber). Context-Aware Configuration and Management of WiFi Direct Groups for Real Opportunistic Networks. In Proceedings of the 14th IEEE International Con-ference on Mobile Ad Hoc and Sensor Systems (MASS)(pp. 266-274). IEEE. 3. Campana Mattia Giovanni, Delmastro Franca, Bruno Raffaele. (2016,

Novem-ber). A machine-learned ranking algorithm for dynamic and personalised car pooling services. In Proceedings of the 19th International IEEE Conference on Intelligent Transportation Systems (ITSC)(pp. 1856-1862). IEEE.

4. Arnaboldi Valerio, Campana Mattia Giovanni, Delmastro Franca, Pagani Elena. (2016, April). PLIERS: a popularity-based recommender system for content dis-semination in online social networks. In Proceedings of the 31st Annual ACM Symposium on Applied Computing(pp. 671-673). ACM.

(12)

(13)

List of Abbreviations

A

AE Autoencoder. 108

AP Access Point. 81

B

BHC Biased Heat Conduction. 46

BT Bluetooth. 102

C

CARS Context-Aware Recommender Systems. 5,

8, 20, 100

CART Classification and Regression Tree. 109

CF Collaborative Filtering. 13

CK ContextKit. 102

CSG Combined Social Graph. XVI, 117, 118

D

D2D Device-to-Device. 2, 56, 80

DCG Discounted Cumulative Gain. 12

DR Dimensionality Reduction. 107

F

FA Feature Agglomeration. 108

G

GKG Global Knowledge Graph. 58

GO Group Owner. 82

GRP Gaussian Random Projection. 108

H

(14)

I

IoP Internet of People. 2

IoT Internet of Things. 1

K

k-NN k-Nearest Neighbors. 109

L

LKG Local Knowledge Graph. 58

M

MAE Mean Absolute Error. 12

MF Matrix Factorization. 15

MSN Mobile Social Networks. 2, 100

N

NDCG Normalized Discounted Cumulative Gain.

12

NMAE Normalized Mean Absolute Error. 12

NMF Non-Negative Matrix Factorization. 108

NN Nearest Neighbors. 16

NRMSE Normalized Root Mean Squared Error. 12

O

OSN Online Social Networks. 2, 5, 25, 101

P

p-PLIERS Pervasive PLIERS. 56, 58

PC Pearson Correlation. 14

PCA Principal Component Analysis. 108

PD Preferential Diffusion. 46

PLIERS PopuLarity-based ItEm Recommender

System. 44

ProbS Probability Spreading. 18, 45

R

RMSE Root Mean Squared Error. 12

RS Recommender Systems. 4, 5, 8, 9

S

SRP Sparse Random Projection. 108

STS Social Tagging Systems. 43

SVM Support Vector Machines. 16, 109

(15)

List of Abbreviations

WFD Wi-Fi Direct. 80, 81, 102

(16)

Notation

Symbols

Iv Interactions frequency among two users on

OSN. 117

Iph(u, v) Physical interactions among two users. 117

O Overlap index used to evaluate graph-based Recommender Systems. 51

Sf Strength of a social link in the Combined

Social Graph. 117

Sv(u, v) Virtual social relationship among two

users. 117

V Variance index used to evaluate

graph-based Recommender Systems. 51 AIT _{Items-Tags adjacency matrix. 47}

AU I _{User-Items adjacency matrix. 47, 56}

AU T _{User-Tags adjacency matrix. 47, 56}

R Ratings matrix. 9, 10, 15, 16, 21

E Users-Items edges in a tripartite graph. 57 F Items-Tags edges in a tripartite graph. 57

GM WFD group members. 89

I Set of items. 10, 47, 57

LN List of nodes in proximity. 87, 88

R Set of ratings. 10

S(ln) Suitability Index of the local node. 87

T Set of tags. 47, 57

U Set of users. 10, 47, 57

(17)

List of Figures

1.1 The Desktop and Mobile worldwide market share trends in the last years

(a), and the expansion of the Internet at its edge (b). . . 2

1.2 Filtering of contents discovered from nearby devices. . . 3

1.3 The high-level architecture of our reference middleware. . . 4

1.4 General representation of the recommendation process. . . 5

2.1 High-level architecture of a Recommender System. . . 10

2.2 Long tail distribution of the items popularity. . . 11

2.3 Example of matrix factorisation. . . 15

2.4 Execution of ProbS and HeatS on a bipartite user-item graph. . . 19

2.5 Example of a multidimensional cube for the U sers×Items×Locations recommendation space. . . 20

2.6 Process of a pre-filtering method to generate contextual recommendations. 21 2.7 Process of a post-filtering method to generate contextual recommendations. 22 2.8 Tensor Factorisation. . . 23

2.9 Classification of CARS according to the type of context information considered and recommendation target. . . 24

2.10 Graphical representation of (a) a basic friendship network, and (b) a trust-network with inferred trust links (dashed lines). . . 25

2.11 Graphical representation of a folksonomy with (a) a tensor, and (b) a graph. . . 31

2.12 Graphical representation of the data dimensions considered in Location-based Social Networks. . . 33

3.1 ProbS and HeatS suggestions. . . 45

3.2 Relevant sub-graph for the target user u3. . . 47

3.3 Structure of the synthetic user-tag bipartite graph. The zoomed area highlights the interests of the users 1 and 3. . . 48

3.4 Popularity of the tags already connected to User 1 (a), and the rankings generated by PLIERS (PL), ProbS (Pr), HeatS (He) and Hybrid (Hy) for her (b). . . 49

(18)

3.5 Popularity of the tags already connected to User 3 (a), and the rankings generated by PLIERS (PL), ProbS (Pr), HeatS (He) and Hybrid (Hy) for her (b). . . 50 3.6 Structure of the synthetic user-tag bipartite graph. The zoomed area

highlights the interests of the users 1 and 3. . . 52 3.7 Results obtained from the link prediction evaluation. . . 53 4.1 Affinity and similarity indices in a tripartite folksonomy graph. . . 57 4.2 Descriptive statistics of the Twitter dataset used for the WFD@Expo2015

scenario. (a) CCDF of the number of tweets per user, (b) CCDF of the number of tags per tweet, (c) Frequency of use of the most used tags, and (d) Summary of the number of elements (i.e., users, items, and tags) contained in the dataset. . . 60 4.3 Precision (a) and Recall (b) gain obtained by PLIERS in a complete

knowledge scenario. . . 61 4.4 Map of Expo 2015 area with the position of five of the simulated

com-munities. Note that the grid in the figure is only an example to show how we divided the area for the simulations, but it does not represent the actual grid. . . 64 4.5 Descriptive statistics of the Twitter datasets used for the WFD@Expo2015

dynamic scenario. (a) shows the CCDF of the number of tweets per user, (b) shows the CCDF of the number of tags per tweet, and (c) shows the usage frequency of the most used tags. . . 66 4.6 Overall number of contacts between nodes (a), and number of contents

generated by nodes (b) during the simulation for the WFD@Expo2015 scenario. . . 67 4.7 Results for the WFD@Expo2015 scenario. (a) shows the average

Jac-card similarity between the LKGs of the agents and the GKG, for dif-ferent number of agents. (b) shows the average Spearman index and (c) shows the average Jaccard similarity between the recommendation list provided by PLIERS by using the LKGs of the agents and the list ob-tained exploiting the GKG, for different number of agents. (d) shows the average Jaccard similarity between the LKGs and the GKG by limiting the knowledge to different time windows in the past. . . 68 4.8 Descriptive statistics of the Twitter datasets used for the Conference

sce-nario: (a) CCDF of the number of tweets per user, (b) CCDF of the number of tags per tweet, and (c) Frequency of use of the most used tags. 69 4.9 Overall number of contacts between nodes (a), and number of contents

generated by nodes (b) during the simulation for the Conference scenario. 70 4.10 Results for the scenario of the KDD conference. (a) shows the average

Jaccard similarity between the LKGs of the agents and the GKG, for dif-ferent number of agents. (b) shows the average Spearman index and (c) shows the average Jaccard similarity between the recommendation list provided by PLIERS by using the LKGs of the agents and the list ob-tained exploiting the GKG, for different number of agents. (d) shows the average Jaccard similarity between the LKGs and the GKG by limiting the knowledge to different time windows in the past. . . 71

(19)

List of Figures

4.11 Graphical representation of the four groups of nodes in the mobility model of Helsinki which live and work in the same districts of the city (a), and the additional three groups of nodes that live and work in

differ-ent districts of the city (b). . . 72

4.12 Descriptive statistics of the Twitter datasets used for the Helsinki sce-nario: (a) CCDF of the number of tweets per user, (b) CCDF of the number of tags per tweet, and (c) Frequency of use of the most used tags. 73 4.13 Overall number of contacts between nodes (a), and number of contents generated by nodes (b) during the simulation for the Helsinki scenario. . 74

4.14 Results for the scenario of the city centre of Helsinki. (a) shows the av-erage Jaccard similarity between the LKGs of the agents and the GKG, for different number of agents. (b) shows the average Spearman index and (c) shows the average Jaccard similarity between the recommenda-tion list provided by PLIERS by using the LKGs of the agents and the list obtained exploiting the GKG, for different number of agents. (d) shows the average Jaccard similarity between the LKGs and the GKG by limiting the knowledge to different time windows in the past. . . 75

5.1 WFD Peer and Service Discovery. . . 83

5.2 Merge of two isolated groups. . . 88

5.3 Travelling between two groups. . . 90

5.4 Battery depletion fitting. . . 92

5.5 Graphical representation of the three simulated scenarios. . . 94

5.6 Message diffusion performance . . . 95

5.7 CCDF of the connection probability between nodes. . . 96

5.8 Subgraphs randomly sampled from the CGs generated by both Baseline and WFDGM at the end of each simulated scenario. . . 97

6.1 High-level architecture of the Context Kit framework. . . 102

6.2 Characterisation of the user’s context and interests using Context Kit. . 105

6.3 Tradition context inferring process. . . 106

6.4 User Interface of the Context Labeler application while the user is se-lecting her current activity (a), and while the app is reading sensor data (b). . . 109

6.5 Scheme of the data processing used to generate the final dataset (a), and distribution of features categories in each data sample. . . 110

6.6 Distribution of the labels in (a) our original dataset, and (b) in the train and test sets after the application of the oversampling technique. . . 112

6.7 Accuracy performance obtained by k-NN, CART and SVM (Figures a,b,c respectively) using the six Dimensionality Reduction algorithms and different number of latent features. Figure d) shows the execution times of the six Dimensionality Reduction algorithms to extract different number of latent features from the entire dataset. . . 113

6.8 Classifiers execution times. . . 114

6.9 Subject-Independent Classification accuracy. . . 114

(20)

6.11 Students’ social relationships modelling results. The social graph based on OSN data is represented in (a); (b) represents the resulting Combined Social Graph; and (c) shows the nodes’ degree distributions in both VSG and CSG. . . 118 7.1 Representation of the multi-graph extracted from the

MyDigitalFoot-print dataset. The blue nodes represent the users contained in the dataset, while the red nodes refer to their shared items. . . 124

(21)

List of Tables

2.1 List of CARS proposed for opportunistic environments. . . 41 3.1 Characteristics of the samples used to evaluate PLIERS against the other

diffusion- and graph-based solutions. . . 51 4.1 Relation between graph similarity (Y ) and (i) number of items generated

at each simulation step (X1), (ii) number of contacts at each step (X2). . 76

5.1 Number of CG’s connected components and percentage of nodes be-longing to the largest one. . . 97 5.2 Power consumption statistics . . . 98

(22)

2.1 The recommendation task . . . 9 2.1.1 Evaluation metrics . . . 11 2.2 Classical approaches . . . 13 2.2.1 Collaborative Filtering . . . 13 2.2.2 Content-based Recommender Systems . . . 16 2.3 Graph-based recommendations . . . 17 2.4 Handling context information . . . 20 2.5 CARS for centralised architectures . . . 24 2.5.1 Social-aware recommendations . . . 25 2.5.2 Tag-based recommendations . . . 29 2.5.3 Location-aware recommendations . . . 32 2.6 CARS for Opportunistic Environments: preliminary solutions . . . 35 2.6.1 Collaborative Filtering . . . 36 2.6.2 Exploiting tags . . . 39 2.7 Concluding remarks and open challenges . . . 40

3 Exploiting tags as context information 43

3.1 The use of Tag-based Recommender Systems . . . 44 3.2 PLIERS: PopuLarity based ItEm Recommender System . . . 47 3.2.1 Notation . . . 47 3.2.2 Algorithm definition . . . 47 3.2.3 PLIERS working principles . . . 49

(23)

Contents

3.3 Experiments . . . 50 3.3.1 Datasets description . . . 51 3.3.2 Evaluation metrics . . . 51 3.4 Obtained results and discussion . . . 52 3.5 Conclusions . . . 53

4 Pervasive PLIERS: A framework for Distributed Recommender Systems 55

4.1 Extension of PLIERS . . . 56 4.2 Pervasive PLIERS . . . 58 4.3 Experimental Evaluation: General Description . . . 59 4.4 PLIERS Experimental Evaluation in a Static Scenario . . . 59 4.4.1 Dataset Description . . . 60 4.4.2 Link Prediction Task . . . 61 4.4.3 Results . . . 61 4.5 p-PLIERS Experimental Evaluation in Dynamic Scenarios . . . 62 4.5.1 p-PLIERS Pervasive Simulator . . . 62 4.5.2 Evaluation metrics . . . 63 4.5.3 Scenario 1 - Big Event: World Food Day @Expo2015 . . . 64 4.5.4 Scenario 2 - Conference: KDD 2015 . . . 68 4.5.5 Scenario 3 - City: Helsinki . . . 72 4.5.6 Discussion . . . 76 4.6 Possible Applications . . . 77 4.6.1 Automatic Download for Content Dissemination and Routing . . 77 4.6.2 Manual Download for File Sharing and Recommendation Services 78 4.7 Conclusions . . . 78

5 WFD-GM: A practical solution for self-forming D2D connections 80

5.1 Wi-Fi Direct . . . 82 5.1.1 Peer Discovery . . . 83 5.1.2 GO Negotiation . . . 83 5.1.3 Service Discovery . . . 84 5.1.4 WPS Provisioning . . . 84 5.2 Limitations of current solutions . . . 85 5.2.1 Selection of the best GO . . . 85 5.2.2 Autonomous group formation . . . 86 5.2.3 Inter-group communications . . . 86 5.2.4 Other approaches . . . 87 5.3 WiFi Direct Group Manager . . . 87 5.4 Experimental evaluation . . . 90 5.4.1 Context parameters estimation . . . 91 5.4.2 Simulated use case scenarios . . . 93 5.4.3 Evaluation metrics and results discussion . . . 94 5.5 Conclusions and future work . . . 98

(24)

6 Modelling the user context 100 6.1 Context Acquisition . . . 101 6.2 The User Physical Context . . . 105 6.2.1 The Context Inference Process . . . 107 6.2.2 Context Labeler: a real physical context dataset . . . 109 6.2.3 Dataset Generation . . . 110 6.2.4 Evaluation . . . 111 6.3 MyDigitalFootprint: a user context data collector . . . 115 6.4 Social Context . . . 116 6.4.1 Combining virtual and physical social interactions . . . 117 6.4.2 Modelling the users’ social context . . . 118 6.5 Discussion . . . 119

7 Conclusion 121

7.0.1 Future Research . . . 123

(25)

CHAPTER

1 Introduction

Nowadays we are living surrounded by a plethora of electronic devices equipped with a continuously increasing amount of both computational and networking capabilities. In particular, the computational resources of modern personal mobile devices (e.g., smartphones, tablets, and wearables) are comparable or even exceed those of desktop computers of the previous five years, and they guarantee a continuous Internet access and several communications opportunities. According to analytics companies (e.g., StatCounter1), the diffusion of mobile devices overwhelmed the number of fixed ones during the first months of 2016, and this trend is expected to increase in the next few years [253] (see Figure 1.1a). Moreover, networking experts foresee that global data traffic generated by mobile devices will increase seven-fold between 2016 and 2021, with a compound annual growth rate (CAGR) of 47%, and reaching 49 exabytes per month by 2021 [57].

These aspects, along with the widespread penetration of Internet of Things (IoT) de-vices embedded in physical objects, contribute to a rapid expansion and evolution of the Internet at its edge much faster than its core [253]. The Internet core is composed of a set of networking apparatus whose primary purpose is to provide connectivity between any device on a global scale and, therefore, it has evolved following an infrastructure-centricperspective. On the contrary, the Internet edge is more human-centric, mainly following the human behaviour while carrying, and often wearing, their mobile devices or interacting with IoT devices [64].

Through these devices, human users have several connectivity opportunities, in-cluding communications flowing through the core Internet or direct communications with other users and devices in proximity by using self-organizing networks (see Fig-ure 1.1b). Direct communications offer also the opportunity to exchange contents or

(26)

0 20 40 60 80 100 2015 2016 2017 2018 Market Share (%) Desktop Mobile (a) Core Internet (b)

Figure 1.1: The Desktop and Mobile worldwide market share trends in the last years (a), and the expan-sion of the Internet at its edge (b).

share computational resources, as envisioned by the opportunistic computing paradigm in which a device with limited resources can offload a computational task to other de-vices in proximity with more available resources [205, 217].

In this scenario, we can refer to a new Internet paradigm called Internet of People (IoP) [63]. Here, humans and their devices are not only simple users of applications and networking services, but they represent active elements of the new Internet, acting as “sensors” able to characterise their surrounding physical environment [161,218], and establish new physical and virtual interactions with other users and devices.

These characteristics leverage the development of a novel set of mobile and perva-sive applications recently proposed in the literature, namely Mobile Social Networks (MSN) [14]. One of the main objectives of MSN is to improve the mobile users’ expe-rience through the opportunistic sharing of contents and resources depending on their current context, in order to increase their social interactions to stimulate the collective awareness about the situation in which they are involved, the current external condi-tions, and the behaviour of other users in proximity [168]. In this way, MSN extend the concept of Online Social Networks (OSN), maintaining similar features for content and experience sharing while projecting them to the physical world of the users through the communications opportunities generated by users’ mobility and self-organising wire-less networks. In this way, MSN intend to stimulate additional social interactions also among unknown users, sharing the same interests and needs.

Among the various approaches for self-organising networks, opportunistic network-ing seems the most suitable one to support the IoP paradigm. Opportunistic networks represent the natural evolution of the legacy MANET paradigm, conceived to cope bet-ter with dynamic network conditions and mobility of human users [201, 247]. Indeed, while in MANETs an end-to-end path must exist between source-destination pairs, in opportunistic networks a stable path between source and destination of a message is not required, and data is transferred through the store-carry-forward paradigm exploiting the nodes’ mobility. According to this paradigm, data is forwarded across the net-work not only through Device-to-Device (D2D) communications, but also exploiting the movements of the nodes themselves, which carry messages while waiting to enter in reciprocal radio range with either the message destination, or a node suitable to reach the destination.

(27)

Figure 1.2: Filtering of contents discovered from nearby devices.

In addition, in this scenario direct and physical contacts between nodes are oppor-tunistically exploited to recognise and disseminate relevant information towards poten-tially interested nodes, without the need for centralised infrastructures or pre-computed paths from source to destination [23].

In this thesis we mainly refer to Opportunistic Environments as the combination of all the aforementioned characteristics of the envisioned future Internet, with a specific attention to context-awareness aspects. In fact, since the user context rapidly changes in opportunistic environments, it is fundamental the development of specific systems able to autonomously recognise and react to those changes, in order to provide personalised services to the user.

Mobile users can also access a massive quantity of information, coming from both remote sources and personal devices in proximity. Therefore, one of the most critical challenges in this scenario is how to efficiently select the most relevant information for the user, avoiding to flood her with a considerable amount of (useless) contents [64]. To this aim, personal mobile devices should act as avatars of their respective human users. They can explore congested cyber landscapes by collecting the available contents, fil-tering them, and keeping the relevant data only, acting as their local users would do if they have to make the same decision. Figure 1.2 shows a graphical representation of this concept: the mobile device of the user in the middle autonomously analyses the contents discovered from other devices in the nearby and automatically filters out those contents that are not interesting for its user or not relevant for the situation in which she is currently involved.

In traditional approaches for data dissemination in self-organising networks, mobile nodes select relevant information based on explicit requests and actions of their users, (e.g., through a manual configuration of the device) [62]. In this case, user’s preferences are well-defined a priori in content categories (e.g., music, sport, movies) and her device should collect all the contents related to these categories. However, in the real world, users’ interests are not static, but they change over time and often depend on the current situation. Therefore, personal mobile devices should be able to automatically learn both the preferences and needs of their local users, depending on the current context in which

(28)

Operating System

Physical & Virtual Sensors Monitors Context Manager Context-Aware Recommender Systems Network Manager Self-forming D2D Routing / Data dissemination Application Manager

App 1 App 1

…

App 1 App 1

Security & Privacy

Figure 1.3: The high-level architecture of our reference middleware.

she is involved. In fact, a considerable portion of the data available in the Internet edge is also very contextualised, i.e., contents may be relevant only in specific situations, and of interest just for a particular group of users. For example, a person may be interested in a different type of content based on her current location (e.g., if she is at work or home), the time of the day (e.g., morning or night), or her social context (e.g., she is alone, with close-friends or acquaintances).

The primary purpose of the dissertation is to design and analyse a new human-centric approach to automatically identify interesting contents and information in op-portunistic environments, based on the preferences of the user and her context, relying only on the computational capabilities of personal mobile devices.

To this aim, we focus on the use of Recommender Systems (RS) as the key element to support the development of personalised and context-aware applications, services, and communication protocols for the Internet of the future.

However, the definition of a context-aware RS for opportunistic environments needs to be supported by additional components able to: (i) establish and manage oppor-tunistic communications and networking through heterogeneous mobile devices, (ii) collect a multitude of context information characterising the user behaviour, her pref-erences, and the surrounding environment, and (iii) define specific user context models and reasoning procedures. For this reason, we envision to integrate the proposed RS in a more general middleware architecture, designed to support the efficient implementa-tion of services and applicaimplementa-tions for opportunistic environments. Figure 1.3 shows the high-level architecture of the middleware. Interacting with the Operating System, the middleware implements a specific layer to collect context information from the sensors integrated in the local device. Upon this sensing layer, a series of different modules are built, including: a Context Manager to model the sensed data and thus inferring the user context; a Network Manager, that manages the creation of self-forming D2D com-munications with other devices in proximity and implements opportunistic routing and data dissemination algorithms; and the context-aware RS, that interacts with the other modules to provide context-aware recommendations and features to the upper-layer ap-plications. Finally, we also envision the presence of a security layer that implements

(29)

1.1. Thesis Contributions

RS

}

User-Item Interactions Additional Information Items filtering

Figure 1.4: General representation of the recommendation process.

security measures to prevent possible security threats, such as unauthorised access, confidentiality disclosure, and privacy invasion [260].

1.1

Thesis Contributions

Recommender Systems (RS) have emerged in the past years as fundamental method to find relevant information within the massive amount of data accessible through the Internet. These systems have been playing a vital and indispensable role in several web domains, such as e-commerce (e.g., Amazon2), media websites (e.g., Netflix3), and also OSN (e.g., Facebook4and Twitter5). Specifically, a RS implements an utility function that predicts how much a user will be interested in a specific item available in the system. In our reference scenario, users can access a heterogeneous set of items available in the network, including multimedia contents, new social relationships, as well as computational resources available in other devices in proximity. In general, recommendations are generated taking into account past user-item interactions (e.g., list of downloaded or shared items by the user), items’ features, as well as additional information used to improve the level of personalisation (e.g., location [34], social relationships [43, 77], or the user emotional state [207]). Figure 1.4 shows the general concept of the recommendation process.

In this work, we define a new information filtering approach for opportunistic en-vironments, based on the use of Context-Aware Recommender Systems (CARS) [252]. CARS represent a particular type of RS that exploits information about the user context to provide more accurate and personalised recommendations, based on the situation in which the user is currently involved. We propose a distributed approach for CARS able to run completely on mobile devices and able to filter off undesired items that can be found in the edge of the Internet, and to select what contents should be addressed to

2_{www.amazon.com} 3_{www.netflix.com} 4_{www.facebook.com} 5_{www.twitter.com}

(30)

which users and in which situation. Traditional CARS are designed for applications running on the Internet core, leveraging on a global and centralised knowledge about the users’ preferences and their history to provide recommendations.

Unfortunately, in opportunistic environments it is not always possible to rely on remote servers to perform the recommendation process, due to the dynamics of the op-portunistic contacts among mobile devices. Indeed, depending on the communication technology, the delay of the data transmission may make the recommendation process useless, since the opportunistic contact between two devices could last just a few sec-onds due to the users’ mobility.

Therefore, we propose a new approach for the implementation of distributed CARS on personal mobile devices, especially designed to provide personalised and context-aware recommendations to mobile user in opportunistic environments. We present our solution as the main component of a middleware architecture that can be used as a comprehensive framework for the evaluation of CARS in these environments through real test beds. To this aim, we also propose a context-aware networking protocol to allow commercial mobile devices to autonomously establish D2D communications and deploy a real self-organising network. In addition, we define a lightweight approach to model and infer the user context directly on the mobile device, combining its sensing capabilities with information related to user’s activities and social interactions, both in the physical and virtual worlds.

Therefore, the research work we describe in this dissertation presents novel contri-butions in multiple fields, paving the way to new research directions both in mobile context modelling and reasoning, and distributed CARS.

1.2

Outline

The rest of the thesis is structured as follows. In Chapter 2, we present the state-of-the-art of RS, with pstate-of-the-articular attention to CARS, highlighting how those systems evolved over time regarding technical solutions, target domains, evaluation metrics, and perfor-mance evaluations. Even though the research on CARS for distributed (opportunistic) environments is still in its infancy, we analyse the characteristics of the few solutions proposed so far in the literature.

In Chapter 3, we introduce PLIERS, PopuLarity ItEm-based Recommender System, as a novel CARS that exploits user-defined tags as simple context information to pro-vide personalised recommendations to the final user, and its performance results in a centralised scenario. Then, in Chapter 4, we present pervasive-PLIERS (p-PLIERS), a novel framework we propose for the implementation of distributed CARS in oppor-tunistic environments.

In Chapter 5 we present Wi-Fi Direct Group Manager (WFD-GM), our context-aware networking protocol able to establish self-forming D2D communications with heterogeneous commercial mobile devices. WFD-GM supports the discovery of new contents and information in proximity that will be evaluated by the CARS module running on the local mobile device and, in particular, by p-PLIERS.

In Chapter 6 we present in details our lightweight approach to model and infer the user context on the mobile device, based on data derived from a high number of hetero-geneous sensors, and information about the user interactions with mobile application,

(31)

1.2. Outline

also taking into account OSN data to model user social relationships in the virtual world. In this Chapter we also describe ContextKit, our sensing framework to mon-itor context data from real mobile devices, and we present the two datasets collected by using ContextKit for the definition and evaluation of new CARS for opportunistic environments.

Finally, we conclude the dissertation drawing our conclusions and presenting some directions for future research in Chapter 7.

(32)

CHAPTER

2 Context-Aware Recommender Systems

The explosive growth in the amount of available information on the Web has created a serious challenge of information overload, preventing users from easily finding in-teresting and useful content on the Internet [144]. Recommender Systems (RS) deal with this problem by filtering relevant content according to user’s preferences, interest, or observed behaviour with respect to a specific item [119]. Thanks to their effec-tiveness to cope with this problem, RS have been applied to suggest different types of items, such as movies [278], music [204], images [182], travel guides [183], news [46], social relationships [225], or scientific citations [24]. Context-Aware Recommender Systems (CARS) represent a special class of RS that aims to improve traditional rec-ommendations by exploiting information about the contextual situation in which a user experienced and rated an item [4].

In this chapter, we present the state-of-the-art of Context-Aware Recommender Sys-tems for both centralised and distributed (e.g., opportunistic) scenarios. We highlight the advantages and drawbacks of different recommendation techniques applied in these environments, and how those systems include different aspects of the user’s context (e.g., location or social relationships) into the recommendation process.

We start summarising in Section 2.1 the general recommendation problem and the evaluation metrics commonly used in the literature to assess this kind of systems. In Section 2.2, we present an overview of standard techniques like Collaborative Filtering (CF) and Content-based Recommender Systems. Then, in Section 2.3, we introduce the underlying idea of Network-based RS, an alternative approach that leverages on graph theory solutions to provide recommendations to the users. Moreover, in Section 2.4, we describe different approaches proposed in the literature to further optimise person-alisation level of the provided recommendations by including context information into the recommendation process.

(33)

2.1. The recommendation task

Finally, in Sections 2.5 and 2.6, we present the main solutions presented in the lit-erature for both centralised and opportunistic scenarios, respectively. The first area has been widely studied in the last years, proposing solutions that can address different tar-get domains (e.g., to recommend people, points-of-intereset - POIs, tags or contents) by exploiting various context information. We classify the proposed solutions by the type of context information used in the recommendation process (e.g., social relationships, tags, location) and the recommendation target (e.g., to recommend contents, tags, or people). On the other hand, the research area of CARS for distributed environments is still in its infancy, and few solutions have been presented in the literature, mainly aimed at optimising content dissemination in opportunistic networks through person-alised recommendations. The main difference between CARS for centrperson-alised and dis-tributed scenarios relies on the knowledge they use to select the recommendations for their final users. In the former case, CARS assume to have access to a complete knowl-edge of all the available objects on the network (i.e., contents, tags, etc.), residing on a centralised infrastructure. Instead, in the latter scenario, CARS can rely only on the local knowledge of each user, represented by the available objects generated by the local user and those advertised by other users in proximity, through D2D communica-tions. In this scenario, each mobile device has a different knowledge related to the items available in the network, which grows up through its mobility and its opportunities to communicate with the others. Another important characteristic of the opportunistic en-vironment is that mobile devices have limited resources, and CARS must be efficient in terms of response time. This is due to the limited and unpredictable duration of the opportunistic contact, during which mobile devices can exchange their local knowl-edge and the recommended objects. In Section 2.6 we present the proposed CARS in this area, highlighting the advantages of using context information to improve the recommendation process and demonstrating their efficiency with respect to centralised solutions. Eventually, in Section 2.7 we present some concluding remarks and open research challenges in this area.

2.1

The recommendation task

As a general concept, Recommender Systems try to identify and foresee users’ interests in specific contents, based on their previous experiences. Figure 2.1 shows the high-level architecture of a typical RS. When a user interacts with the system, she provides a set of explicit or implicit feedback (e.g., likes, clicks, ratings) about her tastes. For example, if a user positively rates an article about a new smartphone, she may also be interested in reading news about mobile apps. Therefore, the basic idea of RS is to exploit this information to infer user interests. Based on the user’s past feedback, RS learn a model to predict how much a user can be interested in new items. Those items are then ranked according to their predicted relevance for the user. Finally, the higher ranked items will be proactively suggested to the user.

The relationship between users and items is generally represented by a matrix R, storing a rating ru,i to identify how much the user u liked the item i in the past. More

formally, the matrix R is called ratings matrix and it can be defined as follows:

(34)

User Recommended items User feedback Prediction Model New items User history Model training

Figure 2.1: High-level architecture of a Recommender System.

where U = {u1, · · · , um} represents the set of users, I = {i1, · · · , in} is the set of

items, and R = {r1, · · · , rk} denotes the set of possible ratings that users can select to

express their grade of interest for a specific item.

The ratings’ range of values highly depends on the application domain. They are often specified as a discrete set of ordered numbers (e.g., a 5-point rating scale is com-monly used in e-commerce websites, like Amazon, and video-on-demand services, like Netflix), or a binary value, as in most of OSN (i.e., “like” on Facebook or a “retweet” on Twitter). In the first case, ratings are considered as explicit feedback of the users, while in the latter we can refer to them as implicit feedback, and they are usually inferred from the users’ activities. In this Chapter, we generally refer to ratings scale including both cases.

A missing value in the ratings matrix can have two meanings: (i) the user did not want to express an opinion about a specific item, or (ii) the user does not know that item yet. As we will discuss in details in the next sections, a great number of recommen-dation techniques (e.g., Collaborative Filtering) aims to predict missing ratings in R in order to generate lists of new items to be suggested to the users. However, there are also other RS (e.g., some network-based RS) that simply provide ranked lists of items without explicitly predicting ratings, using the ratings matrix just to model the users’ preferences.

Typically, there are a lot of missing values in R. In [232] the sparsity of the ratings matrix has been calculated to be generally larger than 99% in commercial systems. This is due to the long tail property [194] (shown in Figure 2.2), which is satisfied by differ-ent real-world settings. According to this property, just a small subset of the contdiffer-ents

(35)

2.1. The recommendation task

Popularity

2.2

Classical approaches

Two main approaches have been proposed in the literature to define Recommender Systems: Collaborative Filtering and Content-based. The former exploits similarities among users’ behaviours to identify the items to suggest, while the latter category fo-cuses on items’ features. In this Section, we describe in details both of them and the main algorithms that implement them.

2.2.1 Collaborative Filtering

Collaborative Filtering(CF) is the most popular and widely implemented technique in RS [215]. The underlying assumption of CF is that people with similar preferences will rate same objects with similar ratings [244]. Existing CF solutions can be categorised in two main classes: (i) memory-based and (ii) model-based methods. Memory-based solutions leverage on similarities in users’ behaviours and preferences to make infer-ences about missing values in the ratings matrix. On the contrary, model-based methods exploit the matrix values to learn a model, similarly to a classifier that trains a model from labeled data. The learned model is then used to predict the relevance of new items for the users.

Memory-based

Memory-based algorithms (also known as Neighbourhood-based) rely on the notion of similarity among users, or items, to predict the possible interest of a user in items that she has not seen (or rated) before. In the literature, memory-based CF solutions are typically divided in two main categories: user-based and item-based. The former approach is based on the assumption that similar users typically rate the items in a

(38)

similar way. Therefore, a user-based CF predicts the rating that a user u might assign to an item by aggregating the ratings that the most similar users to u have previously given to that item. Formally, the predicted rating of a user u to the item j can be formulated as follows: ˆ ru,j = 1 K X k∈Nu Sim(u, k) · rk,j, (2.7)

where Nu is the set of the K users most similar to the target user u; Sim(u, k)

represents the similarity between the users u and k for a predefined similarity measure, and rk,jrepresents the rating made by the user k for the item j.

In contrast with user-based CF, item-based CF focuses on the similarities among items. It is based on the assumption that similar items are rated in a similar way by the same user. In this case, the items recommended to user u are ranked by aggregating the similarities between each candidate item and the items that u has rated in the past. It is possible to formulate the prediction rating for the item-based CF as follows:

ˆ ru,j = 1 K X k∈Ni Sim(j, k) · ru,k, (2.8)

where Nirepresents the set of neighbour items of item j, and Sim(j, k) is the

simi-larity value (for a predefined simisimi-larity measure) between items j and k.

The similarity computation between users (or items) represents a crucial step in memory-based approaches, as it can seriously reduce both the accuracy and the general performance of RS [184]. Several similarity metrics have been proposed in the liter-ature for this purpose, but the Pearson Correlation (PC) similarity seems to provide the most accurate results [108]. PC selects just the co-rated items and considers the differences in the mean and variance of the ratings made by two users u and v. The PC similarity between two users is given by the following formula:

P C(u, v) = Σi∈Iu,v(ru,i− ¯ru) · (rv,i− ¯rv) pΣi∈Iu,v(ru,i− ¯ru)2· Σi∈Iuv(rv,i− ¯rv)2

, (2.9)

where Iu,v is the set of items rated by both users u and v, ru,iand rv,i are the ratings

made by user u and v for the item i, and ¯ru and ¯rv are the mean value of the ratings

made by user u and v. On the other hand, the PC similarity between two items i and j can be calculated comparing the ratings made by users that have rated both items:

P C(i, j) = Σu∈Ui,j(ru,i− ¯ri) · (ru,j − ¯rj) pΣu∈Ui,j(ru,i− ¯ri)

2_{· Σ}

u∈Uij(ru,j − ¯rj)

2, (2.10)

where Ui,jis the set of users who rated both items i and j, and ¯riand ¯rj are the

aver-age rating value obtained by item i and j. For a complete comparison of the similarity measures typically used in memory-based CF, we refer the reader to [184].

The main drawback of memory-based CF is represented by the computational cost: the computation of similarities between all pairs of users, or items, typically requires a

(39)

2.2. Classical approaches

Figure 2.3: Example of matrix factorisation.

quadratic time. However, they gained popularity due to their very simple implementa-tion, providing an intuitive justification for the computed predictions. For instance, in item-based CF, the list of similar items can be presented to the user in order to better understand the reason of the recommendation.

Model-based

Although memory-based CF approaches are easy to implement and useful in effec-tively predicting missing ratings, model-based solutions typically show more accurate results [6]. The main characteristic of model-based CF is the use of machine learning techniques to learn models that are able to predict the missing ratings. In the last few years, different models have been proposed for model-based CF, such as Association rule-based [180, 234], Bayesian networks [179, 238], Support Vector Machines [261], Neural networks [220] and, more recently, Deep learning methods [105]. However, the Matrix Factorization (MF) models [138] are considered to be the state-of-the-art in recommendation systems due to their advantages with respect to scalability and accu-racy [6].

Generally, MF models exploit the typically high correlation between rows (e.g., users) and columns (e.g., items) of an incomplete ratings matrix in order to learn low-rank representations of both users and items. Moreover, these low-low-rank matrices (also referred as matrices of latent factors) can be used to approximate the full rating matrix and then predict missing scores between users and items. Specifically, latent factors derive from the correlation patterns in the ratings matrix R, which can be used to de-scribe with more details both users and items profiles. Consider the toy-example shown in Figure 2.3. The ratings matrix contains the preferences of 3 users for 3 different books. In this case, latent factors may represent the genres of the books (i.e., History and Romance). Therefore, the users’ latent factors (i.e., U) describe how much each user is interested in a specific genre and, in the same way, the items’ latent factors (i.e., V) represent how much a book belongs to a specific category.

Formally, the matrix factorisation method can be expressed as following:

R ≈ U · VT, (2.11)

where R is the full rating matrix, and U and V are two matrices of users and items latent factors, respectively. The main goal of MF is to learn the optimal latent fac-tors (U∗ and V∗) that better approximate R. According to [232], the most common formulation of MF is the follows:

(40)

U∗, V∗ = argmin U,V ( 1 2 M X i=1 N X j=1 Ii,j(ri,j− UiVjT) 2₊ λU 2 kU k 2 F λV 2 kV k 2 F ) , (2.12)

where Ui is the latent factors of user i and, in the same way, Vi represents the latent

factors of item i. Ii,j denotes an indicator function that is equal to 1 if the rating ri,j is

not missing in R. Finally, k·k2_F represents the (squared) Frobenius norm of a matrix, and λUand λV are regularisation parameters to prevent the model’s overfitting1. U and

V can be seen as unknown variables, which need to be learned in order to minimise the objective function (i.e., Equation 2.12). This is typically achieved with the well-known Gradient Descent algorithm or one of its variants (e.g., Stochastic Gradient Descent).

Compared to memory-based approaches, the predictions’ accuracy is not the only advantage of model-based CF. In fact, space requirements for model-based CF are often lower than those required by memory-based algorithms. This is due to the fact that memory-based approaches should load into memory all the ratings in order to perform the recommendations, while the model learned by model-based CF is typically much smaller than the original ratings matrix. However, learning a model may require lots of training data and time. In addition, if the system is highly dynamic (e.g., new users or items are frequently added), it could be necessary to train a new model several times since the current one can easily become obsolete, thus affecting its accuracy. This could be an issue for some specific application domains. For example, in a Mobile Social Network, each node (e.g., mobile device) has a limited knowledge of the items (and users) available in the network, and it could be difficult to train an accurate model.

2.2.2 Content-based Recommender Systems

CF approaches exploit the correlations in the ratings patterns among users of the same system. However, they ignore information about items’ characteristics that can be use-ful to improve the recommendations’ accuracy.

Content-based Recommender Systems[159,198] are specifically designed to recom-mend items similar to the ones that the user liked in the past. In CF the similarity be-tween two items (or two users) is calculated in terms of correlation or similarity among ratings provided by other users. Instead, content-based approaches consider only the ratings provided by the target user and the features of the rated items [6]. Content-based RS are typically implemented using traditional classification and clustering al-gorithms, such as Support Vector Machines (SVM) or Nearest Neighbors (NN) [159]. In SVM, items’ features and users’ ratings are combined together to form a dataset of hf eatures, ratingi instances. Based on this dataset, a specific classifier (or regressor) for the target user is trained in order to predict the ratings of new items, never seen before by the user. On the other hand, in order to classify a new and unrated item, NN compares it with all the stored items, by using a similarity function (typically the Euclidean distance or the Cosine similarity) .

1_{According to [147], we refer to overfitting as the common machine-learning problem whereby the learned model not only fits}

the underlying relationship between variables in the system but also fits the noise unique to each observed sample. Consequently, an overfitted model is not able to well generalise from training data, thus it will fail in making predictions on new data samples.

(41)

2.3. Graph-based recommendations

According to Aggarwal [6] and Tang et al. [244], content-based RS have the follow-ing drawbacks:

1. Items’ features. The accuracy of RS relies on the set of features that describe the items. The identification of the most relevant features is not trivial, and highly depends on the specific application.

2. Over-specialisation. Since the content-based methods rely just on the characteris-tics of the items already rated by the target user, it typically suffers of low diversity and novelty of the recommended items. Thus, a content-based RS typically tends to provide obvious recommendations, which could bother the user in the long term.

3. Training set size. In order to allow a content-based RS to learn the user’s prefer-ences, the user has to rate a sufficient number of items [244]. Otherwise, RS does not has enough information to learn an accurate model and fails to recommend items for a user with few or no ratings.

Despite the aforementioned drawbacks, content-based systems are useful to alleviate some critical problems of CF. For example, when a new item is added to the ratings matrix, CF methods are not able to perform recommendations about this item because the system has not yet collected sufficient ratings about it. In the literature, this problem is called cold-start, and a content-based approach can well complement a CF system because of its ability to exploit the characteristics of the items in the recommendation process [6, 178]. Mixing two or more approaches is often referred as Hybrid RS [3] in which the goal is to combine the strengths of different methods to create a more robust RS.

2.3

Graph-based recommendations

As previously described, Collaborative Filtering leverages on linear algebra to manip-ulate the ratings matrix, while content-based RS mainly focus on features of the items consumed by the target user in the past. Graph-based RS represent a third (and more re-cent) technique that models the relationships between users and their items as a graph, and leverages on graph theory to provide recommendations to the user. In this mod-elling approach, nodes represent users and items, and edges model the different rela-tionships among user-user or user-item pairs (e.g., friendships, follow, likes, share). These relationships can also be used in RS to identify similar users and/or items. In-deed, several graph-based RS have been recently proposed in the literature [275]. Their first objective is to perform a ranking of the nodes to identify the most interesting items for a user or a neighbourhood (e.g., the most similar users/items) to be used in tradi-tional CF methods.

PageRank [189] is the most famous method to produce a ranking of the nodes in a graph. It is based on the idea that a node is important if it is linked to other impor-tant nodes. This simple and general idea can be applied to many different situations, including ranking of websites in a search engine, or finding relevant items (or people) for the recommendation purpose. PageRank is a random-walk based approach. More specifically, it performs an exploration of the given graph by visiting nodes following randomly selected links among them. The long-term frequency of visits to a node (also

(42)

called steady-state probability)represents its final ranking value, which is clearly influ-enced by the number of its incoming links. However, directed graphs can have some nodes (or group of them) without out-going links; this part of the network would act as a trap for the random-walk process. In order to overcome this problem, PageRank uses the so called restart mechanism. According to this strategy, at each transition, the random walk may either jump to an arbitrary node of the network with a probability α, or follow one of the out-going links connected to the current node with probability (1 − α). Formally, the steady-state probability at a node i is defined as follows:

π(i) = α

n + (1 − α) · X

j∈In(i)

π(j) · pj,i, (2.13)

where n is the total number of network’s nodes, In(i) is the set of nodes that have out-going links directed to the node i, and pj,i is the transition probability from node j

to node i.

Although PageRank is very effective in finding popular nodes in the graph, it does not take into account the user’s preferences, which means that it is not able to provide personalised recommendations. To this aim, Haveliwala [103] proposes personalised PageRank, a biased version of PageRank, specifically designed to find popular nodes that are also similar to specific nodes in the graph. In this case, the key idea is to use the restart mechanism to bias the random walk process towards specific nodes that represent the user’s interests. For example, consider a specific OSN represented as a graph, where nodes represent the items available in a social media, and links model the relationships between users and items. The restart nodes represent the items consumed by the target user in the past. Then, exploiting the biased random-walk, personalised PageRank provides a way to calculate similarity scores of nodes based on their structural similarity to the restart nodes in terms of graph topology. Finally, items most similar to the restart nodes can be recommended to the target user.

Even if (personalised) PageRank and other similar random walk-based algorithms (e.g., FolkRank [115], SocialRank [248], and ItemRank [90]) can be directly employed to build ad-hoc Recommender Systems [141, 248], they are mostly used to select user or item’s neighbours in memory-based CF solutions [86,271]. In fact, rather than using standard similarity measures (e.g., Pearson Correlation Coefficient on user’s ratings), is possible to use such structural measures to identify the most relevant users (or items) for the recommendation purpose. Since they only leverage on the topological tran-sitivity of the network’s edges (instead of using the users’ ratings), they are typically effective to alleviate the sparsity problem of the ratings matrix. However, random walk-based approaches typically require multiple iterations before the transition probabilities converge to a steady state.

On the contrary, other solutions require only few steps to generate effective rec-ommendations [293]. Diffusion-based methods [275] represent the most popular ap-proach for graph-based RS. They have been initially proposed by Zhou et al. [293, 294] with their algorithms Probability Spreading (ProbS) [294] and Heat Spreading (HeatS) [293]. These algorithms exploit a bipartite user-item graph where users are directly connected to the items collected in the past.

In ProbS, a resource is initially assigned to each item connected to the target user, initialised to a unitary value. The resource is then uniformly distributed from the