SNOD: a fast sampling method of exploring node orbit degrees for large graphs

Pinghui Wang, Junzhou Zhao, Xiangliang Zhang, Jing Tao, Xiaohong Guan

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Exploring small connected and induced subgraph patterns (CIS patterns, or graphlets) has recently attracted considerable attention. Despite recent efforts on computing how frequent a graphlet appears in a large graph (i.e., the total number of CISes isomorphic to the graphlet), little effort has been made to characterize a node’s graphlet orbit degree, i.e., the number of CISes isomorphic to the graphlet that touch the node at a particular orbit, which is an important fine-grained metric for analyzing complex networks such as learning functions/roles of nodes in social and biological networks. Like global graphlet counting, it is computationally intensive to compute node orbit degrees for a large graph. Furthermore, previous methods of computing global graphlet counts are not suited to solve this problem. In this paper, we propose a novel sampling method SNOD to efficiently estimate node orbit degrees for large-scale graphs and quantify the error of our estimates. To the best of our knowledge, we are the first to study this problem and give a fast scalable solution. We conduct experiments on a variety of real-world datasets and demonstrate that our method SNOD is several orders of magnitude faster than state-of-the-art enumeration methods for accurately estimating node orbit degrees for graphs with millions of edges.
Original languageEnglish (US)
Pages (from-to)301-326
Number of pages26
JournalKnowledge and Information Systems
Volume61
Issue number1
DOIs
StatePublished - Dec 13 2018

Fingerprint Dive into the research topics of 'SNOD: a fast sampling method of exploring node orbit degrees for large graphs'. Together they form a unique fingerprint.

Cite this