A shuman beings, we are continuously struggling to comprehend the mechanism of dierent natural systems. Many times, we face a complex system where the emergent properties of the system at a global level can not be explained by a simple aggregation of the system's components at the micro-level. To better understand the macroscopic system eects, we try to model microscopic events and their interactions. In order to do so, we rely on specialized tools to connect local mechanisms with global phenomena. One such tool is network theory. Networks provide a powerful way of modeling and analyzing complex systems based on interacting elements. The interaction pattern links the elements of the system together and provides a structure that controls how information permeates throughout the system. For example, the passing of information about job opportunities in a society depends on how social ties are organized. The interaction pattern, therefore, often is essential for reconstructing and understanding the global-scale properties of the system. In this thesis, I describe tools and models of network theory that we use and develop to analyze the organization of social or transportation systems. More specifically, we explore complex networks by asking two general questions: First, which mechanistic theoretical models can better explain network formation or spreading processes on networks? And second, what are the signi cant functional units of real networks? For modeling, for example, we introduce a simple agent-based model that considers interacting agents in dynamic networks that in the quest for information generate groups. With the model, we found that the network and the agents' perception are interchangeable; the global network structure and the local information pathways are so entangled that one can be recovered from the other one. For investigating signi cant functional units of a system, we detect, model, and analyze signi cant communities of the network. Previously introduced methods of significance analysis suer from oversimpli ed sampling schemes. We have remedied their shortcomings by proposing two dierent approaches: rst by introducing link prediction and second by using more data when they are available. With link prediction, we can detect statistically signi cant communities in large sparse networks. We test this method on real networks, the sparse network of the European Court of Justice case law, for example, to detect signi cant and insigni cant areas of law. In the presence of large data, on the other hand, we can investigate how underlying assumptions of each method aect the results of the signi cance analysis. We used this approach to investigate dierent methods for detecting signi cant communities of time-evolving networks. We found that, when we highlight and summarize important structural changes in a network, the methods that maintain more dependencies in signi cance analysis can predict structural changes earlier. In summary, we have tried to model the systems with as simple rules as possible to better understand the global properties of the system. We always found that maintaing information about the network structure is essential for explaining important phenomena on the global scale. We conclude that the interaction pattern between interconnected units, the network, is crucial for understanding the global behavior of complex systems because it keeps the system integrated. And remember, everything is connected, albeit not always directly.

As redes sociais se tornaram um novo e importante meio de intercâmbio de informações, ideias e comunicação que aproximam parentes e amigos sem importar as distâncias. Dada a natureza aberta da Internet, as informações podem fluir muito fácil e rápido na população. A rede pode ser representada como um grafo, onde os indivíduos ou organizações são o conjunto de vértices e os relacionamentos ou conexões entre os vértices são o conjunto de arestas. Além disso, as redes sociais representam intrinsecamente a estrutura de um sistema mais complexo que é a sociedade. Estas estruturas estão relacionadas com as características dos indivíduos. Por exemplo, os indivíduos mais populares são aqueles com maior número de conexões. Em particular, é aceito que a estrutura da rede pode afetar a forma como a informação se propaga nas redes sociais. No entanto, ainda não está claro como a estrutura influencia na propagação, como medir seu impacto e quais as possíveis estratégias para controlar o processo de difusão. Nesta tese buscamos contribuir nas análises da interação entre as dinâmicas de propagação de informações e rumores e a estrutura da rede. Propomos um modelo de propagação mais realista considerando a heterogeneidade dos indivíduos na transmissão de ideias ou informações. Nós confirmamos a presença de propagadores mais influentes na dinâmica de rumor e observamos que é possível melhorar ou reduzir expressivamente a difusão de uma informação ao selecionar uma fração muito pequena de propagadores influentes. No caso em que se objetiva selecionar um conjunto de propagadores iniciais que maximizem a difusão de informação, a melhor opção é selecionar os indivíduos mais centrais ou importantes nas comunidades. Porém, se o padrão de conexão dos vértices está negativamente correlacionado, a melhor alternativa é escolher entre os indivíduos mais centrais de toda a rede. Por outro lado, através de abordagens topológicas e de técnicas de aprendizagem máquina, identificamos aos propagadores menos influentes e mostramos que eles atuam como um firewall no processo de difusão. Nós propomos um método adaptativo de reconexão entre os vértices menos influentes para um indivíduo central da rede, sem afetar a distribuição de grau da rede. Aplicando o nosso método em uma pequena fração de propagadores menos influentes, observamos um aumento importante na capacidade de propagação desses vértices e da rede toda. Nossos resultados vêm de uma ampla gama de simulações em conjuntos de dados artificiais e do mundo real e a comparação com modelos clássicos de propagação da literatura. A propagação da informação em redes é de grande relevância para as áreas de publicidade e marketing, educação, campanhas políticas ou de saúde, entre outras. Os resultados desta tese podem ser aplicados e estendidos em diferentes campos de pesquisa como redes biológicas e modelos de comportamento social animal, modelos de propagação de epidemias e na saúde pública, entre outros. / On-line Social networks become a new and important medium of exchange of information, ideas and communication that approximate relatives and friends no matter the distances. Given the open nature of the Internet, the information can flow very easy and fast in the population. The network can be represented as a graph, where individuals or organizations are the set of vertices and the relationship or connection among the vertices are the set of edge. Moreover, the social networks are also intrinsically representing the structure of a more complex system that is the society. These structures are related with characteristics of the subjects, like the most popular individuals have many connections, the correlation in the connectivity of vertices that is a trace of homophily phenomenon, among many others. In particular, it is well accepted that the structure of the network can affect the way the information propagates on the social networks. However, how the structure impacts in the propagation, how to measure that impact and what are the strategies for controlling the propagation of some information, it is still unclear. In this thesis, we seek to contribute in the analysis of the interplay between the dynamics of information and rumor spreading and the structure of the networks. We propose a more realistic propagation model considering the heterogeneity of the individuals in the transmission of ideas or information. We confirm the presence of influential spreaders in the rumor propagation process and found that selecting a very small fraction of influential spreaders, it is possible to expressively improve or reduce de diffusion of some information on the network. In the case we want to select a set of initial spreaders that maximize the information diffusion on the network, the simple and best alternative is to select the most central or important individuals from the networks communities. But, if the pattern of connection of the networks is negatively correlated, the best alternative is to choose from the most central individuals in the whole network. On the other hand, we identify, by topological approach and machine learning techniques, the least influential spreaders and show that they act as a firewall in the propagation process. We propose an adaptative method that rewires one edge for a given vertex to a central individual, without affecting the overall distribution of connection. Applying our proposed method in a little fraction of least influential spreaders, we observed an important increasing in the capacity of propagation of these vertices and in the overall network. Our results are from a wide range of simulations in artificial and real-world data sets and the comparison with the classical rumor propagation model. The propagation of information is of greatest relevance for publicity and marketing area, education, political or health campaigns, among others. The results of this these might be applicable and extended in different research fields like biological networks and animal social behavior models.

As redes sociais se tornaram um novo e importante meio de intercâmbio de informações, ideias e comunicação que aproximam parentes e amigos sem importar as distâncias. Dada a natureza aberta da Internet, as informações podem fluir muito fácil e rápido na população. A rede pode ser representada como um grafo, onde os indivíduos ou organizações são o conjunto de vértices e os relacionamentos ou conexões entre os vértices são o conjunto de arestas. Além disso, as redes sociais representam intrinsecamente a estrutura de um sistema mais complexo que é a sociedade. Estas estruturas estão relacionadas com as características dos indivíduos. Por exemplo, os indivíduos mais populares são aqueles com maior número de conexões. Em particular, é aceito que a estrutura da rede pode afetar a forma como a informação se propaga nas redes sociais. No entanto, ainda não está claro como a estrutura influencia na propagação, como medir seu impacto e quais as possíveis estratégias para controlar o processo de difusão. Nesta tese buscamos contribuir nas análises da interação entre as dinâmicas de propagação de informações e rumores e a estrutura da rede. Propomos um modelo de propagação mais realista considerando a heterogeneidade dos indivíduos na transmissão de ideias ou informações. Nós confirmamos a presença de propagadores mais influentes na dinâmica de rumor e observamos que é possível melhorar ou reduzir expressivamente a difusão de uma informação ao selecionar uma fração muito pequena de propagadores influentes. No caso em que se objetiva selecionar um conjunto de propagadores iniciais que maximizem a difusão de informação, a melhor opção é selecionar os indivíduos mais centrais ou importantes nas comunidades. Porém, se o padrão de conexão dos vértices está negativamente correlacionado, a melhor alternativa é escolher entre os indivíduos mais centrais de toda a rede. Por outro lado, através de abordagens topológicas e de técnicas de aprendizagem máquina, identificamos aos propagadores menos influentes e mostramos que eles atuam como um firewall no processo de difusão. Nós propomos um método adaptativo de reconexão entre os vértices menos influentes para um indivíduo central da rede, sem afetar a distribuição de grau da rede. Aplicando o nosso método em uma pequena fração de propagadores menos influentes, observamos um aumento importante na capacidade de propagação desses vértices e da rede toda. Nossos resultados vêm de uma ampla gama de simulações em conjuntos de dados artificiais e do mundo real e a comparação com modelos clássicos de propagação da literatura. A propagação da informação em redes é de grande relevância para as áreas de publicidade e marketing, educação, campanhas políticas ou de saúde, entre outras. Os resultados desta tese podem ser aplicados e estendidos em diferentes campos de pesquisa como redes biológicas e modelos de comportamento social animal, modelos de propagação de epidemias e na saúde pública, entre outros. / On-line Social networks become a new and important medium of exchange of information, ideas and communication that approximate relatives and friends no matter the distances. Given the open nature of the Internet, the information can flow very easy and fast in the population. The network can be represented as a graph, where individuals or organizations are the set of vertices and the relationship or connection among the vertices are the set of edge. Moreover, the social networks are also intrinsically representing the structure of a more complex system that is the society. These structures are related with characteristics of the subjects, like the most popular individuals have many connections, the correlation in the connectivity of vertices that is a trace of homophily phenomenon, among many others. In particular, it is well accepted that the structure of the network can affect the way the information propagates on the social networks. However, how the structure impacts in the propagation, how to measure that impact and what are the strategies for controlling the propagation of some information, it is still unclear. In this thesis, we seek to contribute in the analysis of the interplay between the dynamics of information and rumor spreading and the structure of the networks. We propose a more realistic propagation model considering the heterogeneity of the individuals in the transmission of ideas or information. We confirm the presence of influential spreaders in the rumor propagation process and found that selecting a very small fraction of influential spreaders, it is possible to expressively improve or reduce de diffusion of some information on the network. In the case we want to select a set of initial spreaders that maximize the information diffusion on the network, the simple and best alternative is to select the most central or important individuals from the networks communities. But, if the pattern of connection of the networks is negatively correlated, the best alternative is to choose from the most central individuals in the whole network. On the other hand, we identify, by topological approach and machine learning techniques, the least influential spreaders and show that they act as a firewall in the propagation process. We propose an adaptative method that rewires one edge for a given vertex to a central individual, without affecting the overall distribution of connection. Applying our proposed method in a little fraction of least influential spreaders, we observed an important increasing in the capacity of propagation of these vertices and in the overall network. Our results are from a wide range of simulations in artificial and real-world data sets and the comparison with the classical rumor propagation model. The propagation of information is of greatest relevance for publicity and marketing area, education, political or health campaigns, among others. The results of this these might be applicable and extended in different research fields like biological networks and animal social behavior models.

This study has been conducted with Sirius International as a case company. The investigation has revolved around the weaknesses Sirius, along with the authors, have identified concerning the international collaboration and communication. It was later shown that these problems were based on a low sense of unity in the organization as a result of the lack of knowledge sharing, knowledge management, and spread of organization related information. It was decided to evaluate whether a corporate social network (CSN) could assist in these problems and if so, decide what system would be the most appropriate in regards to the internal needs and requirements at Sirius. The major challenges brought on with an implementation of a CSN, and how to face these, were investigated as a part of the evaluation whether a CSN would be appropriate for Sirius or not. The study showed that a CSN was an appropriate choice for Sirius in order to improve the international communication, collaboration, and unity. The most suitable choice was determined to be Yammer, as it best suited the internal requirements and needs. Along with these results, the largest challenge with an implementation and future use of the system was user acceptance and overall usage of the system. If the CSN is not used, none of the visions, goals, or purposes will be fulfilled. / Denna studie har gjorts med Sirius International som case-företag. Undersökningen har kretsat kring svagheterna som Sirius, tillsammans med författarna har identifierat kring det internationella samarbetet och kommunikationen. Det visade sig senare att dessa problem var grundade i en låg känsla av samhörighet i organisationen och att detta var ett resultat av den låga nivån av kunskapsspridning, kunskapshantering och spridning av organisationsrelaterad information. Beslutet togs att undersöka huruvida ett företags-baserat socialt nätverk kunde hjälpa vid dessa problem och, om fallet var sådant, komma fram till vilket socialt nätverk som skulle vara mest lämpat vid avseende på de interna behoven och kraven från Sirius. Vid undersökningen om huruvida ett socialt nätverk var lämpligt för Sirius gjordes också en undersökning för att identifiera de största utmaningarna med en implementation av ett socialt nätverk och hur dessa skall bemötas och övervinnas. Studien visade att ett företagsbaserat socialt nätverk var ett lämpligt val för att överkomma problemen i Sirius och förbättra den internationella kommunikationen, samarbetet och samhörigheten. Det lämpligaste sociala nätverket för Sirius blev Yammer som bäst täckte de interna behoven och kraven hos Sirius. Tillsammans med dessa resultat visade undersökningen att den största utmaningen med en implementation och framtida nyttjande av systemet var användaracceptans och generell användning av systemet. Om ett socialt nätverk inte används så kan inga av visionerna, målen eller syftena med systemet infrias.