Online social media, such as Facebook, Twitter, and LinkedIn, provides users with services that enable them to interact both globally and instantly. The nature of social media interactions follows a constantly growing pattern that requires selection mechanisms to find and analyze interesting data. These interactions on social media can then be modeled into interaction networks, which enable network-based and graph-based methods to model and understand users’ behaviors on social media. These methods could also benefit the field of complex networks in terms of finding initial seeds in the information cascade model. This thesis aims to investigate how to efficiently collect user-generated content and interactions from online social media sites. A novel method for data collection that is using an exploratory research, which includes prototyping, is presented, as part of the research results in this thesis.   Analysis of social data requires data that covers all the interactions in a given domain, which has shown to be difficult to handle in previous work. An additional contribution from the research conducted is that a novel method of crawling that extracts all social interactions from Facebook is presented. Over the period of the last few years, we have collected 280 million posts from public pages on Facebook using this crawling method. The collected posts include 35 billion likes and 5 billion comments from 700 million users. The data collection is the largest research dataset of social interactions on Facebook, enabling further and more accurate research in the area of social network analysis.   With the extracted data, it is possible to illustrate interactions between different users that do not necessarily have to be connected. Methods using the same data to identify and cluster different opinions in online communities have also been developed and evaluated. Furthermore, a proposed method is used and validated for finding appropriate seeds for information cascade analyses, and identification of influential users. Based upon the conducted research, it appears that the data mining approach, association rule learning, can be used successfully in identifying influential users with high accuracy. In addition, the same method can also be used for identifying seeds in an information cascade setting, with no significant difference than other network-based methods. Finally, privacy-related consequences of posting online is an important area for users to consider. Therefore, mitigating privacy risks contributes to a secure environment and methods to protect user privacy are presented.

Orientadores: Siome Klein Goldenstein, Ricardo da Silva Torres / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-22T01:52:05Z (GMT). No. of bitstreams: 1 Rezende_RodrigoCarvalho_M.pdf: 3704794 bytes, checksum: 387c6f6ddc154e08ed8277b50d9a99df (MD5) Previous issue date: 2012 / Resumo: Esta dissertação estuda técnicas de Link Analysis para o problema de se calcular similaridade entre artigos acadêmicos organizados em uma biblioteca digital. Neste trabalho construímos um conjunto de dados e desenvolvemos um protocolo experimental para avaliar a eficácia das técnicas desenvolvidas. Para lidar com a alta complexidade dos algoritmos de similaridade para o nosso conjunto de dados, estudamos técnicas de amostragem de grafos e avaliamos objetivamente a qualidade das amostras geradas por estes métodos. A partir deste estudo, propomos um novo algoritmo de amostragem baseado na técnica Forest Fire. Experimentos realizados demonstram a superioridade do algoritmo de amostragem proposto. Além disso, apresenta-se uma nova meta-função de similaridade para artigos acadêmicos que considera apenas a informação de citação entre artigos, sem levar em conta o conteúdo textual e seus metadados para dizer o quanto um artigo é similar a outro. Esta meta-função transforma medidas de similaridade locais, como o coeficiente Jaccard e Adamic/Adar, em medidas recursivas, cuja similaridade depende recursivamente da similaridade de outros artigos relacionados, explorando a ideia de que dois artigos são mais similares na medida em que estão associados a artigos que também são similares. Para avaliação de eficácia do método proposto, criamos um gabarito de similaridade, que deriva da classificação hierárquica dos artigos no sistema de classificação de 1998 da Association for Computer Machinery (ACM). Este gabarito cria uma noção de similaridade tal que dois artigos são mais similares na medida em que são classificados em classes similares, isto é, que estão em classes hierarquicamente próximas. Experimentos são conduzidos no grafo de citação de artigos, extraído da biblioteca digital da ACM, contendo um subconjunto de 122.774 artigos e 523.699 arestas de citações, e comparam esta nova meta função de similaridade com o gabarito de similaridade e revelam que esta gera melhor eficácia que as medidas de similaridade locais consideradas. Além disso, avaliamos esta técnica na atividade prática de busca, por exemplo, e confirmamos que este meta-algoritmo melhora a eficácia das medidas locais consideradas / Abstract: These work studies techniques of Link Analysis used to address the problem of computing the similarity between academic papers organized in a digital library. We constructed a bibliographic dataset and developed an experimental protocol to evaluate the effectiveness of these techniques. To handle the high complexity of the similarity algorithms applied to our dataset, we study graph sampling techniques and evaluate the quality of the samples generated by these methods. This study lead to the proposal of a new sampling algorithm based on an existing technique named Forest Fire. Experiments results demonstrate the superiority of the proposed sampling algorithm. Moreover, we present a new metasimilarity function for scholarly articles that considers only the citation information, which does not take into account their textual content and its metadata, to compute how much an article is similar to another. This meta-function transforms local similarity measures, such as the Jaccard coefficient and Adamic/Adar, into recursive measures, whose similarity score recursively depends on the similarity of other related articles, exploring the idea that two articles are more similar if they are associated with articles which are also similar. To evaluate the effectiveness of the proposed method, we constructed a groundtruth of similarity, which derives from a hierarchical classification system of the Association for Computer Machinery (ACM). This groundtruth creates a notion of similarity such that two articles are more similar if they fall into similar classes (those that are hierarchically close to each other). Experiments are conducted in the citation graph, extracted from the ACM Digital Library, containing a subset of 122,774 articles and 523,699 citation edges. Obtained results demonstrate that this new meta-similarity function outperforms baselines. Furthermore, these results are confirmed in other experiments concerning the use of the proposed meta-functions in similarity search tasks / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientadores: André Franceschi de Angelis, Regina Lúcia de Oliveira Moraes / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-27T04:53:50Z (GMT). No. of bitstreams: 1 Libardi_PaulaLucieneOliveira_M.pdf: 1610224 bytes, checksum: a08b75cd1a30c421927617ee8b6ac8d4 (MD5) Previous issue date: 2015 / Resumo: A identificação de usuários falecidos em Redes Sociais Online é um desafio em aberto e, dado o tamanho das principais redes, abordagens que envolvam intervenção manual são impraticáveis. Usuários inativos por longo tempo inviabilizam soluções simples tais como a expiração de um prazo desde o último acesso, o que torna difícil a diferenciação entre inativos e falecidos. Esta pesquisa iniciou-se com o pressuposto de que o problema poderia ser parcialmente resolvido com métodos automáticos e a hipótese era de que dois métodos aqui propostos, um baseado na análise de frequência de mensagens trocadas entre usuários e outro fundamentado na combinação de informações da topologia da rede junto a inspeções de mensagens, poderiam identificar satisfatoriamente parte dos usuários falecidos. Para testar esta hipótese, recorreu-se à simulação computacional, usando topologias livre de escala e aleatória. O programa que simula as redes foi construído de forma a aplicar e testar os métodos de identificação de falecidos, seguindo padrões de projeto que permitem facilmente a troca ou o encadeamento dos algoritmos a validar. Dessa característica, originou-se um terceiro método, que é a combinação das saídas de algoritmos detectores aplicados anteriormente à rede. Os resultados da pesquisa validaram a hipótese, sendo que os dois métodos propostos inicialmente tiveram, cada qual, índices de acerto superiores a 70% na maioria dos casos simulados, independentemente da topologia da rede. Em ambos os métodos, no entanto, é necessária uma calibração de dois parâmetros operacionais, o que exige algum conhecimento da rede examinada e influencia na taxa de detecção. O último método mostrou-se bastante eficiente, com detecção correta superior a 94%, e capaz de absorver flutuações na taxa de detecção dos demais métodos advindas de suas respectivas parametrizações. Portanto, os objetivos da pesquisa foram plenamente atingidos, com a validação da hipótese inicial, a proposta de três métodos para a solução do problema e a geração de um produto tecnológico, o Demortuos, que é o software de simulação da rede e teste dos métodos, atualmente em processo de registro no Instituto Nacional da Propriedade Industrial (INPI). Adicionalmente, foram abertas possibilidades para o desenvolvimento de métodos automáticos para busca de outras classes de usuários / Abstract: Identifying deceased users in Online Social Networks is an open challenge and, given the size of the main networks, approaches involving manual intervention are impractical. Inactive users for a long time prevent simple solutions such as the expiration of a period since the last entry, making it difficult to differentiate between inactive and deceased users. This research began with the assumption that the problem could be partially solved with automated methods and the hypothesis was that two methods proposed here, one based on frequency analysis of messages exchanged between users and the other based on the combination of topology information network with the messages of inspections, could satisfactorily identify the part of deceased users. To test this hypothesis, we used the computer simulation, using free topologies of scale and random, the latter for comparison purposes. The program that simulates the network was constructed to implement and test the deceased identification methods, following design patterns that easily allow the exchange or the chain of algorithms to validate. This characteristic gave up a third method, which is combining the outputs of detectors algorithms previously applied to the network. The survey results validated the hypothesis, and the two proposed methods initially had, each, hit rates of over 70% in most cases simulated, regardless of the network topology. In both methods, however, two operating parameters calibration is necessary, which requires some knowledge of the network and examined influences the detection rate. The last method proved to be very efficient with proper detection above 94%, and able to absorb fluctuations in the detection rate of other methods resulting from their respective parameterization. Therefore, the research objectives were fully achieved, with the validation of the initial hypothesis, the proposed three methods for the solution of the problem and the generation of a technological product, Demortuos, which is the network simulation software and testing methods currently in the registration process at the National Institute of Industrial Property (INPI). Moreover, possibilities are opened for the development of automated methods to search for other classes of users / Mestrado / Tecnologia e Inovação / Mestra em Tecnologia

O estudo de redes complexas tem alavancado um tremendo interesse em anos recentes. Uma das características salientes de redes complexas é a presença de comunidades, ou grupos de nós densamente conectados. A detecção de comunidades pode não apenas ajudar a entender as estruturas topológicas de redes complexas, mas também pode fornecer novas técnicas para aplicações reais, como mineração de dados. Neste trabalho, propomos um novo modelo para detecção de comunidades em redes complexas, no qual várias partículas caminham na rede e competem umas com as outras para marcar seu próprio território e rejeitar partículas intrusas. O processo atinge o equilíbrio dinâmico quando cada comunidade tem apenas uma partícula. Nossa abordagem não apenas pode obter bons resultados na detecção de comunidades, como também apresenta diversas características interessantes: 1) O processo de competição de partículas é similar a muitos processos naturais e sociais, tais como competição de animais por recursos, exploração territorial por humanos (animais), campanhas eleitorais, etc.. Portanto, o modelo proposto neste trabalho pode ser útil para simular a dinâmica evolutiva de tais processos. 2) Neste modelo, nós introduzimos uma regra para controlar o nível de aleatoriedade do passeio da partícula. Descobrimos que uma pequena porção de aleatoriedade pode aumentar bastante a taxa de detecção de comunidades. Nossa descoberta é análoga ao notável fenômeno chamado ressonância estocástica onde o desempenho de um sistema determinístico não-linear pode ser bastante melhorado através da introdução de um certo nível de ruído. É interessante notar que tal fenômeno é observado em uma situação diferente aos sistemas clássicos de ressonância estocástica. 3) Nossa descoberta indica que a aleatoriedade tem um papel importante em sistemas evolutivos. Ela serve para automaticamente escapar de armadilhas não desejáveis e explorar novos espaços, isto é, ela é um descobridor de novidades. 4) Uma análise quantitativa para processo de competição entre duas particulas e duas comunidades foi conduzida, a qual é um passo de avanço para desenvolvimento de teoria fundamental de aprendizado competitivo / Study of complex networks has triggered tremendous interests in recent years. One of the salient features of complex networks is the presence of communities, or groups of densely connected nodes. Community detection can not only help to understand the topological structure of complex networks, but also provide new techniques for real applications, such as data mining. In this work, a new model for complex network community detection is proposed, in which several particles walk in the network and compete with each other to mark their own territory and reject particle intruders. The process reaches dynamics equilibrium when each community has only one particle. This approach not only can get good community detection results, but also presents several interesting features: 1) The particle competition process is rather similar to many natural and social processes, such as resource competition by animals, territory exploration by humans (animal), election campaigns, etc.. Thus, the model proposed in this work may be useful to simulate dynamical evolution of such processes. 2) In this model, a rule to control the level of randomness of particle walking is introduced. We found a small portion of randomness can largely improve the community detection rate. Such a finding is analogous to a remarkable phenomenon called stochastic resonance (SR) where the performance of a nonlinear deterministic system can be largely enhanced by introducing a certain level of noise. Interestingly, such a SR-type phenomenon is observed in quite a different situation from classical SR systems. 3) Our finding indicates that randomness has an important role in evolutionary systems and in machine learning. It serves to automatically escape some undesirable traps and explore new spaces, i.e., it is a novelty finder. 4) A quantitative analysis for two particle competition in two communities is provided. This is a step toward the development of fundamental theory of competitive learning

Diferentes tipos de neurônios possuem formas distintas, um fator importante para a regulação da forma é a expressão gênica. Além disso, esta característica também está relacionada com a conectividade entre as células nervosas, formando redes. Por meio delas ocorrem as dinâmicas, como por exemplo o aprendizado. Neste trabalho foi desenvolvido um arcabouço de modelagem e simulação neuronal, para analisar a integração das etapas desde a expressão gênica, passando pela geração dos neurônios até as dinâmicas, permitindo o estudo do sistema e relacionamento entre as partes. Na etapa de geração, foram utilizados diferentes padrões de expressão gênica. Por meio dos neurônios, foram criadas as redes, caracterizadas utilizando medidas de centralidade. Ademais, foram executadas as dinâmicas integra-e-dispara, que simula a comunicação entre os neurônios, e o desenvolvimento hebiano, que é uma dinâmica aplicada para simular o aprendizado. Para quantificar a influência da expressão gênica, foram utilizadas as medidas de correlação de Pearson e a informação mútua. Por meio destes testes, foi possível observar que a expressão gênica influencia todas as etapas, sendo que nelas, exceto na geração da forma neuronal, os padrões de expressão com que os neurônios foram organizados também são um fator importante. Além disso, na medida de centralidade betweenness centrality, foi possível observar a formação de caminhos, denominados caminhos do betweenness. Para descrever os caminhos, foram feitas comparações entre as redes neuronais e outras redes espaciais. Assim, foi possível observar que estes caminhos são uma característica comum em redes geográficas e estão relacionados com as comunidades da rede. / Different types of neurons have distinct shapes. An important factor for shape regulation is gene expression, which is also related to the connectivity between nervous cells, creating networks. Dynamics, such as learning, can take place in those networks. In this work we developed a framework for modeling and simulating neurons allowing an integrated analysis from gene expression to dynamics. It will allow the study of the system as a whole as well as the relationships between its parts. In the neuron generation step, we used different patterns of gene expression. The networks were created using those neurons, and several centrality measures were computed to characterize them. Moreover, the dynamic processes considered were the integrate-and-fire model, which simulates communication between neurons, and the hebbian development, which is applied to simulate learning. During every step, Pearsons correlation and mutual information between the level of expression was measured, quantifying the influence of gene expression. Through these experiments it was observed that the gene expression influences all steps, which is in all cases, except in the generation of neuronal shape, an important factor. In addition, by analyzing the betweenness centrality measure, it is possible to observe the formation of paths. To study these paths, comparisons between models and other spatial networks were performed. Thus, it was possible to observe that paths are a common feature in other geographical networks, being related to the connections between network communities.

Na natureza e na ciência, dados e informações que desviam significativamente da média frequentemente possuem grande relevância. Esses dados são usualmente denominados na literatura como outliers. A identificação de outliers é importante em muitas aplicações reais, tais como detecção de fraudes, diagnóstico de falhas, e monitoramento de condições médicas. Nos últimos anos tem-se testemunhado um grande interesse na área de Redes Complexas. Redes complexas são grafos de grande escala que possuem padrões de conexão não trivial, mostrando-se uma poderosa maneira de representação e abstração de dados. Embora um grande montante de resultados tenham sido reportados nesta área de pesquisa, pouco tem sido explorado acerca de detecção de outliers em redes complexas. Considerando-se a dinâmica de uma caminhada aleatória, foram propostos neste trabalho uma medida de distância e um método de ranqueamento de outliers. Através desta técnica, é possível detectar como outlier não somente nós periféricos, mas também nós centrais (hubs), depedendo da estrutura da rede. Também foi identificado que existem características bem definidas entre os nós outliers, relacionadas a funcionalidade dos mesmos para a rede. Além disso, foi descoberto que nós outliers têm papel importante para a rotulação a priori na tarefa de detecção de comunidades semi-supervisionada. Isto porque os nós centrais são bons difusores de informação e os nós periféricos encontram-se em regiões de borda de comunidade. Baseado nessa observação, foi proposto um método de detecção de comunidades semi-supervisionado. Os resultados de simulações mostram que essa abordagem é promissora / In nature and science, information and data that deviate significantly from the average value often have great relevance. These data are often called in literature as outliers. Outlier identification is important in many real applications, such as fraud detection, fault diagnosis, monitoring of medical conditions. In recent years, it has been witnessed a great interest in the area of Complex Networks. Complex networks are large-scale graphs with non-trivial connection patterns, proving to be a powerful way of data representation and abstraction. Although a large amount of results have been reported in this research area, little has been explored about the outlier detection in complex networks. Considering the dynamics of a random walk, we proposed in this paper a distance measure and a outlier ranking method. By using this technique, we can detect not only peripheral nodes, but also central nodes (hubs) as outliers, depending on the network structure. We also identified that there are well defined relationship between the outlier nodes and the functionality of the same nodes for the network. Furthermore, we found that outliers play an important role to label a priori nodes in the task of semi-supervised community detection. This is because the hubs are good information disseminators and peripheral nodes are usually localized in the regions of community edges. Based on this observation, we proposed a method of semi-supervised community detection. The simulation results show that this approach is promising

The complex network theory has been extensively used to understand various natural and artificial phenomena made of interconnected parts. This representation enables the study of dynamical processes running on complex systems, such as epidemics and rumor spreading. The evolution of these dynamical processes is influenced by the organization of the network. The size of some real world networks makes it prohibitive to analyse the whole network computationally. Thus it is necessary to represent it by a set of topological measures or to reduce its size by means of sampling. In addition, most networks are samples of a larger networks whose structure may not be captured and thus, need to be inferred from samples. In this work, we study both problems: the influence of the structure of the network in spreading processes and the effects of sampling in the structure of the network. Our results suggest that it is possible to predict the final fraction of infected individuals and the final fraction of individuals that came across a rumor by modeling them with a beta regression model and using topological measures as regressors. The most influential measure in both cases is the average search information, that quantifies the ease or difficulty to navigate through a network. We have also shown that the structure of a sampled network differs from the original network and that the type of change depends on the sampling method. Finally, we apply four sampling methods to study the behaviour of the epidemic threshold of a network when sampled with different sampling rates and found out that the breadth-first search sampling is most appropriate method to estimate the epidemic threshold among the studied ones. / Vários fenômenos naturais e artificiais compostos de partes interconectadas vem sendo estudados pela teoria de redes complexas. Tal representação permite o estudo de processos dinâmicos que ocorrem em redes complexas, tais como propagação de epidemias e rumores. A evolução destes processos é influenciada pela organização das conexões da rede. O tamanho das redes do mundo real torna a análise da rede inteira computacionalmente proibitiva. Portanto, torna-se necessário representá-la com medidas topológicas ou amostrá-la para reduzir seu tamanho. Além disso, muitas redes são amostras de redes maiores cuja estrutura é difícil de ser capturada e deve ser inferida de amostras. Neste trabalho, ambos os problemas são estudados: a influência da estrutura da rede em processos de propagação e os efeitos da amostragem na estrutura da rede. Os resultados obtidos sugerem que é possível predizer o tamanho da epidemia ou do rumor com base em um modelo de regressão beta com dispersão variável, usando medidas topológicas como regressores. A medida mais influente em ambas as dinâmicas é a informação de busca média, que quantifica a facilidade com que se navega em uma rede. Também é mostrado que a estrutura de uma rede amostrada difere da original e que o tipo de mudança depende do método de amostragem utilizado. Por fim, quatro métodos de amostragem foram aplicados para estudar o comportamento do limiar epidêmico de uma rede quando amostrada com diferentes taxas de amostragem. Os resultados sugerem que a amostragem por busca em largura é a mais adequada para estimar o limiar epidêmico entre os métodos comparados.

The importance of modelling the spreading of infectious diseases as part of a public health strategy has been highlighted by the ongoing coronavirus pandemic. This includes identifying the geographical areas or travel routes most likely to contribute to the spreading of an outbreak. These areas and routes can then be monitored as part of an early warning system, be part of intervention strategies, e.g. lockdowns, aiming to mitigate the spreading of the disease or be a focus of vaccination campaigns.  This thesis focus on developing a network-based infection model between the municipalities of Sweden in order to identify the areas most likely to contribute to an epidemic. First, a human mobility model is constructed based on the well-known radiation model. Then a network-based SEIR compartmental model is employed to simulate epidemic outbreaks with various parameters. Finally, the adoption of the influence maximization problem known in network science to identify the municipalities having the largest impact on the spreading of infectious diseases.  The resulting super-spreading municipalities point towards confirmation of the known fact that central highly populated regions in highly populated areas carry a greater risk than their neighbours initially. However, once these areas are targeted, the other resulting nodes show a greater variety in geographical location than expected. Furthermore, a correlation can be seen between increased infections time and greater variety, although more empirical data is required to support this claim.   For further evaluation of the model, the mobility network was studied due to its central role in creating data for the model parameters. Commuting data in the Gothenburg region were compared to the estimations, showing an overall good accuracy with major deviations in few cases.

Spatial and topological features of urban road networks have been observed variously in the past. No previous study, however, has investigated and compared an extensive data set from cities all over the world regarding their network properties. In this work, re-spectively 20 large cities from 5 continents and Germany are analyzed. In the process, node degree, link length, shortest paths, detour index as well as measures for rectangu-larity are used to characterize and to differentiate the networks. While most networks properties are quite diverse from continent to continent, the detour index as a measure of efficiency shows remarkable similarities and homogeneity over all regions, independ-ent of their spatial network structure. It is shown that in some cities this efficiency is mainly sustained by a subnetwork of major roads, while in others it relies on a balance between minor and major roads. Rectangularity in all regions is shown to be predomi-nant in the structure of minor road subnetworks, while it is shown that this feature is not trivially connected to the node degree.:Table of Contents List of Figures V List of Tables VI Chapter 1 Introduction 1 Chapter 2 Preliminaries 4 2.1 Complex Networks 4 2.2 Network Characteristics 5 2.2.1 Node Degree 5 2.2.2 Link Length 6 2.2.3 Shortest Path Length 7 2.2.4 Detour Index 7 2.2.5 Rectangularity 8 2.3 Data 11 2.3.1 Data Source and Analyzed Cities 11 2.3.2 Data Structure 12 2.3.3 Data Quality 14 2.4 Data Preprocessing 15 2.4.1 Removal of Dead Ends 16 2.4.2 Removal of Transient Nodes 17 2.4.3 Merging of Multi-Node Intersections and Roads with Separated Lanes 17 2.5 Network Modifications 20 Chapter 3 Results and Discussion 23 3.1 Unmodified Networks 23 3.1.1 Node Degree 23 3.1.2 Link Length 25 3.1.3 Network Efficiency 28 3.1.4 Rectangularity 30 3.2 Modified Networks and Comparison to Unmodified Networks 36 3.2.1 Node Degree 37 3.2.2 Link Length 39 3.2.3 Network Efficiency 41 3.2.4 Rectangularity 46 Chapter 4 Conclusion and Outlook 49 References 51 Appendix A Detailed Results of Unmodified Networks 55 Appendix A.1 Europe 55 Appendix A.2 Anglo America 56 Appendix A.3 Latin America 57 Appendix A.4 Asia 58 Appendix A.5 Africa 59 Appendix A.6 Germany 60 Appendix B Corrupted Networks due to Merging of Intersections with Radius 50 m 61 Appendix C Modification 2 62 Appendix D Spatial Distributions of Network Measures 63 Appendix D.1 Node Degree 63 Appendix D.2 Link Length 64 Appendix D.3 Detour Index 65 Appendix D.4 Rectangularity 66 Appendix E Detailed results of modified networks 67 Appendix E.1 Europe 67 Appendix E.2 Anglo America 68 Appendix E.3 Latin America 69 Appendix E.4 Asia 70 Appendix E.5 Africa 71 Appendix E.6 Germany 72 / Räumliche und topografische Eigenschaften urbaner Straßennetzwerke sind in der Ver-gangenheit vielfältig untersucht wurden. Keine der bisherigen Studien hat jedoch eine umfassende Anzahl weltweiter Städte auf ihre Netzwerkeigenschaften untersucht. In dieser Arbeit werden jeweils 20 Großstädte aus 5 Kontinenten analysiert. Knotengrad, Kantenlängen, kürzeste Pfade, Detour Index sowie die Rechtwinkligkeit werden schritt-weise untersucht, um die Netzwerke zu charakterisieren und voneinander zu differen-zieren. Während die meisten Netzwerkmaße große Unterscheide von Kontinent zu Kon-tinent aufweisen, lassen sich beim Detour Index, welcher ein Maß für die Effizienz im Netzwerk dient, bemerkenswerte Gemeinsamkeiten in allen Regionen unabhängig von der räumlichen Netzwerkstruktur feststellen. Es wird gezeigt, dass die Effizienz in eini-gen Städten hauptsächlich durch ein Teilnetz von Hauptstraßen getragen wird, während sie anderswo auf einer Balance zwischen Haupt- und Nebenstraßen beruht. Vor allem in der Struktur von Nebenstraßennetzwerken kann Rechtwinkligkeit festgestellt werden, während gleichzeitig wird, dass letztere in keinem trivialen Zusammenhang mit dem Knotengrad steht.:Table of Contents List of Figures V List of Tables VI Chapter 1 Introduction 1 Chapter 2 Preliminaries 4 2.1 Complex Networks 4 2.2 Network Characteristics 5 2.2.1 Node Degree 5 2.2.2 Link Length 6 2.2.3 Shortest Path Length 7 2.2.4 Detour Index 7 2.2.5 Rectangularity 8 2.3 Data 11 2.3.1 Data Source and Analyzed Cities 11 2.3.2 Data Structure 12 2.3.3 Data Quality 14 2.4 Data Preprocessing 15 2.4.1 Removal of Dead Ends 16 2.4.2 Removal of Transient Nodes 17 2.4.3 Merging of Multi-Node Intersections and Roads with Separated Lanes 17 2.5 Network Modifications 20 Chapter 3 Results and Discussion 23 3.1 Unmodified Networks 23 3.1.1 Node Degree 23 3.1.2 Link Length 25 3.1.3 Network Efficiency 28 3.1.4 Rectangularity 30 3.2 Modified Networks and Comparison to Unmodified Networks 36 3.2.1 Node Degree 37 3.2.2 Link Length 39 3.2.3 Network Efficiency 41 3.2.4 Rectangularity 46 Chapter 4 Conclusion and Outlook 49 References 51 Appendix A Detailed Results of Unmodified Networks 55 Appendix A.1 Europe 55 Appendix A.2 Anglo America 56 Appendix A.3 Latin America 57 Appendix A.4 Asia 58 Appendix A.5 Africa 59 Appendix A.6 Germany 60 Appendix B Corrupted Networks due to Merging of Intersections with Radius 50 m 61 Appendix C Modification 2 62 Appendix D Spatial Distributions of Network Measures 63 Appendix D.1 Node Degree 63 Appendix D.2 Link Length 64 Appendix D.3 Detour Index 65 Appendix D.4 Rectangularity 66 Appendix E Detailed results of modified networks 67 Appendix E.1 Europe 67 Appendix E.2 Anglo America 68 Appendix E.3 Latin America 69 Appendix E.4 Asia 70 Appendix E.5 Africa 71 Appendix E.6 Germany 72

Durch die Anwendung der Theorie Komplexer Netzwerke auf die Topologie komplexer Materialflusssysteme (MFS), im Speziellen auf Gepäckförderanlagen (GFA) in Flughäfen, wurden Erkenntnisse für die Generierung und Optimierung der Layouts gewonnen. Zunächst wird die einfache Anwendbarkeit von Netzwerkanalysemethoden auf komplexe MFS gezeigt. Dadurch können generische Eigenschaften der Systeme untersucht werden, die mit anderen Methoden nicht zugänglich sind. Des Weiteren wird dargelegt, dass alle untersuchten GFA ähnliche Charakteristiken aufweisen, was zukünftig für die Generierung der Topologien genutzt werden kann. Durch diese Analysemethodik werden wichtige Einblicke in Materialflüsse in GFA ohne aufwändige Simulationen möglich. Bereits einfache Analysen lassen neue Schlüsse auf Eigenschaften wie die Robustheit und Leistung eines MFS zu. Die Algorithmen sind leicht in der frühen Planungsphase einsetzbar und versprechen ein ausgereifteres System, welches in späteren (Simulations-) Phasen mit geringeren Änderungen auskommt.