Published by the Foundation for Open Access Statistics Editors-in-chief: Bettina Grün, Torsten Hothorn, Rebecca Killick, Edzer Pebesma, Achim Zeileis    ISSN 1548-7660; CODEN JSSOBK
Authors: Tomaž Hočevar, Janez Demšar
Title: Computation of Graphlet Orbits for Nodes and Edges in Sparse Graphs
Abstract: Graphlet analysis is a useful tool for describing local network topology around individual nodes or edges. A node or an edge can be described by a vector containing the counts of different kinds of graphlets (small induced subgraphs) in which it appears, or the "roles" (orbits) it has within these graphlets. We implemented an R package with functions for fast computation of such counts on sparse graphs. Instead of enumerating all induced graphlets, our algorithm is based on the derived relations between the counts, which decreases the time complexity by an order of magnitude in comparison with past approaches.

Page views:: 1433. Submitted: 2014-06-23. Published: 2016-07-28.
Paper: Computation of Graphlet Orbits for Nodes and Edges in Sparse Graphs     Download PDF (Downloads: 1376)
orca_1.1-1.tar.gz: R source package Download (Downloads: 108; 42KB)
v71i10.R: R replication code Download (Downloads: 124; 801B) Replication code for benchmark Download (Downloads: 62; 1MB)
schools-wiki-edges.txt: Replication data Download (Downloads: 369; 1MB)
schools-wiki-nodes.txt: Replication data Download (Downloads: 3390; 80KB)

DOI: 10.18637/jss.v071.i10

This work is licensed under the licenses
Paper: Creative Commons Attribution 3.0 Unported License
Code: GNU General Public License (at least one of version 2 or version 3) or a GPL-compatible license.