Partitionnement de donnéesvignette|upright=1.2|Exemple de clustering hiérarchique. Le partitionnement de données (ou data clustering en anglais) est une méthode en analyse des données. Elle vise à diviser un ensemble de données en différents « paquets » homogènes, en ce sens que les données de chaque sous-ensemble partagent des caractéristiques communes, qui correspondent le plus souvent à des critères de proximité (similarité informatique) que l'on définit en introduisant des mesures et classes de distance entre objets.
Line graphEn théorie des graphes, le line graph L(G) d'un graphe non orienté G, est un graphe qui représente la relation d'adjacence entre les arêtes de G. Le nom line graph vient d'un article de Harary et Norman publié en 1960. La même construction avait cependant déjà été utilisée par Whitney en 1932 et Krausz en 1943. Il est également appelé graphe adjoint. Un des premiers et des plus importants théorèmes sur les line graphs est énoncé par Hassler Whitney en 1932, qui prouve qu'en dehors d'un unique cas exceptionnel, la structure de G peut être entièrement retrouvée à partir de L(G) dans le cas des graphes connexes.
Graphe cubiqueEn théorie des graphes, une branche des mathématiques, un graphe cubique est un graphe régulier de degré 3. En d'autres termes, c'est un graphe dans lequel il y a exactement trois arêtes incidentes à chaque sommet. Le graphe complet K4 est le plus petit graphe cubique. Le graphe biparti complet K3,3 est le plus petit graphe cubique non-planaire. Le graphe de Petersen est le plus petit graphe cubique de maille 5. Le graphe de Heawood est le plus petit graphe cubique de maille 6.
Graphe régulierEn théorie des graphes, un graphe régulier est un graphe où tous les sommets ont le même nombre de voisins, c'est-à-dire le même degré ou valence. Un graphe régulier dont les sommets sont de degré est appelé un graphe -régulier ou graphe régulier de degré . Un graphe 0-régulier est un ensemble de sommets déconnectés; un graphe 1-régulier a un nombre pair de sommets et est un ensemble d'arêtes déconnectées ou couplage; enfin, un graphe 2-régulier est un ensemble de cycles déconnectés.
Théorie spectrale des graphesEn mathématiques, la théorie spectrale des graphes s'intéresse aux rapports entre les spectres des différentes matrices que l'on peut associer à un graphe et ses propriétés. C'est une branche de la théorie algébrique des graphes. On s'intéresse en général à la matrice d'adjacence et à la matrice laplacienne normalisée. Soit un graphe , où désigne l'ensemble des sommets et l'ensemble des arêtes. Le graphe possède sommets, notés et arêtes, notées .
Graphe aléatoirevignette|Graphe orienté aléatoire avec 20 nœuds et une probabilité de présence d'arête égale à 0,1. En mathématiques, un graphe aléatoire est un graphe généré par un processus aléatoire. Le premier modèle de graphes aléatoires a été popularisé par Paul Erdős et Alfréd Rényi dans une série d'articles publiés entre 1959 et 1968. Il y a deux modèles d'Erdős et Rényi, formellement différents, mais étroitement liés : le graphe aléatoire binomial et le graphe aléatoire uniforme.
Classe de complexitéEn informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.
Graphe fortement régulierEn théorie des graphes, qui est un domaine des mathématiques, un graphe fortement régulier est un type de graphe régulier. Soit G = (V,E) un graphe régulier ayant v sommets et degré k. On dit que G est fortement régulier s'il existe deux entiers λ et μ tels que Toute paire de sommets adjacents a exactement λ voisins communs. Toute paire de sommets non-adjacents a exactement μ voisins communs. Un graphe avec ces propriétés est appelé un graphe fortement régulier de type (v,k,λ,μ).
Eigenvector centralityIn graph theory, eigenvector centrality (also called eigencentrality or prestige score) is a measure of the influence of a node in a network. Relative scores are assigned to all nodes in the network based on the concept that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes. A high eigenvector score means that a node is connected to many nodes who themselves have high scores. Google's PageRank and the Katz centrality are variants of the eigenvector centrality.
Computational complexityIn computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.
DBSCANDBSCAN (density-based spatial clustering of applications with noise) est un algorithme de partitionnement de données proposé en 1996 par Martin Ester, Hans-Peter Kriegel, Jörg Sander et Xiaowei Xu. Il s'agit d'un algorithme fondé sur la densité dans la mesure qui s’appuie sur la densité estimée des clusters pour effectuer le partitionnement. thumb|400px|Les points A sont les points déjà dans le cluster. Les points B et C sont atteignables depuis A et appartiennent donc au même cluster.
Valeur propre, vecteur propre et espace propreEn mathématiques, et plus particulièrement en algèbre linéaire, le concept de vecteur propre est une notion algébrique s'appliquant à une application linéaire d'un espace dans lui-même. Il correspond à l'étude des axes privilégiés, selon lesquels l'application se comporte comme une dilatation, multipliant les vecteurs par une même constante. Ce rapport de dilatation est appelé valeur propre, les vecteurs auxquels il s'applique s'appellent vecteurs propres, réunis en un espace propre.
K-moyennesLe partitionnement en k-moyennes (ou k-means en anglais) est une méthode de partitionnement de données et un problème d'optimisation combinatoire. Étant donnés des points et un entier k, le problème est de diviser les points en k groupes, souvent appelés clusters, de façon à minimiser une certaine fonction. On considère la distance d'un point à la moyenne des points de son cluster ; la fonction à minimiser est la somme des carrés de ces distances.
Tracé de graphesEn théorie des graphes, le tracé de graphes consiste à représenter des graphes dans le plan. Le tracé de graphes est utile à des applications telles que la conception de circuits VLSI, l'analyse de réseaux sociaux, la cartographie, et la bio-informatique. Les graphes sont généralement représentés en utilisant des points, disques ou boites pour représenter les sommets, et des courbes ou des segments pour représenter les arêtes. Pour les graphes orientés, on utilise habituellement ses flèches en bout d'arête pour représenter l'orientation.
Graphe de CayleyEn mathématiques, un graphe de Cayley (du nom d'Arthur Cayley) est un graphe qui encode la structure d'un groupe. C'est un outil important pour l'étude de la combinatoire et de la géométrie des groupes. Étant donné un groupe et une partie génératrice de ce groupe, le graphe de Cayley Cay(G,S) est construit comme suit : À chaque élément de , on associe un sommet . À chaque élément de , on associe une couleur . Pour tout et , on trace une arête orientée de couleur du sommet vers le sommet .
Centralitéthumb|right|300px|Exemples de A) Centralité d'intermédiarité, B) Centralité de proximité, C) Centralité de vecteur propre, D) Centralité de degré, E) Centralité harmonique et F) Centralité de Katz sur le même graphe. En théorie des graphes et en théorie des réseaux, les indicateurs de centralité sont des mesures censées capturer la notion d'importance dans un graphe, en identifiant les sommets les plus significatifs.
Coloration de graphethumb|Une coloration du graphe de Petersen avec 3 couleurs. En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune.
Determining the number of clusters in a data setDetermining the number of clusters in a data set, a quantity often labelled k as in the k-means algorithm, is a frequent problem in data clustering, and is a distinct issue from the process of actually solving the clustering problem. For a certain class of clustering algorithms (in particular k-means, k-medoids and expectation–maximization algorithm), there is a parameter commonly referred to as k that specifies the number of clusters to detect.
ComplexitéLa complexité caractérise le comportement d'un système dont les composants interagissent localement et de façon non linéaire, ce qui se traduit par un comportement difficilement prédictible. La complexité peut donc caractériser un système "composé d'un grand nombre d'éléments interagissant sans coordination centrale, sans plan établi par un architecte, et menant spontanément à l'émergence de structures complexes" (Alain Barrat, directeur de recherche au Centre de physique théorique de Marseille); mais aussi caractériser des systèmes composés de peu d'éléments (voir le chaos déterministe).
Théorie de la complexité (informatique théorique)vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée ...) requis par un algorithme pour résoudre un problème algorithmique.
