O crescimento constante dos dados musicais na Internet tem encorajado diversos pesquisadores a desenvolver ferramentas adequadas para a análise e a classificação destes dados. O objetivo principal de tais ferramentas é extrair a informação de forma compacta e representativa ao conteúdo dos bancos de dados. Dentro deste contexto, os gêneros musicais apresentam descrições importantes para o desenvolvimento destas ferramentas. Além dos mesmos serem usados frequentemente para organizar coleções musicais e refletirem a interação ente culturas, resumem características (padrões) comuns entre as peças musicais. Em face ao exposto, a principal motivação deste projeto de pesquisa é propor uma maneira original, e de baixo esforço computacional, para representar os gêneros musicais e investigar a contribuição desta representação em aplicações e estudos que estão inseridos no contexto de pesquisas que envolvem a recuperação da informação musical. A representação proposta refere-se aos padrões rítmicos das músicas, uma vez que o ritmo configura um aspecto musical significante na discriminação dos gêneros. Os padrões rítmicos são estabelecidos pela dependência temporal das notas musicais presentes na percussão, de forma que cada música é representada por um vetor de probabilidades condicionais entre pares e trios de notas computadas pelo uso de cadeias de Markov de primeira e segunda ordem. Os padrões rítmicos de diversos gêneros são explorados em aplicações como: classificação, síntese musical, recomendação musical, humor/emoção em música, e análise de aspectos evolutivos. Constatou-se que estes, como estabelecidos neste estudo, são sensíveis à discriminação dos gêneros, evidenciando sequências de notas que são comuns aos mesmos, e sequências que são distintas e características de cada um. Uma segunda motivação deste projeto é o uso de medidas topológicas de redes e dígrafos de músicas para a análise dos dados. Comunidades obtidas nestas redes proporcionaram a definição de uma abordagem não supervisionada, a qual apresentou taxas de desempenho superiores ao agrupamento hierárquico. A determinação das características rítmicas de cada música motivou o desenvolvimento de estratégias para a composição automática e para a geração de listas de reprodução, assim como para a averiguação da relação destes padrões com aspectos emotivos. Por fim, uma análise estatística da evolução do ritmo de diferentes gêneros é desempenhada, na qual verificou-se a presença de mecanismos de inovação e recuperação. Estes mecanismos parecem ser consequência da competição entre fatores que favorecem a inovação de material musical, e fatores que a previnem, como, por exemplo, a obediência às regras de composição que mantém as características fundamentais de cada gênero. / Musical databases have increased in number and size continuously, paving the way to large amounts of online music data, including discographies, biographies and lyrics. The constant growth of data on the Internet has attracted musical research for developing tools to analyze and classify music data. The main objective of such tools is to extract reliable information to adequately represent and compact music content in databases. In this context, musical genres are particularly interesting descriptors, since they have being used for years to organize music collections, reflect interaction between cultures and summarize common features (or patterns) between musical pieces. The main motivation of this study is to propose a original and low cost framework to represent musical genres, as well as investigate the contribution of this representation in applications and studies that are placed in the context of music information retrieval researches. The representation of music content is referred to the rhythmic patterns, since rhythm configures a significant aspect in the discrimination of musical genres. The rhythmic patterns are determined by the temporal dependency of the musical notes present in the percussion, so that each song is represented by a vector of conditional probabilities between pairs and triples of notes, computed by the use of first and second order Markov chains. The rhythm patterns from distinct genres are investigated in applications such as: classification, music synthesis, music recommendation, mood/emotion in music, and analysis of evolutionary aspects. The main finding is that the rhythmic patterns as established in this study are sensitive to the genre discrimination, suggesting that there are sequences of notes common to all genres, and sequences that are distinct and characteristics of each one. A second motivation for this study is the use of topological measures of music networks and music digraphs for the data analysis. Communities obtained from these networks contributed to the definition of an unsupervised approach that provided performance rates superior to the hierarchical clustering. The rhythmic patterns also motivated the development of strategies for automatic composition, for the generation of playlists, and the analysis of the relationship between these patterns and emotional aspects. Finally, a statistical analysis of the rhythm evolution is performed, in which the principal finding is the presence of innovation and retrieval mechanisms for all genres. These mechanisms seems to be the result of the competition between factors that promote the innovation, and factors that prevent it, as, for example, the obedience to composition rules that retains the fundamental characteristics of each genre.

Diferentes sistemas do mundo real podem ser representados por redes. As redes são estruturas nas quais seus vértices (nós) representam entidades e links representam relações entre essas entidades. Além disso, as redes caracterizam-se por ser estruturas dinâmicas, o que implica na rápida aparição e desaparição de entidades e seus relacionamentos. Nesse cenário, um dos problemas importantes a serem enfrentados no contexto das redes, é da predição de links, isto é, prever a ocorrência futura de um link ainda não existente entre dois vértices com base nas informações já existentes. A importância da predição de links deve-se ao fato de ter aplicações na recuperação de informação, identificação de interações espúrias e, ainda, na avaliação de mecanismos de evolução das redes. Para enfrentar o problema da predição de links, a maioria dos métodos utiliza informações da vizinhança topológica das redes para atribuir um valor que represente a probabilidade de conexão futura entre um par de vértices analisados. No entanto, recentemente têm aparecido métodos híbridos, caracterizados por usar outras informações além da vizinhança topológica, sendo as informações das comunidades as normalmente usadas, isso, devido ao fato que, ao serem grupos de vértices densamente ligados entre si e esparsamente ligados com vértices de outros grupos, fornecem informações que podem ser úteis para determinar o comportamento futuro das redes. Assim, neste trabalho são apresentadas duas propostas na linha dos métodos baseados nas informações das comunidades para predição de links. A primeira proposta consiste em um novo índice de similaridade que usa as informações dos vértices pertencentes a mesma comunidade na vizinhança de um par de vértices analisados, bem como as informações dos vértices pertencentes a diferentes comunidades nessa mesma vizinhança. A segunda proposta consiste de um conjunto de índices obtidos a partir da reformulação de algumas propostas já existentes, porém, inserindo neles informações dos vértices pertencentes unicamente à mesma comunidade na vizinhança topológica de um par de vértices analisados. Experimentos realizados em dez redes complexas de diferentes domínios demonstraram que, em geral, os índices propostos obtiveram desempenho superior às abordagens usuais / Different real-world systems can be represented as networks. Networks are structures in which vertices (nodes) represent entities and links represent relationships between these entities. Moreover, networks are dynamic structures, which implies rapid appearance and disappearance of entities and their relationships. In this scenario, the link prediction problem attempts to predict the future existence of a link between a pair of vertices considering existing information. The link prediction importance is due to the fact of having different applications in areas such as information retrieval, identification of spurious interactions, as well as for understanding mechanisms of network evolution. To address the link prediction problem, many proposals use topological information to assign a value that represents the likelihood of a future connection between a pair of vertices. However, hybrid methods have appeared recently. These methods use additional information such as community information. Communities are groups of vertices densely connected among them and sparsely connected to vertices from other groups, providing useful information to determinate the future behavior of networks. So, this research presents two proposals for link prediction based on communities information. The first proposal consists of a new similarity index that uses information about the communities that the vertices in the neighborhood of a analyzed pair of vertices belong. The second proposal is a set of indices obtained from the reformulation of various existing proposals, however, using only the information from vertices belonging to the same community in the neighborhood of a pair of vertices analyzed. Experiments conducted in ten complex networks of different fields show the proposals outperform traditional approaches

Segmentação de imagens é ainda uma etapa desafiadora do processo de reconhecimento de padrões. Entre as abordagens de segmentação, muitas são baseadas em particionamento em grafos, as quais apresentam alguns inconvenientes, sendo um deles o tempo de processamento muito elevado. Com as recentes pesquisas na teoria de redes complexas, as técnicas de reconhecimento de padrões baseadas em grafos melhoraram consideravelmente. A identificação de grupos de vértices pode ser considerada um processo de detecção de comunidades de acordo com a teoria de redes complexas. Como o agrupamento de dados está relacionado com a segmentação de imagens, esta também pode ser abordada através de redes complexas. No entanto, a segmentação de imagens baseado em redes complexas apresenta uma limitação fundamental, que é o número excessivo de nós na rede. Neste trabalho é proposta uma abordagem de redes complexas para segmentação de imagens de grandes dimensões que é ao mesmo tempo precisa e rápida. Para alcançar este objetivo, é incorporado o conceito de Super Pixels, visando reduzir o número de nós da rede. Os experimentos mostraram que a abordagem proposta produz segmentações de boa qualidade em baixo tempo de processamento. Além disso uma das principais contribuições deste trabalho é a determinação dos melhores parâmetros, uma vez que torna o método bastante independente dos parâmetros, o que não fora alcançado antes em nenhuma pesquisa da área / Image segmentation is still a challenging stage of the pattern recognition process. Amongst the various segmentation approaches, some are based on graph partitioning, many of which show some drawbacks, such as the high processing times. Recent trends on complex network theory have contributed considerably to the development of graph-based pattern recognition techniques. The identification of group of vertices can be considered a community detection process according to complex network theory. Since data clustering is closely related to image segmentation, image segmentation tasks can also be tackled by complex networks. However, complex network-based image segmentation poses a very important limitation: the excessive number of nodes of the underlying network. In this work we propose a approach based on complex networks suitable for the segmentation of image with large dimensions that is accurate and yet fast. To accomplish that, we have incorporated the concept of Super Pixels aiming at reducing the number of the nodes in the network. The results have shown that the proposed approach delivered accurate image segmentation within low computational times. Another contribution worth mentioning is the determination of the best values for the parameters needed by the underlying graphbased segmentation and community detection algorithms, which enabled the proposed approach to become less dependent on the parameters. To the best of our knowledge, this is a new contribution to the field

Au cours de la dernière décennie, les réseaux (les graphes) se sont révélés être un outil efficace pour modéliser des systèmes complexes. La problématique de détection de communautés est une tâche centrale dans l’analyse des réseaux complexes. La majeur partie des travaux dans ce domaine s’intéresse à la structure topologique des réseaux. Cependant, dans plusieurs cas réels, les réseaux complexes ont un ensemble d’attributs associés aux nœuds et/ou aux liens. Ces réseaux sont dites : réseaux attribués. Mes activités de recherche sont basées principalement sur la détection des communautés dans les réseaux attribués. Pour aborder ce problème, on s’est intéressé dans un premier temps aux attributs relatifs aux liens, qui sont un cas particulier des réseaux multiplexes. Un multiplex est un modèle de graphe multi-relationnel. Il est souvent représenté par un graphe multi-couches. Chaque couche contient le même ensemble de nœuds mais encode une relation différente. Dans mes travaux de recherche, nous proposons une étude comparative des différentes approches de détection de communautés dans les réseaux multiplexes. Cette étude est faite sur des réseaux réels. Nous proposons une nouvelle approche centrée "graine" pour la détection de communautés dans les graphes multiplexes qui a nécessité la redéfinition des métriques de bases des réseaux complexes au cas multiplex. Puis, nous proposons une approche de clustering dans les réseaux attribués qui prend en considération à la fois les attributs sur les nœuds et sur les liens. La validation de mes approches a été faite avec des indices internes et externes, mais aussi par une validation guidée par un système de recommandation que nous avons proposé et dont la détection de communautés est sa tâche principale. Les résultats obtenus sur ces approches permettent d’améliorer la qualité des communautés détectées en prenant en compte les informations sur les attributs du réseaux. De plus, nous offrons des outils d’analyse des réseaux attribués sous le langage de programmation R. / In complex networks analysis field, much effort has been focused on identifying graphs communities of related nodes with dense internal connections and few external connections. In addition to node connectivity information that are mostly composed by different types of links, most real-world networks contains also node and/or edge associated attributes which can be very relevant during the learning process to find out the groups of nodes i.e. communities. In this case, two types of information are available : graph data to represent the relationship between objects and attributes information to characterize the objects i.e nodes. Classic community detection and data clustering techniques handle either one of the two types but not both. Consequently, the resultant clustering may not only miss important information but also lead to inaccurate findings. Therefore, various methods have been developed to uncover communities in networks by combining structural and attribute information such that nodes in a community are not only densely connected, but also share similar attribute values. Such graph-shape data is often referred to as attributed graph.This thesis focuses on developing algorithms and models for attributed graphs. Specifically, I focus in the first part on the different types of edges which represent different types of relations between vertices. I proposed a new clustering algorithms and I also present a redefinition of principal metrics that deals with this type of networks.Then, I tackle the problem of clustering using the node attribute information by describing a new original community detection algorithm that uncover communities in node attributed networks which use structural and attribute information simultaneously. At last, I proposed a collaborative filtering model in which I applied the proposed clustering algorithms.

The past decades have seen a fast-growing and dynamic trend of network science and its applications. From the Internet to Facebook, from telecommunications to power grids, from protein interactions to paper citations, networks are everywhere and the network paradigm is pervasive. Network analysis and mining has become an important tool for scientific research and industrial applications to diverse domains. For example, finding communities within social networks enables us to identify groups of densely connected customers who may share similar interests and behaviors and thus generate more effective recommender systems; investigating the supply-network topological structure and growth model improves the resilience of supply networks against disruptions; and modeling influence diffusion in social networks provides insights into viral marketing strategies. However, none of these tasks is trivial. In fact, community detection, resilience analysis, and influence-diffusion modeling are all important challenges in complex networks. My PhD research contributes to these endeavors by exploring the implicit knowledge of connectivity and proximity encoded in the network graph topology. Our research originated from an attempt to find communities in networks. After carefully examining real-life communities and the features and limitations of a set of widely-used centrality measures, we develop a simple but powerful reachability-based influence-diffusion model. Based upon this model, we propose a new influence centrality and a novel shared-influence-neighbor (SIN) similarity. The former differentiates the comprehensive influence significance more precisely, and the latter gives rise to a refined vertex-pair closeness metric. Then we develop an influence-guided spherical K-means (IGSK) algorithm for community detection. Further, we propose two novel influence-guided label propagation (IGLP) algorithms for finding hierarchical communities in complex networks. Experiments on both real-life networks and synthetic benchmarks demonstrate superior performance of our algorithms in both undirected/directed and unweighted/weighted networks. Another research topic we investigated is resilience analysis of supply networks. Supply networks play an important role in product distribution, and survivability is a critical concern in supply-network design and analysis. We exploit the resilience embedded in supply-network topology by exploring the multiple-path reachability of each demand node to other nodes, and propose a novel resilience metric. We also develop new supply-network growth mechanisms that reflect the heterogeneous roles of different types of units in supply networks. We incorporate them into two fundamental network topologies (random-graph topology and scale-free topology), and evaluate the resilience under random disruptions and targeted attacks using the new resilience metric. The experimental results verify the validity of our resilience metric and the effectiveness of our growth model. This research provides a generic framework and important insights into the construction of robust supply networks. Finally, we investigate activation-based influence-diffusion modeling for viral marketing. One of the fundamental problems in viral marketing is to find a small set of initial adopters who can trigger the largest further adoptions through word-of-mouth-based influence propagation in the network. We propose a novel multiple-path asynchronous threshold (MAT) model, in which we quantitatively measure influence and keep track of its diffusion and aggregation during the diffusion process. Our MAT model captures both direct and indirect influence, influence attenuation along diffusion paths, temporal influence decay, and individual diffusion dynamics. Our work is an important step toward a more realistic diffusion model. Further, we develop two effective and efficient heuristics (IV-Greedy and IV-Community) to tackle the influence-maximization problem. Our experiments on four real-life networks demonstrate their excellent performance in terms of both influence spread and efficiency. Our work provides preliminary but significant insights and implications for diffusion research and marketing practice.

Road traffic congestion causes several problems. For instance, slow moving traffic in congested regions poses a safety hazard to vehicles approaching the congested region and increased commuting times lead to higher transportation costs and increased pollution.The work carried out in this thesis aims to detect and track road traffic congestion in real time. Real-time road congestion detection is important to allow for mechanisms to e.g. improve traffic safety by sending advanced warnings to drivers approaching a congested region and to mitigate congestion by controlling adaptive speed limits. In addition, the tracking of the evolution of congestion in time and space can be a valuable input to the development of the road network. Traffic sensors in Stockholm’s road network are represented as a directed weighted graph and the congestion detection problem is formulated as a streaming graph processing problem. The connected components algorithm and existing graph processing algorithms originally used for community detection in social network graphs are adapted for the task of road congestion detection. The results indicate that a congestion detection method based on the streaming connected components algorithm and the incremental Dengraph community detection algorithm can detect congestion with accuracy at best up to 94% for connected components and up to 88% for Dengraph. A method based on hierarchical clustering is able to detect congestion while missing details such as shockwaves, and the Louvain modularity algorithm for community detection fails to detect congested regions in the traffic sensor graph.Finally, the performance of the implemented streaming algorithms is evaluated with respect to the real-time requirements of the system, their throughput and memory footprint. / Vägtrafikstockningar orsakar flera problem. Till exempel utgör långsam trafik i överbelastade områden en säkerhetsrisk för fordon som närmar sig den överbelastade regionen och ökade pendeltider leder till ökade transportkostnader och ökad förorening.Arbetet i denna avhandling syftar till att upptäcka och spåra trafikstockningar i realtid. Detektering av vägtrafiken i realtid är viktigt för att möjliggöra mekanismer för att t.ex. förbättra trafiksäkerheten genom att skicka avancerade varningar till förare som närmar sig en överbelastad region och för att mildra trängsel genom att kontrollera adaptiva hastighetsgränser. Dessutom kan spårningen av trängselutveckling i tid och rum vara en värdefull inverkan på utvecklingen av vägnätet. Trafikavkännare i Stockholms vägnät representeras som en riktad vägd graf och problemet med överbelastningsdetektering är formulerat som ett problem med behandling av flödesgrafer. Den anslutna komponentalgoritmen och befintliga grafbehandlingsalgoritmer som ursprungligen användes för communitydetektering i sociala nätgravar är anpassade för uppgiften att detektera vägtäthet. Resultaten indikerar att en överbelastningsdetekteringsmetod baserad på den strömmande anslutna komponentalgoritmen och den inkrementella Dengraph communitydetekteringsalgoritmen kan upptäcka överbelastning med noggrannhet i bästa fall upp till 94% för anslutna komponenter och upp till 88% för Dengraph. En metod baserad på hierarkisk klustring kan detektera överbelastning men saknar detaljer som shockwaves, och Louvain modularitetsalgoritmen för communitydetektering misslyckas med att detektera överbelastade områden i trafiksensorns graf.Slutligen utvärderas prestandan hos de implementerade strömmalgoritmerna med hänsyn till systemets realtidskrav, deras genomströmning och minnesfotavtryck.

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 the Web has become more and more important to our daily lives, algorithms that can effectively utilize the link structure have become more and more important. One such task has been to find communities in social network data. Recently, however, there has been increased interest in augmenting links with additional semantic information. We examine link classification from the point of view of scientometrics, with an eye towards applying what has been learned about scientific citation to Web linking. Some community detection algorithms are reviewed, and one that has been developed for topical community finding on the Web is adapted to typed scientific citations.

As the Web has become more and more important to our daily lives, algorithms that can effectively utilize the link structure have become more and more important. One such task has been to find communities in social network data. Recently, however, there has been increased interest in augmenting links with additional semantic information. We examine link classification from the point of view of scientometrics, with an eye towards applying what has been learned about scientific citation to Web linking. Some community detection algorithms are reviewed, and one that has been developed for topical community finding on the Web is adapted to typed scientific citations.

Several applied sciences model system dynamics with networks. Since networks often contain thousands or millions of nodes and links, researchers have developed methods that reveal and high- light their essential structures. One such method developed by researchers in IceLab uses information theory to compress descrip- tions of network flows with memory based on paths rather than links and identify hierarchically nested modules with long flow persistence times. However, current visualization tools for navigat- ing and exploring nested modules build on obsolete software that requires plugins and cannot handle such memory networks. Drawing from ideas in cartography, this thesis presents a pow- erful visualization method that enables researchers to analyze and explore modular decompositions of any network. The resulting application uses an efficient graph layout algorithm adapted with a simulation based on information flow. Like in a topographic map, zooming into the map successively reveals more detailed commu- nity structures and network features in a continuous fashion.