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.

Online social networks have become a powerful venue for political activism. In many cases large, insular online communities form that have been shown to be powerful diffusion mechanisms of both misinformation and propaganda. In some cases these groups users advocate actions or policies that could be construed as extreme along nearly any distribution of opinion, and are thus called Online Extremist Communities (OECs). Although these communities appear increasingly common, little is known about how these groups form or the methods used to influence them. The work in this thesis provides researchers a methodological framework to study these groups by answering three critical research questions: How can we detect large dynamic online activist or extremist communities? What automated tools are used to build, isolate, and influence these communities? What methods can be used to gain novel insight into large online activist or extremist communities? These group members social ties can be inferred based on the various affordances offered by OSNs for group curation. By developing heterogeneous, annotated graph representations of user behavior I can efficiently extract online activist discussion cores using an ensemble of unsupervised machine learning methods. I call this technique Ensemble Agreement Clustering. Through manual inspection, these discussion cores can then often be used as training data to detect the larger community. I present a novel supervised learning algorithm called Multiplex Vertex Classification for network bipartition on heterogeneous, annotated graphs. This methodological pipeline has also proven useful for social botnet detection, and a study of large, complex social botnets used for propaganda dissemination is provided as well. Throughout this thesis I provide Twitter case studies including communities focused on the Islamic State of Iraq and al-Sham (ISIS), the ongoing Syrian Revolution, the Euromaidan Movement in Ukraine, as well as the alt-Right.

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

<div> <div> <div> <p>The use of graph-structured data in applications is increasing day by day. In order to infer useful information from such data, fast analytics and software tools are required. One of the graph analytics techniques used is community detection. Community detection is the technique of finding structural communities within a graph. Such communities are defined as groups which have highly connected nodes and have similarities with each other. </p> <p>This research proposes a parallel heuristic for faster community detection using the parallel version of the Louvain algorithm: Grappolo. The Louvain algorithm is a hierarchical algorithm that focuses on modularity optimization. It gained popularity because of its ability to detect high-quality communities faster than the other existing community detection algorithms. However, the Louvain algorithm is a sequential algorithm. To reduce the execution time of the Louvain algorithm, a parallel version named Grappolo exists in the literature. This algorithm proposes parallel heuristics that address the challenges that occur due to parallelizing the sequential Louvain algorithm. </p> <p>In this study, the researcher is investigating if Grappolo can be further parallelized to further reduce the execution time maintaining the quality of communities detected. To evaluate the proposed heuristic, it was tested on an OpenMP multithreaded environment. It was implemented on source codes of Android malware applications. However, as compared to Grapplolo, the proposed modified version resulted in higher execution times for the inputs tested. The modularity of the communities detected was similar to the Grappolo implementation. </p> </div> </div> </div>

No description available.