Online social networks (OSNs) are Web platforms providing different services to facilitate social interaction among their users. A particular kind of OSNs is the location-based social network (LBSN), which adds services based on location. One of the most important challenges in LBSNs is the link prediction problem. Link prediction problem aims to estimate the likelihood of the existence of future friendships among user pairs. Most of the existing studies in link prediction focus on the use of a single information source to perform predictions, i.e. only social information (e.g. social neighborhood) or only location information (e.g. common visited places). However, some researches have shown that the combination of different information sources can lead to more accurate predictions. In this sense, in this thesis we propose different link prediction methods based on the use of different information sources naturally existing in these networks. Thus, we propose seven new link prediction methods using the information related to user membership in social overlapping groups: common neighbors within and outside of common groups (WOCG), common neighbors of groups (CNG), common neighbors with total and partial overlapping of groups (TPOG), group naïve Bayes (GNB), group naïve Bayes of common neighbors (GNB-CN), group naïve Bayes of Adamic-Adar (GNB-AA) and group naïve Bayes of Resource Allocation (GNB-RA). Due to that social groups exist naturally in networks, our proposals can be used in any type of OSN.We also propose new eight link prediction methods combining location and social information: Check-in Observation (ChO), Check-in Allocation (ChA), Within and Outside of Common Places (WOCP), Common Neighbors of Places (CNP), Total and Partial Overlapping of Places (TPOP), Friend Allocation Within Common Places (FAW), Common Neighbors of Nearby Places (CNNP) and Nearby Distance Allocation (NDA). These eight methods are exclusively for work in LBSNs. Obtained results indicate that our proposals are as competitive as state-of-the-art methods, or better than they in certain scenarios. Moreover, since our proposals tend to be computationally more efficient, they are more suitable for real-world applications. / Redes sociais online (OSNs) são plataformas Web que oferecem serviços para promoção da interação social entre usuários. OSNs que adicionam serviços relacionados à geolocalização são chamadas redes sociais baseadas em localização (LBSNs). Um dos maiores desafios na análise de LBSNs é a predição de links. A predição de links refere-se ao problema de estimar a probabilidade de conexão futura entre pares de usuários que não se conhecem. Grande parte das pesquisas que focam nesse problema exploram o uso, de maneira isolada, de informações sociais (e.g. amigos em comum) ou de localização (e.g. locais comuns visitados). Porém, algumas pesquisas mostraram que a combinação de diferentes fontes de informação pode influenciar o incremento da acurácia da predição. Motivado por essa lacuna, neste trabalho foram desenvolvidos diferentes métodos para predição de links combinando diferentes fontes de informação. Assim, propomos sete métodos que usam a informação relacionada à participação simultânea de usuários en múltiples grupos sociais: common neighbors within and outside of common groups (WOCG), common neighbors of groups (CNG), common neighbors with total and partial overlapping of groups (TPOG), group naïve Bayes (GNB), group naïve Bayes of common neighbors (GNB-CN), group naïve Bayes of Adamic-Adar (GNB-AA), e group naïve Bayes of Resource Allocation (GNB-RA). Devido ao fato que a presença de grupos sociais não está restrita a alguns tipo de redes, essas propostas podem ser usadas nas diversas OSNs existentes, incluindo LBSNs. Também, propomos oito métodos que combinam o uso de informações sociais e de localização: Check-in Observation (ChO), Check-in Allocation (ChA), Within and Outside of Common Places (WOCP), Common Neighbors of Places (CNP), Total and Partial Overlapping of Places (TPOP), Friend Allocation Within Common Places (FAW), Common Neighbors of Nearby Places (CNNP), e Nearby Distance Allocation (NDA). Tais propostas são para uso exclusivo em LBSNs. Os resultados obtidos indicam que nossas propostas são tão competitivas quanto métodos do estado da arte, podendo até superá-los em determinados cenários. Ainda mais, devido a que na maioria dos casos nossas propostas são computacionalmente mais eficientes, seu uso resulta mais adequado em aplicações do mundo real.
Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-16112017-085356 |
Date | 18 August 2017 |
Creators | Rebaza, Jorge Carlos Valverde |
Contributors | Lopes, Alneu de Andrade |
Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
Source Sets | Universidade de São Paulo |
Language | English |
Detected Language | English |
Type | Tese de Doutorado |
Format | application/pdf |
Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0275 seconds