No description available.

Ce travail de thèse concerne la fouille de données sur des graphes attribués. Il s'agit de graphes dans lesquels des propriétés, encodées sous forme d'attributs, sont associées à chaque sommet. Notre objectif est la découverte, dans ce type de données, de sous-graphes organisés en plusieurs groupes de sommets fortement connectés et homogènes au regard des attributs. Plus précisément, nous définissons l'extraction sous contraintes d'ensembles de sous-graphes densément connectés et tels que les sommets partagent suffisamment d'attributs. Pour cela nous proposons deux familles de motifs originales ainsi que les algorithmes justes et complets permettant leur extraction efficace sous contraintes. La première famille, nommée Ensembles Maximaux de Cliques Homogènes, correspond à des motifs satisfaisant des contraintes concernant le nombre de sous-graphes denses, la taille de ces sous-graphes et le nombre d'attributs partagés. La seconde famille, nommée Collections Homogènes de k-cliques Percolées emploie quant à elle une notion de densité plus relaxée permettant d'adapter la méthode aux données avec des valeurs manquantes. Ces deux méthodes sont appliquées à l'analyse de deux types de réseaux, les réseaux de coopérations entre chercheurs et les réseaux d'interactions de protéines. Les motifs obtenus mettent en évidence des structures utiles dans un processus de prise de décision. Ainsi, dans un réseau de coopérations entre chercheurs, l'analyse de ces structures peut aider à la mise en place de collaborations scientifiques entre des groupes travaillant sur un même domaine. Dans le contexte d'un graphe de protéines, les structures exhibées permettent d'étudier les relations entre des modules de protéines intervenant dans des situations biologiques similaires. L'étude des performances en fonction de différentes caractéristiques de graphes attribués réels et synthétiques montre que les approches proposées sont utilisables sur de grands jeux de données. / The work presented in this thesis deals with data mining approaches for the analysis of attributed graphs. An attributed graph is a graph where properties, encoded by means of attributes, are associated to each vertex. In such data, our objective is the discovery of subgraphs formed by several dense groups of vertices that are homogeneous with respect to the attributes. More precisely, we define the constraint-based extraction of collections of subgraphs densely connected and such that the vertices share enough attributes. To this aim, we propose two new classes of patterns along with sound and complete algorithms to compute them efficiently using constraint-based approaches. The first family of patterns, named Maximal Homogeneous Clique Set (MHCS), contains patterns satisfying constraints on the number of dense subgraphs, on the size of these subgraphs, and on the number of shared attributes. The second class of patterns, named Collection of Homogeneous k-clique Percolated components (CoHoP), is based on a relaxed notion of density in order to handle missing values. Both approaches are used for the analysis of scientific collaboration networks and protein-protein interaction networks. The extracted patterns exhibit structures useful in a decision support process. Indeed, in a scientific collaboration network, the analysis of such structures might give hints to propose new collaborations between researchers working on the same subjects. In a protein-protein interaction network, the analysis of the extracted patterns can be used to study the relationships between modules of proteins involved in similar biological situations. The analysis of the performances, on real and synthetic data, with respect to different attributed graph characteristics, shows that the proposed approaches scale well for large datasets.

L'objectif de cette thèse est de réussir à utiliser des décompositions de graphes afin de résoudre des problèmes algorithmiques sur les graphes. Notre objet d'étude principal est la classe des graphes de Berge apprivoisés. Les graphes de Berge sont les graphes ne possédant ni cycle de longueur impaire supérieur à 4 ni complémentaire de cycle de longueur impaire supérieure à 4. Dans les années 60, Claude Berge a conjecturé que les graphes de Berge étaient des graphes parfaits. C'est-à-dire que la taille de la plus grande clique est exactement le nombre minimum de couleurs nécessaire à une coloration propre et ce pour tout sous-graphe. En 2002, Chudnovsky, Robertson, Seymour et Thomas ont démontré cette conjecture en utilisant un théorème de structure: les graphes de Berge sont basiques ou admettent une décomposition. Ce résultat est très utile pour faire des preuves par induction. Cependant, une des décompositions du théorème, la skew-partition équilibrée, est très difficile à utiliser algorithmiquement. Nous nous focalisons donc sur les graphes de Berge apprivoisés, c'est-à-dire les graphes de Berge sans skew-partition équilibrée. Pour pouvoir faire des inductions, nous devons adapter le théorème destructure de Chudnovsky et al à notre classe. Nous prouvons un résultat plus fort: les graphes de Berge apprivoisés sont basiques ou admettent une décomposition telle qu'un côté de la décomposition soit toujours basique. Nous avons de plus un algorithme calculant cette décomposition. Nous utilisons ensuite notre théorème pour montrer que les graphes de Berge apprivoisés admettent la propriété du grand biparti, de la clique-stable séparation et qu'il existe un algorithme polynomial permettant de calculer le stable maximum. / The goal of this these is to use graph's decompositions to solve algorithmic problems on graphs. We will study the class of Berge tame graphs. A Berge graph is a graph without cycle of odd length at least 4 nor complement of cycle of odd length at least 4.In the 60's, Claude Berge conjectured that Berge graphs are perfect graphs. The size of the biggest clique is exactly the number of colors required to color the graph. In 2002, Chudnovsky, Robertson, Seymour et Thomas proved this conjecture using a theorem of decomposition: Berge graphs are either basic or have a decomposition. This is a useful result to do proof by induction. Unfortunately, one of the decomposition, the skew-partition, is really hard to use. We arefocusing here on Berge tame graphs, i.e~Berge graph without balanced skew-partition. To be able to do induction, we must first adapt the Chudnovsky et al's theorem of structure to our class. We prove a stronger result: Berge tame graphs are basic or have a decomposition such that one side is always basic. We also have an algorithm to compute this decomposition. We then use our theorem to prouve that Berge tame graphs have the big-bipartite property, the clique-stable set separation property and there exists a polytime algorithm to compute the maximum stable set.

Cette thèse porte sur des aspects structuraux et algorithmiques des graphes. Elle est divisée en deux parties, qui comportent deux études différentes : une partie sur des algorithmes centralisés-séquentiels, et une autre sur des algorithmes distribués. Dans la première partie, on étudie des aspects algorithmiques de deux structures de graphes appelés séparateurs minimaux et cliques maximales potentielles. Ces deux objets sont au coeur d'un méta-théorème dû à Fomin, Todinca and Villanger (SIAM J. Comput. 2015), qui affirme qu'une grande famille des problèmes d'optimisation peut être résolue en temps polynomial, si le graphe d'entrée contient un nombre polynomial de séparateurs minimaux. La contribution de cette partie consiste à prolonger le méta-théorème de Fomin et al. de deux manières : d'un côté, on l'adapte pour qu'il soit valide pour une plus grande famille des problèmes ; de l'autre, on étend ces résultats à des version paramétrées, pour certains paramètres des graphes. La deuxième partie de la thèse correspond à une étude du modèle appelé « Diffusion dans une Clique Congestionnée ». Dans ce modèle, les sommets d'un graphe communiquent entre eux dans des rondes synchrones, en diffusant un message de petite taille, visible par tout autre sommet. L'objectif ici est d'élaborer des protocoles qui reconnaissent des classes de graphes, en minimisant la taille des messages et le nombre de rondes. La contribution de cette partie est l'étude du rôle du hasard dans ce modèle, et la conception de protocoles pour la reconnaissance et la reconstruction des certaines classes des graphes. / This thesis is about structural and algorithmic aspects of graphs. It is divided in two parts, which are about two different studies: one part is about centralized-sequential algorithms, and the other part is about distributed algorithms. In the first part of the thesis we study algorithmic applications of two graph structures called minimal separators and potential maximal cliques. These two objects are in the core of a meta-theorem due to Fomin, Todinca and Villanger (SIAM J. Comput. 2015), which states that a large family of graph optimization problems can be solved in polynomial time, when the input is restricted to the family of graphs with polynomially many minimal separators. The contribution of this part of the thesis is to extend the meta-theorem of Fomin et al. in two ways. On one hand, we adapt it to be valid into a larger family of problems. On the other hand, we extend it into a parameterized version, for several graph parameters. In the second part of this thesis we study the broadcast congested clique model. In this model, the nodes of a graph communicate in synchronous rounds, broadcasting a message of small size visible to every other node. The goal is to design protocols that recognize graph classes minimizing the number of rounds and the message sizes. The contribution of this part is to explore the role of randomness on this model, and provide protocols for the recognition and reconstruction of some graph classes.

Cette thèse présente des algorithmes de résolution de quatre problèmes de clique : clique de poids maximum (MVWCP), s-plex maximum (MsPlex), clique maximum équilibrée dans un graphe biparti (MBBP) et clique partition (CPP). Les trois premiers problèmes sont des généralisations ou relaxations du problème de la clique maximum, tandis que le dernier est un problème de couverture. Ces problèmes, ayant de nombreuses applications pratiques, sont NP-difficiles, rendant leur résolution ardue dans le cas général. Nous présentons ici des algorithmes de recherche locale, principalement basés sur la recherche tabou, permettant de traiter efficacement ces problèmes ; chacun de ces algorithmes emploie des composants originaux et spécifiquement adaptés aux problèmes traités, comme de nouveaux opérateurs ou mécanismes perturbatifs. Nous y intégrons également des stratégies telles que la réduction de graphe ou la propagation afin de traiter des réseaux de plus grande taille. Des expérimentations basées sur des jeux d’instances nombreux et variés permettent de montrer la compétitivité de nos algorithmes en comparaison avec les autres stratégies existantes. / This thesis considers four clique problems: the maximum vertex weight clique problem (MVWCP), the maximum s-plex problem (MsPlex), the maximum balanced biclique problem (MBBP) and the clique partitioning problem (CPP). The first three are generalization and relaxation of the classic maximum clique problem (MCP), while the last problem belongs to a clique grouping problem. These combinatorial problems have numerous practical applications. Given that they all belong to the NP-Hard family, it is computationally difficult to solve them in the general case. For this reason, this thesis is devoted to develop effective algorithms to tackle these challenging problems. Specifically, we propose two restart tabu search algorithms based on a generalized PUSH operator for MVWCP, a frequency driven local search algorithms for MsPlex, a graph reduction based tabu search as well as effective exact branch and bound algorithms for MBBP and lastly, a three phase local search algorithm for CPP. In addition to the design of efficient move operators for local search algorithms, we also integrate components like graph reduction or upper bound propagation in order to deal deal with very large real-life networks. The experimental tests on a wide range of instances show that our algorithms compete favorably with the main state-of-the-art algorithms.

Dans ce travail, nous présentons trois nouveaux algorithmes pour le problème de la clique de poids maximum. Les trois algorithmes dépendent d'un ordre initial des sommets. Deux ordres sont considérés, l'un en fonction de la pondération des sommets et l'autre en fonction de la taille voisinage des sommets. Le premier algorithme, que nous avons appelé BITCLIQUE, est une algorithme de séparation et évaluation. Il réunit efficacement plusieurs idées déjà utilisées avec succès pour résoudre le problème, comme l'utilisation d'une heuristique de coloration pondérée en nombres entiers pour l'évaluation ; et l'utilisation de vecteurs de bits pour simplifier les opérations sur le graphe. L'algorithme proposé surpasse les algorithmes par séparation et évaluation de l'état de l'art sur la plupart des instances considérées en terme de nombre de sous-problèmes énumérés ainsi que en terme de temps d'exécution. La seconde version est un algorithme des poupées russes, BITRDS, qui intègre une stratégie d'évaluation et de ramification de noeuds basée sur la coloration pondérée. Les simulations montrent que BITRDS réduit à la fois le nombre de sous-problèmes traités et le temps d'exécution par rapport à l'algorithme de l'état de l'art basée sur les poupées russes sur les graphes aléatoires avec une densité supérieure à 50%. Cette différence augmente à la mesure que la densité du graphe augmente. D'ailleurs, BITRDS est compétitif avec BITCLIQUE avec une meilleure performance sur les instances de graphes aléatoires avec une densité comprise entre 50% et 80%. Enfin, nous présentons une coopération entre la méthode poupées russes et la méthode de ``Resolution Search''. L'algorithme proposé, appelé BITBR, utilise au même temps la coloration pondérée et les limites supérieures donnés par les poupées pour trouver un ``nogood''. L'algorithme hybride réduit le nombre d'appels aux heuristiques de coloration pondérée, atteignant jusqu'à 1 ordre de grandeur par rapport à BITRDS. Plusieurs simulations sont réalisées avec la algorithmes proposés et les algorithmes de l'état de l'art. Les résultats des simulations sont rapportés pour chaque algorithme en utilisant les principaux instances disponibles dans la littérature. Enfin, les orientations futures de la recherche sont discutées. / In this work, we present three new exact algorithms for the maximum weight clique problem. The three algorithms depend on an initial ordering of the vertices. Two ordering are considered, as a function of the weights of the vertices or the weights of the neighborhoods of the vertices. This leads to two versions of each algorithm. The first one, called BITCLIQUE, is a combinatorial Branch & Bound algorithm. It effectively combines adaptations of several ideas already successfully employed to solve the problem, such as the use of a weighted integer coloring heuristic for pruning and branching, and the use of bitmap for simplifying the operations on the graph. The proposed algorithm outperforms state-of-the-art Branch & Bound algorithms in most instances of the considered in terms of the number of enumerated subproblems as well in terms of computational time The second one is a Russian Dolls, called BITRDS, which incorporates the pruning and branching strategies based on weighted coloring. Computational tests show that BITRDS reduces both the number of enumerated subproblems and execution time when compared to the previous state-of-art Russian Dolls algorithm for the problem in random graph instances with density above 50%. As graph density increases, this difference increases. Besides, BITRDS is competitive with BITCLIQUE with better performance in random graph instances with density between 50% and 80%. Finally, we present a cooperation between the Russian Dolls method and the Resolution Search method. The proposed algorithm, called BITBR, uses both the weighted coloring and upper bounds given by the dolls to find a nogood. The hybrid algorithm reduces the number of coloring heuristic calls, reaching up to 1 order of magnitude when compared with BITRDS. However, this reduction decreases the execution time only in a few instances. Several computational experiments are carried out with the proposed and state-of-the-art algorithms. Computational results are reported for each algorithm using the main instances available in the literature. Finally, future directions of research are discussed.

Submitted by Maria Aparecida (cidazen@gmail.com) on 2017-04-04T14:57:07Z No. of bitstreams: 1 Samario Jose Lima Meireles.pdf: 5051030 bytes, checksum: dda872455dd2092963a9db897ee15455 (MD5) / Made available in DSpace on 2017-04-04T14:57:07Z (GMT). No. of bitstreams: 1 Samario Jose Lima Meireles.pdf: 5051030 bytes, checksum: dda872455dd2092963a9db897ee15455 (MD5) Previous issue date: 2017-03-06 / CAPES / In this research are analyzed the processes of selection of political leaders of the maranhense branch of the Brazilian bar association, with emphasis on the period between 1983 and 2015. The investigation focused on fourteen elective disputes through which the boards of directors of the entity were chosen. In the operationalization of the study, we sought to apprehend chains of leaders-followers who competed within the institution, evidencing the flows of entries, exits, approximations and distancing. In order to do so, the trajectories of the main protagonists (egos of networks) who competed for positions of direction of the OAB/MA were reconstituted, as well as the clicks of leaders who were formed in these clashes and the cleavages constructed by means of constant realignments in the alliances. Therefore, firstly, the resources accumulated by the agents that stood out in these disputes were identified, and secondly, the networks of relations (through the use of the UCINET and NETDRAW programs) constituted and activated for electoral purposes, also seeking to reveal the social bases of interconnections, ties and links more or less ephemeral. / Nesta pesquisa são analisados os processos de seleção dos dirigentes políticos da seccional maranhense da Ordem dos Advogados do Brasil, com ênfase no período compreendido entre 1983 e 2015. A investigação centrou-se em catorze disputas eletivas mediante as quais foram escolhidas as diretorias da entidade. Na operacionalização do estudo, buscou-se apreender cadeias de líderes-seguidores que rivalizaram no âmbito da instituição, evidenciando os fluxos de entradas, saídas, aproximações e distanciamentos. Para tanto, foram reconstituídas as trajetórias dos principais protagonistas (egos de redes) que concorreram a postos de direção da OAB/MA, bem como as cliques de dirigentes que foram formadas nesses embates e as clivagens construídas por meios de realinhamentos constantes nas alianças. Sendo assim, em primeiro lugar, foram identificados os recursos acumulados pelos agentes que se destacaram nessas contendas e, em segundo lugar, as redes de relações (por intermédio do uso dos programas UCINET e NETDRAW) constituídas e ativadas com objetivos eleitorais, buscando também revelar as bases sociais de interconexões, elos e vínculos mais ou menos efêmeros.

Tese de mestrado. Mestrado Integrado em Engenharia Informática e Computação. Faculdade de Engenharia. Universidade do Porto. 2012

In this report, we initiate study on understanding a theoretical model for distributed computing called Congested Clique. This report presents constant-time and near-constant-time distributed algorithms for a variety of problems in the Congested Clique model. We start by showing how to compute a 3-ruling set in expected O(log log log n) rounds and using this, we obtain a constant-approximation to metric facility location, also in expected O(log log log n) rounds. In addition, assuming an input metric space of constant doubling dimension, we obtain constant-round algorithms to compute maximal independent set on distance-threshold graphs and constant-factor approximation to the metric facility location problem. These results significantly improve on the running time of the fastest known algorithms for these problems in the Congested Clique setting. Then, we study two fundamental graph problems, Graph Connectivity (GC) and Minimum Spanning Tree (MST), in the Congested Clique model, and present several new bounds on the time and message complexities of randomized algorithms for these problems. No non-trivial (i.e., super-constant) time lower bounds are known for either of the aforementioned problems; in particular, an important open question is whether or not constant-round algorithms exist for these problems. We make progress toward answering this question by presenting randomized Monte Carlo algorithms for both problems that run in O(log log log n) rounds (where n is the size of the clique). In addition, assuming an input metric space of constant doubling dimension, we obtain constant-round algorithm the MST problem. Our results improve by an exponential factor on the long-standing (deterministic) time bound of O(log log n) rounds for these problems due to Lotker et al. (SICOMP 2005). Our algorithms make use of several algorithmic tools including graph sketching, random sampling, and fast sorting. Thus far there has been little work on understanding the message complexity of problems in the Congested Clique. In this report, we initiate a study on the message complexity of Congested Clique algorithms. We study two graph problems, Graph Connectivity (GC) and Minimum Spanning Tree (MST), in the Congested Clique model, focusing on the design of fast algorithms with low message complexity. Our motivation comes from recently established connections between the Congested Clique model and models of large-scale distributed computing such as MapReduce (Hegeman et al., SIROCCO 2014) and the “big data” model (Klauck et al., SODA 2015). For these connections to be fruitful, Congested Clique algorithms not only need to be fast, they also need to have low message complexity. While the aforementioned algorithms are fast, they have an Ω(n2) message complexity, which makes them impractical in the context of the MapReduce and “big data” models. This motivates our goal of achieving low message complexity, without sacrificing the speed of the algorithm. We start with the simpler GC problem and show that it can be solved in O(log log log n) rounds using only O(n poly log n) messages. Then we derive subroutines to aid our earlier MST algorithm to run in O(log log log n) rounds using O(m poly log n) messages on an m-edge input graph. Then, we present an algorithm running in O(log* n) rounds, with message complexity O (sqrt(m · n)) and then build on this algorithm to derive a family of algorithms, containing for any ε, 0 < ε ≤ 1, an algorithm running in O(log*n/ε) rounds, using O(n^(1+ε/ε)) messages. Setting ε = log log n/ log n leads to the first sub-logarithmic round Congested Clique MST algorithm that uses only O (n) messages. Our results are a step toward understanding the power of randomization in the Congested Clique with respect to both time and message complexity.

Graph theory is fascinating branch of math. Leonhard Euler introduced the concept of Graph Theory in his paper about the seven bridges of Konigsberg published in 1736. In a nutshell, graph theory is the study of pair-wise relationships between objects. Each object is represented using a vertex and in case of a relationship between a pair of vertices, they will be connected using an edge. In this dissertation, graph theory is used to study several important combinatorial optimization problems. In chapter 2, we study the multi-dimensional assignment problem using their underlying hypergraphs. It will be shown how the MAP can be represented by a k-partite graph and how any solution to MAP is associated to a k-clique in the respective k-partite graph. Two heuristics are proposed to solve the MAP and computational studies are performed to compare the performance of the proposed methods with exact solutions. On the heels of chapter 3, a new branch-and-bound method is proposed to solve the problem of finding all k-cliques in a k-partite graph. The new method utilizes bitsets as the data-structure to represent graph data. A new pruning method is introduced in BitCLQ, and CPU instructions are used to improve the performance of the branch-and-bound method. BitCLQ gains up to 300% speed up over existing methods. In chapter 4, two new heuristic to solve decomposable cost MAP's are proposed. The proposed heuristic are based on the partitioning of the underlying graph representing the MAP. In the first heuristic method, MAP's are partitioned into several smaller MAP's with the same dimensiality and smaller cardinality. The solution to the original MAP is constructed incrementally, by using the solutions obtained from each of the smaller MAP's. The second heuristic works in the same fashion. But instead of partitioning the graph along the cardinality, graphs are divided into smaller graphs with the same cardinality but smaller dimensionality. The result of each heuristic is then compared with a well-known existing heuristic. An important problem in graph theory is the maximum clique problem (MCQ). A clique in a graph is defined as a complete subgraph. MCQ problem entails finding the size of the largest clique contained in a graph. General branch-and-bound methods to solve MCQ use graph coloring to find an upper bound on the size of the maximum clique. Recently, a new MAX-SAT based branch-and-bound method for MCQ is proposed that improves the quality of the upper bound obtained from graph coloring. In chapter 5, a branch and bound algorithm is proposed for the maximum clique problem. The proposed method uses bitsets as the data-structure. The result of the computational studies to compare the proposed method with existing methods for MCQ is provided. Chapter 6 contains an application of a graph theory in solving a risk management problem. A new mixed-integer mathematical model to formulate a risk-based network is provided. It will be shown that an optimal solution of the model is a maximal clique in the underlying graph representing the network. The model is then solved using a graph-theoretic approach and the results are compared to CPLEX.