O cada vez maior número de tecnologias que fornecem serviços de geolocalização tem possibilitado gerar uma grande quantidade de dados de geolocalização. Estes dados, são armazenados principalmente como pontos de localização com informação temporal. Uma trajetória é definida como uma sequência discreta e finita destes pontos de localização. Nos últimos anos, a recente área de mineração de trajetórias visa aproveitar esta abundância de dados. Nesta área, existem várias técnicas de mineração desenvolvidas, mas todas elas dependem diretamente da qualidade das trajetórias. Assim, o preprocessamento tem um papel primordial na mineração de trajetórias. Entre as tarefas de preprocessamento, um problema relevante é a reconstrução ou inferência de trajetórias. Devido ao alto consumo de energia de dispositivos de localização como o GPS e ao crescente uso de geo-marcações nas redes sociais, que possibilita a construção de trajetórias ordenando temporalmente estas marcações, muitas das trajetórias existentes apresentam taxas de amostragem muito baixas. A maioria das pesquisas nesse problema utilizam, no caso de áreas urbanizadas, informações do grafo formado por ruas e cruzamentos. Porém, elas levam em conta apenas trajetórias de veículos principalmente pelo fato que muitos dos percursos dos pedestres ficam fora das ruas. Atualmente, graças às plataformas livres de mapas colaborativos, é possível incluir estes trajetos como parte das informações de ruas. Assim, este projeto tem o objetivo de investigar o uso das informações das ruas na reconstrução de trajetórias, principalmente de pedestres. O escopo da proposta compreende o desenvolvimento de uma rede social geo-localizada com o intuito de capturar dados de localização. Posteriormente, estes dados serão anonimizados, utilizados na reconstrução de trajetórias de pedestres e disponibilizados para uso em pesquisas futuras. / The ever-greater number of technologies providing location-based services has allowed the generation of big amounts of geolocation data. This data is mainly stored as location points in conjunction with temporal information. A trajectory is defined as a discrete and finite sequence of this kind of points. In recent years, the relatively new field of trajectory data mining aims to leverage this abundance of data. On this field, there are several data mining techniques developed, but all of these depend on trajectory quality. Hence, preprocessing becomes relevant to this field. Among trajectory data mining tasks, one important problem is trajectory reconstruction. Due to the high energy consumption of geolocation devices like GPS and the growing usage of geo-tags in social networks, which can represent trajectories by being sorted chronologically, most of these trajectories are collected at low sampling rates. A majority of research on this problem is focused on using road network information in urbanized areas to reconstruct trajectories. However, these approaches take into account vehicle trajectories only due to fact that most pedestrian paths do not always follow the same road network routes than vehicles. Currently, thanks to open collaborative maps, it is possible to add pedestrian paths to the road network structure. Thereby, this project aims to research the usage of road network information in pedestrian trajectories reconstruction. This projects scope comprises the development of a location-based social network to collect geolocation data. Subsequently, this data will be anonymized, used for pedestrian trajectory reconstruction and, finally, made available for research purposes.

O cada vez maior número de tecnologias que fornecem serviços de geolocalização tem possibilitado gerar uma grande quantidade de dados de geolocalização. Estes dados, são armazenados principalmente como pontos de localização com informação temporal. Uma trajetória é definida como uma sequência discreta e finita destes pontos de localização. Nos últimos anos, a recente área de mineração de trajetórias visa aproveitar esta abundância de dados. Nesta área, existem várias técnicas de mineração desenvolvidas, mas todas elas dependem diretamente da qualidade das trajetórias. Assim, o preprocessamento tem um papel primordial na mineração de trajetórias. Entre as tarefas de preprocessamento, um problema relevante é a reconstrução ou inferência de trajetórias. Devido ao alto consumo de energia de dispositivos de localização como o GPS e ao crescente uso de geo-marcações nas redes sociais, que possibilita a construção de trajetórias ordenando temporalmente estas marcações, muitas das trajetórias existentes apresentam taxas de amostragem muito baixas. A maioria das pesquisas nesse problema utilizam, no caso de áreas urbanizadas, informações do grafo formado por ruas e cruzamentos. Porém, elas levam em conta apenas trajetórias de veículos principalmente pelo fato que muitos dos percursos dos pedestres ficam fora das ruas. Atualmente, graças às plataformas livres de mapas colaborativos, é possível incluir estes trajetos como parte das informações de ruas. Assim, este projeto tem o objetivo de investigar o uso das informações das ruas na reconstrução de trajetórias, principalmente de pedestres. O escopo da proposta compreende o desenvolvimento de uma rede social geo-localizada com o intuito de capturar dados de localização. Posteriormente, estes dados serão anonimizados, utilizados na reconstrução de trajetórias de pedestres e disponibilizados para uso em pesquisas futuras. / The ever-greater number of technologies providing location-based services has allowed the generation of big amounts of geolocation data. This data is mainly stored as location points in conjunction with temporal information. A trajectory is defined as a discrete and finite sequence of this kind of points. In recent years, the relatively new field of trajectory data mining aims to leverage this abundance of data. On this field, there are several data mining techniques developed, but all of these depend on trajectory quality. Hence, preprocessing becomes relevant to this field. Among trajectory data mining tasks, one important problem is trajectory reconstruction. Due to the high energy consumption of geolocation devices like GPS and the growing usage of geo-tags in social networks, which can represent trajectories by being sorted chronologically, most of these trajectories are collected at low sampling rates. A majority of research on this problem is focused on using road network information in urbanized areas to reconstruct trajectories. However, these approaches take into account vehicle trajectories only due to fact that most pedestrian paths do not always follow the same road network routes than vehicles. Currently, thanks to open collaborative maps, it is possible to add pedestrian paths to the road network structure. Thereby, this project aims to research the usage of road network information in pedestrian trajectories reconstruction. This projects scope comprises the development of a location-based social network to collect geolocation data. Subsequently, this data will be anonymized, used for pedestrian trajectory reconstruction and, finally, made available for research purposes.

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.

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.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-04-12T20:38:00Z No. of bitstreams: 1 IURY DEWAR CRUZ DE OLIVEIRA NUNES - DISSERTAÇÃO PPGCC 2014..pdf: 1148640 bytes, checksum: 9e084516af4065804bc3489d60d75384 (MD5) / Made available in DSpace on 2018-04-12T20:38:00Z (GMT). No. of bitstreams: 1 IURY DEWAR CRUZ DE OLIVEIRA NUNES - DISSERTAÇÃO PPGCC 2014..pdf: 1148640 bytes, checksum: 9e084516af4065804bc3489d60d75384 (MD5) Previous issue date: 2014-08-28 / As Redes Sociais Baseadas em Localização (RSBL) surgiram com o propósito de permitir que os usuários possam compartilhar com sua rede de amigos informações a respeito dos pontos de interesse (POIs) que eles visitaram. Neste contexto, a capacidade de recomendar novos lugares para que os usuários possam visitar é importante, pois pode, eventualmente, melhorar a experiência destes usuários ao utilizar o sistema. O contexto geogr´afico certamente influencia os usu´arios na hora de escolher os locais a serem visitados. Sendo assim, inicialmente analisamos este contexto de forma isolada, através de recomendadores de POIs puramente baseados em informacões geográficas. Além disso, propomos um novo recomendador puramente geográfico baseado em Kernels Gaussianos. Os resultados dos nossos experimentos demonstraram que o modelo proposto consegue alcançar uma maior acurácia que os recomendadores puramente geográficos presentes no estado-da-arte na maioria dos casos avaliados. Porém esta mesma análise demonstrou que o contexto geográfico isoladamente não é capaz de gerar recomendações com alta acurácia de forma geral. Logo, ao modelar um recomendador de POIs é necessário combinar as informações geográficas com outros contextos a fim de melhorar sua acurácia. Sendo assim, também propomos um novo recomendador de POIs que consegue capturar as preferências de usuários (de forma similar às técnicas de filtragem colaborativa) e informações geográficas em um único modelo baseado em difusão de grafos. Este recomendador visa aprender um ranking personalizado de lugares a serem recomendados para cada usuário levando em consideração os lugares visitados por outros usuários com preferências similares, as distâncias entre os lugares visitados e os lugares candidatos à recomendação, e as regiões as quais o usuário visita mais frequentemente. Os nossos experimentos mostraram que este modelo consegue ser mais eficiente que os modelos de recomendações de POIs presentes no estado-da-arte, além de conseguir alcançar uma acurácia igual ou superior às abordagens comparadas. todos os experimentos foram realizados utilizando dados reais de uma das RSBL mais populares atualmente: o Foursquare. / Location-Based Social Networks (LBSN) emerged with the purpose of allowing users to share, with their friends, information about points of interest (POIs) they visited. In this context, the ability to recommend new places for users to visit is important because it can eventually improve the overall user experience while using the system. The geographical context certainly influences the locations that the users choose to visit. Therefore, initially we analyzed this context separately, through the recommenders of POIs purely based on geographical information. Furthermore, we propose a new geographicaware recommender based on Gaussian Kernels. The results of our experiments demonstrated that the proposed model can achieve higher accuracy than the state-of-the art recommenders solely based on geographical information, in most of the cases evaluated. However, this same analysis showed that the geographical context alone is not able to generate recommendations owith high accuracy. So to model a new recommender of POIs, it is necessary to combine geographic information with other contexts in order to achieve high accuracy. Thus, we also propose a new recommender of POIs that can capture the preferences of users (similar to collaborative filtering techniques) and geographical information in a single model based on diffusion on graphs. This recommender aims to learn a personalized ranking of places to be recommended for each user taking into consideration the places visited by other users with similar preferences, the distances between the places visited and places candidates for recommendation, and the regions which the user visits more often. Our experiments showed that this model can be more efficient than state-of-the-art recommenders of POIs, also achieving an accuracy equal to or greater than the compared approaches. All experiments were conducted using real data from one of the most popular RSBL nowadays: Foursquare.