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.

abstract: This dissertation studies routing in small-world networks such as grids plus long-range edges and real networks. Kleinberg showed that geography-based greedy routing in a grid-based network takes an expected number of steps polylogarithmic in the network size, thus justifying empirical efficiency observed beginning with Milgram. A counterpart for the grid-based model is provided; it creates all edges deterministically and shows an asymptotically matching upper bound on the route length. The main goal is to improve greedy routing through a decentralized machine learning process. Two considered methods are based on weighted majority and an algorithm of de Farias and Megiddo, both learning from feedback using ensembles of experts. Tests are run on both artificial and real networks, with decentralized spectral graph embedding supplying geometric information for real networks where it is not intrinsically available. An important measure analyzed in this work is overpayment, the difference between the cost of the method and that of the shortest path. Adaptive routing overtakes greedy after about a hundred or fewer searches per node, consistently across different network sizes and types. Learning stabilizes, typically at overpayment of a third to a half of that by greedy. The problem is made more difficult by eliminating the knowledge of neighbors' locations or by introducing uncooperative nodes. Even under these conditions, the learned routes are usually better than the greedy routes. The second part of the dissertation is related to the community structure of unannotated networks. A modularity-based algorithm of Newman is extended to work with overlapping communities (including considerably overlapping communities), where each node locally makes decisions to which potential communities it belongs. To measure quality of a cover of overlapping communities, a notion of a node contribution to modularity is introduced, and subsequently the notion of modularity is extended from partitions to covers. The final part considers a problem of network anonymization, mostly by the means of edge deletion. The point of interest is utility preservation. It is shown that a concentration on the preservation of routing abilities might damage the preservation of community structure, and vice versa. / Dissertation/Thesis / Ph.D. Computer Science 2011

Networks have been widely used to describe interactions among objects in diverse fields. Given the interest in explaining a network by its structure, much attention has been drawn to finding clusters of nodes with dense connections within clusters but sparse connections between clusters. Such clusters are called communities, and identifying such clusters is known as community detection. Here, to perform community detection, I focus on stochastic blockmodels (SBM), a class of statistically-based generative models. I present a flexible SBM that represents different types of data as well as node attributes under a Bayesian framework. The proposed models explicitly capture community behavior by guaranteeing that connections are denser within communities than between communities. First, I present a degree-corrected SBM based on a logistic regression formulation to model binary networks. To fit the model, I obtain posterior samples via Gibbs sampling based on Polya-Gamma latent variables. I conduct inference based on a novel, canonically mapped centroid estimator that formally addresses label non-identifiability and captures representative community assignments. Next, to accommodate large-scale datasets, I further extend the degree-corrected SBM to a broader family of generalized linear models with group correction terms. To conduct exact inference efficiently, I develop an iteratively-reweighted least squares procedure that implicitly updates sufficient statistics on the network to obtain maximum a posteriori (MAP) estimators. I demonstrate the proposed model and estimation on simulated benchmark networks and various real-world datasets. Finally, I develop a Bayesian SBM for community-structured covariance selection. Here, I assume that the data at each node are Gaussian and a latent network where two nodes are not connected if their observations are conditionally independent given observations of other nodes. Under the context of biological and social applications, I expect that this latent network shows a block dependency structure that represents community behavior. Thus, to identify the latent network and detect communities, I propose a hierarchical prior in two levels: a spike-and-slab prior on off-diagonal entries of the concentration matrix for variable selection and a degree-corrected SBM to capture community behavior. I develop an efficient routine based on ridge regularization and MAP estimation to conduct inference.

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.

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

Les communautés sont des groupes de nœuds (sommets) qui partagent probablement des propriétés communes et/ou jouent des rôles similaires dans le graphe. Ils peuvent extraire des structures spécifiques des réseaux complexes, et par conséquent la détection de ces communautés a été étudiée dans de nombreux domaines où les systèmes sont souvent représentés sous forme de graphes. La détection de communautés est en fait un problème de classification (ou clustering) sur les graphes, et l'information disponible dans ce problème est souvent sous la forme de similitudes ou de différences (entre les nœuds). Nous commençons par une situation de base où les nœuds dans le graphe sont regroupés selon leurs similarités et proposons une nouvelle approche de clustering enc-partition nommée algorithme Median Evidential C-Means (MECM). Cette approche étend la méthode de classification par médiane dans le cadre de la théorie des fonctions de croyance. En outre, une détection de communautés fondée sur l'approche MECM est également présentée. L'approche proposée permet de fournir des partitions crédales selon des similarités avec seulement des données connues. La mesure de dissimilarité pourrait être ni symétrique et même ne comporter aucune exigences de métriques.Elle est simplement intuitive. Ainsi, elle élargit la portée d'applications des partitions crédales. Afin de saisir les divers aspects des structures de communautés, nous pouvons avoir besoin de plusieurs nœuds plutôt qu'un seul pour représenter un prototype représentant un groupe d'individus. Motivée par cette idée, une approche de détection de communautés fondée sur le Similarity-based Multiple Prototype (SMP) est proposée.Les valeurs de centralité sont utilisées comme critère pour sélectionner plusieurs nœuds(prototypes) pour caractériser chaque communauté, et les poids des prototypes sont considérés pour décrire le degré de représentativité des objets liés à leur propre communauté. Ensuite, la similarité entre chaque nœud et les communautés est définie. Les nœuds sont divisés pour former des communautés selon leurs similarités. Les partitions nettes et floues peuvent être obtenues par l'approche SMP. Ensuite, nous étendons l'approche SMP au cadre des fonctions de croyance pour obtenir des partitions crédales de sorte que l'on puisse obtenir une meilleure compréhension de la structure des données. Les poids du prototype sont incorporés dans la fonction d’objectif de la communauté. La composition de masse et les poids des prototypes ont pu être mis à jour alternativement pendant le processus d'optimisation. Dans ce cas,chaque groupe peut être décrit en utilisant de multiples prototypes pondérés. Comme nous allons le montrer, les poids des prototypes peuvent également nous fournir des informations utiles pour l'analyse des données. la règle de mise à jour et le critère de propagation du LPA sont étendus aux fonctions de croyance. Une nouvelle approche de détection de communautés, appelée Semisupervised Evidential Label Propagation (SELP) est proposée comme une version améliorée de la méthode LPA conventionnelle. L'un des avantages de l'approche SELP est quelle permet de tenir compte de la connaissance préalable disponible sur les étiquettes des communautés de certains individus. Ceci est tr` es courant dans la pratique réelle. Dans la méthode SELP, les nœuds sont divisés en deux partis. Certains contiennent des nœuds labellisés et les autres des nœuds non labellisés. Les labels sont propagés depuis les nœuds labellisés à ceux non labellisés, étape par étape en utilisant la règle crédibiliste de propagation de labels proposée. Les performances des approches proposées sont évaluées en utilisant les graphes de référence des ensembles de données et des graphes générés. Nos résultats expérimentaux illustrent l'efficacité des algorithmes de classification proposés et des méthodes de détection de communautés. / Communities are groups of nodes (vertices) which probably share common properties and/or play similar roles within the graph. They can extract specific structures from complex networks, and consequently community detection has attracted considerable attention crossing many areas where systems are often represented as graphs. We consider in this work to represent graphs as relational data, and propose models for the corresponding relational data clustering. Four approaches are brought forward to handle the community detection problem under different scenarios. We start with a basic situation where nodes in the graph are clustered based on the dissimilarities and propose a new c-partition clustering approach named Median Evidential C-Means (MECM) algorithm. This approach extends the median clustering methods in the framework of belief function theory. Moreover, a community detection scheme based on MECM is presented. The proposed approach could provide credal partitions for data sets with only known dissimilarities. The dissimilarity measure could be neither symmetric nor fulfilling any metric requirements. It is only required to be of intuitive meaning. Thus it expands application scope of credal partitions. In order to capture various aspects of the community structures, we may need more members rather than one to be referred as the prototypes of an individual group. Motivated by this idea, a Similarity-based Multiple Prototype (SMP) community detection approach is proposed. The centrality values are used as the criterion to select multiple prototypes to characterize each community. The prototype weights are derived to describe the degree of representativeness of objects for their own communities. Then the similarity between each node and community is defined, and the nodes are partitioned into divided communities according to these similarities. Crisp and fuzzy partitions could be obtained by the application of SMP. Following, we extend SMP in the framework of belief functions to get credal partitions so that we can gain a better understanding of the data structure. The prototype weights are incorporate into the objective function of evidential clustering. The mass membership and the prototype weights could be updated alternatively during the optimization process. In this case, each cluster could be described using multiple weighted prototypes. As we will show, the prototype weights could also provide us some useful information for structure analysis of the data sets. Lastly, the original update rule and propagation criterion of LPA are extended in the framework of belief functions. A new community detection approach, called Semi-supervised Evidential Label Propagation (SELP), is proposed as an enhanced version of the conventional LPA. One of the advantages of SELP is that it could take use of the available prior knowledge about the community labels of some individuals. This is very common in real practice. In SELP, the nodes are divided into two parts. One contains the labeled nodes, and the other includes the unlabeled ones. The community labels are propagated from the labeled nodes to the unlabeled ones step by step according to the proposed evidential label propagation rule. The performance of the proposed approaches is evaluated using benchmark graph data sets and generated graphs. Our experimental results illustrate the effectiveness of the proposed clustering algorithms and community detection approaches.

Dans le contexte des réseaux complexes, cette thèse s’inscrit dans deux axes : (1) Méthodologiede la détection de communautés et (2) Evaluation de la qualité des algorithmes de détection de communautés. Dans le premier axe, nous nous intéressons en particulier aux approches fondées sur les Leaders (sommets autour desquels s’agrègent les communautés). Premièrement, nous proposons un enrichissement de la méthodologie LICOD qui permet d’évaluer les différentes stratégies des algorithmes fondés sur les leaders, en intégrant différentes mesures dans toutes les étapes de l’algorithme. Deuxièmement, nous proposons une extension de LICOD, appelée it-LICOD. Cette extension introduit une étape d’auto-validation de l’ensemble des leaders. Les résultats expérimentaux de it-LICOD sur les réseaux réels et artificiels sont bons par rapport à LICOD et compétitifs par rapport aux autres méthodes. Troisièmement, nous proposons une mesure de centralité semi-locale, appelée TopoCent, pour remédier au problème de la non-pertinence des mesures locales et de la complexité de calcul élevée des mesures globales. Nous montrons expérimentalement que LICOD est souvent plus performant avec TopoCent qu’avec les autres mesures de centralité. Dans le deuxième axe, nous proposons deux méthodes orientées-tâche, CLE et PLE, afin d’évaluer les algorithmes de détection de communautés. Nous supposons que la qualité de la solution des algorithmes peut être estimée en les confrontant à d’autres tâches que la détection de communautés en elle-même. Dans la méthode CLE nous utilisons comme tâche la classification non-supervisée et les algorithmes sont évalués sur des graphes générés à partir des jeux de données numériques. On bénéficie dans ce cas de la disponibilité de la vérité de terrain (les regroupements) de plusieurs jeux de données numériques. En ce qui concerne la méthode PLE, la qualité des algorithmes est mesurée par rapport à leurs contributions dans une tâche de prévision de liens. L’expérimentation des méthodes CLE et PLE donne de nouveaux éclairages sur les performances des algorithmes de détection de communautés / In this thesis we focus, on one hand, on community detection in complex networks, and on the other hand, on the evaluation of community detection algorithms. In the first axis, we are particularly interested in Leaders driven community detection algorithms. First, we propose an enrichment of LICOD : a framework for building different leaders-driven algorithms. We instantiate different implementations of the provided hotspots. Second, we propose an extension of LICOD, we call it-LICOD. This extension introduces a self-validation step of all identified leaders. Experimental results of it-LICOD on real and artificial networks show that it outperform the initial LICOD approach. Obtained results are also competitive with those of other state-of-the art methods. Thirdly, we propose a semi-local centrality measure, called TopoCent, that address the problem of the irrelevance of local measures and high computational complexity of globalmeasures. We experimentally show that LICOD is often more efficient with TopoCent than with the other classical centrality measures. In the second axis, we propose two task-based community evaluation methods : CLE and PLE. We examine he hypothesis that the quality of community detection algorithms can be estimated by comparing obtained results in the context of other relevent tasks. The CLE approach, we use a data clustering task as a reference. The PLE method apply a link prediction task. We show that the experimentation of CLE and PLE methods gives new insights into the performance of community detection algorithms.