Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-04-07T15:49:01Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) tese_jcbr_201511.pdf: 2348357 bytes, checksum: 5ab9955a4ce8849c92d0631d6674d12e (MD5) / Made available in DSpace on 2016-04-07T15:49:01Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) tese_jcbr_201511.pdf: 2348357 bytes, checksum: 5ab9955a4ce8849c92d0631d6674d12e (MD5) Previous issue date: 2015-08-25 / CNPq / A web, inicialmente um mero repositório de informações estáticas, transformou-se numa enorme fonte de aplicações diversas, proporcionando ou fomentando entretenimento, negócios e relacionamentos. Com essa evolução, a web passou a conter uma enorme quantidade de informações valiosas sobre produtos e serviços, especialmente em sites de compra, sites específicos para avaliação de produtos e até mesmo em redes sociais. Com as ferramentas adequadas, é possível monitorar opiniões ou mensurar a aceitação de um objeto qualquer a partir de dados disponíveis online, ao invés de realizar pesquisas de opinião usuais, que são demoradas, trabalhosas, tem alto custo e alcançam um número bastante restrito de pessoas. Com o monitoramento online, todo o processo de consolidação de opiniões pode ser realizado de forma automática, oferecendo um feedback imediato e mais representativo sobre o objeto avaliado. O problema geral desta proposta de tese é a classificação dos usuários de acordo com suas opiniões sobre um objeto de interesse. Comumente, a classificação das opiniões emitidas por um dado usuário é feita através da classificação de sentimentos expressos em textos, postagens ou comentários. Se a classificação de opiniões, no entanto, for realizada em ambientes nos quais haja conexões entre seus usuários (como as redes sociais), uma nova dimensão de informação se apresenta: através da análise dos relacionamentos, é possível inferir as opiniões de usuários a partir da opinião de seus contatos. A abordagem proposta neste trabalho para realização de análise de sentimento em redes sociais é baseada no princípio da assortatividade, que estabelece que indivíduos tendem a se conectar a outros com os quais apresentam alto grau de semelhança. A partir desse conceito, são aplicadas técnicas de classificação coletiva sobre o grafo que representa a rede social. A intenção é explorar o fato de que a classificação coletiva não utiliza apenas as características locais dos nós no processo de inferência, mas também as características e classes dos nós relacionados. Além disso, a classificação é executada de forma simultânea sobre todas as instâncias, o que permite considerar as influências que cada instância exerce sobre outras às quais está relacionada. Para avaliação da viabilidade do método proposto, foi implementado um protótipo que usa um algoritmo de relaxation labeling para a classificação coletiva de opiniões de usuários, e foi desenvolvido um estudo de caso para predição de preferência política de usuários do Twitter, que alcançou resultados promissores. / The web, which was initially a mere repository for static information, has turned into a huge source of different applications, containing not only information but also promoting entertainment, business and relationships. Thus, the web currently has plenty of valuable information on products and services, especially in shopping, product evaluation and social networks websites. With the proper tools, it is possible to monitor opinions or to measure acceptance of a given object from data available online, instead of running usual polls, which are time and labor consuming, expensive and have limited reach. With online monitoring, the opinion consolidation process may be done automatically, offering an immediate, representative feedback on the evaluated object. This thesis proposal general problem is the classification of users according to his/her opinions given a target object. Commonly, the user opinion classification is performed through the use of text classifiers over his/her texts, comments or posts. If this opinion classification process takes place in environments where there are connections among its users (like social networks), a new information dimension shows up: through analysis of users relationships, it is possible to infer users opinions by using his/her contacts opinions. The approach proposed here to social networks sentiment analysis is based on the homophily principle, which states that users are more likely to connect to similar others. Using that concept, we apply collective classification techniques on the graph that represents the social network. The intention is to leverage the fact that collective classification uses not only the local node features in the inference process, but also the features and classes of the neighborhood. Besides, the classification is executed simultaneously on all nodes, which allows considering the influences of each node on its neighbors. To evaluate the proposed method, we implemented a prototype which uses a relaxation labeling algorithm for the collective classification of users opinions, and developed a case study to predict the political preference of users in Twitter, achieving promising results.

<p>The most important networks from different domains—such as Computing, Organization, Economic, Social, Academic, and Biology—are networks that change over time. For example, in an organization there are email and collaboration networks (e.g., different people or teams working on a document). Apart from the connectivity of the networks changing over time, they can contain attributes such as the topic of an email or message, contents of a document, or the interests of a person in an academic citation or a social network. Analyzing these dynamic networks can be critical in decision-making processes. For instance, in an organization, getting insight into how people from different teams collaborate, provides important information that can be used to optimize workflows.</p> <p><br></p> <p>Network generative models provide a way to study and analyze networks. For example, benchmarking model performance and generalization in tasks like node classification, can be done by evaluating models on synthetic networks generated with varying structure and attribute correlation. In this work, we begin by presenting our systemic study of the impact that graph structure and attribute auto-correlation on the task of node classification using collective inference. This is the first time such an extensive study has been done. We take advantage of a recently developed method that samples attributed networks—although static—with varying network structure jointly with correlated attributes. We find that the graph connectivity that contributes to the network auto-correlation (i.e., the local relationships of nodes) and density have the highest impact on the performance of collective inference methods.</p> <p><br></p> <p>Most of the literature to date has focused on static representations of networks, partially due to the difficulty of finding readily-available datasets of dynamic networks. Dynamic network generative models can bridge this gap by generating synthetic graphs similar to observed real-world networks. Given that motifs have been established as building blocks for the structure of real-world networks, modeling them can help to generate the graph structure seen and capture correlations in node connections and activity. Therefore, we continue with a study of motif evolution in <em>dynamic</em> temporal graphs. Our key insight is that motifs rarely change configurations in fast-changing dynamic networks (e.g. wedges intotriangles, and vice-versa), but rather keep reappearing at different times while keeping the same configuration. This finding motivates the generative process of our proposed models, using temporal motifs as building blocks, that generates dynamic graphs with links that appear and disappear over time.</p> <p><br></p> <p>Our first proposed model generates dynamic networks based on motif-activity and the roles that nodes play in a motif. For example, a wedge is sampled based on the likelihood of one node having the role of hub with the two other nodes being the spokes. Our model learns all parameters from observed data, with the goal of producing synthetic graphs with similar graph structure and node behavior. We find that using motifs and node roles helps our model generate the more complex structures and the temporal node behavior seen in real-world dynamic networks.</p> <p><br></p> <p>After observing that using motif node-roles helps to capture the changing local structure and behavior of nodes, we extend our work to also consider the attributes generated by nodes’ activities. We propose a second generative model for attributed dynamic networks that (i) captures network structure dynamics through temporal motifs, and (ii) extends the structural roles of nodes in motifs to roles that generate content embeddings. Our new proposed model is the first to generate synthetic dynamic networks and sample content embeddings based on motif node roles. To the best of our knowledge, it is the only attributed dynamic network model that can generate <em>new</em> content embeddings—not observed in the input graph, but still similar to that of the input graph. Our results show that modeling the network attributes with higher-order structures (e.g., motifs) improves the quality of the networks generated.</p> <p><br></p> <p>The generative models proposed address the difficulty of finding readily-available datasets of dynamic networks—attributed or not. This work will also allow others to: (i) generate networks that they can share without divulging individual’s private data, (ii) benchmark model performance, and (iii) explore model generalization on a broader range of conditions, among other uses. Finally, the evaluation measures proposed will elucidate models, allowing fellow researchers to push forward in these domains.</p>