Δίκτυα που εμφανίζουν μόνιμα μια συγκεκριμένη ιδιότητα ανεξάρτητα από το μέγεθος και την πυκνότητά τους ονομάζονται ανεξάρτητα από την κλίμακα (scale-free). Σε πολλά πραγματικά δίκτυα αυτή η ιδιότητα ταυτίζεται με την κατανομή των βαθμών των κόμβων σύμφωνα με τον νόμο της δύναμης με εκθέτη στο διάστημα [2..4]. Η εργασία παρουσιάζει τρία στατικά μοντέλα κατασκευής scale-free δικτύων με την παραπάνω ιδιότητα, βασισμένα στο δυναμικό μοντέλο Barabási-Albert, και επιχειρεί να προσεγγίσει πειραματικά τον χρωματικό τους αριθμό. / Networks that exhibit a certain quality irrespective of their size and density are called scale-free. In many real-life networks this quality coincides with a power-law distribution of the nodes' degree with exponent ranging in [2..4]. This work presents three static models for constructing scale-free networks, based on the dynamic Barabási-Albert model, and attempts to experimentally approximate their chromatic number.

Advancement of micro-electro-mechanics and wireless communication have proliferated the deployment of large-scale wireless sensor networks. Due to cost, size and power constraints, at most a few sensor nodes can be equipped with a global positioning system; such nodes (whose positions can be accurately determined) are referred to as anchors. However, one can deter-mine the distance between two nearby sensors using some form of local communication. The problem of computing the positions of the non-anchor nodes from the inter-sensor distances and anchor positions is referred as sensor network localization (SNL). In this dissertation, our aim is to develop an accurate, efficient, and scalable localization algorithm, which can operate both in the presence and absence of anchors. It has been demon-strated in the literature that divide-and-conquer approaches can be used to localize large net-works without compromising the localization accuracy. The core idea with such approaches is to partition the network into overlapping subnetworks, localize each subnetwork using the available distances (and anchor positions), and finally register the subnetworks in a single coordinate system. In this regard, the contributions of this dissertation are as follows: We study the global registration problem and formulate a necessary “rigidity” condition for uniquely recovering the global sensor locations. In particular, we present a method for efficiently testing rigidity, and a heuristic for augmenting the partitioned network to enforce rigidity. We present a mechanism for partitioning the network into smaller subnetworks using cliques. Each clique is efficiently localized using multidimensional scaling. Finally, we use a recently proposed semidefinite program (SDP) to register the localized subnetworks. We develop a scalable ADMM solver for the SDP in question. We present simulation results on random and structured networks to demonstrate the pro-posed methods perform better than state-of-the-art methods in terms of run-time, accuracy, and scalability.

Ha Minh Lam et M. Morales ont introduit une classe d'idéaux binomiaux qui est une extension binomiale d'idéaux monomiaux libres de carrés.Étant donné I un idéal monomial quadratique de k[x] libre de carrés et J une somme d'idéaux de scroll de k[z] qui satisfont certaines conditions, nous définissons l'extension binomiale de I comme B=I+J. Le sujet de cette thèse est d'étudier le nombre p plus grand tel que les sizygies de B son linéaires jusqu'au pas p-1. Sous certaines conditions d'ordre imposées sur les facettes du complexe de Stanley-Reisner de I nous obtiendrons un ordre > pour les variables de l'anneau de polynomes k[z]. Ensuite nous prouvons pour un calcul des bases de Gröbner que l'idéal initial in(B), sous l'ordre lexicographique induit par l'ordre de variables >, est quadratique libre de carrés. Nous montrerons que B est régulier si et seulement si I est 2-régulier. Dans le cas géneral, lorsque I n'est pas 2-régulier nous trouverons une borne pour l'entier q maximal qui satisfait que les premier q-1 sizygies de B son linéaires. En outre, en supossant que J est un idéal torique et en imposant des conditions supplémentaires, nous trouveron une borne supérieure pour l'entier q maximal qui satisfait que les premier q-1 sizygies de B son linéaires. En imposant des conditions supplémentaires, nous prouverons que les deux bornes sont égaux. / Ha Minh Lam et M. Morales introduced a family of binomial ideals that are binomial extensions of square free monomial ideals. Let I be a square free monomial ideal of k[x] and J a sum of scroll ideals in k[z] with some extra conditions, we define the binomial extension of $I$ as $B=I+Jsubset sis$. The aim of this thesis is to study the biggest number p such that the syzygies of B are linear until the step p-1. Due to some order conditions given to the facets of the Stanley-Reisner complex of I we get an order > for the variables of the polynomial ring k[z]. By a calculation of the Gröbner basis of the ideal $B$ we obtain that the initial ideal in(B) is a square free monomial ideal. We will prove that B is 2-regular iff I is 2-regular. In the general case, wheter I is not 2-regular we will find a lower bound for the the maximal integer q which satisfies that the first q-1 sizygies of B are linear. On the other hand, wheter J is toric and supposing other conditions, we will find a upper bound for the integer q which satisfies that the first q-1 syzygies of B are linear. By given more conditions we will prove that the twobounds are equal.

本研究為探討網路演化過程中的群聚現象，說明網路是否能夠藉由訊息傳遞的過程而浮現出族群分離的現象，為此我們架構了一個電腦模型，同時加入了突現行為（mutation）的考量，藉此來瞭解網路形成過程中的不理性行為是否有影響族群群聚的功效存在，探討在不同的突現發生機率下，網路演化過程中的群聚現象是否會隨著突現發生機率的不同而產生不同的結果。至於，在連結形成方面，我們設定連結如果要形成的話，必須要雙方玩家都願意採取相同的投資動作才能成立，連結必須要雙方玩家都相互協調的情況下才能建立，所以玩家每期都會先選擇要進行的投資策略，其次才依照雙方所選擇的投資動作來決定連結是否建立，並不像以往的文獻中所述，完全依照玩家是否有連結誘因存在來決定連結是否建立，在本研究中玩家是依照雙方所選擇的投資動作來決定連結是否形成。 在此研究中，我們以富人和窮人的投資合作過程為故事背景，假定玩家都有兩種投資策略可以選擇，玩家會從中擇一採用，當雙方玩家協商之後，如果雙方都願意採取相同的投資動作的話，則連結就會建立。設定富人選擇投資策略的自由度較高，而窮人選擇投資策略的自由度較低，因此當玩家開始去尋找適合的合作伙伴時，窮人所受的限制較多，而富人所受的限制較少，但是為了避免設定了太強的假設，所以本研究盡量使用較為薄弱的假設，盡可能使窮人與富人之間的差異性不大且符合現實。在這種行為模式的設定下，我們利用兩個群聚比例來計算每期所形成的同性質連結數目，藉由這兩個群聚比例的變化來探究網路形成過程中的群聚分離狀況，因此我們利用了一個較為間接的方式來瞭解所要討論的議題。 本研究透過演算模擬得到幾個結論：（1）平均群聚比例會隨著突現發生機率趨於0而不斷提升，代表網路隨著突現發生機率的下滑，族群分離的程度會隨之趨於明顯。（2）當突現發生機率很低時，平均群聚比例會隨著玩家每期能夠建立的最大連結數目增加而下滑，網路內的族群分離現象逐漸不明顯。但是當突現發生機率很高時，卻會維持在平均的水準。（3）當玩家的人數增多時，突現的發生對群聚比例會有提升的效果存在，不管最大連結數目為何都會有如此的結果。（4）如果市場上處於一個貧富人數不均的環境下，則隨著網路的演化最後所計算出來的族群現象就會越明顯，富人自然會和富人相連，而窮人自然會和窮人相連，群聚現象是自然演變出來的。（5）若搜尋時採隨機模式，則平均群聚比例在突現發生機率很高時會較一般模式差，而在突現發生機率很低時則與一般模式差異不大。（6）若突現僅限於連結的斷裂，且窮人的動作選擇僅限於投資策略二，則平均群聚比例則會趨近於一。

No description available.

Cette thèse s'articule autour de la détection de similarités globales et locales dans les structures protéiques. Premièrement les structures sont comparées, mesurées en termes de distance métrique dans un but de classification supervisée. Cette classification des domaines structuraux au sein de classifications hiérarchiques se fait par le biais de dominances et d'apprentissages permettant d'assigner plus rapidement et de manière exacte de nouveaux domaines. Deuxièmement, nous proposons une méthode de manière de traduire un problème biologique dans les formalisme des graphes. Puis nous résolvons ce problème via le parcours de ces graphes pour extraire les différentes sous-structures similaires. Cette méthode repose sur des notions de compatibilités entre éléments des structures ainsi que des critères de distances entre éléments. Ces techniques sont capables de détecter des événements tels que des permutations circulaires, des charnières (flexibilité) et des répétitions de motifs structuraux. Finalement nous proposons une nouvelle approche dans l'analyse fine de structures afin de faciliter la recherche de régions divergentes entre structures 3D fortement similaires. / This thesis focusses on local and global similarities and divergences inside protein structures. First, structures are scored, with criteria of similarity and distance in order to provide a supervised classification. This structural domain classification inside existing hierarchical databases is possible by using dominances and learning. These methods allow to assign new domains with accuracy and exactly. Second we focusses on local similarities and proposed a method of protein comparison modelisation inside graphs. Graph traversal allows to find protein similar substructures. This method is based on compatibility between elements and criterion of distances. We can use it and detect events such that circular permutations, hinges and structural motif repeats. Finally we propose a new approach of accurate protein structure analysis that focused on divergences between similar structures.

No description available.

Cette thèse réunit en trois articles mon intérêt éclectique pour la théorie des graphes. Le premier problème étudié est la conjecture de Erdos-Faber-Lovász: La réunion de k graphes complets distincts, ayant chacun k sommets, qui ont deux-à-deux au plus un sommet en commun peut être proprement coloriée en k couleurs. Cette conjecture se caractérise par le peu de résultats publiés. Nous prouvons qu’une nouvelle classe de graphes, construite de manière inductive, satisfait la conjecture. Le résultat consistera à présenter une classe qui ne présente pas les limitations courantes d’uniformité ou de régularité. Le deuxième problème considère une conjecture concernant la couverture des arêtes d’un graphe: Si G est un graphe simple avec alpha(G) = 2, alors le nombre minimum de cliques nécessaires pour couvrir l’ensemble des arêtes de G (noté ecc(G)) est au plus n, le nombre de sommets de G. La meilleure borne connue satisfaite par ecc(G) pour tous les graphes avec nombre d’indépendance de deux est le minimum de n + delta(G) et 2n − omega(racine (n log n)), où delta(G) est le plus petit nombre de voisins d’un sommet de G. Notre objectif a été d’obtenir la borne ecc(G) <= 3/2 n pour une classe de graphes la plus large possible. Un autre résultat associé à ce problème apporte la preuve de la conjecture pour une classe particulière de graphes: Soit G un graphe simple avec alpha(G) = 2. Si G a une arête dominante uv telle que G \ {u,v} est de diamètre 3, alors ecc(G) <= n. Le troisième problème étudie le jeu de policier et voleur sur un graphe. Presque toutes les études concernent les graphes statiques, et nous souhaitons explorer ce jeu sur les graphes dynamiques, dont les ensembles d’arêtes changent au cours du temps. Nowakowski et Winkler caractérisent les graphes statiques pour lesquels un unique policier peut toujours attraper le voleur, appellés cop-win, à l’aide d’une relation <= définie sur les sommets de ce graphe: Un graphe G est cop-win si et seulement si la relation <= définie sur ses sommets est triviale. Nous adaptons ce théorème aux graphes dynamiques. Notre démarche nous mène à une relation nous permettant de présenter une caractérisation des graphes dynamiques cop-win. Nous donnons ensuite des résultats plus spécifiques aux graphes périodiques. Nous indiquons aussi comment généraliser nos résultats pour k policiers et l voleurs en réduisant ce cas à celui d’un policier unique et un voleur unique. Un algorithme pour décider si, sur un graphe périodique donné, k policiers peuvent capturer l voleurs découle de notre caractérisation. / This thesis represents in three articles my eclectic interest for graph theory. The first problem is the conjecture of Erdos-Faber-Lovász: If k complete graphs, each having k vertices, have the property that every pair of distinct complete graphs have at most one vertex in common, then the vertices of the resulting graph can be properly coloured by using k colours. This conjecture is notable in that only a handful of classes of EFL graphs are proved to satisfy the conjecture. We prove that the Erdos-Faber-Lovász Conjecture holds for a new class of graphs, and we do so by an inductive argument. Furthermore, graphs in this class have no restrictions on the number of complete graphs to which a vertex belongs or on the number of vertices of a certain type that a complete graph must contain. The second problem addresses a conjecture concerning the covering of the edges of a graph: The minimal number of cliques necessary to cover all the edges of a simple graph G is denoted by ecc(G). If alpha(G) = 2, then ecc(G) <= n. The best known bound satisfied by ecc(G) for all the graphs with independence number two is the minimum of n + delta(G) and 2n − omega(square root (n log n)), where delta(G) is the smallest number of neighbours of a vertex in G. In this type of graph, all the vertices at distance two from a given vertex form a clique. Our approach is to extend all of these n cliques in order to cover the maximum possible number of edges. Unfortunately, there are graphs for which it’s impossible to cover all the edges with this method. However, we are able to use this approach to prove a bound of ecc(G) <= 3/2n for some newly studied infinite families of graphs. The third problem addresses the game of Cops and Robbers on a graph. Almost all the articles concern static graphs, and we would like to explore this game on dynamic graphs, the edge sets of which change as a function of time. Nowakowski and Winkler characterize static graphs for which a cop can always catch the robber, called cop-win graphs, by means of a relation <= defined on the vertices of such graphs: A graph G is cop-win if and only if the relation <= defined on its vertices is trivial. We adapt this theorem to dynamic graphs. Our approach leads to a relation, that allows us to present a characterization of cop-win dynamic graphs. We will then give more specific results for periodic graphs, and we will also indicate how to generalize our results to k cops and l robbers by reducing this case to one with a single cop and a single robber. An algorithm to decide whether on a given periodic graph k cops can catch l robbers follows from our characterization.