network

patternMatch

##set_network

Description

L'action (disponible dans l'ensemble d'actions ) permet d'interroger un graphe pour y trouver des correspondances de motifs (pattern matching). C'est un outil très puissant pour rechercher des sous-graphes spécifiques ou des structures topologiques particulières au sein d'un vaste réseau (un peu comme chercher une aiguille, mais avec la forme de l'aiguille précise, dans une botte de foin en réseau !). L'action prend en charge les graphes orientés et non orientés, et permet de spécifier le motif recherché sous forme de tables de nœuds et de liens de requête.

Syntaxe Officielle
proc cas;
network.patternMatch /
code="string"
deterministic=TRUE | FALSE
direction="DIRECTED" | "UNDIRECTED"
links={name="table-name", caslib="string", ...}
linksQuery={name="table-name", caslib="string", ...}
linksQueryVar={expandLower="var", expandUpper="var", from="var", to="var", ...}
linksVar={from="var", to="var", weight="var", ...}
nodes={name="table-name", ...}
nodesQuery={name="table-name", ...}
nodesQueryVar={node="var", ...}
nodesVar={node="var", weight="var", ...}
outMatchGraphLinks={name="table-name", ...}
outMatchGraphNodes={name="table-name", ...}
outMatchLinks={name="table-name", ...}
outMatchNodes={name="table-name", ...}
maxMatchesPerQuery=integer | "ALL"
maxTime=double;
run;
quit;

Paramètres Clés

Nom du paramètre Description
direction Spécifie s'il faut considérer le graphe d'entrée comme orienté () ou non orienté (). Par défaut, il est non orienté.
links Spécifie la table de données d'entrée () qui contient les informations sur les liens du graphe principal.
nodes Spécifie la table de données d'entrée qui contient les informations sur les nœuds du graphe principal (optionnel si définis implicitement par les liens).
linksQuery Spécifie la table de données d'entrée qui définit les liens du motif de requête (le sous-graphe que vous recherchez).
nodesQuery Spécifie la table de données d'entrée qui définit les nœuds du motif de requête.
outMatchNodes Table de sortie contenant les mappages des nœuds correspondants aux motifs trouvés.
outMatchLinks Table de sortie contenant les liens des sous-graphes correspondants.
code Spécifie une chaîne d'entrée contenant des fonctions pour un filtrage avancé des correspondances.

Préparation des données

Création du graphe principal et du graphe de requête

Génération de tables en mémoire CAS représentant un petit réseau d'interactions, ainsi qu'un motif de requête (ici, une recherche de triangles A-B-C).

1PROC CAS;
2 datastep.runCode / code="
3 data mycas.linkSet;
4 length from $2 to $2;
5 input from $ to $;
6 datalines;
7 A B
8 B C
9 C A
10 C D
11 D E
12 E C
13 ;
14 run;
15 data mycas.queryLinks;
16 length from $2 to $2;
17 input from $ to $;
18 datalines;
19 X Y
20 Y Z
21 Z X
22 ;
23 run;
24 ";
25RUN;
26QUIT;

Exemples d'utilisation

Recherche de motifs de base

Recherche du motif triangulaire spécifié dans `queryLinks` au sein du graphe principal `linkSet`.

1PROC CAS;
2 network.patternMatch /
3 direction="UNDIRECTED"
4 links={name="linkSet"}
5 linksQuery={name="queryLinks"}
6 outMatchNodes={name="matchNodes", replace=true}
7 outMatchLinks={name="matchLinks", replace=true};
8RUN;
9QUIT;
Résultat Attendu :
L'action identifiera les deux triangles présents dans le graphe principal (A-B-C et C-D-E) et générera les tables `matchNodes` et `matchLinks` détaillant ces occurrences.
Recherche avancée avec limite et graphe orienté

Même recherche, mais en considérant les liens comme orientés et en limitant le nombre de correspondances par requête à 10 pour des raisons de performance sur de gros volumes.

1PROC CAS;
2 network.patternMatch /
3 direction="DIRECTED"
4 maxMatchesPerQuery=10
5 links={name="linkSet"}
6 linksVar={from="from", to="to"}
7 linksQuery={name="queryLinks"}
8 linksQueryVar={from="from", to="to"}
9 outMatchNodes={name="matchNodesDir", replace=true}
10 outMatchLinks={name="matchLinksDir", replace=true};
11RUN;
12QUIT;
Résultat Attendu :
Les tables de sortie contiendront les correspondances respectant strictement le sens des liens (les cycles orientés A->B->C->A, etc.). Le processus s'arrêtera s'il trouve plus de 10 occurrences.
Sommaire