Graph augmentation concerns the addition of edges to a graph to satisfy some connectivity property of a graph. Previous research in this field has been preoccupied with edge augmentation; however the research in this document focuses on the addition of vertices to a graph to satisfy a specific connectivity property: ensuring that all the nodes of the graph are contained within cycles. A distinction is made between graph augmentation (edge addition), and graph enlargement (vertex addition). This document expands on previous research into a graph matching problem known as the “shoe matching problem” and the role of a graph enlargement algorithm in finding this solution. The aim of this research was to develop new and efficient algorithms to solve the graph enlargement problem as applied to the shoe matching problem and to improve on the naïve algorithm of Sanders. Three new algorithms focusing on graph enlargement and the shoe matching problem are presented, with positive results overall. The new enlargement algorithms: cost-optimised, matrix, and subgraph, succeeded in deriving the best result (least number of total nodes required) in 37%, 53%, and 57% of cases respectively (measured across 120 cases). In contrast, Sanders’s algorithm has a success rate of only 20%; thus the new algorithms have a varying success rate of approximately 2 to 3 times that of Sanders’s algorithm. / Computing / M. Sc. Computing

La notion de communauté, transverse à  l'analyse des réseaux sociaux, a attiré une attention grandissante à  travers les sciences ces dix dernières années. Les nombreuses tentatives pour modéliser aussi bien l'incarnation sociologiquedu concept aussi bien que sa manifestation structurelle dans le réseau social n'ont jusqu'à  présent que vaguement convergé. Aucun consensus formel n'a été atteint sur les aspects quantifiables de la communauté, et ceci malgré lesliens forts la reliant aux dimensions dynamique et topologique du réseau sous-jacent.Présentant une approche novatrice à  l'évaluation des communautés, cette thèse introduit et se base sur la cohésion, une métrique qui capture la qualitéintrinsèque, en tant que communauté, d'un ensemble de sommets dans un réseau. Il a été montré au travers d'une experience à  large échelle, dans laquelle les individus sondés ont pu noter l'aspect communautaires de groupes d'amis leur étant présentés, que la cohésion, définie en lien avec la notion de triades sociales, est fortement correlée à  la perception subjective de la communauté. Reflétant la complexité des interactions sociales, il est démontré que leproblème de trouver des communautés maximalement cohésive est NP-dur. En utilisant une heuristique approximant les résultats de ce problème, un certain nombre d'applications de la cohésion à  des données réelles sont mises en avant: de son application à  la visualisation de réseaux complexes, à  l'étude de l'évolution des groupes d'agrément du sénat états-unien, à  la compréhesion des liens entre psychologie et structure du réseau social.L'utilisation de la cohésion apporte un éclairage non trivial dans l'étude de la structure des grands réseaux de terrain et dans la relation entre structure et sémantique. / Community, a notion transversal to all areas of Social Network Analysis, has drawn tremendous amount of attention across the sciences in the past decades. Numerous attempts to characterize both the sociological embodiment of the concept as well as its observable structural manifestation in the social network have to this date only converged in spirit. No formal consensus has been reached on the quantifiable aspects of community, despite it being deeply linked to topological and dynamic aspects of the underlying social network. Presenting a fresh approach to the evaluation of communities, this thesis introduces and builds upon the cohesion, a novel metric which captures the intrinsic quality, as a community, of a set of nodes in a network. The cohesion, defined in terms of social triads, was found to be highly correlated to the subjective perception of communitiness through the use of a large-scale online experiment in which users were able to compute and rate the quality of their social groups on Facebook. Adequately reflecting the complexity of social interactions, the problem of finding a maximally cohesive group inside a given social network is shown to be NP-hard. Using a heuristic approximation algorithm, applications of the cohesion to broadly different use cases are highlighted, ranging from its application to network visualization, to the study of the evolution of agreement groups in the United States Senate, to the understanding of the intertwinement between subjects' psychological traits and the cohesive structures in their social neighborhood. The use of the cohesion proves invaluable in that it offers non-trivial insights on the network structure and its relation to the associated semantic.

Orientadores: Cid Carvalho de Souza, Eduardo Candido Xavier / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T06:06:38Z (GMT). No. of bitstreams: 1 Bogue_EduardoTheodoro_M.pdf: 1929433 bytes, checksum: 1c490811ba46f8482ede0d93da1163f8 (MD5) Previous issue date: 2014 / Resumo: Neste projeto, nós estudamos o Problema da Máxima Interseção de k-Subconjuntos (kMIS). Dado um inteiro k, um conjunto base U e uma coleção S de subconjuntos de U, o problema kMIS consiste em selecior k subconjuntos distintos S1, S2, ... , Sk em S cujo tamanho da interseção de |S1 ? S2 ? ... ? Sk| seja máxima. Trata-se de um problema NP-difícil e difícil de ser aproximado que ocorre em aplicações de áreas como biologia computacional e privacidade de dados. Até o nosso conhecimento, nenhum método exato foi proposto para resolver este problema. Neste trabalho, introduzimos cinco formulações de programação linear inteira para o problema, sendo três baseadas no método de Branch-and-Bound e duas no método de Branch-and-Cut. Além disso, uma heurística gulosa e uma meta-heurística GRASP foram desenvolvidas com o intuito de gerar bons limitantes inferiores. A heurística GRASP desenvolvida foi capaz de encontrar soluções muito próximas da solução ótima. Ademais, introduzimos um método muito eficiente de pré-processamento para reduzir o tamanho da entrada. Experimentos computacionais foram realizados de forma a analisar o desempenho dos modelos de programação linear inteira em questão, demonstrando que os modelos baseados no método de Branch-and-Cut obtiveram melhores resultados / Abstract: In this project, we study the Maximum k-Subset Intersection problem (kMIS). Given an integer k, a ground set U and a collection S of subsets of U, the kMIS problem is to select k distinct subsets S1, S2, ... , Sk in S whose intersection size |S1 ? S2 ? ... ? Sk| is maximum. The kMIS problem is NP-hard and hard to approximate and occurs in areas of applications such as computational biology and data privacy. To the best of our knowledge, no exact method was proposed to solve this problem. In this work, we introduce five integer linear programming formulations for the problem, three using a simple Branch-and-Bound method and two using a Branch-and-Cut method. We also present a greedy heuristic and a metaheuristic GRASP developed in order to generate good lower bounds. The heuristic GRASP developed was able to find solutions very close to the optimal ones. Furthermore, we introduce a very efficient preprocessing procedure to reduce the size of the input. Computational experiments were performed in order to analyze the performance of the integer linear programming models in question, showing that the Branch-and-Cut models performed better / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T08:59:09Z (GMT). No. of bitstreams: 1 Reis_MarcioFelix_M.pdf: 1988657 bytes, checksum: 6ee5ea6ba406aea3ccb7e3332e679eab (MD5) Previous issue date: 2014 / Resumo: Neste trabalho estudamos o problema da árvore geradora com muitas folhas (PAGMF). Este problema pode ser usado como abstração para diversos problemas práticos e sabe-se que é NP-difícil. Estudamos, implementamos e executamos testes para algoritmos aproximados e exatos para o PAGMF e para um caso particular que considera apenas grafos cúbicos. O principal objetivo do trabalho foi verificar o comportamento prático dos algoritmos estudados. Para as instâncias testadas, em geral, o algoritmo guloso apresentou melhores resultados para o PAGMF e o algoritmo 2-aproximado teve os melhores resultados para os grafos cúbicos / Abstract: In this work we study the maximum leaf spanning tree problem (MLSTP). This problem can be used as an abstraction for many practical problems and is known to be NP-hard. We studied, implemented and executed tests for approximate and exact algorithms for the MLSTP and for a particular case that considers only cubic graphs. The main objective of this study was to investigate the practical behavior of the algorithms studied. For the tested instances, in general, the greedy algorithm showed better results for the MLSTP and the 2-approximate algorithm had the best results for cubic graphs / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Célia Picinin de Mello / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T10:47:23Z (GMT). No. of bitstreams: 1 Pedrotti_Vagner_D.pdf: 2015411 bytes, checksum: 4a6917f5811bde65dedbf0f7ab2577c5 (MD5) Previous issue date: 2011 / Resumo: Nesta tese de doutoramento sáo considerados três problemas em grafos, para os quais sáo obtidos resultados quando a entrada é restrita a algumas classes. Todos os problemas sáo problemas de otimização combinatória sobre grafos simples e apresentam diferentes classificações de complexidade. Em dois casos, o estudo focou classes de grafos com "poucos iYs" e ° uso da decomposição modular. No último caso, considerou-se uma subclasse dos grafos de intervalos e a aplicação de uma técnica conhecida como pullback. O primeiro problema estudado é o Problema dos Separadores Minimais, para o qual são conhecidos algoritmos polinomiais em toda classe de grafos que possuir um número polinomial de separadores minimais. Serão dados, como contribuição deste trabalho, um algoritmo linear para listar os separadores minimais de grafos P4-carregados estendidos e limitantes justos no número e tamanho dos separadores minimais destes grafos, bem como de algumas de suas subclasses, P4-carregada, P4-arrumada e P4-íeve. Estes resultados estendem um algoritmo anterior para grafos P4-esparsos, ao mesmo tempo que incluem estas classes de grafos entre as que possuem um número de separadores minimais limitado por um função linear no número de vértices do grafo. Em seguida, será tratado o Problema de Empacotamento de Cliques, uma extensão do problema de emparelhamento máximo. Para a maioria das classes de grafos mais importantes, o problema é NP-Difícil. A contribuição apresentada resolve este problema em tempo polinomial (para qualquer tamanho fixo de clique) em grafos P4-arrumados, através de uma técnica similar a utilizada para os cografos. Infelizmente, para as superclasses mais estudadas da classe P4-arrumada, este problema é NP-Difícil, o que é um indício de que a técnica utilizada foi totalmente aproveitada em relação ás classes com poucos _P4's. Por fim, será estudado o Problema da Coloração Total Forte, uma variação do problema clássico da coloração total, que foi introduzido há pouco tempo e ainda tem sua complexidade computacional desconhecida. Como esperado, existem algoritmos polinomiais apenas para classes bastante simples de grafos. Além da complexidade, outro importante ponto em aberto para o problema é a conjectura de que o número de cores necessárias na solução do problema para um grafo G seria limitado por A(G) + 3. A técnica do pullback, já utilizada para os Problemas de Coloração de Arestas e Coloração Total em grafos dualmente cordais será estendida, resultando em um algoritmo linear para grafos indiferença (também conhecido como grafos de intervalos próprios). Este algoritmo produz uma solução que valida a conjectura nesta classe de grafos. Estas contribuições confirmam a importância da decomposição modular em algoritmos para classes de grafos com "poucos iYs" e ampliam o uso da técnica do pullback para variações dos problemas clássicos de coloração / Abstract: In this doctoral thesis, three problems on graphs are considered and results are given for them when the input is resctricted to some graph classes. All the problems are combinatorial optimization problems on simple graphs and have distinct classihcations of complexity. In two of them, the research focused on graph classes known as graphs with "few iVs" and on the use of modular decomposition on such graphs. In the last problem, a subclass of interval graphs was studied with respect to the application of the technique known as pullback. The first problem studied is the Minimal Separator Problem. For this problem, there exists polynomial time algorithms for every class of graphs which has a polynomial number of minimal separators. A linear-time algorithm, that lists all minimal separators of extended iVladen graphs, is presented. Moreover, tight bounds on the number and on the total size of minimal separators are given for extended iVladen graphs and for some of their subclasses: the iVladen, iVtidy, and iVlite graphs. This result extends a previous algorithm for iVspai'se graphs and gives, for the above classes, better bounds on the number of minimal separators that were already known to be polynomial. Then, the Clique Packing Problem is analyzed. The problem is an extension of the classical Maximum Matching Problem and is NP-Hard for almost all graph classes. The contribution presented solves the problem in polynomial time (for any fixed clique size) in iVtidy graphs through a technique similar to that used for cographs. However, the most well-known superclasses of iVtidy graphs contains split graphs, for which this problem is NP-Hard. This is an evidence that the technique was fully explored with respect of graph classes with few iVs. At last, the Strong Total Coloring Problem is considered. It is a recently introduced variation of the classical Total Coloring Problem and its complexity is still unknown. As expected, there are quite few graph classes for which the problem has a polynomial time algorithm. Besides its complexity, another important open question for this problem is a conjecture which states that A(G) + 3 colors are sufficient for coloring any graph G. A known technique, called pullback, used for edge and total coloring of dually chordal graphs is extended to derive a linear time algorithm for indifference graphs (also known as proper interval graphs). This algorithm produces solutions that validate the conjecture for this graph class. These contributions assert the importance of modular decomposition in algorithms for graph classes with "few P4's" and broaden the pullback technique to variations of classical coloring problems / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Doctorat en Sciences / info:eu-repo/semantics/nonPublished

For a graph G, the minimum dominating set problem is to find a minimum size set S of vertices of G such that every vertex is either in S or adjacent to a vertex in the set. The decision version of this problem, which asks whether G has a dominating set of a particular size k, is known to be NP-complete, and no polynomial time algorithm to solve the problem is currently known to exist. The queen domination problem is to find the minimum number of queens which, collectively, can attack every square on an n by n chess board. The related border queen problem is to find such a collection of queens with the added restriction that all queens lie on the outer border of the board. This thesis studies practical exponential time algorithms for solving domination problems, and presents an experimental comparison of several different algorithms, with the goal of producing a broadly effective general domination solver for use by future researchers. The developed algorithms are then used to solve several open problems, including cases of the queen domination problem and the border queen problem. In addition, new theoretical upper bounds are presented for the border queen problem for some families of queen graphs. / Graduate

In this thesis we study the application of a novel sampling technique to building fully-dynamic randomized graph algorithms. We present the following results: \begin{enumerate} \item A randomized algorithm to estimate the size of a cut in an undirected graph $G = (V, E)$ where $V$ is the set of nodes and $E$ is the set of edges and $n = |V|$ and $m = |E|$. Our algorithm processes edge insertions and deletions in $O(\log^2n)$ time. For a cut $(U, V\setminus U)$ of size $K$ for any subset $U$ of $V$, $|U| < |V|$ our algorithm returns an estimate $x$ of the size of the cut satisfying $K/2 \leq x \leq 2K$ with high probability in $O(|U|\log n)$ time. \item A randomized distributed algorithm for maintaining a spanning forest in a fully-dynamic synchronous network. Our algorithm maintains a spanning forest of a graph with $n$ nodes, with worst case message complexity $\tilde{O}(n)$ per edge insertion or deletion where messages are of size $O(\text{polylog}(n))$. For each node $v$ we require memory of size $\tilde{O}(degree(v))$ bits. This improves upon the best previous algorithm with respect to worst case message complexity, given by Awerbuch, Cidon, and Kutten, which has an amortized message complexity of $O(n)$ and worst case message complexity of $O(n^2)$. \end{enumerate} / Graduate / 0984 / b_mountjoy9@hotmail.com

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

<div> Graph representation learning and Graph Neural Network (GNNs) models provide flexible tools for modeling and representing relational data (graphs) in various application domains. Specifically, node embedding methods provide continuous representations for vertices that has proved to be quite useful for prediction tasks, and Graph Neural Networks (GNNs) have recently been used for semi-supervised node and graph classification tasks with great success. </div><div> </div><div> However, most node embedding methods for unsupervised tasks consider a simple, sparse graph, and are mostly optimized to encode aspects of the network structure (typically local connectivity) with random walks. And GNNs model dependencies among the attributes of nearby neighboring nodes rather than dependencies among observed node labels, which makes it not expressive enough for semi-supervised node classification tasks. </div><div> </div><div> This thesis will investigate methods to address these limitations, including: </div><div><br></div><div> (1) For heterogeneous graphs: Development of a method for dense(r), heterogeneous graphs that incorporates global statistics into the negative sampling procedure with applications in recommendation tasks;</div><div> (2) For capturing long-range role equivalence: Formalized notions of representation-based equivalence w.r.t regular/automorphic equivalence in a single graph or multiple graph samples, which is employed in a embedding-based models to capture long-range equivalence patterns that reflect topological roles; </div><div> (3) For collective classification: Since GNNs model dependencies among the attributes of nearby neighboring nodes rather than dependencies among observed node labels, we develop an add-on collective learning framework to GNNs that provably boosts their expressiveness for node classification tasks, beyond that of an {\em optimal} WL-GNN, utilizing self-supervised learning and Monte Carlo sampled embeddings to incorporate node labels during inductive learning for semi-supervised node classification tasks.</div>