Efficient orbit-aware triad and quad census in directed and undirected graphs

Ortmann, Mark; Brandes, Ulrik

Efficient orbit-aware triad and quad census in directed and undirected graphs

Dateien

Ortmann_0-419552.pdfGröße: 1.33 MBDownloads: 327

Datum

2017

Open Access-Veröffentlichung

Open Access Gold

Sammlungen

Informatik und Informationswissenschaft

Publikationstyp

Zeitschriftenartikel

Publikationsstatus

Published

Erschienen in

Applied Network Science. 2017, 2, 13. eISSN 2364-8228. Available under: doi: 10.1007/s41109-017-0027-2

Zusammenfassung

The prevalence of select substructures is an indicator of network effects in applications such as social network analysis and systems biology. Moreover, subgraph statistics are pervasive in stochastic network models, and they need to be assessed repeatedly in MCMC sampling and estimation algorithms. We present a new approach to count all induced and non-induced four-node subgraphs (the quad census) on a per-node and per-edge basis, complete with a separation into their non-automorphic roles in these subgraphs. It is the first approach to do so in a unified manner, and is based on only a clique-listing subroutine. Computational experiments indicate that, despite its simplicity, the approach outperforms previous, less general approaches.

By way of the more presentable triad census, we additionally show how to extend the quad census to directed graphs. As a byproduct we obtain the asymptotically fastest triad census algorithm to date.

Fachgebiet (DDC)

004 Informatik

Schlagwörter

Graphlets, Motifs, Subgraph census, Graph statistics

Zitieren

ISO 690

ORTMANN, Mark, Ulrik BRANDES, 2017. Efficient orbit-aware triad and quad census in directed and undirected graphs. In: Applied Network Science. 2017, 2, 13. eISSN 2364-8228. Available under: doi: 10.1007/s41109-017-0027-2

BibTex

@article{Ortmann2017-12Effic-39740,
  year={2017},
  doi={10.1007/s41109-017-0027-2},
  title={Efficient orbit-aware triad and quad census in directed and undirected graphs},
  volume={2},
  journal={Applied Network Science},
  author={Ortmann, Mark and Brandes, Ulrik},
  note={Article Number: 13}
}

RDF

<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39740">
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-08-02T13:04:39Z</dc:date>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:abstract xml:lang="eng">The prevalence of select substructures is an indicator of network effects in applications such as social network analysis and systems biology. Moreover, subgraph statistics are pervasive in stochastic network models, and they need to be assessed repeatedly in MCMC sampling and estimation algorithms. We present a new approach to count all induced and non-induced four-node subgraphs (the quad census) on a per-node and per-edge basis, complete with a separation into their non-automorphic roles in these subgraphs. It is the first approach to do so in a unified manner, and is based on only a clique-listing subroutine. Computational experiments indicate that, despite its simplicity, the approach outperforms previous, less general approaches.&lt;br /&gt;&lt;br /&gt;By way of the more presentable triad census, we additionally show how to extend the quad census to directed graphs. As a byproduct we obtain the asymptotically fastest triad census algorithm to date.</dcterms:abstract>
    <dc:creator>Ortmann, Mark</dc:creator>
    <dc:rights>Attribution 4.0 International</dc:rights>
    <dc:contributor>Ortmann, Mark</dc:contributor>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-08-02T13:04:39Z</dcterms:available>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:contributor>Brandes, Ulrik</dc:contributor>
    <dcterms:issued>2017-12</dcterms:issued>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/39740"/>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by/4.0/"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/39740/1/Ortmann_0-419552.pdf"/>
    <dcterms:title>Efficient orbit-aware triad and quad census in directed and undirected graphs</dcterms:title>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/39740/1/Ortmann_0-419552.pdf"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:language>eng</dc:language>
    <dc:creator>Brandes, Ulrik</dc:creator>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Ja