Dissertations / Theses on the topic 'Labeled graph'

In recent years, the popularity of graph databases has grown rapidly. This paper focuses on single-graph as an effective model to represent information and its related graph mining techniques. In frequent pattern mining in a single-graph setting, there are two main problems: support measure and search scheme. In this paper, we propose a novel framework for constructing support measures that brings together existing minimum-image-based and overlap-graph-based support measures. Our framework is built on the concept of occurrence / instance hypergraphs. Based on that, we present two new support measures: minimum instance (MI) measure and minimum vertex cover (MVC) measure, that combine the advantages of existing measures. In particular, we show that the existing minimum-image-based support measure is an upper bound of the MI measure, which is also linear-time computable and results in counts that are close to number of instances of a pattern. Although the MVC measure is NP-hard, it can be approximated to a constant factor in polynomial time. We also provide polynomial-time relaxations for both measures and bounding theorems for all presented support measures in the hypergraph setting. We further show that the hypergraph-based framework can unify all support measures studied in this paper. This framework is also flexible in that more variants of support measures can be defined and profiled in it.

Soit L un ensemble fini d’éléments appelés étiquettes. On appelle graphe étiqueté simple, un graphe simple dans lequel à chaque arête est associée une étiquette prise dans L. Le problème de l’arbre couvrant de nombre d’étiquettes minimal (en anglais: the minimum labeling spanning tree problem, MLSTP) est un problème d’optimisation combinatoire consistant à trouver un arbre couvrant dans un graphe étiqueté simple en utilisant un nombre minimum d’étiquettes. Le problème est NP-dur. Il a fait l’objet d’un nombre important de recherche au cours des dernières années. L’une de ces directions de recherche a par ailleurs conduit à l’étude d’une généralisation du problème dite problème généralisée de l’arbre couvrant de nombre d’étiquettes minimal(en anglais: the generalized minimum labeling spanning tree problem, GMLSTP). Le problème GMLSTP modélise les situations dans lesquelles plusieurs étiquettes peuvent être assignées à un arête. Les deux problèmes ont plusieurs applications pratiques dans des domaines importants tels que la conception de réseaux informatiques, la conception de réseaux de transport multimodaux et la compression de données. Nous proposons dans cette thèse plusieurs résultats théoriques contribuant à l’implantation de nouveaux schémas de résolution pratique de ces problèmes. En particulier, sur le plan théorique, nous avons introduit de nouveaux concepts, définitions, propriétés et théorèmes utiles, ainsi qu’une étude polyédrale du domaine des points réalisables d’une nouvelle formulation de GMLSTP. Cette formulation et son analyse ont permi le développement d’algorithmes de branchement et de coupe (branch-and-cut) pour la résolution exacte des problèmes. De nouvelles heuristiques ont été également développées — telles que l’algorithme basé sur la métaheuristique MSLB, et l’heuristique constructive pMVCA. Des résultats d’expériences numériques sur des benchmarks du problème MLSTP sont données. Elles démontrent la qualité des approches proposées dans cette thèse puisque, aussi bien pour les approches exactes qu’approchées, nous obtenons, comparativement à l’état de l’art du domaine, les meilleurs résultats de la littérature
The minimum labeling spanning tree problem (MLSTP) is a combinatorial optimization problem that consists in finding a spanning tree in a simple edge-labeled graph, i.e., a graph inwhich each edge has one label associated, by using a minimum number of labels. It is anNP-hard problem that has attracted substantial research attention in recent years. In its turn,the generalized minimum labeling spanning tree problem (GMLSTP) is a generalization of theMLSTP that allows the situation in which multiple labels can be assigned to an edge. Bothproblems have several practical applications in important areas such as computer network design, multimodal transportation network design, and data compression. This thesis addressesseveral connectivity problems defined over edge-labeled graphs, in special the minimum labeling spanning tree problem and its generalized version. The contributions in this work can beclassified between theoretical and practical. On the theoretical side, we have introduced newuseful concepts, definitions, properties and theorems regarding edge-labeled graphs, as well asa polyhedral study on the GMLSTP. On the practical side, we have proposed new heuristics— such as the metaheuristic-based algorithm MSLB, and the constructive heuristic pMVCA —and exact methods — such as new mathematical formulations and branch-and-cut algorithms —for solving the GMLSTP. Computational experiments over well established benchmarks for theMLSTP are reported, showing that the new approaches introduced in this work have achievedthe best results for both heuristic and exact methods in comparison with the state-of-the-artmethods in the literature
O Problema da Árvore Geradora com Rotulação Mínima (MLSTP, do inglês minimum labelingspanning tree problem) é um problema de otimização combinatória que consiste em encontraruma árvore de cobertura em um grafo com arestas rotuladas, isto é, um grafo no qual cada arestapossui um rótulo associado, utilizando o menor número de rótulos. Este problema é NP-difícile tem atraído bastante atenção em pesquisas nos últimos anos. Por sua vez, o Problema Generalizado da Árvore Geradora com Rotulação Mínima (GMLSTP, do inglês generalized minimum labeling spanning tree problem) é uma generalização do MLSTP na qual se permite que múltiplos rótulos sejam associados a uma aresta. Ambos os problemas tem aplicações práticas em áreas importantes, como Projeto de Redes de Computadores, Projeto de Redes de Transporte Multimodais e Compactação de Dados. Esta tese aborda vários problemas de conectividade definidos em grafos com arestas rotuladas, em especial o Problema da Árvore Geradora com Rotulação Mínima e sua versão generalizada. As contribuições neste trabalho podem ser classificadas entre teóricas e práticas. Dentre as contribuições teóricas, introduzimos novos conceitos,definições, propriedades e teoremas úteis em relação a grafos com arestas rotuladas, bem como um estudo poliédrico sobre o GMLSTP. Dentre as contribuições práticas, propusemos novas heurísticas _ como o algoritmo baseado na metaheurística MSLB e a heurística construtiva pMVCA _ e métodos exatos _ como novas formulações matemáticas e algoritmos branch- and-cut _ para resolver o GMLSTP. Os experimentos computacionais realizados utilizando conjuntos de instâncias bem estabelecidos para o MLSTP são relatados, mostrando que as novas abordagens introduzidas neste trabalho alcançaram os melhores resultados para métodosheurísticos e exatos em comparação com estado da arte da literatura

Le partitionnement consiste à rechercher une partition d'éléments, de sorte que les éléments d'un même cluster soient plus similaires que les éléments de différents clusters. Les données proviennent de différentes sources et prennent des formes différentes. L'un des défis consiste à concevoir un système capable de tirer parti des différentes sources de données. Certaines contraintes peuvent être connues sur les données. On peut savoir qu'un objet est d'un certain type ou que deux objets partagent le même type ou sont de types différents. On peut également savoir qu'à l'échelle globale, les différents types d'objets apparaissent avec une fréquence connue. Dans cette thèse, nous nous concentrons sur le partitionnement avec trois types de contraintes: les contraintes d'étiquettes, les contraintes de paires et les contraintes de lois de puissance. Une contrainte d'étiquette spécifie dans quel cluster appartient un objet. Les contraintes par paire spécifient que les paires d'objets doivent ou ne doivent pas partager le même cluster. Enfin, la contrainte de loi de puissance est une contrainte globale qui spécifie que la distribution des tailles de cluster est soumise à une loi de puissance. Nous voulons montrer que l'introduction de la semi-supervision aux algorithmes de clustering peut modifier et améliorer les solutions retournées par des algorithmes de clustering non supervisés. Nous contribuons à cette question en proposant des algorithmes pour chaque type de contraintes. Nos expériences sur les ensembles de données UCI et les jeux de données en langage naturel montrent la bonne performance de nos algorithmes et donnent des indications pour des travaux futurs prometteurs
Clustering is the task of finding a partition of items, such that items in the same cluster are more similar than items in different clusters. One challenge consists in designing a system capable of taking benefit of the different sources of data. Among the different forms a piece of data can take, the description of an object can take the form of a feature vector: a list of attributes that takes a value. Objects can also be described by a graph which captures the relationships objects have with each others. In addition to this, some constraints can be known about the data. It can be known that an object is of a certain type or that two objects share the same type or are of different types. It can also be known that on a global scale, the different types of objects appear with a known frequency. In this thesis, we focus on clustering with three different types of constraints: label constraints, pairwise constraints and power-law constraint. A label constraint specifies in which cluster an object belong. Pairwise constraints specify that pairs of object should or should not share the same cluster. Finally, the power-law constraint is a cluster-level constraint that specifies that the distribution of cluster sizes are subject to a power-law. We want to show that introducing semi-supervision to clustering algorithms can alter and improve the solutions returned by unsupervised clustering algorithms. We contribute to this question by proposing algorithms for each type of constraints. Our experiments on UCI data sets and natural language processing data sets show the good performance of our algorithms and give hints towards promising future works

Thesis (PhD)--Stellenbosch University, 2015.
ENGLISH ABSTRACT : In this thesis, a number of combinatorial objects are enumerated. Du and Yin as well as Shin and Zeng (by a different approach) proved an elegant formula for the number of labelled trees with respect to a given in degree sequence, where each edge is oriented from a vertex of lower label towards a vertex of higher label. We refine their result to also take the number of sources (vertices of in degree 0) or sinks (vertices of out degree 0) into account. We find formulas for the mean and variance of the number of sinks or sources in these trees. We also obtain a differential equation and a functional equation satisfied by the generating function for these trees. Analogous results for labelled trees with two marked vertices, related to functional digraphs, are also established. We extend the work to count reachable vertices, sinks and leaf sinks in these trees. Among other results, we obtain a counting formula for the number of labelled trees on n vertices in which exactly k vertices are reachable from a given vertex v and also the average number of vertices that are reachable from a specified vertex in labelled trees of order n. In this dissertation, we also enumerate certain families of set partitions and related tree-like structures. We provide a proof for a formula that counts connected cycle-free families of k set partitions of {1, . . . , n} satisfying a certain coherence condition and then establish a bijection between these families and the set of labelled free k-ary cacti with a given vertex-degree distribution. We then show that the formula also counts coloured Husimi graphs in which there are no blocks of the same colour that are incident to one another. We extend the work to count coloured oriented cacti and coloured cacti. Noncrossing trees and related tree-like structures are also considered in this thesis. Specifically, we establish formulas for locally oriented noncrossing trees with a given number of sources and sinks, and also with given indegree and outdegree sequences. The work is extended to obtain the average number of reachable vertices in these trees. We then generalise the concept of noncrossing trees to find formulas for the number of noncrossing Husimi graphs, cacti and oriented cacti. The study is further extended to find formulas for the number of bicoloured noncrossing Husimi graphs and the number of noncrossing connected cycle-free pairs of set partitions.
AFRIKAANSE OPSOMMING : In hierdie tesis word ’n aantal kombinatoriese objekte geenumereer. Du en Yin asook Shin en Zeng (deur middel van ’n ander benadering) het ’n elegante formule vir die aantal geëtiketteerde bome met betrekking tot ’n gegewe ingangsgraadry, waar elke lyn van die nodus met die kleiner etiket na die nodus met die groter etiket toe georiënteer word. Ons verfyn hul resultaat deur ook die aantal bronne (nodusse met ingangsgraad 0) en putte (nodusse met uitgangsgraad 0) in ag te neem. Ons vind formules vir die gemiddelde en variansie van die aantal putte of bronne in hierdie bome. Ons bepaal verder ’n differensiaalvergelyking en ’n funksionaalvergelyking wat deur die voortbringende funksie van hierdie bome bevredig word. Analoë resultate vir geëtiketteerde bome met twee gemerkte nodusse (wat verwant is aan funksionele digrafieke), is ook gevind. Ons gaan verder voort deur ook bereikbare nodusse, bronne en putte in hierdie bome at te tel. Onder andere verkry ons ’n formule vir die aantal geëtiketteerde bome met n nodusse waarin presies k nodusse vanaf ’n gegewe nodus v bereikbaar is asook die gemiddelde aantal nodusse wat bereikbaar is vanaf ’n gegewe nodus. Ons enumereer in hierdie tesis verder sekere families van versamelingsverdelings en soortgelyke boom-vormige strukture. Ons gee ’n bewys vir ’n formule wat die aantal van samehangende siklus-vrye families van k versamelingsverdelings op {1, . . . , n} wat ’n sekere koherensie-vereiste bevredig, en ons beskryf ’n bijeksie tussen hierdie familie en die versameling van geëtiketteerde vrye k-êre kaktusse met ’n gegewe nodus-graad-verdeling. Ons toon ook dat hierdie formule ook gekleurde Husimi-grafieke tel waar blokke van dieselfde kleur nie insident met mekaar mag wees nie. Ons tel verder ook gekleurde georiënteerde kaktusse en gekleurde kaktusse. Nie-kruisende bome en soortgelyke boom-vormige strukture word in hierdie tesis ook beskou. On bepaal spesifiek formules vir lokaal georiënteerde nie-kruisende bome wat ’n gegewe aantal bronne en putte het asook nie-kruisende bome met gegewe ingangs- en uitgangsgraadrye. Ons gaan voort deur die gemiddelde aantal bereikbare nodusse in hierdie bome te bepaal. Ons veralgemeen dan die konsep van nie-kruisende bome en vind formules vir die aantal nie-kruisende Husimi-grafieke, kaktusse en georiënteerde kaktusse. Laastens vind ons ’n formule vir die aantaal tweegekleurde nie-kruisende Husimi-grafieke en die aantal nie-kruisende samehangende siklus-vrye pare van versamelingsverdelings.

Den stora mängden tillgänglig data på internet kan användas för att förbättra förutsägelser genom maskininlärning. Problemet är att sådan data ofta är i ett obehandlat format och kräver att någon manuellt bestämmer etiketter på den insamlade datan innan den kan användas av algoritmen. Semi-supervised learning (SSL) är en teknik där algoritmen använder ett fåtal förbehandlade exempel och därefter automatiskt bestämmer etiketter för resterande data. Ett tillvägagångssätt inom SSL är att representera datan i en graf, vilket kallas för graf-baserad semi-supervised learning (GSSL), och sedan hitta likheter mellan noderna i grafen för att automatiskt bestämma etiketter.Vårt mål i denna uppsatsen är att förenkla de avancerade processerna och stegen för att implementera en GSSL-algoritm. Vi kommer att gå igen grundläggande steg som hur utvecklingsmiljön ska installeras men även mer avancerade steg som data pre-processering och feature extraction. Feature extraction metoderna som uppsatsen använder sig av är bag-of-words (BOW) och term frequency-inverse document frequency (TF-IDF). Slutgiltligen presenterar vi klassificering av dokument med Label Propagation (LP) och Multinomial Naive Bayes (MNB) samt en detaljerad beskrivning över hur GSSL fungerar.Vi presenterar även prestanda för klassificering-algoritmerna genom att klassificera 20 Newsgroup datasetet med LP och MNB. Resultaten dokumenteras genom två olika utvärderingspoäng vilka är F1-score och accuracy. Vi gör även en jämförelse mellan MNB och LP med två olika typer av kärnor, KNN och RBF, på olika mängder av förbehandlade träningsdokument. Resultaten ifrån klassificering-algoritmerna visar att MNB är bättre på att klassificera datasetet än LP.
The large amount of available data on the web can be used to improve the predictions made by machine learning algorithms. The problem is that such data is often in a raw format and needs to be manually labeled by a human before it can be used by a machine learning algorithm. Semi-supervised learning (SSL) is a technique where the algorithm uses a few prepared samples to automatically prepare the rest of the data. One approach to SSL is to represent the data in a graph, also called graph-based semi-supervised learning (GSSL), and find similarities between the nodes for automatic labeling.Our goal in this thesis is to simplify the advanced processes and steps to implement a GSSL-algorithm. We will cover basic tasks such as setup of the developing environment and more advanced steps such as data preprocessing and feature extraction. The feature extraction techniques covered are bag-of-words (BOW) and term frequency-inverse document frequency (TF-IDF). Lastly, we present how to classify documents using Label Propagation (LP) and Multinomial Naive Bayes (MNB) with a detailed explanation of the inner workings of GSSL. We showcased the classification performance by classifying documents from the 20 Newsgroup dataset using LP and MNB. The results are documented using two different evaluation scores called F1-score and accuracy. A comparison between MNB and the LP-algorithm using two different types of kernels, KNN and RBF, was made on different amount of labeled documents. The results from the classification algorithms shows that MNB is better at classifying the data than LP.

En collaboration avec des chercheurs en biologie à Jussieu, nous étudions des graphes issus de données biologiques afin de d'en améliorer la compréhension. Ces graphes sont constitués à partir de fragments d'ADN, nommés reads. Chaque read correspond à un sommet, et deux sommets sont reliés si les deux séquences d'ADN correspondantes ont un taux de similarité suffisant. Ainsi se forme des graphes ayant une structure bien particulière que nous nommons hub-laminaire. Un graphe est dit hub-laminaire s'il peut être résumé en quelques plus courts chemins dont tous les sommets du graphe soient proche. Nous étudions en détail le cas où le graphe est composé d'un unique plus court chemin d'excentricité faible, ce problème a été initialement défini par Dragan 2017. Nous améliorons la preuve d'un algorithme d'approximation déjà existant et en proposons un nouveau, effectuant une 3-approximation en temps linéaire. De plus, nous analysons le lien avec le problème de k-laminarité défini par Habib 2016, ce dernier consistant en la recherche d'un diamètre de faible excentricité. Nous étudions ensuite le problème du cycle isométrique de plus faible excentricité. Nous montrons que ce problème est NP-complet et proposons deux algorithmes d'approximations. Nous définissons ensuite précisément la structure "hub-laminaire" et présentons un algorithme d'approximation en temps O(nm). Nous confrontons cet algorithme à des graphes générés par une procédure aléatoire et l'appliquons à nos données biologiques. Pour finir nous montrons que le calcul du cycle isométrique d'excentricité minimale permet le plongement d'un graphe dans un cercle avec une distorsion multiplicative faible. Le calcul d'une décomposition hub-laminaire permet quant à lui une représentation compacte des distances avec une distorsion additive bornée
In collaboration with reserchears in biology at Université Pierre et Marie Curie, we study graphs coming from biological data in order to improve our understanding of it. Those graphs come from DNA fragments, named reads. Each read is a vertex and two vertices are linked if the DNA sequences are similar enough. Such graphs have a particuliar structure that we name hub-laminar. A graph is said to be hub-laminar if it may be represented as a (small) set of shortest paths such that every vertex of the graph is close to one of those paths. We first study the case where the graph is composed of an unique shortest path of low eccentricity. This problem was first definied by Dragan 2017. We improve the proof of an approximation algorithm already existing and propose a new one, a 3-approximation running in linear time. Furthermore we show its link with the k-laminar problem defined by Habib 2016, consisting in finding a diameter of low eccentricity. We then define and study the problem of the isometric cycle of minimal eccentricity. We show that this problem is NP-complete and propose two approximation algorithms. We then properly define what is an hub-laminar decomposition and we show an approximation algorithm running in O(nm). We test this algorithm with randomly generated graphs and apply it to our biolgical data. Finaly we show that computing an isometric cycle of low eccentricity allows to embed a graph into a cycle with a low multiplicative distortion. Computing an hub-laminar decomposition allows a compact representation of distances with a low additive distortion

In program analysis, unknown properties for terms are typically represented symbolically as variables. Bound constraints on these variables can then specify multiple optimisation goals for computer programs and nd application in areas such as type theory, security, alias analysis and resource reasoning. Resolution of bound constraints is a problem steeped in graph theory; interdependencies between the variables is represented as a constraint graph. Additionally, constants are introduced into the system as concrete bounds over these variables and constants themselves are ordered over a lattice which is, once again, represented as a graph. Despite graph algorithms being central to bound constraint solving, most approaches to program optimisation that use bound constraint solving have treated their graph theoretic foundations as a black box. Little has been done to investigate the computational costs or design e cient graph algorithms for constraint resolution. Emerging examples of these lattices and bound constraint graphs, particularly from the domain of language-based security, are showing that these graphs and lattices are structurally diverse and could be arbitrarily large. Therefore, there is a pressing need to investigate the graph theoretic foundations of bound constraint solving. In this thesis, we investigate the computational costs of bound constraint solving from a graph theoretic perspective for Information Flow Analysis (IFA); IFA is a sub- eld of language-based security which veri es whether con dentiality and integrity of classified information is preserved as it is manipulated by a program. We present a novel framework based on graph decomposition for solving the (atomic) bound constraint problem for IFA. Our approach enables us to abstract away from connections between individual vertices to those between sets of vertices in both the constraint graph and an accompanying security lattice which defines ordering over constants. Thereby, we are able to achieve significant speedups compared to state-of-the-art graph algorithms applied to bound constraint solving. More importantly, our algorithms are highly adaptive in nature and seamlessly adapt to the structure of the constraint graph and the lattice. The computational costs of our approach is a function of the latent scope of decomposition in the constraint graph and the lattice; therefore, we enjoy the fastest runtime for every point in the structure-spectrum of these graphs and lattices. While the techniques in this dissertation are developed with IFA in mind, they can be extended to other application of the bound constraints problem, such as type inference and program analysis frameworks which use annotated type systems, where constants are ordered over a lattice.

Negli ultimi anni del secolo scorso l’avvento di Internet ha permesso di avere a disposizione innumerevoli quantità di testi consultabili online, provenienti sia da libri e riviste, sia da nuove forme di comunicazione della rete quali email, forum, newsgroup e chat. 
Le soluzioni adottate nel settore del Text Mining (d’ora in poi abbreviato in TM), che è l’estensione del Data Mining rivolto a dati testuali non strutturati, si basano su fondamenti informatici, statistici e linguistici e sono in linea di principio applicabili a documenti di qualsiasi dimensione.
Con l’avvento dei Social Networks la quantità e la dimensione dei dati testuali da analizzare è cresciuta in maniera sub-esponenziale e benché le tecniche disponibili rimangono comunque valide e applicabili, negli ultimi quattro/cinque anni la ricerca si è concentrata su una tecnica emergente, chiamata semantic hashing, che consente di mappare documenti di qualunque tipo in stringhe binarie.
Sfruttando questa nuova branca di ricerca, lo scopo principale di questa tesi è di definire, progettare ed implementare un algoritmo di clustering che prendendo in input questi dati binari sia in grado di etichettare tali dati in maniera più precisa ed in tempi minori rispetto a quanto fanno gli altri approcci presenti in letteratura.
Dopo una descrizione di quelle che sono le principali tecniche di TM, seguirà una trattazione relativa all’hashing semantico e alle basi teoriche su cui questo si fonda per poi introdurre l’algoritmo adoperato per fare clustering, presentandone lo schema architetturale di funzionamento e la relativa implementazione. 
Infine saranno comparati e analizzati i risultati dell’esecuzione dell’algoritmo, chiamato d’ora in poi Label Propagation (abbreviato in LP), con quelli ottenuti con tecniche standard.

Les graphes sont des structures mathématiques capable de modéliser certains systèmes complexes.Une des nombreuses problématiques liée aux graphes concerne la détection de communautés qui vise à trouver une partition en sommet d'un graphe en vue d'en comprendre la structure. A titre d'exemple, en représentant des contratsd'assurances par des noeuds et leurs degrés de similarité par une arête,détecter des groupes de noeuds fortement connectésconduit à détecter des profils similaires, et donc a voir des profils à risques.De nombreux algorithmes ont essayé de répondreà ce problème.Une des méthodes est la propagation de labels qui consiste à ce quechaque noeud puisse recevoir un label par un vote majoritaire de ses voisins.Bien que cette méthode soit simple à mettre en oeuvre,elle présente une grande instabilité due au non déterminisme del'algorithme et peut dans certains cas ne pas détecter de structures communautaires.La première contribution de cette thèse sera de i) proposerune méthode de stabilisation de la propagation de labelstout en appliquant des barrages artificiels pour limiter les possibles mauvaises propagations.Les réseaux complexes ont également comme caractéristique que certains noeuds puissent appartenir à plusieurs communautés, on parle alors de recouvrements. C'est en ce sens que la secondecontribution de cette thèse portera sur ii) la créationd'un algorithme auquel seront adjointes des fonctions d'appartenancespour détecter de possibles recouvrements via des noeuds candidats au chevauchement.La taille des graphes est également une notion à considérer dans la mesure où certains réseaux peuvent contenir plusieursmillions de noeuds et d'arêtes.Nous proposons iii) une version parallèleet distribuée de la détection de communautés en utilisant la propagation de labels par coeur.Une étude comparative sera effectuée pour observerla qualité de partitionnement et de recouvrement desalgorithmes proposés
Graphs are mathematical structures amounting to a set of nodes (objects or persons) in which some pairs are in linked with edges. Graphs can be used to model complex systems.One of the main problems in graph theory is the community detection problemwhich aims to find a partition of nodes in the graph to understand its structure.For instance, by representing insurance contracts by nodes and their relationship by edges,detecting groups of nodes highly connected leads to detect similar profiles and to evaluate risk profiles. Several algorithms are used as aresponse to this currently open research field.One of the fastest method is the label propagation.It's a local method, in which each node changes its own label according toits neighbourhood.Unfortunately, this method has two major drawbacks. The first is the instability of the method. Each trialgives rarely the same result.The second is a bad propagation which can lead to huge communities without sense (giant communities problem).The first contribution of the thesis is i) proposing a stabilisation methodfor the label propagation with artificial dams on edges of some networks in order to limit bad label propagations. Complex networks are also characterized by some nodes which may belong to several communities,we call this a cover.For example, in Protein–protein interaction networks, some proteins may have several functions.Detecting these functions according to their communities could help to cure cancers. The second contribution of this thesis deals with the ii)implementation of an algorithmwith functions to detect potential overlapping nodes .The size of the graphs is also to be considered because some networks contain several millions of nodes and edges like the Amazon product co-purchasing network.We propose iii) a parallel and a distributed version of the community detection using core label propagation.A study and a comparative analysis of the proposed algorithms will be done based on the quality of the resulted partitions and covers

A Probabilistically Checkable Proof (PCP) of a mathematical statement is a proof written in a special manner that allows for efficient probabilistic verification. The celebrated PCP Theorem states that for every family of statements in NP, there is a probabilistic verification procedure that checks the validity of a PCP proof by reading only 3 bits from it. This landmark theorem, and the works leading up to it, laid the foundation for many subsequent works in computational complexity theory, the most prominent among them being the study of inapproximability of combinatorial optimization problems. This thesis focuses on a broad class of combinatorial optimization problems called Constraint Satisfaction Problems (CSPs). In an instance of a CSP problem of arity k, we are given a set of variables taking values from some finite domain, and a set of constraints each involving a subset of at most k variables. The goal is to find an assignment that simultaneously satisfies as many constraints as possible. An alternative formulation of the goal that is commonly used is Gap-CSP, where the goal is to decide whether a CSP instance is satisfiable or far from satisfiable, where the exact meaning of being far from satisfiable varies depending on the problems.We first study Boolean CSPs, where the domain of the variables is {0,1}. The main question we study is the hardness of distinguishing satisfiable Boolean CSP instances from those for which no assignment satisfies more than some epsilon fraction of the constraints. Intuitively, as the arity increases, the CSP gets more complex and thus the hardness parameter epsilon should decrease. We show that for Boolean CSPs of arity k, it is NP-hard to distinguish satisfiable instances from those that are at most 2^{~O(k^{1/3})}/2^k-satisfiable. We also study coloring of graphs and hypergraphs. Given a graph or a hypergraph, a coloring is an assignment of colors to vertices, such that all edges or hyperedges are non-monochromatic. The gap problem is to distinguish instances that are colorable with a small number of colors, from those that require a large number of colors. For graphs, we prove that there exists a constant K_0>0, such that for any K >= K_0, it is NP-hard to distinguish K-colorable graphs from those that require 2^{Omega(K^{1/3})} colors. For hypergraphs, we prove that it is quasi-NP-hard to distinguish 2-colorable 8-uniform hypergraphs of size N from those that require 2^{(log N)^{1/4-o(1)}} colors. In terms of techniques, all these results are based on constructions of PCPs with perfect completeness, that is, PCPs where the probabilistic proof verification procedure always accepts a correct proof. Not only is this a very natural property for proofs, but it can also be an essential requirement in many applications. It has always been particularly challenging to construct PCPs with perfect completeness for NP statements due to limitations in techniques. Our improved hardness results build on and extend many of the current approaches. Our Boolean CSP result and GraphColoring result were proved by adapting the Direct Sum of PCPs idea by Siu On Chan to the perfect completeness setting. Our proof for hypergraph coloring hardness improves and simplifies the recent work by Khot and Saket, in which they proposed the notion of superposition complexity of CSPs.
Ett probabilistiskt verifierbart bevis (eng: Probabilistically Checkable Proof, PCP) av en matematisk sats är ett bevis skrivet på ett speciellt sätt vilket möjliggör en effektiv probabilistisk verifiering. Den berömda PCP-satsen säger att för varje familj av påståenden i NP finns det en probabilistisk verifierare som kontrollerar om en PCP bevis är giltigt genom att läsa endast 3 bitar från det. Denna banbrytande sats, och arbetena som ledde fram till det, lade grunden för många senare arbeten inom komplexitetsteorin, framförallt inom studiet av approximerbarhet av kombinatoriska optimeringsproblem. I denna avhandling fokuserar vi på en bred klass av optimeringsproblem i form av villkorsuppfyllningsproblem (engelska ``Constraint Satisfaction Problems'' CSPs). En instans av ett CSP av aritet k ges av en mängd variabler som tar värden från någon ändlig domän, och ett antal villkor som vart och ett beror på en delmängd av högst k variabler. Målet är att hitta ett tilldelning av variablerna som samtidigt uppfyller så många som möjligt av villkoren. En alternativ formulering av målet som ofta används är Gap-CSP, där målet är att avgöra om en CSP-instans är satisfierbar eller långt ifrån satisfierbar, där den exakta innebörden av att vara ``långt ifrån satisfierbar'' varierar beroende på problemet.Först studerar vi booleska CSPer, där domänen är {0,1}. Den fråga vi studerar är svårigheten av att särskilja satisfierbara boolesk CSP-instanser från instanser där den bästa tilldelningen satisfierar högst en andel epsilon av villkoren. Intuitivt, när ariten ökar blir CSP mer komplexa och därmed bör svårighetsparametern epsilon avta med ökande aritet. Detta visar sig vara sant och ett första resultat är att för booleska CSP av aritet k är det NP-svårt att särskilja satisfierbara instanser från dem som är högst 2^{~O(k^{1/3})}/2^k-satisfierbara. Vidare studerar vi färgläggning av grafer och hypergrafer. Givet en graf eller en hypergraf, är en färgläggning en tilldelning av färger till noderna, så att ingen kant eller hyperkant är monokromatisk. Problemet vi analyserar är att särskilja instanser som är färgbara med ett litet antal färger från dem som behöver många färger. För grafer visar vi att det finns en konstant K_0>0, så att för alla K >= K_0 är det NP-svårt att särskilja grafer som är K-färgbara från dem som kräver minst 2^{Omega(K^{1/3})} färger. För hypergrafer visar vi att det är kvasi-NP-svårt att särskilja 2-färgbara 8-likformiga hypergrafer som har N noder från dem som kräv minst 2^{(log N)^{1/4-o(1)}} färger. Samtliga dessa resultat bygger på konstruktioner av PCPer med perfekt fullständighet. Det vill säga PCPer där verifieraren alltid accepterar ett korrekt bevis. Inte bara är detta en mycket naturlig egenskap för PCPer, men det kan också vara ett nödvändigt krav för vissa tillämpningar. Konstruktionen av PCPer med perfekt fullständighet för NP-påståenden ger tekniska komplikationer och kräver delvis utvecklande av nya metoder. Vårt booleska CSPer resultat och vårt Färgläggning resultat bevisas genom att anpassa ``Direktsumman-metoden'' introducerad av Siu On Chan till fallet med perfekt fullständighet. Vårt bevis för hypergraffärgningssvårighet förbättrar och förenklar ett färskt resultat av Khot och Saket, där de föreslog begreppet superpositionskomplexitet av CSP.

QC 20150916

A good image representation is vital for image comparision and classification; it may affect the classification accuracy and efficiency. The purpose of this thesis was to explore novel and appropriate image representations. Another aim was to investigate these representations for image classification. Finally, novel features were examined for improving image classification accuracy. Images of interest to this thesis were textile design images. The motivation of analysing textile design images is to help designers browse images, fuel their creativity, and improve their design efficiency. In recent years, bag-of-words model has been shown to be a good base for image representation, and there have been many attempts to go beyond this representation. Bag-of-words models have been used frequently in the classification of image data, due to good performance and simplicity. “Words” in images can have different definitions and are obtained through steps of feature detection, feature description, and codeword calculation. The model represents an image as an orderless collection of local features. However, discarding the spatial relationships of local features limits the power of this model. This thesis exploited novel image representations, bag of shapes and region label graphs models, which were based on bag-of-words model. In both models, an image was represented by a collection of segmented regions, and each region was described by shape descriptors. In the latter model, graphs were constructed to capture the spatial information between groups of segmented regions and graph features were calculated based on some graph theory. Novel elements include use of MRFs to extract printed designs and woven patterns from textile images, utilisation of the extractions to form bag of shapes models, and construction of region label graphs to capture the spatial information. The extraction of textile designs was formulated as a pixel labelling problem. Algorithms for MRF optimisation and re-estimation were described and evaluated. A method for quantitative evaluation was presented and used to compare the performance of MRFs optimised using alpha-expansion and iterated conditional modes (ICM), both with and without parameter re-estimation. The results were used in the formation of the bag of shapes and region label graphs models. Bag of shapes model was a collection of MRFs' segmented regions, and the shape of each region was described with generic Fourier descriptors. Each image was represented as a bag of shapes. A simple yet competitive classification scheme based on nearest neighbour class-based matching was used. Classification performance was compared to that obtained when using bags of SIFT features. To capture the spatial information, region label graphs were constructed to obtain graph features. Regions with the same label were treated as a group and each group was associated uniquely with a vertex in an undirected, weighted graph. Each region group was represented as a bag of shape descriptors. Edges in the graph denoted either the extent to which the groups' regions were spatially adjacent or the dissimilarity of their respective bags of shapes. Series of unweighted graphs were obtained by removing edges in order of weight. Finally, an image was represented using its shape descriptors along with features derived from the chromatic numbers or domination numbers of the unweighted graphs and their complements. Linear SVM classifiers were used for classification. Experiments were implemented on data from Liberty Art Fabrics, which consisted of more than 10,000 complicated images mainly of printed textile designs and woven patterns. Experimental data was classified into seven classes manually by assigning each image a text descriptor based on content or design type. The seven classes were floral, paisley, stripe, leaf, geometric, spot, and check. The result showed that reasonable and interesting regions were obtained from MRF segmentation in which alpha-expansion with parameter re-estimation performs better than alpha-expansion without parameter re-estimation or ICM. This result was not only promising for textile CAD (Computer-Aided Design) to redesign the textile image, but also for image representation. It was also found that bag of shapes model based on MRF segmentation can obtain comparable classification accuracy with bag of SIFT features in the framework of nearest neighbour class-based matching. Finally, the result indicated that incorporation of graph features extracted by constructing region label graphs can improve the classification accuracy compared to both bag of shapes model and bag of SIFT models.

碩士
國立臺灣師範大學
資訊工程學系
103
Graph is a powerful abstraction of structural data, which is applied to model the various relations among data in a real world. Recently, a new kind of patterns called frequent neighborhood patterns is defined for a large labeled graph. Frequent neighborhood patterns have the downward closure property of the support measure and provide meaningful interpretations of pattern mining. The previous work used an Apriori-like approach to combine the discovered frequent neighborhood patterns into larger candidate patterns, many of the generated candidates may not appear in the graph. In this thesis, we propose an algorithm, which is called the gSFNP algorithm, to find frequent neighborhood patterns efficiently. By applying a pattern growth approach, a data structure of pattern is designed to store the information of the matched sub-graphs for speeding up the following pattern growth computation. Besides, the minimum DFS code of a pattern is used to avoid finding graph isomorphic patterns. Moreover, we propose another MapReduce version of the gSFNP algorithm, which is called the gSFNP_MR algorithm, to solve the problem of insufficient memory in a centralized environment. Finally, we evaluate the performance of gSFNP and gSFNP_MR. The experimental results show that both the proposed algorithms have shorter response time than the previous work.

This thesis focuses on two fundamental machine learning problems:unsupervised learning, where no label information is available, and semi-supervised learning, where a small amount of labels are given in addition to unlabeled data. These problems arise in many real word applications, such as Web analysis and bioinformatics,where a large amount of data is available, but no or only a small amount of labeled data exists. Obtaining classification labels in these domains is usually quite difficult because it involves either manual labeling or physical experimentation. This thesis approaches these problems from two perspectives: graph based and distribution based. First, I investigate a series of graph based learning algorithms that are able to exploit information embedded in different types of graph structures. These algorithms allow label information to be shared between nodes in the graph---ultimately communicating information globally to yield effective unsupervised and semi-supervised learning. In particular, I extend existing graph based learning algorithms, currently based on undirected graphs, to more general graph types, including directed graphs, hypergraphs and complex networks. These richer graph representations allow one to more naturally capture the intrinsic data relationships that exist, for example, in Web data, relational data, bioinformatics and social networks. For each of these generalized graph structures I show how information propagation can be characterized by distinct random walk models, and then use this characterization to develop new unsupervised and semi-supervised learning algorithms. Second, I investigate a more statistically oriented approach that explicitly models a learning scenario where the training and test examples come from different distributions. This is a difficult situation for standard statistical learning approaches, since they typically incorporate an assumption that the distributions for training and test sets are similar, if not identical. To achieve good performance in this scenario, I utilize unlabeled data to correct the bias between the training and test distributions. A key idea is to produce resampling weights for bias correction by working directly in a feature space and bypassing the problem of explicit density estimation. The technique can be easily applied to many different supervised learning algorithms, automatically adapting their behavior to cope with distribution shifting between training and test data.

Wang, Dingyan.
Thesis (M.Phil.)--Chinese University of Hong Kong, 2011.
Includes bibliographical references (p. 97-110).
Abstracts in English and Chinese.
Abstract --- p.ii
Acknowledgement --- p.vi
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Overview --- p.1
Chapter 1.2 --- Motivations --- p.6
Chapter 1.3 --- Contributions --- p.9
Chapter 1.4 --- Organizations of This Thesis --- p.11
Chapter 2 --- Background --- p.14
Chapter 2.1 --- Label Propagation Learning Framework --- p.14
Chapter 2.1.1 --- Graph-based Semi-supervised Learning --- p.14
Chapter 2.1.2 --- Green's Function Learning Framework --- p.16
Chapter 2.2 --- Recommendation Methods --- p.19
Chapter 2.2.1 --- Traditional Memory-based Methods --- p.19
Chapter 2.2.2 --- Traditional Model-based Methods --- p.20
Chapter 2.2.3 --- Label Propagation Recommendation Models --- p.22
Chapter 2.2.4 --- Latent Feature Recommendation Models . --- p.24
Chapter 2.2.5 --- Social Recommendation Models --- p.25
Chapter 2.2.6 --- Tag-based Recommendation Models --- p.25
Chapter 3 --- Recommendation with Latent Features --- p.28
Chapter 3.1 --- Motivation and Contributions --- p.28
Chapter 3.2 --- Item Graph --- p.30
Chapter 3.2.1 --- Item Graph Definition --- p.30
Chapter 3.2.2 --- Item Graph Construction --- p.31
Chapter 3.3 --- Label Propagation Recommendation Model with Latent Features --- p.33
Chapter 3.3.1 --- Latent Feature Analysis --- p.33
Chapter 3.3.2 --- Probabilistic Matrix Factorization --- p.35
Chapter 3.3.3 --- Similarity Consistency Between Global and Local Views (SCGL) --- p.39
Chapter 3.3.4 --- Item-based Green's Function Recommendation Based on SCGL --- p.41
Chapter 3.4 --- Experiments --- p.41
Chapter 3.4.1 --- Dataset --- p.43
Chapter 3.4.2 --- Baseline Methods --- p.43
Chapter 3.4.3 --- Metrics --- p.45
Chapter 3.4.4 --- Experimental Procedure --- p.45
Chapter 3.4.5 --- Impact of Weight Parameter u --- p.46
Chapter 3.4.6 --- Performance Comparison --- p.48
Chapter 3.5 --- Summary --- p.50
Chapter 4 --- Recommendation with Social Network --- p.51
Chapter 4.1 --- Limitation and Contributions --- p.51
Chapter 4.2 --- A Social Recommendation Framework --- p.55
Chapter 4.2.1 --- Social Network --- p.55
Chapter 4.2.2 --- User Graph --- p.57
Chapter 4.2.3 --- Social-User Graph --- p.59
Chapter 4.3 --- Experimental Analysis --- p.60
Chapter 4.3.1 --- Dataset --- p.61
Chapter 4.3.2 --- Metrics --- p.63
Chapter 4.3.3 --- Experiment Setting --- p.64
Chapter 4.3.4 --- Impact of Control Parameter u --- p.65
Chapter 4.3.5 --- Performance Comparison --- p.67
Chapter 4.4 --- Summary --- p.69
Chapter 5 --- Recommendation with Tags --- p.71
Chapter 5.1 --- Limitation and Contributions --- p.71
Chapter 5.2 --- Tag-Based User Modeling --- p.75
Chapter 5.2.1 --- Tag Preference --- p.75
Chapter 5.2.2 --- Tag Relevance --- p.78
Chapter 5.2.3 --- User Interest Similarity --- p.80
Chapter 5.3 --- Tag-Based Label Propagation Recommendation --- p.83
Chapter 5.4 --- Experimental Analysis --- p.84
Chapter 5.4.1 --- Douban Dataset --- p.85
Chapter 5.4.2 --- Experiment Setting --- p.86
Chapter 5.4.3 --- Metrics --- p.87
Chapter 5.4.4 --- Impact of Tag and Rating --- p.88
Chapter 5.4.5 --- Performance Comparison --- p.90
Chapter 5.5 --- Summary --- p.92
Chapter 6 --- Conclusions and Future Work --- p.94
Chapter 6.0.1 --- Conclusions --- p.94
Chapter 6.0.2 --- Future Work --- p.96
Bibliography --- p.97

碩士
國立清華大學
資訊工程學系
104
Image segmentation is an important issue in image editing and computer vision. Due to the complexity of information in images, efficient extraction of a foreground object is a challenging problem. Recently, several approaches based on optimization by graph cuts have been developed which successfully combine the color feature with the edge information. A problem is that the segmentation results heavily depend on the seeds selection. However, it is difficult to obtaining reliable seeds automatically. To overcome this problem, we propose an automatic scheme for image segmentation. Compare to the classical binary-label graph cuts, the results by the multi-label graph cuts do not heavily depend on the seeds selection. Our method uses the multi-label graph cuts to separate an image into multiple segments, and then classify the segments into the object and the background. We introduce the standard deviation to adapt the importance between the properties in our method. Experiments show that the proposed method yields more accurate segmentation results than the previous automatic approach and is comparable to the interactive approach.

This thesis develops a number of graph-based techniques that are capable of measuring the dynamic behaviour of a network and discusses their application in network management. By representing a computer network as a time series of uniquely labelled graphs, it is possible to measure the degree of change that has occurred between a pair of graphs, and hence the dynamics in a network. Concepts introduced include the median graph, intra- and inter- graph clustering, and hierarchical graph representations. The focus is on producing efficient algorithms and improved measures of network change. It is believed that these graph-based techniques for measuring network dynamics have great potential in network anomaly detection, and thus will improve reliability of enterprise intranets.

This thesis presents the first sub-quadratic circle graph recognition algorithm, and develops improved algorithms for two important hierarchical decomposition schemes: modular decomposition and split decomposition. The modular decomposition algorithm results from unifying two different approaches previously employed to solve the problem: divide-and-conquer and factorizing permutations. It runs in linear-time, and is straightforward in its understanding, correctness, and implementation. It merely requires a collection of trees and simple traversals of these trees. The split-decomposition algorithm is similar in being straightforward in its understanding and correctness. An efficient implementation of the algorithm is described that uses the union-find data-structure. A novel charging argument is used to prove the running-time. The algorithm is the first to use the recent reformulation of split decomposition in terms of graph-labelled trees. This facilitates its extension to circle graph recognition. In particular, it allows us to efficiently apply a new lexicographic breadth-first search characterization of circle graphs developed in the thesis. Lexicographic breadth-first search is additionally responsible for the efficiency of the split decomposition algorithm, and contributes to the simplicity of the modular decomposition algorithm.

Computational learning theory is a branch of theoretical computer science that re-imagines the role of an algorithm from an agent of computation to an agent of learning. The operations of computers become those of the human mind; an important step towards illuminating the limitations of artificial intelligence. The central difference between a learning algorithm and a traditional algorithm is that the learner has access to an oracle who, in constant time, can answer queries about that to be learned. Normally an algorithm would have to discover such information on its own accord. This subtle change in how we model problem solving results in changes in the computational complexity of some classic problems; allowing us to re-examine them in a new light. Specifically two known result are examined: one positive, one negative. It is know that one can efficiently learn Deterministic Finite Automatons with queries, not so of Non-Deterministic Finite Automatons. We generalize these Automatons into Labeled Transition Systems and attempt to learn them using a stronger query.