Espace intrinsèque d'un graphe et recherche de communautés.
Identifieur interne : 001B29 ( Hal/Checkpoint ); précédent : 001B28; suivant : 001B30Espace intrinsèque d'un graphe et recherche de communautés.
Auteurs : Alain Lelu [France] ; Martine Cadot [France]Source :
- Revue I3 - Information Interaction Intelligence [ 1630-649X ] ; 2011-10.
Descripteurs français
- mix :
English descriptors
- mix :
Abstract
Determining the number of relevant dimensions in the eigen-space of a graph Laplacian matrix is a central issue in many spectral graph-mining applications. We tackle here the problem of finding out the "right" dimensionality of Laplacian matrices, especially those often encountered in the domains of social or biological graphs: the ones underlying large, sparse, unoriented and unweighted graphs, often endowed with a power-law degree distribution. We present here the application of a randomization test to this problem. After a small introductive example, we validate our approach first on an artificial sparse and scale-free graph, with two intermingled clusters, then on two real-world social graphs ("Football-league", "Mexican Politician Network"), where the actual, intrinsic dimensions appear to be 10 and 2 respectively ; we illustrate the optimality of the transformed dataspaces both visually and numerically, by means of a densitybased clustering technique and a decision tree.
Url:
Links toward previous steps (curation, corpus...)
Links to Exploration step
Hal:hal-00641128Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="fr">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="1"><hal:affiliation type="researchteam" xml:id="struct-54311" status="OLD"><orgName>Knowledge Information and Web Intelligence</orgName><orgName type="acronym">KIWI</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche/equipes/kiwi</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="IdRef">02636817X</idno><idno type="ISNI">0000000122597504</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Cadot, Martine" sort="Cadot, Martine" uniqKey="Cadot M" first="Martine" last="Cadot">Martine Cadot</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-24433" status="OLD"><orgName>Machine Learning and Computational Biology</orgName><orgName type="acronym">ABC</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche/equipes/abc</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="IdRef">02636817X</idno><idno type="ISNI">0000000122597504</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-00641128</idno><idno type="halId">hal-00641128</idno><idno type="halUri">https://hal.archives-ouvertes.fr/hal-00641128</idno><idno type="url">https://hal.archives-ouvertes.fr/hal-00641128</idno><date when="2011-10">2011-10</date><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></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="fr">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="1"><hal:affiliation type="researchteam" xml:id="struct-54311" status="OLD"><orgName>Knowledge Information and Web Intelligence</orgName><orgName type="acronym">KIWI</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche/equipes/kiwi</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="IdRef">02636817X</idno><idno type="ISNI">0000000122597504</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Cadot, Martine" sort="Cadot, Martine" uniqKey="Cadot M" first="Martine" last="Cadot">Martine Cadot</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-24433" status="OLD"><orgName>Machine Learning and Computational Biology</orgName><orgName type="acronym">ABC</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche/equipes/abc</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="IdRef">02636817X</idno><idno type="ISNI">0000000122597504</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author></analytic><series><title level="j">Revue I3 - Information Interaction Intelligence</title><idno type="ISSN">1630-649X</idno><imprint><date type="datePub">2011-10</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><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="en">Determining the number of relevant dimensions in the eigen-space of a graph Laplacian matrix is a central issue in many spectral graph-mining applications. We tackle here the problem of finding out the "right" dimensionality of Laplacian matrices, especially those often encountered in the domains of social or biological graphs: the ones underlying large, sparse, unoriented and unweighted graphs, often endowed with a power-law degree distribution. We present here the application of a randomization test to this problem. After a small introductive example, we validate our approach first on an artificial sparse and scale-free graph, with two intermingled clusters, then on two real-world social graphs ("Football-league", "Mexican Politician Network"), where the actual, intrinsic dimensions appear to be 10 and 2 respectively ; we illustrate the optimality of the transformed dataspaces both visually and numerically, by means of a densitybased clustering technique and a decision tree.</div></front></TEI><hal api="V3"><titleStmt><title xml:lang="fr">Espace intrinsèque d'un graphe et recherche de communautés.</title><author role="aut"><persName><forename type="first">Alain</forename><surname>Lelu</surname></persName><email>Alain.Lelu@univ-fcomte.fr</email><idno type="halauthor">223091</idno><orgName ref="#struct-242365"></orgName><affiliation ref="#struct-54311"></affiliation><affiliation ref="#struct-31478"></affiliation><affiliation ref="#struct-130475"></affiliation></author><author role="aut"><persName><forename type="first">Martine</forename><surname>Cadot</surname></persName><email>cadot@loria.fr</email><idno type="halauthor">444542</idno><affiliation ref="#struct-24433"></affiliation></author><editor role="depositor"><persName><forename>Martine</forename><surname>Cadot</surname></persName><email>cadot@loria.fr</email></editor></titleStmt><editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2011-11-14 22:35:54</date><date type="whenWritten">2011-01-30</date><date type="whenModified">2016-05-18 08:56:22</date><date type="whenReleased">2011-11-14 22:35:54</date><date type="whenProduced">2011-10</date></edition><respStmt><resp>contributor</resp><name key="107511"><persName><forename>Martine</forename><surname>Cadot</surname></persName><email>cadot@loria.fr</email></name></respStmt></editionStmt><publicationStmt><distributor>CCSD</distributor><idno type="halId">hal-00641128</idno><idno type="halUri">https://hal.archives-ouvertes.fr/hal-00641128</idno><idno type="halBibtex">lelu:hal-00641128</idno><idno type="halRefHtml">Revue I3 - Information Interaction Intelligence, Cépaduès, 2011, 2011 (1), pp.1-25</idno><idno type="halRef">Revue I3 - Information Interaction Intelligence, Cépaduès, 2011, 2011 (1), pp.1-25</idno></publicationStmt><seriesStmt><idno type="stamp" n="SHS">Sciences de l'Homme et de la Société</idno><idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno><idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno><idno type="stamp" n="UNIV-FCOMTE">Université de Franche-Comté</idno><idno type="stamp" n="INPL">Institut National Polytechnique de Lorraine</idno><idno type="stamp" n="LABO-LORIA-SET" p="LORIA">LABO-LORIA-SET</idno><idno type="stamp" n="LORIA2">Publications du LORIA</idno><idno type="stamp" n="LORIA-CSAI" p="LORIA">Systèmes complexes et intelligence artificielle</idno><idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno><idno type="stamp" n="SIC">archiveSIC</idno><idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno></seriesStmt><notesStmt><note type="audience" n="3">National</note><note type="popular" n="0">No</note><note type="peer" n="1">Yes</note></notesStmt><sourceDesc><biblStruct><analytic><title xml:lang="fr">Espace intrinsèque d'un graphe et recherche de communautés.</title><author role="aut"><persName><forename type="first">Alain</forename><surname>Lelu</surname></persName><email>Alain.Lelu@univ-fcomte.fr</email><idno type="halAuthorId">223091</idno><orgName ref="#struct-242365"></orgName><affiliation ref="#struct-54311"></affiliation><affiliation ref="#struct-31478"></affiliation><affiliation ref="#struct-130475"></affiliation></author><author role="aut"><persName><forename type="first">Martine</forename><surname>Cadot</surname></persName><email>cadot@loria.fr</email><idno type="halAuthorId">444542</idno><affiliation ref="#struct-24433"></affiliation></author></analytic><monogr><idno type="halJournalId" status="VALID">1094</idno><idno type="issn">1630-649X</idno><title level="j">Revue I3 - Information Interaction Intelligence</title><imprint><publisher>Cépaduès</publisher><biblScope unit="volume">2011</biblScope><biblScope unit="issue">1</biblScope><biblScope unit="pp">1-25</biblScope><date type="datePub">2011-10</date></imprint></monogr></biblStruct></sourceDesc><profileDesc><langUsage><language ident="fr">French</language></langUsage><textClass><keywords scheme="author"><term xml:lang="en">graph</term><term xml:lang="en">graph Laplacian</term><term xml:lang="en">dimensionality reduction</term><term xml:lang="en">intrinsic dimension</term><term xml:lang="en">randomization test</term><term xml:lang="en">dominant eigen-subspace</term><term xml:lang="en">graph clustering</term><term xml:lang="en">density clustering method</term><term xml:lang="en">scale-free graph</term><term xml:lang="en">Cattell's scree.</term><term xml:lang="fr">graphe</term><term xml:lang="fr">laplacien d'un graphe</term><term xml:lang="fr">réduction de dimensions</term><term xml:lang="fr">dimension intrinsèque</term><term xml:lang="fr">test de randomisation</term><term xml:lang="fr">clustering de graphe</term><term xml:lang="fr">méthode densitaire de clustering</term><term xml:lang="fr">graphe sans échelle</term><term xml:lang="fr">extraction de communautés</term><term xml:lang="fr">éboulis de Cattell.</term></keywords><classCode scheme="halDomain" n="info.info-oh">Computer Science [cs]/Other [cs.OH]</classCode><classCode scheme="halDomain" n="info.info-ir">Computer Science [cs]/Information Retrieval [cs.IR]</classCode><classCode scheme="halDomain" n="shs.info">Humanities and Social Sciences/Library and information sciences</classCode><classCode scheme="halDomain" n="stat.me">Statistics [stat]/Methodology [stat.ME]</classCode><classCode scheme="halTypology" n="ART">Journal articles</classCode></textClass><abstract xml:lang="en">Determining the number of relevant dimensions in the eigen-space of a graph Laplacian matrix is a central issue in many spectral graph-mining applications. We tackle here the problem of finding out the "right" dimensionality of Laplacian matrices, especially those often encountered in the domains of social or biological graphs: the ones underlying large, sparse, unoriented and unweighted graphs, often endowed with a power-law degree distribution. We present here the application of a randomization test to this problem. After a small introductive example, we validate our approach first on an artificial sparse and scale-free graph, with two intermingled clusters, then on two real-world social graphs ("Football-league", "Mexican Politician Network"), where the actual, intrinsic dimensions appear to be 10 and 2 respectively ; we illustrate the optimality of the transformed dataspaces both visually and numerically, by means of a densitybased clustering technique and a decision tree.</abstract><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 noeuds 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.</abstract></profileDesc></hal></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001B29 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Checkpoint/biblio.hfd -nk 001B29 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Hal
|étape= Checkpoint
|type= RBID
|clé= Hal:hal-00641128
|texte= Espace intrinsèque d'un graphe et recherche de communautés.
}}
| This area was generated with Dilib version V0.6.33. |  |