Espace intrinsèque d'un graphe et recherche de communautés
Identifieur interne : 002797 ( Main/Exploration ); précédent : 002796; suivant : 002798Espace intrinsèque d'un graphe et recherche de communautés
Auteurs : Alain Lelu [France] ; Martine Cadot [France]Source :
- Information interaction intelligence [ 1630-649X ] ; 2011.
Descripteurs français
- Pascal (Inist)
- mix :
English descriptors
- KwdEn :
- mix :
Abstract
La recherche de communautés dans un graphe se heurte à des problèmes épineux de représentation (formes convexes, recouvrantes, individus isolés...) dont l'abord optimal est réalisé par les méthodes spectrales, basées sur les dimensions propres du Laplacien de ce graphe. Déterminer le nombre de dimensions à prendre en considération est essentiel pour beaucoup d'applications. On s'attaque ici à ce problème dans le cadre de graphes non-orientés et non pondérés, qui inclut un type de graphe courant dans les applications de réseaux biologiques et sociaux, ceux munis d'une distribution des degrés de leurs nœuds en loi de puissance. Nous proposons à cet effet un test de randomisation, indépendant des lois de distribution. Après un petit exemple introductif, nous validons d'abord notre approche sur un graphe artificiel de ce type comportant deux communautés, puis sur deux graphes de test « Football League » et « Mexican Politician Network », où nous montrons à partir des résultats d'une méthode densitaire de clustering le caractère optimal du nombre de dimensions extraites.
Url:
Affiliations:
- France
- Bourgogne-Franche-Comté, Franche-Comté, Grand Est, Lorraine (région), Île-de-France
- Besançon, Nancy, Paris
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000120
- to stream PascalFrancis, to step Curation: 000891
- to stream PascalFrancis, to step Checkpoint: 000117
- to stream Main, to step Merge: 002841
- to stream Hal, to step Corpus: 005B39
- to stream Hal, to step Curation: 005B39
- to stream Hal, to step Checkpoint: 001B29
- to stream Main, to step Merge: 002119
- to stream Main, to step Curation: 002797
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="fr" level="a">Espace intrinsèque d'un graphe et recherche de communautés</title>
<author><name sortKey="Lelu, Alain" sort="Lelu, Alain" uniqKey="Lelu A" first="Alain" last="Lelu">Alain Lelu</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LORIA</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>Université de Franche-Comté/LASELDI</s1>
<s2>Besançon</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Bourgogne-Franche-Comté</region>
<region type="old region">Franche-Comté</region>
<settlement type="city">Besançon</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="03"><s1>Université de Nancy/Département Informatique</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="04"><s1>Institut des Sciences de la Communication du CNRS</s1>
<s2>Paris</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Île-de-France</region>
<region type="old region">Île-de-France</region>
<settlement type="city">Paris</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Cadot, Martine" sort="Cadot, Martine" uniqKey="Cadot M" first="Martine" last="Cadot">Martine Cadot</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LORIA</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>Université de Franche-Comté/LASELDI</s1>
<s2>Besançon</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Bourgogne-Franche-Comté</region>
<region type="old region">Franche-Comté</region>
<settlement type="city">Besançon</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="03"><s1>Université de Nancy/Département Informatique</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="04"><s1>Institut des Sciences de la Communication du CNRS</s1>
<s2>Paris</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Île-de-France</region>
<region type="old region">Île-de-France</region>
<settlement type="city">Paris</settlement>
</placeName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">12-0146979</idno>
<date when="2011">2011</date>
<idno type="stanalyst">PASCAL 12-0146979 INIST</idno>
<idno type="RBID">Pascal:12-0146979</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000120</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000891</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000117</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000117</idno>
<idno type="wicri:doubleKey">1630-649X:2011:Lelu A:espace:intrinseque:d</idno>
<idno type="wicri:Area/Main/Merge">002841</idno>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00641128</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00641128</idno>
<idno type="wicri:Area/Hal/Corpus">005B39</idno>
<idno type="wicri:Area/Hal/Curation">005B39</idno>
<idno type="wicri:Area/Hal/Checkpoint">001B29</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">001B29</idno>
<idno type="wicri:doubleKey">1630-649X:2011:Lelu A:espace:intrinseque:d</idno>
<idno type="wicri:Area/Main/Merge">002119</idno>
<idno type="wicri:Area/Main/Curation">002797</idno>
<idno type="wicri:Area/Main/Exploration">002797</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="fr" level="a">Espace intrinsèque d'un graphe et recherche de communautés</title>
<author><name sortKey="Lelu, Alain" sort="Lelu, Alain" uniqKey="Lelu A" first="Alain" last="Lelu">Alain Lelu</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LORIA</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>Université de Franche-Comté/LASELDI</s1>
<s2>Besançon</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Bourgogne-Franche-Comté</region>
<region type="old region">Franche-Comté</region>
<settlement type="city">Besançon</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="03"><s1>Université de Nancy/Département Informatique</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="04"><s1>Institut des Sciences de la Communication du CNRS</s1>
<s2>Paris</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Île-de-France</region>
<region type="old region">Île-de-France</region>
<settlement type="city">Paris</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Cadot, Martine" sort="Cadot, Martine" uniqKey="Cadot M" first="Martine" last="Cadot">Martine Cadot</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LORIA</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>Université de Franche-Comté/LASELDI</s1>
<s2>Besançon</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Bourgogne-Franche-Comté</region>
<region type="old region">Franche-Comté</region>
<settlement type="city">Besançon</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="03"><s1>Université de Nancy/Département Informatique</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="04"><s1>Institut des Sciences de la Communication du CNRS</s1>
<s2>Paris</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Île-de-France</region>
<region type="old region">Île-de-France</region>
<settlement type="city">Paris</settlement>
</placeName>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Information interaction intelligence</title>
<title level="j" type="abbreviated">Inf. interact. intell.</title>
<idno type="ISSN">1630-649X</idno>
<imprint><date when="2011">2011</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Information interaction intelligence</title>
<title level="j" type="abbreviated">Inf. interact. intell.</title>
<idno type="ISSN">1630-649X</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Convex shape</term>
<term>Dimension reduction</term>
<term>Laplacian</term>
<term>Non directed graph</term>
<term>Power law</term>
<term>Probability distribution</term>
<term>Randomization</term>
<term>Soccer</term>
<term>Social network</term>
<term>Spectral method</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Randomisation</term>
<term>Football</term>
<term>Forme convexe</term>
<term>Réseau social</term>
<term>Méthode spectrale</term>
<term>Laplacien</term>
<term>Graphe non orienté</term>
<term>Loi puissance</term>
<term>Loi probabilité</term>
<term>Réduction dimension</term>
</keywords>
<keywords scheme="mix" xml:lang="en"><term>Cattell's scree.</term>
<term>density clustering method</term>
<term>dimensionality reduction</term>
<term>dominant eigen-subspace</term>
<term>graph</term>
<term>graph Laplacian</term>
<term>graph clustering</term>
<term>intrinsic dimension</term>
<term>randomization test</term>
<term>scale-free graph</term>
</keywords>
<keywords scheme="mix" xml:lang="fr"><term>clustering de graphe</term>
<term>dimension intrinsèque</term>
<term>extraction de communautés</term>
<term>graphe</term>
<term>graphe sans échelle</term>
<term>laplacien d'un graphe</term>
<term>méthode densitaire de clustering</term>
<term>réduction de dimensions</term>
<term>test de randomisation</term>
<term>éboulis de Cattell.</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="fr">La recherche de communautés dans un graphe se heurte à des problèmes épineux de représentation (formes convexes, recouvrantes, individus isolés...) dont l'abord optimal est réalisé par les méthodes spectrales, basées sur les dimensions propres du Laplacien de ce graphe. Déterminer le nombre de dimensions à prendre en considération est essentiel pour beaucoup d'applications. On s'attaque ici à ce problème dans le cadre de graphes non-orientés et non pondérés, qui inclut un type de graphe courant dans les applications de réseaux biologiques et sociaux, ceux munis d'une distribution des degrés de leurs nœuds en loi de puissance. Nous proposons à cet effet un test de randomisation, indépendant des lois de distribution. Après un petit exemple introductif, nous validons d'abord notre approche sur un graphe artificiel de ce type comportant deux communautés, puis sur deux graphes de test « Football League » et « Mexican Politician Network », où nous montrons à partir des résultats d'une méthode densitaire de clustering le caractère optimal du nombre de dimensions extraites.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
</country>
<region><li>Bourgogne-Franche-Comté</li>
<li>Franche-Comté</li>
<li>Grand Est</li>
<li>Lorraine (région)</li>
<li>Île-de-France</li>
</region>
<settlement><li>Besançon</li>
<li>Nancy</li>
<li>Paris</li>
</settlement>
</list>
<tree><country name="France"><region name="Grand Est"><name sortKey="Lelu, Alain" sort="Lelu, Alain" uniqKey="Lelu A" first="Alain" last="Lelu">Alain Lelu</name>
</region>
<name sortKey="Cadot, Martine" sort="Cadot, Martine" uniqKey="Cadot M" first="Martine" last="Cadot">Martine Cadot</name>
<name sortKey="Cadot, Martine" sort="Cadot, Martine" uniqKey="Cadot M" first="Martine" last="Cadot">Martine Cadot</name>
<name sortKey="Cadot, Martine" sort="Cadot, Martine" uniqKey="Cadot M" first="Martine" last="Cadot">Martine Cadot</name>
<name sortKey="Cadot, Martine" sort="Cadot, Martine" uniqKey="Cadot M" first="Martine" last="Cadot">Martine Cadot</name>
<name sortKey="Lelu, Alain" sort="Lelu, Alain" uniqKey="Lelu A" first="Alain" last="Lelu">Alain Lelu</name>
<name sortKey="Lelu, Alain" sort="Lelu, Alain" uniqKey="Lelu A" first="Alain" last="Lelu">Alain Lelu</name>
<name sortKey="Lelu, Alain" sort="Lelu, Alain" uniqKey="Lelu A" first="Alain" last="Lelu">Alain Lelu</name>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002797 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002797 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Exploration |type= RBID |clé= Pascal:12-0146979 |texte= Espace intrinsèque d'un graphe et recherche de communautés }}
This area was generated with Dilib version V0.6.33. |