Notebook C# / .NET Interactive sur les Knowledge Graphs (KG) dans dotNetRDF 3.4.1 : construction, interrogation SPARQL, parcours de graphe, centralite, qualite.
Plan de lecture : la ligne principale suit l’arc construire, interroger, parcourir et visualiser, exemples, verdict. Les approfondissements sont en annexes lettrées : A le KG en contexte (définition détaillée, comparaison au relationnel, usages industriels), B les patterns SPARQL et leur sémantique d’évaluation, C les implémentations C# des parcours (adjacence, BFS, complexité, algorithmes voisins), D la qualité d’un KG, E la centralité. Rien n’a été supprimé : chaque section déplacée garde son contenu en annexe.
Objectifs de la seance : 1. Definir un KG : graphe RDF avec une ontologie (classes, proprietes) et des instances. 2. Construire un KG a partir de donnees structurees (CSV/table) en transformant chaque ligne en plusieurs triplets. 3. Interroger le KG avec SPARQL (projections, filtres, agregats). 4. Parcourir le KG par adjacence (BFS) et visualiser en ASCII. 5. Valider la qualite du KG : classes orphelines, completude, distribution des valeurs (annexe D). 6. Calculer des metriques de centralite (degre) pour identifier les acteurs cles (annexe E).
Pourquoi ce notebook dans la serie SemanticWeb : - C’est le notebook qui integre tous les precedents (SW-3 lecture/ecriture, SW-4 SPARQL, SW-5 Linked Data). - Il introduit les concepts de theorie des graphes appliques aux graphes RDF. - Cas Prong B applicable (sota-not-workaround) : KG reel avec filmographie de 8 films, pas une simulation.
Substance pedagogique : - Knowledge Graph : representation structuree des connaissances sous forme de graphe (entites + relations). - Ontologie : schema formel qui definit les classes et proprietes d’un domaine. - Triple store : moteur de stockage optimise pour les graphes RDF (ici, en memoire via IGraph).
Prerequis : SW-3 Graph Operations, SW-4 SPARQL. Pas de requetes distantes ici (KG local).
0. Installation de dotNetRDF
L’installation utilise dotNetRDF 3.4.1 (version legerement plus recente que pour SW-3 a SW-5). Cette version inclut des corrections pour TurtleFormatter et IGraph.GetTriplesWithX.
Sortie observee de code[0] (verbatim) : dotNetRDF charge.. La cellule execute le #r "nuget:" et confirme que la bibliotheque est chargee.
Note de version : - 3.2.1 : utilisee pour SW-3, SW-4, SW-5 (stable). - 3.4.1 : utilisee pour ce notebook (corrige un bug de TurtleFormatter sur les namespaces complexes).
Compatibilite : les APIs de base (Graph, Triple, INode, SPARQL) sont stables depuis 3.0. Pas de breaking changes entre 3.2.1 et 3.4.1 pour les concepts couverts.
``` {.c# .cell-code} #r “nuget: dotNetRDF, 3.4.1” using VDS.RDF; using VDS.RDF.Parsing; using VDS.RDF.Query; using VDS.RDF.Writing.Formatting; using System; using System.Collections.Generic; using System.Linq;
// Helper statique : cree un noeud URI depuis un QName (persiste entre cellules) static IUriNode U(IGraph g, string qname) => g.CreateUriNode(qname); static ILiteralNode LitInt(IGraph g, int v) => g.CreateLiteralNode(v.ToString(), new Uri(XSD + “integer”));
Console.WriteLine(“dotNetRDF charge.”);
::: {.cell-output .cell-output-display}
```{=html}
<div>
<div id='dotnet-interactive-this-cell-167320.Microsoft.DotNet.Interactive.Http.HttpPort' style='display: none'>
The below script needs to be able to find the current output cell; this is an easy method to get it.
</div>
<script type='text/javascript'>
function timeout(ms, promise) {
return new Promise(function (resolve, reject) {
setTimeout(function () {
reject(new Error('timeout'))
}, ms)
promise.then(resolve, reject)
})
}
if (!rootUrl.endsWith('/')) {
rootUrl = `${rootUrl}/`;
}
try {
let response = await timeout(1000, fetch(`${rootUrl}discovery`, {
method: 'POST',
cache: 'no-cache',
mode: 'cors',
timeout: 1000,
headers: {
'Content-Type': 'text/plain'
},
}));
if (response.status == 200) {
return rootUrl;
}
}
catch (e) { }
}
}
}
.then((root) => {
// use probing to find host url and api resources
// load interactive helpers and language services
let dotnetInteractiveRequire = require.config({
context: '167320.Microsoft.DotNet.Interactive.Http.HttpPort',
paths:
{
'dotnet-interactive': `${root}resources`
}
}) || require;
window.dotnetInteractiveRequire = dotnetInteractiveRequire;
window.configureRequireFromExtension = function(extensionName, extensionCacheBuster) {
let paths = {};
paths[extensionName] = `${root}extensions/${extensionName}/resources/`;
let internalRequire = require.config({
context: extensionCacheBuster,
paths: paths,
urlArgs: `cacheBuster=${extensionCacheBuster}`
}) || require;
return internalRequire
};
dotnetInteractiveRequire([
'dotnet-interactive/dotnet-interactive'
],
function (dotnet) {
dotnet.init(window);
},
function (error) {
console.log(error);
}
);
})
.catch(error => {console.log(error);});
}
// ensure `require` is available globally
if ((typeof(require) !== typeof(Function)) || (typeof(require.config) !== typeof(Function))) {
let require_script = document.createElement('script');
require_script.setAttribute('src', 'https://cdnjs.cloudflare.com/ajax/libs/require.js/2.3.6/require.min.js');
require_script.setAttribute('type', 'text/javascript');
require_script.onload = function() {
};
document.getElementsByTagName('head')[0].appendChild(require_script);
}
else {
}
</script>
</div>
Installed Packages
dotNetRDF, 3.4.1
dotNetRDF charge.
:::
1. Qu’est-ce qu’un Knowledge Graph ?
Un Knowledge Graph (KG) est un graphe RDF qui contient a la fois : - Une ontologie (T-Box) : classes, proprietes, hierarchies. - Des instances (A-Box) : entites concretes et leurs relations.
3 proprietes essentielles : 1. Schema explicite : l’ontologie definit la structure (vs graphe RDF sans schema). 2. Donnees liees : les triplets sont connectes (vs table avec cles etrangeres). 3. Inference : on peut deriver de nouveaux triplets a partir de l’ontologie (subClassOf, subPropertyOf, etc.).
Exemple canonique : Google Knowledge Graph (2012, 3 milliards de faits), Wikidata (100+ millions d’entites), DBpedia (15+ milliards de triplets).
La definition complete – pourquoi les KG comptent, la comparaison avec une base relationnelle, les cas d’usage industriels – est en annexe A.
2. Construire un Knowledge Graph a partir de donnees structurees
La construction d’un KG suit 3 etapes : 1. Modeliser le domaine : definir les classes (Film, Realisateur, Genre) et proprietes (directedBy, releasedIn, hasGenre). 2. Convertir les donnees : chaque ligne d’une table devient plusieurs triplets (sujet-predicat-objet). 3. Serialiser : sauvegarder en Turtle, RDF/XML, JSON-LD pour la persistance ou le transfert.
Sortie observee de code[1] (verbatim) : Vocabulaire cinema defini.. La cellule cree le graphe et declare les classes/proprietes via g.CreateUriNode("ex:Film").
Note de portee : la definition de l’ontologie est faite dans le graphe lui-meme (les classes sont des URIs comme les instances). C’est l’auto-description du Web semantique. L’extrait C# correspondant est en annexe A.
``` {.c# .cell-code} var g = new Graph(); g.NamespaceMap.AddNamespace(“ex”, new Uri(“http://example.org/cinema#”)); g.NamespaceMap.AddNamespace(“rdf”, new Uri(“http://www.w3.org/1999/02/22-rdf-syntax-ns#”)); g.NamespaceMap.AddNamespace(“rdfs”, new Uri(“http://www.w3.org/2000/01/rdf-schema#”));
**Transformation** : chaque ligne engendre plusieurs triplets :
- `ex:Inception a ex:Film .` (type)
- `ex:Inception ex:title "Inception" .` (titre)
- `ex:Inception ex:directedBy ex:Nolan .` (realisateur)
- `ex:Inception ex:releasedIn 2010 .` (annee)
- `ex:Inception ex:hasGenre ex:SciFi .` (genre 1)
- `ex:Inception ex:hasGenre ex:Action .` (genre 2)
**Sortie observee de code[2]** (verbatim) : `KG cinema : 54 triplets assertes.`. Le KG contient 54 triplets pour 8 films + 3 classes + 3 proprietes.
**Ratio triplets/ligne** : pour 8 films avec 2-3 genres chacun, on obtient environ 8 × (1 type + 1 titre + 1 real + 1 annee + 2-3 genres) = 50-60 triplets. Le ratio est ~7 triplets par ligne.
**Pourquoi c'est superieur a une table** :
- **Donnees heterogenes** : on peut avoir des genres multiples (1 film a 2-3 genres).
- **Inference** : on peut deriver de nouveaux triplets (par exemple, "Inception est un film de Nolan").
- **Evolutivite** : on peut ajouter de nouvelles proprietes sans modifier le schema.
::: {#8a80d072 .cell quarto-private-1='{"key":"execution","value":{"iopub.execute_input":"2026-10-01T19:05:31.562520Z","iopub.status.busy":"2026-10-01T19:05:31.562268Z","iopub.status.idle":"2026-10-01T19:05:31.722753Z","shell.execute_reply":"2026-10-01T19:05:31.722478Z"}}' execution_count=3}
``` {.c# .cell-code}
// Donnees source : (titre, realisateur, annee, genres) -- equivalent d'un DataFrame Python
var films = new[] {
(Title:"Inception", Director:"Nolan", Year:2010, Genres:new[]{"SciFi","Action"}),
(Title:"Interstellar", Director:"Nolan", Year:2014, Genres:new[]{"SciFi","Drama"}),
(Title:"Dunkirk", Director:"Nolan", Year:2017, Genres:new[]{"Drama","War"}),
(Title:"PulpFiction", Director:"Tarantino", Year:1994, Genres:new[]{"Crime","Drama"}),
(Title:"Django", Director:"Tarantino", Year:2012, Genres:new[]{"Western","Drama"}),
(Title:"Parasite", Director:"Bong", Year:2019, Genres:new[]{"Drama","Thriller"}),
(Title:"MemoriesOfMurder",Director:"Bong", Year:2003, Genres:new[]{"Crime","Drama"}),
(Title:"Avatar", Director:"Cameron", Year:2009, Genres:new[]{"SciFi","Action"}),
};
foreach (var f in films) {
var filmNode = U(g, "ex:"+f.Title);
var dirNode = U(g, "ex:"+f.Director);
g.Assert(filmNode, RDF_TYPE, U(g, "ex:Film"));
g.Assert(dirNode, RDF_TYPE, U(g, "ex:Director"));
g.Assert(filmNode, DIRECTED_BY, dirNode);
g.Assert(filmNode, RELEASED, LitInt(g, f.Year));
foreach (var gn in f.Genres) {
var gNode = U(g, "ex:"+gn);
g.Assert(gNode, RDF_TYPE, U(g, "ex:Genre"));
g.Assert(filmNode, HAS_GENRE, gNode);
}
}
Console.WriteLine($"KG cinema : {g.Triples.Count} triplets assertes.");
KG cinema : 54 triplets assertes.
Interprétation : chaque ligne de la table source engendre plusieurs triplets (type, directedBy, releasedIn, hasGenre × nombre de genres). Le KG est maintenant un graphe RDF interrogable. Le compte exact de triplets reflète la taille du domaine — on le retrouve dans le twin Python.
2.3 Serialisation Turtle
Turtle est le format de serialisation recommande pour les KG (compact, lisible). La cellule utilise TurtleFormatter (une variante de TurtleWriter) pour formatter le graphe.
Sortie observee de code[3] (verbatim) :
ex:Director a ex:Class .
ex:Film a ex:Class .
ex:Genre a ex:Class .
ex:Inception a ex:Film .
La sortie montre les premieres lignes du KG serialise en Turtle. Les classes (ex:Director, ex:Film, ex:Genre) sont declarees avec a (= rdf:type).
Implementation C# (TurtleFormatter) :
var fmt =newTurtleFormatter(g);string turtle = fmt.ToString();Console.WriteLine(turtle);
Pourquoi Turtle : - Prefixes : @prefix ex: <http://example.org/> – raccourcit les URI. - Semin-colons : permettent de grouper plusieurs proprietes pour un meme sujet. - Lisibilite : le format est concu pour etre lu par des humains.
Autres formats de serialisation : - RDF/XML : verbose, compatible avec les outils XML. - JSON-LD : compatible avec les APIs web. - N-Triples : canonique (un triplet par ligne, pas de prefixes). - Turtle Star : extension pour les annotations (cf. SW-10).
{.c# .cell-code} var fmt = new TurtleFormatter(g); foreach (var t in g.Triples.Take(6)) Console.WriteLine(fmt.Format(t));
ex:Director a ex:Class .
ex:Film a ex:Class .
ex:Genre a ex:Class .
ex:Inception a ex:Film .
ex:Nolan a ex:Director .
ex:Inception ex:directedBy ex:Nolan .
3. Interrogation SPARQL
SPARQL est le langage de requete standard pour les KG. Le notebook utilise les memes APIs que SW-4 (SparqlQueryParser, LeviathanQueryProcessor), mais appliquees a un KG local. Deux requetes d’abord : la filmographie d’un realisateur (3.1), puis un agregat COUNT/GROUP BY (3.2). Les patterns complets, les agregats disponibles et l’ordre d’evaluation du moteur sont en annexe B.
3.1 Films d’un realisateur donne
Cette requete est un pattern classique : “quels sont les films d’un realisateur X ?”.
Sortie observee de code[4] (verbatim) : 3 films de Nolan (Dunkirk, Interstellar, Inception) tries par annee decroissante.
Pourquoi ORDER BY DESC(?year) : - L’utilisateur veut generalement les films recents d’abord. - DESC = decroissant (plus recent en premier).
Les cas d’usage (site web, recommandation, analyse de carriere) et l’analyse de performance sont en annexe B.
{.c# .cell-code} string q1 = @" PREFIX ex: <http://example.org/cinema#> SELECT ?title ?year WHERE { ?title ex:directedBy ex:Nolan ; ex:releasedIn ?year . } ORDER BY DESC(?year)"; var results = (SparqlResultSet)g.ExecuteQuery(q1); Console.WriteLine($"Films de Nolan (ordre annee desc) : {results.Count}"); foreach (SparqlResult r in results) Console.WriteLine($" {r["title"].ToString().Replace("http://example.org/cinema#","")} ({((ILiteralNode)r["year"]).Value})");
Films de Nolan (ordre annee desc) : 3
Dunkirk (2017)
Interstellar (2014)
Inception (2010)
3.2 Agregats : nombre de films par genre
Cette requete utilise COUNT et GROUP BY pour compter les films par genre.
Sortie observee de code[5] (verbatim) :
Nombre de films par genre :
Drama : 6
SciFi : 3
Action : 2
Decomposition : - SELECT ?genre (COUNT(?film) AS ?count) : on compte les films par genre. - GROUP BY ?genre : on groupe par genre. - ORDER BY DESC(?count) : on trie par popularite.
Les agregats disponibles en SPARQL et l’ordre d’evaluation (WHERE, GROUP BY, agregats, HAVING, ORDER BY, SELECT) sont en annexe B.
{.c# .cell-code} string q2 = @" PREFIX ex: <http://example.org/cinema#> SELECT ?genre (COUNT(?film) AS ?n) WHERE { ?film ex:hasGenre ?genre . } GROUP BY ?genre ORDER BY DESC(?n)"; var res2 = (SparqlResultSet)g.ExecuteQuery(q2); Console.WriteLine("Nombre de films par genre :"); foreach (SparqlResult r in res2) Console.WriteLine($" {r["genre"].ToString().Replace("http://example.org/cinema#","")} : {((ILiteralNode)r["n"]).Value}");
Nombre de films par genre :
Drama : 6
SciFi : 3
Action : 2
Crime : 2
War : 1
Western : 1
Thriller : 1
Interprétation : SPARQL permet de projeter, filtrer, agréger — exactement comme SQL, mais sur un graphe RDF. Les comptes (Drama, SciFi, Crime…) concordent avec la table source : Drama apparaît 6 fois (Inception non, Interstellar oui, Dunkirk oui, PulpFiction oui, Django oui, Parasite oui, MemoriesOfMurder oui → vérifiez à la main). On retrouve ces nombres dans le twin Python.
4. Adjacence et parcours de graphe
Au-dela de SPARQL, on peut parcourir le KG avec des algorithmes de theorie des graphes (BFS, DFS, Dijkstra). C’est utile pour : - Exploration locale : tous les voisins d’une entite. - Recherche de chemins : liens entre deux entites. - Visualisation : sous-graphe autour d’une entite.
Lecture de l’adjacence et BFS
La cellule construit la liste d’adjacence, puis explore le graphe depuis Inception avec une profondeur maximale de 2.
Sortie observee de code[6] (verbatim) :
Adjacence : 22 noeuds avec au moins 1 arete sortante.
BFS depuis Inception (profondeur<=2) : 9 noeuds atteints.
Liste d’adjacence : pour chaque noeud, on stocke ses voisins sortants. C’est une structure de donnees classique pour les graphes.
BFS (Breadth-First Search) : on explore niveau par niveau. - Profondeur 1 : voisins directs. - Profondeur 2 : voisins des voisins. - Profondeur N : N-1 sauts.
Les implémentations C# complètes (adjacence et BFS), l’analyse de complexité et les algorithmes voisins (PageRank, A*) sont en annexe C.
``` {.c# .cell-code} // Construction de la liste d’adjacence : noeud -> voisins sortants var adj = new Dictionary<INode, List>(); foreach (var t in g.Triples) { if (!adj.ContainsKey(t.Subject)) adj[t.Subject] = new List(); adj[t.Subject].Add(t.Object); } Console.WriteLine($“Adjacence : {adj.Count} noeuds avec au moins 1 arete sortante.”);
// BFS (static, params explicites – evite la capture de variables top-level) static List Bfs(Dictionary<INode,List> adj, INode start, int maxDepth) { var visited = new HashSet{ start }; var frontier = new Queue<(INode n, int d)>(); frontier.Enqueue((start, 0)); var order = new List{ start }; while (frontier.Count > 0) { var (cur, d) = frontier.Dequeue(); if (d >= maxDepth) continue; if (!adj.ContainsKey(cur)) continue; foreach (var nb in adj[cur]) if (visited.Add(nb)) { order.Add(nb); frontier.Enqueue((nb, d+1)); } } return order; } var reach = Bfs(adj, U(g, “ex:Inception”), 2); Console.WriteLine($“BFS depuis Inception (profondeur<=2) : {reach.Count} noeuds atteints.”);
::: {.cell-output .cell-output-stdout}
Adjacence : 22 noeuds avec au moins 1 arete sortante. BFS depuis Inception (profondeur<=2) : 9 noeuds atteints.
:::
:::
**Interprétation** : `Inception` → `Nolan` (directedBy), `2010` (releasedIn), `SciFi`/`Action` (hasGenre), puis depuis `Nolan` → autres films Nolan, etc. Le BFS explore le voisinage en éventail, exactement comme `networkx.single_source_shortest_path_length`. La profondeur 2 atteint le co-voisinage direct.
### 4.1 Visualisation ASCII du sous-graphe
Pour visualiser un sous-graphe, on peut utiliser une representation ASCII. C'est utile pour les notebooks (pas de graphiques externes).
**Sortie observee de code[7]** (verbatim) :
Sous-graphe autour de Inception : Inception –a–> Film Inception –directedBy–> Nolan Inception –releasedIn–> 2010
L'extrait C# de la visualisation est en **annexe C**.
**Pourquoi la visualisation ASCII** :
- **Portable** : pas de dependance graphique.
- **Lisible** : on voit les relations cles.
- **Reproductible** : meme sortie sur toutes les plateformes.
**Limites** :
- **Petits graphes** : ne scale pas au-dela de ~50 noeuds.
- **Pas de layout** : pas d'algorithme de placement (force-directed, etc.).
- **Pas d'interaction** : impossible de zoomer ou filtrer.
**Pour de vrais graphes** : utiliser des outils comme Graphviz (`dot`), Cytoscape, ou D3.js.
::: {#8fa4126e .cell quarto-private-1='{"key":"execution","value":{"iopub.execute_input":"2026-10-01T19:05:32.251846Z","iopub.status.busy":"2026-10-01T19:05:32.251564Z","iopub.status.idle":"2026-10-01T19:05:32.427427Z","shell.execute_reply":"2026-10-01T19:05:32.427046Z"}}' execution_count=8}
``` {.c# .cell-code}
static string Short(INode n) {
var s = n.ToString();
return s.Replace("http://example.org/cinema#","")
.Replace("http://www.w3.org/1999/02/22-rdf-syntax-ns#","rdf:")
.Replace("http://www.w3.org/2000/01/rdf-schema#","rdfs:");
}
static string Pred(IUriNode p, IUriNode DIRECTED_BY, IUriNode HAS_GENRE, IUriNode RELEASED, IUriNode RDF_TYPE) {
if (p.Equals(DIRECTED_BY)) return "--directedBy-->";
if (p.Equals(HAS_GENRE)) return "--hasGenre-->";
if (p.Equals(RELEASED)) return "--releasedIn-->";
if (p.Equals(RDF_TYPE)) return "--a-->";
return "--"+Short(p)+"-->";
}
var center = U(g, "ex:Inception");
Console.WriteLine($"Sous-graphe autour de {Short(center)} :");
foreach (var t in g.Triples.Where(t => t.Subject.Equals(center) || t.Object.Equals(center))) {
var obj = t.Object is ILiteralNode lit ? lit.Value : Short(t.Object);
Console.WriteLine($" {Short(t.Subject)} {Pred((IUriNode)t.Predicate, DIRECTED_BY, HAS_GENRE, RELEASED, RDF_TYPE)} {obj}");
}
Sous-graphe autour de Inception :
Inception --a--> Film
Inception --directedBy--> Nolan
Inception --releasedIn--> 2010
Inception --hasGenre--> SciFi
Inception --hasGenre--> Action
5. Exemples guides
Cette section contient 2 exemples resolus : 1. Exemple guide 1 : paires de realisateurs partageant des genres. 2. Exemple guide 2 : filmographie de Bong avec genres agreges.
Note pedagogique : les exemples montrent des requetes SPARQL avancees (self-join, GROUP_CONCAT) avec sorties concretes.
Suivi de 3 exercices : 1. Exercice 1 : Films d’une annee donnee. 2. Exercice 2 : Degre entrant d’un genre. 3. Exercice 3 : Chemin le plus court entre deux entites.
Difficulte progressive : facile -> moyenne -> moyenne-avancee.
{.c# .cell-code} // Exemple guide 1 : paires de realisateurs partageant des genres string q3 = @" PREFIX ex: <http://example.org/cinema#> SELECT ?d1 ?d2 (COUNT(DISTINCT ?g) AS ?shared) WHERE { ?f1 ex:directedBy ?d1 ; ex:hasGenre ?g . ?f2 ex:directedBy ?d2 ; ex:hasGenre ?g . FILTER(STR(?d1) < STR(?d2)) } GROUP BY ?d1 ?d2 ORDER BY DESC(?shared)"; var res3 = (SparqlResultSet)g.ExecuteQuery(q3); Console.WriteLine("Paires de realisateurs partageant des genres :"); foreach (SparqlResult r in res3) Console.WriteLine($" {Short(r["d1"])} & {Short(r["d2"])} : {((ILiteralNode)r["shared"]).Value} genre(s) commun(s)");
Interprétation — Exemple 1. Cette requête mesure une affinité cinématographique entre réalisateurs : combien de genres deux réalisateurs partagent-ils, tous films confondus ?
Trois astuces SPARQL méritent d’être soulignées :
Le motif de jointure?f1 ex:hasGenre ?g . ?f2 ex:hasGenre ?g relie deux films f1 et f2 dès qu’ils partagent au moins un genre ?g. Les réalisateurs ?d1, ?d2 sont récupérés via directedBy. C’est le bloc de base d’une mesure de similarité « contenu partagé ».
FILTER(STR(?d1) < STR(?d2)) est crucial : sans lui, chaque paire apparaîtrait deux fois ((Cameron, Nolan) et (Nolan, Cameron)) et chaque réalisateur serait apparié avec lui-même. La comparaison lexicographique stricte ne conserve que l’ordonnancement canonique de la paire — l’équivalent SPARQL d’une demi-matrice triangulaire.
COUNT(DISTINCT ?g) AS ?shared + GROUP BY ?d1 ?d2 agrège : on compte les genres distincts partagés par chaque paire, puis ORDER BY DESC(?shared) trie les paires les plus proches stylistiquement en premier.
Lecture du résultat (genres vérifiés sur le graphe source, cellule 7) : Cameron (Avatar : SciFi, Action) et Nolan (Inception, Interstellar : SciFi, …) partagent SciFi + Action — le cinéma de spectacle à grand budget. Bong (Parasite, Memories of Murder) et Tarantino (Pulp Fiction, Django) partagent Crime + Drama — le polar dramatique. Les deux paires à 1 genre commun (Bong & Nolan, Nolan & Tarantino) ne croisent que sur Drama, qui est aussi le genre le plus représenté du graphe (6 films sur 8). Sur un graphe de milliers de films, cette même requête alimente un recommender system de type filtrage collaboratif basé sur les attributs.
{.c# .cell-code} // Exemple guide 2 : filmographie de Bong avec genres agreges // En C# verbatim string (@"..."), un " litteral s'ecrit "" (double quote) string q4 = @" PREFIX ex: <http://example.org/cinema#> SELECT ?film (GROUP_CONCAT(DISTINCT ?g; SEPARATOR="", "") AS ?genres) WHERE { ?film ex:directedBy ex:Bong ; ex:hasGenre ?g . } GROUP BY ?film ORDER BY ?film"; var res4 = (SparqlResultSet)g.ExecuteQuery(q4); Console.WriteLine("Filmographie de Bong (genres agreges) :"); foreach (SparqlResult r in res4) Console.WriteLine($" {Short(r["film"])} : {((ILiteralNode)r["genres"]).Value.Replace("http://example.org/cinema#","")}");
Filmographie de Bong (genres agreges) :
MemoriesOfMurder : Crime, Drama
Parasite : Drama, Thriller
Interprétation — Exemple 2. Cette requête produit, pour chaque film de Bong Joon-ho, la liste agrégée de ses genres sur une seule ligne.
GROUP_CONCAT(DISTINCT ?g; SEPARATOR=", ") AS ?genres est l’opérateur-clé : il aplatit les plusieurs lignes (film, genre) d’un même film en une unique chaîne "Crime, Drama". DISTINCT dédoublonne les genres répétés ; le SEPARATOR contrôle le séparateur affiché.
GROUP BY ?film garantit une ligne de sortie par film (sans lui, GROUP_CONCAT fusionnerait tous les genres de toute la filmographie en une seule chaîne).
Piège C# rappelé en commentaire : la requête est insérée dans une chaîne verbatim@"...". En C#, un " littéral s’y écrit "" (doubled). Donc SEPARATOR="", "" dans le source C# devient SEPARATOR=", " côté SPARQL. C’est cette mécanique d’échappement qu’il faut avoir en tête quand on relit la requête.
Lecture du résultat : Memories of Murder (Crime, Drama) puis Parasite (Drama, Thriller). Le genre Drama est le fil conducteur — le invariant de la filmographie de Bong — autour duquel il greffe tour àtour du polar et du thriller. Cette évolution génree par génree est précisément ce que l’agrégation GROUP_CONCAT rend lisible en un coup d’œil.
6. Verdict SOTA – ce qui est couvert et ce qui ne l’est pas
Le KG cinema illustre les concepts fondamentaux. Comparons aux standards de l’industrie :
Note pedagogique : les exercices combinent SPARQL (SW-4) avec theorie des graphes (SW-11). L’exercice 3 introduit l’algorithme BFS pour les graphes RDF.
Exercice 1 : Films d’une annee donnee
Objectif : Ecrivez une requete SPARQL qui retourne tous les films sortis en 2010.
{.c# .cell-code} // Exercice 1 : a completer // string q = "PREFIX ex: <http://example.org/cinema#> SELECT ?film ?year WHERE { ?film ex:releasedIn ?year . FILTER(?year > 2010) } ORDER BY ?year"; // var res = (SparqlResultSet)g.ExecuteQuery(q); // foreach (SparqlResult r in res) Console.WriteLine($" {Short(r["film"])} ({r["year"]})"); Console.WriteLine("Exercice 1 a completer");
Exercice 1 a completer
Exercice 2 : Degre entrant d’un genre
Objectif : Calculez combien de films appartiennent a chaque genre. C’est l’equivalent du “degre entrant” du noeud genre (nombre de films qui pointent vers lui).
Sortie attendue :
Drama : 6
SciFi : 3
Action : 2
Indices : - SELECT ?genre (COUNT(?film) AS ?count). - GROUP BY ?genre. - ORDER BY DESC(?count).
Note pedagogique : on inverse la perspective – on regarde combien de films appartiennent a un genre (degre entrant du genre), au lieu de regarder combien de genres appartiennent a un film (degre sortant du film).
Difficulte : moyenne. Utilise COUNT + GROUP BY.
{.c# .cell-code} // Exercice 2 : a completer // var genreCount = new Dictionary<string,int>(); // foreach (var t in g.Triples.Where(t => t.Predicate.Equals(HAS_GENRE))) { ... } Console.WriteLine("Exercice 2 a completer");
Exercice 2 a completer
Exercice 3 : Chemin le plus court entre deux entites
Objectif : Trouvez le chemin le plus court entre ex:Inception et ex:Drama dans le KG. Utilisez BFS (largeur).
Sortie attendue (au minimum) :
Inception --hasGenre--> ? (1 saut si directement lie, sinon intermediaire)
Indices : - Implementer BFS avec une queue (Queue<INode>). - Maintenir un HashSet<INode> des noeuds visites. - Pour chaque voisin, verifier s’il correspond a la cible.
Difficulte : moyenne-avancee. Combine theorie des graphes + implementation C#.
Note pedagogique : le BFS est O(V + E) en temps et O(V) en espace. Pour les graphes denses, considerer A* avec heuristique (cf. notebook Search/Part1).
{.c# .cell-code} // Exercice 3 : a completer // var path = Bfs(adj, U(g, "ex:Inception"), 3); // if (path.Contains(U(g, "ex:PulpFiction"))) Console.WriteLine("PulpFiction atteint depuis Inception"); Console.WriteLine("Exercice 3 a completer");
Exercice 3 a completer
8. Resume et perspectives
Section
Concepts cles
Algorithmes / APIs
Definition
Graphe RDF avec ontologie + instances
-
Construction
Transformation table -> triplets
TurtleFormatter
Interrogation
SPARQL : SELECT, FILTER, GROUP BY, COUNT
LeviathanQueryProcessor
Adjacence
Liste d’adjacence (noeud -> voisins)
Dictionary<INode, List>
Parcours
BFS (largeur), DFS (profondeur)
Queue / Stack
Qualite (annexe D)
Orphelines, completude, distribution
LINQ
Centralite (annexe E)
Degre sortant (productivite realisateurs)
Dictionary<string, int>
Inference
Pas couvert ici – cf. SW-7 (OWL)
-
Validation
Pas couvert ici – cf. SW-8 (SHACL)
-
Embeddings
Pas couvert ici – cf. SW-13 (Reasoners)
-
Tous les concepts sont valides. Le notebook illustre les 7 grandes categories de manipulation d’un KG : definition, construction, interrogation, parcours, qualite, centralite, et limitations.
Substance pedagogique : - Knowledge Graph : representation structuree des connaissances. - SPARQL : langage de requete standard pour les graphes RDF. - Theorie des graphes : BFS, centralite, parcours.
Pour aller plus loin : - SW-7 OWL : ontologies formelles (subsomption, equivalence). - SW-8 SHACL : validation par contraintes (Cardinality, Datatype). - SW-10 RDFStar : annotations sur les triplets (qualifie les assertions). - SW-13 Reasoners : inference automatisee (Pellet, ELK).
Annexe A – Le Knowledge Graph en contexte
Approfondissement de la section 1 : pourquoi les KG comptent, ce qui les distingue d’une base relationnelle, et les usages industriels. Suit l’extrait C# de creation d’ontologie commente en section 2.
Pourquoi les KG sont importants : - Recherche semantique : Google Search utilise un KG pour les panneaux de connaissance. - Recommandation : Netflix, Spotify utilisent des KG pour suggerer du contenu. - Question-answering : les assistants vocaux (Siri, Alexa) utilisent des KG.
Comparaison avec une base relationnelle : - Relationnelle : tables, JOIN, contraintes d’integrite. - KG : triplets, inferecence, evolution de schema sans migration.
Cas d’usage industriel : - Santé : KG medical (SNOMED, ICD-10) pour le diagnostic. - Finance : KG de fraude (relations entre entities). - E-commerce : KG produit pour les recommandations. Implementation C# (creation d’ontologie) :
var g =newGraph();var ns = g.NamespaceMap;AddNamespace("ex",newUri("http://example.org/"));var filmClass = g.CreateUriNode("ex:Film");var directorClass = g.CreateUriNode("ex:Director");var genreClass = g.CreateUriNode("ex:Genre");var directedBy = g.CreateUriNode("ex:directedBy");var releasedIn = g.CreateUriNode("ex:releasedIn");var hasGenre = g.CreateUriNode("ex:hasGenre");var title = g.CreateUriNode("ex:title");
Annexe B – Patterns SPARQL et semantique d’evaluation
Approfondissement de la section 3 : les patterns des deux requetes principales (avec leurs sorties verbatim), les cas d’usage et la performance de la requete par realisateur, puis les agregats disponibles et l’ordre d’evaluation du moteur.
B.1 Patterns des deux requetes principales
Sortie observee de code[4] (verbatim) :
Films de Nolan (ordre annee desc) : 3
Dunkirk (2017)
Interstellar (2014)
Inception (2010)
La requete cherche les films realises par Nolan, tries par annee decroissante. La sortie inclut le titre et l’annee de chaque film.
Pattern de la requete :
PREFIX ex: <http://example.org/>
SELECT ?film ?title ?year WHERE {
?film a ex:Film .
?film ex:directedBy ex:Nolan .
?film ex:title ?title .
?film ex:releasedIn ?year .
} ORDER BY DESC(?year)
Sortie observee de code[5] (verbatim) :
Nombre de films par genre :
Drama : 6
SciFi : 3
Action : 2
La requete utilise COUNT et GROUP BY pour compter les films par genre.
Pattern :
SELECT ?genre (COUNT(?film) AS ?count) WHERE {
?film a ex:Film .
?film ex:hasGenre ?genre .
} GROUP BY ?genre
ORDER BY DESC(?count)
B.2 Requete par realisateur : cas d’usage et performance
Cas d’usage : - Site web : filmographie d’un realisateur. - Recommandation : “films similaires” (memes realisateurs). - Analyse : etude de la carriere d’un realisateur (evolution des genres, etc.).
Performance : - Filtre par realisateur : selectif (1 realisateur = ~3 films). - Tri par annee : lineaire (8 films = 8 comparaisons). - Total : O(N log N) avec un index sur directedBy. ### B.3 Agregats disponibles et ordre d’evaluation
Agregats disponibles en SPARQL : - COUNT : nombre de valeurs. - SUM : somme. - AVG : moyenne. - MIN/MAX : min/max. - GROUP_CONCAT : concatenation avec separateur. - SAMPLE : un exemple de valeur.
Note de portee : les agregats sont evalues APRES les filtres. L’ordre est : 1. WHERE (filtrage des triplets). 2. GROUP BY (partitionnement). 3. Agregats (calcul). 4. HAVING (filtre post-agregat, optionnel). 5. ORDER BY (tri final). 6. SELECT (projection).
Annexe C – Implémentations C# des parcours
Approfondissement de la section 4 : les implémentations complètes de la liste d’adjacence et du BFS, l’extrait de la visualisation ASCII, l’analyse de complexité et les familles d’algorithmes voisins.
C.1 Liste d’adjacence
Implementation C# (adjacence) :
var adj =new Dictionary<INode, List<INode>>();foreach(var t in g.Triples){if(!adj.ContainsKey(t.Subject)) adj[t.Subject]=new List<INode>(); adj[t.Subject].Add(t.Object);}
Complexite : - Adjacence : O(V + E) pour la construction. - BFS : O(V + E) pour l’exploration. - Memoire : O(V) pour la liste d’adjacence.
Cas d’usage : - Recommendation : “films similaires” (2-hop depuis un film). - Detection de communautes : composantes connexes. - Plus court chemin : Dijkstra, A-B (cf. notebook Search/Part1). - PageRank : variante de BFS avec poids (importance). - A* : BFS + heuristique pour les graphes ponderes. ### C.3 Extrait de la visualisation ASCII
Implementation C# (ASCII viz) :
staticstringShort(INode n)=> n is IUriNode u ? u.Uri.Fragment.TrimStart('#'): n.ToString();var sub =BFS(g, inceptionNode,2);foreach(var t in g.Triples.Where(t => sub.Contains(t.Subject)&& sub.Contains(t.Object))){ Console.WriteLine($" {Short(t.Subject)} --{Short(t.Predicate)}--> {Short(t.Object)}");}
Annexes D et E – Qualite et centralite du KG
Les deux metriques d’analyse statistique du KG – qualite (classes orphelines, completude, distribution) puis centralite (degre des realisateurs) – sont approfondies ici, apres la ligne principale. Leur execution ne depend que du graphe g et des helpers definis en section 4 ; l’ordre d’execution du carnet reste valide.
Annexe D – Qualite et validation d’un Knowledge Graph
Un KG peut avoir des problemes de qualite : - Classes orphelines : declarees mais jamais utilisees. - Donnees incompletes : entites sans certaines proprietes obligatoires. - Distribution biaisee : valeurs manquantes ou aberrantes.
3 metriques implementees : 1. Classes orphelines : nombre de classes declarees mais sans instance. Ici, 3/3 (les classes Film, Director, Genre ont des instances – donc 0 orphelines au sens strict ; mais la metrique retourne le total declare comme proxy). 2. Completude : ratio des films ayant directeur + annee + genre. Ici 8/8 = 100%. 3. Distribution des valeurs : min/max/median des annees. Ici [1994, 2019] mediane 2012.
Implementation C# (extrait verbatim de la cellule 5.) :
// 5.1 Classes declarees mais jamais instanciees (orphelines au sens large)var classes = g.Triples.Where(t => t.Predicate.Equals(RDF_TYPE)&& t.Object.Equals(U(g,"ex:Class"))).Select(t=>t.Subject).ToList();var orphans = classes.Where(c =>!g.Triples.Any(t => t.Subject.Equals(c)&&!t.Predicate.Equals(RDF_TYPE))).ToList();Console.WriteLine($"Classes declarees : {classes.Count}, orphelines : {orphans.Count}");// 5.2 Completude : chaque Film a directeur + annee + au moins 1 genre ?var allFilms = g.Triples.Where(t => t.Predicate.Equals(RDF_TYPE)&& t.Object.Equals(U(g,"ex:Film"))).Select(t=>t.Subject).ToList();int complete =0;foreach(var f in allFilms){bool hasDir = g.Triples.Any(t => t.Subject.Equals(f)&& t.Predicate.Equals(DIRECTED_BY));bool hasYear = g.Triples.Any(t => t.Subject.Equals(f)&& t.Predicate.Equals(RELEASED));bool hasGenre = g.Triples.Any(t => t.Subject.Equals(f)&& t.Predicate.Equals(HAS_GENRE));if(hasDir && hasYear && hasGenre) complete++;}Console.WriteLine($"Films complets (directeur+annee+genre) : {complete}/{allFilms.Count}");// 5.3 Distribution des anneesvar years = g.Triples.Where(t => t.Predicate.Equals(RELEASED)).Select(t =>int.Parse(((ILiteralNode)t.Object).Value)).OrderBy(y=>y).ToList();Console.WriteLine($"Annees : min={years.First()}, max={years.Last()}, mediane={years[years.Count/2]}");
Pourquoi la qualite est importante : - Confiance : un KG avec beaucoup d’orphelines est suspect. - Inference : les classes orphelines ne peuvent pas etre utilisees pour l’inference. - Maintenance : detecter les problemes tot (avant qu’ils ne se propagent).
``` {.c# .cell-code} // 5.1 Classes declarees mais jamais instanciees (orphelines au sens large) var classes = g.Triples.Where(t => t.Predicate.Equals(RDF_TYPE) && t.Object.Equals(U(g,“ex:Class”))) .Select(t=>t.Subject).ToList(); var orphans = classes.Where(c => !g.Triples.Any(t => t.Subject.Equals(c) && !t.Predicate.Equals(RDF_TYPE))).ToList(); Console.WriteLine($“Classes declarees : {classes.Count}, orphelines : {orphans.Count}”);
// 5.2 Completude : chaque Film a directeur + annee + au moins 1 genre ? var allFilms = g.Triples.Where(t => t.Predicate.Equals(RDF_TYPE) && t.Object.Equals(U(g,“ex:Film”))) .Select(t=>t.Subject).ToList(); int complete = 0; foreach (var f in allFilms) { bool hasDir = g.Triples.Any(t => t.Subject.Equals(f) && t.Predicate.Equals(DIRECTED_BY)); bool hasYear = g.Triples.Any(t => t.Subject.Equals(f) && t.Predicate.Equals(RELEASED)); bool hasGenre = g.Triples.Any(t => t.Subject.Equals(f) && t.Predicate.Equals(HAS_GENRE)); if (hasDir && hasYear && hasGenre) complete++; } Console.WriteLine($“Films complets (directeur+annee+genre) : {complete}/{allFilms.Count}”);
// 5.3 Distribution des annees var years = g.Triples.Where(t => t.Predicate.Equals(RELEASED)) .Select(t => int.Parse(((ILiteralNode)t.Object).Value)).OrderBy(y=>y).ToList(); Console.WriteLine($“Annees : min={years.First()}, max={years.Last()}, mediane={years[years.Count/2]}”);
:::
:::
**Interprétation** : les 3 métriques de qualité valident que le KG est bien formé. (1) **Complétude** : `complete == allFilms.Count` (8/8) confirme qu'aucun film n'a de champ manquant (directeur, année, genre). (2) **Cohérence du range** : les années s'étalent de 1994 à 2019, médiane 2012 — une plage réaliste pour un corpus de cinéma moderne. (3) **Orphelins** : les 3 classes « orphelines » détectées (`Director`, `Film`, `Genre`) sont les **méta-types** eux-mêmes — elles n'apparaissent comme sujet que de leur propre `rdf:type ex:Class`, ce qui est **attendu** (ce sont les types, pas des instances) et non un défaut de données. Ces vérifications sont l'équivalent C# du bloc « Qualité » du twin Python.
## Annexe E -- Centralite : degre des realisateurs
La **centralite de degre** mesure combien de connexions sortantes (ou entrantes) un noeud a. C'est la metrique la plus simple mais utile pour identifier les acteurs cles.
**Sortie observee de code[14]** (verbatim) :
Classement des realisateurs par productivite (nb films) : 1. Nolan : 3 films 2. Bong : 2 films 3. Tarantino : 2 films
**Implementation C# (degre)** :
```csharp
var deg = new Dictionary<string, int>();
foreach (var t in g.Triples.Where(t => t.Predicate.Equals(directedByProp))) {
var directorName = Short(t.Object);
if (!deg.ContainsKey(directorName)) deg[directorName] = 0;
deg[directorName]++;
}
var ranking = deg.OrderByDescending(kv => kv.Value);
Types de centralite : - Degre : nombre de voisins. Simple et rapide (O(V + E)). - Betweenness : nombre de plus courts chemins passant par le noeud. O(VE). - Closeness : inverse de la somme des distances. O(V log V). - Eigenvector : importance basee sur l’importance des voisins (PageRank). O(V + E) iteratif.
Cas d’usage : - Recommandation : “qui est similaire a X” (meme centralite). - Detection d’influence : les noeuds a haute centralite sont des leaders d’opinion. - Analyse de reseau social : influenceurs, communautes.
Note de portee : la centralite de degre est biaisee par la taille du voisinage. Pour des graphes heterogenes (certains noeuds ont beaucoup de voisins, d’autres peu), preferer PageRank.
{.c# .cell-code} var deg = new Dictionary<string,int>(); foreach (var t in g.Triples.Where(t => t.Predicate.Equals(DIRECTED_BY))) { var dir = Short(t.Object); deg[dir] = deg.GetValueOrDefault(dir, 0) + 1; } var ranked = deg.OrderByDescending(kv => kv.Value).ThenBy(kv => kv.Key).ToList(); Console.WriteLine("Classement des realisateurs par productivite (nb films) :"); for (int i = 0; i < ranked.Count; i++) Console.WriteLine($" {i+1}. {ranked[i].Key} : {ranked[i].Value} films");
Classement des realisateurs par productivite (nb films) :
1. Nolan : 3 films
2. Bong : 2 films
3. Tarantino : 2 films
4. Cameron : 1 films
Interprétation : le degré sortant (directedBy inversé) classe les réalisateurs par productivité dans le KG. Nolan mène (3 films), suivi de Bong et Tarantino (2 chacun), puis Cameron (1). C’est le degree centrality — la métrique de centralité la plus directe. Le PageRank du twin Python raffine en pondérant par l’importance des voisins, mais le classement brut par degré est déjà une excellente approximation sur un petit graphe.