Dynamic graphs, community detection, and Riemannian geometry
Identifieur interne : 000849 ( Ncbi/Merge ); précédent : 000848; suivant : 000850Dynamic 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
Links toward previous steps (curation, corpus...)
- to stream Pmc, to step Corpus: 000172
- to stream Pmc, to step Curation: 000172
- to stream Pmc, to step Checkpoint: 000336
Links to Exploration step
PMC:6214282Le 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">000172</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000172</idno><idno type="wicri:Area/Pmc/Curation">000172</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Curation">000172</idno><idno type="wicri:Area/Pmc/Checkpoint">000336</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Checkpoint">000336</idno><idno type="wicri:Area/Ncbi/Merge">000849</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><pmc article-type="research-article"><pmc-dir>properties open_access</pmc-dir>
<front><journal-meta><journal-id journal-id-type="nlm-ta">Appl Netw Sci</journal-id><journal-id journal-id-type="iso-abbrev">Appl Netw Sci</journal-id><journal-title-group><journal-title>Applied Network Science</journal-title></journal-title-group><issn pub-type="epub">2364-8228</issn><publisher><publisher-name>Springer International Publishing</publisher-name><publisher-loc>Cham</publisher-loc></publisher></journal-meta><article-meta><article-id pub-id-type="pmid">30839776</article-id><article-id pub-id-type="pmc">6214282</article-id><article-id pub-id-type="publisher-id">59</article-id><article-id pub-id-type="doi">10.1007/s41109-018-0059-2</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research</subject></subj-group></article-categories><title-group><article-title>Dynamic graphs, community detection, and Riemannian geometry</article-title></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">http://orcid.org/0000-0002-0083-4000</contrib-id><name><surname>Bakker</surname><given-names>Craig</given-names></name><address><email>craig.bakker@pnnl.gov</email></address><xref ref-type="aff" rid="Aff1"></xref></contrib><contrib contrib-type="author"><name><surname>Halappanavar</surname><given-names>Mahantesh</given-names></name><address><email>mahantesh.halappanavar@pnnl.gov</email></address><xref ref-type="aff" rid="Aff1"></xref></contrib><contrib contrib-type="author"><name><surname>Visweswara Sathanur</surname><given-names>Arun</given-names></name><address><email>arun.sathanur@pnnl.gov</email></address><xref ref-type="aff" rid="Aff1"></xref></contrib><aff id="Aff1"><institution-wrap><institution-id institution-id-type="ISNI">0000 0001 2218 3491</institution-id><institution-id institution-id-type="GRID">grid.451303.0</institution-id><institution>Pacific Northwest National Laboratory,</institution></institution-wrap>902 Battelle Boulevard, Richland, 99352 WA United States</aff></contrib-group><pub-date pub-type="epub"><day>29</day><month>3</month><year>2018</year></pub-date><pub-date pub-type="pmc-release"><day>29</day><month>3</month><year>2018</year></pub-date><pub-date pub-type="ppub"><year>2018</year></pub-date><volume>3</volume><issue>1</issue><elocation-id>3</elocation-id><history><date date-type="received"><day>31</day><month>10</month><year>2017</year></date><date date-type="accepted"><day>26</day><month>2</month><year>2018</year></date></history><permissions><copyright-statement>© The Author(s) 2018</copyright-statement><license license-type="OpenAccess"><license-p><bold>Open Access</bold> This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/licenses/by/4.0/">http://creativecommons.org/licenses/by/4.0/</ext-link>), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.</license-p></license></permissions><abstract id="Abs1"><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></abstract><kwd-group xml:lang="en"><title>Keywords</title><kwd>Community detection</kwd><kwd>Dynamic graphs</kwd><kwd>Riemannian geometry</kwd></kwd-group><funding-group><award-group><funding-source><institution-wrap><institution-id institution-id-type="FundRef">http://dx.doi.org/10.13039/100011661</institution-id><institution>Pacific Northwest National Laboratory</institution></institution-wrap></funding-source><award-id>204751</award-id></award-group></funding-group><custom-meta-group><custom-meta><meta-name>issue-copyright-statement</meta-name><meta-value>© The Author(s) 2018</meta-value></custom-meta></custom-meta-group></article-meta></front></pmc><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/CovidV2/Data/Ncbi/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000849 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Ncbi/Merge/biblio.hfd -nk 000849 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Sante
|area= CovidV2
|flux= Ncbi
|étape= Merge
|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/Ncbi/Merge/RBID.i -Sk "pubmed:30839776" \
| HfdSelect -Kh $EXPLOR_AREA/Data/Ncbi/Merge/biblio.hfd \
| NlmPubMed2Wicri -a CovidV2
| This area was generated with Dilib version V0.6.33. |  |