Serveur d'exploration sur la recherche en informatique en Lorraine

Attention, ce site est en cours de développement !
Attention, site généré par des moyens informatiques à partir de corpus bruts.
Les informations ne sont donc pas validées.

Espace intrinsèque d'un graphe et recherche de communautés

Identifieur interne : 000117 ( PascalFrancis/Checkpoint ); précédent : 000116; suivant : 000118

Espace intrinsèque d'un graphe et recherche de communautés

Auteurs : Alain Lelu [France] ; Martine Cadot [France]

Source :

RBID : Pascal:12-0146979

Descripteurs français

English descriptors

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.


Affiliations:


Links toward previous steps (curation, corpus...)


Links to Exploration step

Pascal:12-0146979

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>
</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>
</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>
<inist>
<standard h6="B">
<pA>
<fA01 i1="01" i2="1">
<s0>1630-649X</s0>
</fA01>
<fA03 i2="1">
<s0>Inf. interact. intell.</s0>
</fA03>
<fA05>
<s2>11</s2>
</fA05>
<fA06>
<s2>1</s2>
</fA06>
<fA08 i1="01" i2="1" l="FRE">
<s1>Espace intrinsèque d'un graphe et recherche de communautés</s1>
</fA08>
<fA09 i1="01" i2="1" l="FRE">
<s1>Conférence MARAMI 2010 (Modèles et Analyse des Réseaux : Approches Mathématiques et Informatique)</s1>
</fA09>
<fA11 i1="01" i2="1">
<s1>LELU (Alain)</s1>
</fA11>
<fA11 i1="02" i2="1">
<s1>CADOT (Martine)</s1>
</fA11>
<fA12 i1="01" i2="1">
<s1>BOULET (Romain)</s1>
<s9>ed.</s9>
</fA12>
<fA12 i1="02" i2="1">
<s1>THIRIOT (Samuel)</s1>
<s9>ed.</s9>
</fA12>
<fA14 i1="01">
<s1>LORIA</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</fA14>
<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>
</fA14>
<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>
</fA14>
<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>
</fA14>
<fA20>
<s1>31-55</s1>
</fA20>
<fA21>
<s1>2011</s1>
</fA21>
<fA23 i1="01">
<s0>FRE</s0>
</fA23>
<fA24 i1="01">
<s0>eng</s0>
</fA24>
<fA43 i1="01">
<s1>INIST</s1>
<s2>27327</s2>
<s5>354000509998620020</s5>
</fA43>
<fA44>
<s0>0000</s0>
<s1>© 2012 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45>
<s0>1 p.3/4</s0>
</fA45>
<fA47 i1="01" i2="1">
<s0>12-0146979</s0>
</fA47>
<fA60>
<s1>P</s1>
<s2>C</s2>
</fA60>
<fA61>
<s0>A</s0>
</fA61>
<fA64 i1="01" i2="1">
<s0>Information interaction intelligence</s0>
</fA64>
<fA66 i1="01">
<s0>FRA</s0>
</fA66>
<fC01 i1="01" l="FRE">
<s0>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.</s0>
</fC01>
<fC02 i1="01" i2="X">
<s0>001D02A06</s0>
</fC02>
<fC02 i1="02" i2="X">
<s0>001D02B07B</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE">
<s0>Randomisation</s0>
<s5>06</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG">
<s0>Randomization</s0>
<s5>06</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA">
<s0>Aleatorización</s0>
<s5>06</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE">
<s0>Football</s0>
<s5>07</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG">
<s0>Soccer</s0>
<s5>07</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA">
<s0>Fútbol</s0>
<s5>07</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE">
<s0>Forme convexe</s0>
<s5>18</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG">
<s0>Convex shape</s0>
<s5>18</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA">
<s0>Forma convexa</s0>
<s5>18</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE">
<s0>Réseau social</s0>
<s5>19</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG">
<s0>Social network</s0>
<s5>19</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA">
<s0>Red social</s0>
<s5>19</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE">
<s0>Méthode spectrale</s0>
<s5>23</s5>
</fC03>
<fC03 i1="05" i2="X" l="ENG">
<s0>Spectral method</s0>
<s5>23</s5>
</fC03>
<fC03 i1="05" i2="X" l="SPA">
<s0>Método espectral</s0>
<s5>23</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE">
<s0>Laplacien</s0>
<s5>24</s5>
</fC03>
<fC03 i1="06" i2="X" l="ENG">
<s0>Laplacian</s0>
<s5>24</s5>
</fC03>
<fC03 i1="06" i2="X" l="SPA">
<s0>Laplaciano</s0>
<s5>24</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE">
<s0>Graphe non orienté</s0>
<s5>25</s5>
</fC03>
<fC03 i1="07" i2="X" l="ENG">
<s0>Non directed graph</s0>
<s5>25</s5>
</fC03>
<fC03 i1="07" i2="X" l="SPA">
<s0>Grafo no orientado</s0>
<s5>25</s5>
</fC03>
<fC03 i1="08" i2="X" l="FRE">
<s0>Loi puissance</s0>
<s5>26</s5>
</fC03>
<fC03 i1="08" i2="X" l="ENG">
<s0>Power law</s0>
<s5>26</s5>
</fC03>
<fC03 i1="08" i2="X" l="SPA">
<s0>Ley poder</s0>
<s5>26</s5>
</fC03>
<fC03 i1="09" i2="X" l="FRE">
<s0>Loi probabilité</s0>
<s5>27</s5>
</fC03>
<fC03 i1="09" i2="X" l="ENG">
<s0>Probability distribution</s0>
<s5>27</s5>
</fC03>
<fC03 i1="09" i2="X" l="SPA">
<s0>Ley probabilidad</s0>
<s5>27</s5>
</fC03>
<fC03 i1="10" i2="X" l="FRE">
<s0>Réduction dimension</s0>
<s5>28</s5>
</fC03>
<fC03 i1="10" i2="X" l="ENG">
<s0>Dimension reduction</s0>
<s5>28</s5>
</fC03>
<fC03 i1="10" i2="X" l="SPA">
<s0>Reducción dimensión</s0>
<s5>28</s5>
</fC03>
<fN21>
<s1>114</s1>
</fN21>
</pA>
<pR>
<fA30 i1="01" i2="1" l="FRE">
<s1>Conférence MARAMI 2010 (Modèles et Analyse des Réseaux : Approches Mathématiques et Informatique)</s1>
<s2>1</s2>
<s3>Toulouse FRA</s3>
<s4>2010-10-11</s4>
</fA30>
</pR>
</standard>
</inist>
<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/PascalFrancis/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000117 | SxmlIndent | more

Ou

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Checkpoint/biblio.hfd -nk 000117 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    PascalFrancis
   |étape=   Checkpoint
   |type=    RBID
   |clé=     Pascal:12-0146979
   |texte=   Espace intrinsèque d'un graphe et recherche de communautés
}}

Wicri

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022