Dynamic graphs, community detection, and Riemannian geometry
Identifieur interne : 000727 ( Main/Exploration ); précédent : 000726; suivant : 000728Dynamic graphs, community detection, and Riemannian geometry
Auteurs : Craig Bakker ; Mahantesh Halappanavar ; Arun Visweswara SathanurSource :
- Applied Network Science [ 2364-8228 ] ; 2018.
Abstract
A community is a subset of a wider network where the members of that subset are more strongly connected to each other than they are to the rest of the network. In this paper, we consider the problem of identifying and tracking communities in graphs that change over time – dynamic community detection – and present a framework based on Riemannian geometry to aid in this task. Our framework currently supports several important operations such as interpolating between and averaging over graph snapshots. We compare these Riemannian methods with entry-wise linear interpolation and find that the Riemannian methods are generally better suited to dynamic community detection. Next steps with the Riemannian framework include producing a Riemannian least-squares regression method for working with noisy data and developing support methods, such as spectral sparsification, to improve the scalability of our current methods.
The online version of this article (10.1007/s41109-018-0059-2) contains supplementary material, which is available to authorized users.
Url:
DOI: 10.1007/s41109-018-0059-2
PubMed: 30839776
PubMed Central: 6214282
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Pmc, to step Corpus: 000103
- to stream Pmc, to step Curation: 000103
- to stream Pmc, to step Checkpoint: 000146
- to stream Ncbi, to step Merge: 000756
- to stream Ncbi, to step Curation: 000756
- to stream Ncbi, to step Checkpoint: 000756
- to stream Main, to step Merge: 000729
- to stream Main, to step Curation: 000727
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Dynamic graphs, community detection, and Riemannian geometry</title><author><name sortKey="Bakker, Craig" sort="Bakker, Craig" uniqKey="Bakker C" first="Craig" last="Bakker">Craig Bakker</name><affiliation><nlm:aff id="Aff1"></nlm:aff></affiliation></author><author><name sortKey="Halappanavar, Mahantesh" sort="Halappanavar, Mahantesh" uniqKey="Halappanavar M" first="Mahantesh" last="Halappanavar">Mahantesh Halappanavar</name><affiliation><nlm:aff id="Aff1"></nlm:aff></affiliation></author><author><name sortKey="Visweswara Sathanur, Arun" sort="Visweswara Sathanur, Arun" uniqKey="Visweswara Sathanur A" first="Arun" last="Visweswara Sathanur">Arun Visweswara Sathanur</name><affiliation><nlm:aff id="Aff1"></nlm:aff></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PMC</idno><idno type="pmid">30839776</idno><idno type="pmc">6214282</idno><idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC6214282</idno><idno type="RBID">PMC:6214282</idno><idno type="doi">10.1007/s41109-018-0059-2</idno><date when="2018">2018</date><idno type="wicri:Area/Pmc/Corpus">000103</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000103</idno><idno type="wicri:Area/Pmc/Curation">000103</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Curation">000103</idno><idno type="wicri:Area/Pmc/Checkpoint">000146</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Checkpoint">000146</idno><idno type="wicri:Area/Ncbi/Merge">000756</idno><idno type="wicri:Area/Ncbi/Curation">000756</idno><idno type="wicri:Area/Ncbi/Checkpoint">000756</idno><idno type="wicri:Area/Main/Merge">000729</idno><idno type="wicri:Area/Main/Curation">000727</idno><idno type="wicri:Area/Main/Exploration">000727</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Dynamic graphs, community detection, and Riemannian geometry</title><author><name sortKey="Bakker, Craig" sort="Bakker, Craig" uniqKey="Bakker C" first="Craig" last="Bakker">Craig Bakker</name><affiliation><nlm:aff id="Aff1"></nlm:aff></affiliation></author><author><name sortKey="Halappanavar, Mahantesh" sort="Halappanavar, Mahantesh" uniqKey="Halappanavar M" first="Mahantesh" last="Halappanavar">Mahantesh Halappanavar</name><affiliation><nlm:aff id="Aff1"></nlm:aff></affiliation></author><author><name sortKey="Visweswara Sathanur, Arun" sort="Visweswara Sathanur, Arun" uniqKey="Visweswara Sathanur A" first="Arun" last="Visweswara Sathanur">Arun Visweswara Sathanur</name><affiliation><nlm:aff id="Aff1"></nlm:aff></affiliation></author></analytic><series><title level="j">Applied Network Science</title><idno type="eISSN">2364-8228</idno><imprint><date when="2018">2018</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en"><p>A community is a subset of a wider network where the members of that subset are more strongly connected to each other than they are to the rest of the network. In this paper, we consider the problem of identifying and tracking communities in graphs that change over time – dynamic community detection – and present a framework based on Riemannian geometry to aid in this task. Our framework currently supports several important operations such as interpolating between and averaging over graph snapshots. We compare these Riemannian methods with entry-wise linear interpolation and find that the Riemannian methods are generally better suited to dynamic community detection. Next steps with the Riemannian framework include producing a Riemannian least-squares regression method for working with noisy data and developing support methods, such as spectral sparsification, to improve the scalability of our current methods.</p><sec><title>Electronic supplementary material</title><p>The online version of this article (10.1007/s41109-018-0059-2) contains supplementary material, which is available to authorized users.</p></sec></div></front><back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Absil, Pa" uniqKey="Absil P">PA Absil</name></author><author><name sortKey="Mahony, R" uniqKey="Mahony R">R Mahony</name></author><author><name sortKey="Sepulchre, R" uniqKey="Sepulchre R">R Sepulchre</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Arsigny, V" uniqKey="Arsigny V">V Arsigny</name></author><author><name sortKey="Fillard, P" uniqKey="Fillard P">P Fillard</name></author><author><name sortKey="Pennec, X" uniqKey="Pennec X">X Pennec</name></author><author><name sortKey="Ayache, N" uniqKey="Ayache N">N Ayache</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Batson, J" uniqKey="Batson J">J Batson</name></author><author><name sortKey="Spielman, Da" uniqKey="Spielman D">DA Spielman</name></author><author><name sortKey="Srivastava, N" uniqKey="Srivastava N">N Srivastava</name></author><author><name sortKey="Ten, Sh" uniqKey="Ten S">SH Ten</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Boccaletti, S" uniqKey="Boccaletti S">S Boccaletti</name></author><author><name sortKey="Latora, V" uniqKey="Latora V">V Latora</name></author><author><name sortKey="Moreno, Y" uniqKey="Moreno Y">Y Moreno</name></author><author><name sortKey="Chavez, M" uniqKey="Chavez M">M Chavez</name></author><author><name sortKey="Hwang, Du" uniqKey="Hwang D">DU Hwang</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Boguna, M" uniqKey="Boguna M">M Boguná</name></author><author><name sortKey="Papadopoulos, F" uniqKey="Papadopoulos F">F Papadopoulos</name></author><author><name sortKey="Krioukov, D" uniqKey="Krioukov D">D Krioukov</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Bonnabel, S" uniqKey="Bonnabel S">S Bonnabel</name></author><author><name sortKey="Sepulchre, R" uniqKey="Sepulchre R">R Sepulchre</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Boothby, Wm" uniqKey="Boothby W">WM Boothby</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Cazabet, R" uniqKey="Cazabet R">R Cazabet</name></author><author><name sortKey="Amblard, F" uniqKey="Amblard F">F Amblard</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Domokos, G" uniqKey="Domokos G">G Domokos</name></author><author><name sortKey="Sipos, Ar" uniqKey="Sipos A">AR Sipos</name></author><author><name sortKey="Szab, T" uniqKey="Szab T">T Szabó</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Fenn, Dj" uniqKey="Fenn D">DJ Fenn</name></author><author><name sortKey="Porter, Ma" uniqKey="Porter M">MA Porter</name></author><author><name sortKey="Mucha, Pj" uniqKey="Mucha P">PJ Mucha</name></author><author><name sortKey="Mcdonald, M" uniqKey="Mcdonald M">M McDonald</name></author><author><name sortKey="Williams, S" uniqKey="Williams S">S Williams</name></author><author><name sortKey="Johnson, Nf" uniqKey="Johnson N">NF Johnson</name></author><author><name sortKey="Jones, Ns" uniqKey="Jones N">NS Jones</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Fortunato, S" uniqKey="Fortunato S">S Fortunato</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Girvan, M" uniqKey="Girvan M">M Girvan</name></author><author><name sortKey="Newman, Me" uniqKey="Newman M">ME Newman</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Greene, J" uniqKey="Greene J">J Greene</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Harris, Jm" uniqKey="Harris J">JM Harris</name></author><author><name sortKey="Hirst, Jl" uniqKey="Hirst J">JL Hirst</name></author><author><name sortKey="Mossinghoff, M" uniqKey="Mossinghoff M">M Mossinghoff</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Keshava Prasad, T" uniqKey="Keshava Prasad T">T Keshava Prasad</name></author><author><name sortKey="Goel, R" uniqKey="Goel R">R Goel</name></author><author><name sortKey="Kandasamy, K" uniqKey="Kandasamy K">K Kandasamy</name></author><author><name sortKey="Keerthikumar, S" uniqKey="Keerthikumar S">S Keerthikumar</name></author><author><name sortKey="Kumar, S" uniqKey="Kumar S">S Kumar</name></author><author><name sortKey="Mathivanan, S" uniqKey="Mathivanan S">S Mathivanan</name></author><author><name sortKey="Telikicherla, D" uniqKey="Telikicherla D">D Telikicherla</name></author><author><name sortKey="Raju, R" uniqKey="Raju R">R Raju</name></author><author><name sortKey="Shafreen, B" uniqKey="Shafreen B">B Shafreen</name></author><author><name sortKey="Venugopal, A" uniqKey="Venugopal A">A Venugopal</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Krioukov, D" uniqKey="Krioukov D">D Krioukov</name></author><author><name sortKey="Papadopoulos, F" uniqKey="Papadopoulos F">F Papadopoulos</name></author><author><name sortKey="Vahdat, A" uniqKey="Vahdat A">A Vahdat</name></author><author><name sortKey="Bogu, M" uniqKey="Bogu M">M Boguñá</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Krioukov, D" uniqKey="Krioukov D">D Krioukov</name></author><author><name sortKey="Papadopoulos, F" uniqKey="Papadopoulos F">F Papadopoulos</name></author><author><name sortKey="Kitsak, M" uniqKey="Kitsak M">M Kitsak</name></author><author><name sortKey="Vahdat, A" uniqKey="Vahdat A">A Vahdat</name></author><author><name sortKey="Bogu, M" uniqKey="Bogu M">M Boguñá</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Lambiotte, R" uniqKey="Lambiotte R">R Lambiotte</name></author><author><name sortKey="Delvenne, Jc" uniqKey="Delvenne J">JC Delvenne</name></author><author><name sortKey="Barahona, M" uniqKey="Barahona M">M Barahona</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Mitchell, Hd" uniqKey="Mitchell H">HD Mitchell</name></author><author><name sortKey="Eisfeld, Aj" uniqKey="Eisfeld A">AJ Eisfeld</name></author><author><name sortKey="Sims, Ac" uniqKey="Sims A">AC Sims</name></author><author><name sortKey="Mcdermott, Je" uniqKey="Mcdermott J">JE McDermott</name></author><author><name sortKey="Matzke, Mm" uniqKey="Matzke M">MM Matzke</name></author><author><name sortKey="Webb Robertson, Bjm" uniqKey="Webb Robertson B">BJM Webb-Robertson</name></author><author><name sortKey="Tilton, Sc" uniqKey="Tilton S">SC Tilton</name></author><author><name sortKey="Tchitchek, N" uniqKey="Tchitchek N">N Tchitchek</name></author><author><name sortKey="Josset, L" uniqKey="Josset L">L Josset</name></author><author><name sortKey="Li, C" uniqKey="Li C">C Li</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Mucha, Pj" uniqKey="Mucha P">PJ Mucha</name></author><author><name sortKey="Richardson, T" uniqKey="Richardson T">T Richardson</name></author><author><name sortKey="Macon, K" uniqKey="Macon K">K Macon</name></author><author><name sortKey="Porter, Ma" uniqKey="Porter M">MA Porter</name></author><author><name sortKey="Onnela, Jp" uniqKey="Onnela J">JP Onnela</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Newman, Mej" uniqKey="Newman M">MEJ Newman</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Nguyen, Np" uniqKey="Nguyen N">NP Nguyen</name></author><author><name sortKey="Dinh, Tn" uniqKey="Dinh T">TN Dinh</name></author><author><name sortKey="Shen, Y" uniqKey="Shen Y">Y Shen</name></author><author><name sortKey="Thai, Mt" uniqKey="Thai M">MT Thai</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Pennec, X" uniqKey="Pennec X">X Pennec</name></author><author><name sortKey="Fillard, P" uniqKey="Fillard P">P Fillard</name></author><author><name sortKey="Ayache, N" uniqKey="Ayache N">N Ayache</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Rand, Wm" uniqKey="Rand W">WM Rand</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Tantipathananandh, C" uniqKey="Tantipathananandh C">C Tantipathananandh</name></author><author><name sortKey="Berger Wolf, Ty" uniqKey="Berger Wolf T">TY Berger-Wolf</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Traag, Va" uniqKey="Traag V">VA Traag</name></author><author><name sortKey="Bruggeman, J" uniqKey="Bruggeman J">J Bruggeman</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Vandereycken, B" uniqKey="Vandereycken B">B Vandereycken</name></author></analytic></biblStruct></listBibl></div1></back></TEI><affiliations><list></list><tree><noCountry><name sortKey="Bakker, Craig" sort="Bakker, Craig" uniqKey="Bakker C" first="Craig" last="Bakker">Craig Bakker</name><name sortKey="Halappanavar, Mahantesh" sort="Halappanavar, Mahantesh" uniqKey="Halappanavar M" first="Mahantesh" last="Halappanavar">Mahantesh Halappanavar</name><name sortKey="Visweswara Sathanur, Arun" sort="Visweswara Sathanur, Arun" uniqKey="Visweswara Sathanur A" first="Arun" last="Visweswara Sathanur">Arun Visweswara Sathanur</name></noCountry></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Sante/explor/CovidV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000727 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000727 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Sante
|area= CovidV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= PMC:6214282
|texte= Dynamic graphs, community detection, and Riemannian geometry
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Main/Exploration/RBID.i -Sk "pubmed:30839776" \
| HfdSelect -Kh $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd \
| NlmPubMed2Wicri -a CovidV1
| This area was generated with Dilib version V0.6.33. |  |