CoDE Publications CoDE Publications
IRIDIA Publications IRIDIA Publications
SMG Publications
WIT Publications
WIT Publications
SMG Publications
Home People Research Activities Publications Teaching Resources
By Class By Topic By Year Technical Reports
By Class By Topic By Year Technical Reports
login
G. Verhaegen. Graph Analysis Applied to US Patents. Mémoire d'Ingénieur Civil Informaticien, Université libre de Bruxelles, Brussels, Belgium, 2010.

Abstract

Le présent travail consiste en l'étude du graphe formé par les brevets déposés à l'office américain des brevets. Les graphes se citant entre eux, il existe un graphe naturel sous-jacent à l'ensemble des brevets. Nous commençons par expliquer le contexte dans lequel se situe notre travail en présentant brièvement le fonctionnement des brevets. Nous introduisons ensuite les notions théoriques indispensables et le vocabulaire propre à l'étude des graphes, tant du point de vue mathématique que du point de vue informatique. L'essentiel du travail consiste en l'exploration de différents algorithmes. Nous commençons par présenter deux algorithmes d'évaluation de l'importance d'un noeud, PageRank, l'algorithme de Google, et HITS. Ces algorithmes ont pour but d'établir un classement entre les noeuds selon différents critères. Les résultats sont brièvement présentés. Nous souhaitons ensuite nous attaquer au problème du clustering. Etant données la complexité de ce genre de calcul et la taille de notre graphe, nous commençons par essayer de réduire cette dernière en découpant le graphe, d'abord en cherchant des sous-graphes disjoints, ensuite en essayant de séparer le graphe en coupant le moins de liens possible. Il apparait que le graphe des brevets est plus connecté que nous ne l'espérions, et nous n'arrivons pas à significativement réduire sa taille. Nous passons finalement au problème du clustering lui-même, en présentant trois approches différentes en détail : un découpage progressif du graphe en coupant des liens, dans le but d'isoler des morceaux de mieux en mieux connectés; une méthode de groupement inspirée de la conception de circuit électronique, et un algorithme plus classique appelé k-means. Nous n'avons, par manque de temps, pas réussi à faire tourner ces trois algorithmes; nous avons toutefois pu écarter le second, et nous pensons présenter tous les éléments nécessaires pour la réalisation du premier et du troisième. Nous concluons ce travail en énonçant un certain nombre de pistes qu'il serait, selon nous, intéressant d'explorer plus avant.


Updated: 2017-03-27