Graphlet decomposition: framework, algorithms, and applications

详细信息    查看全文

• 作者：Nesreen K. Ahmed ; Jennifer Neville ; Ryan A. Rossi…
• 关键词：Graphlet ; Motif ; Graph mining ; Graph kernel ; Classification ; Graph features ; Higher ; order graph statistics ; Biological networks ; Visual graph analytics
• 刊名：Knowledge and Information Systems
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：50
• 期：3
• 页码：689-722
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Information Systems and Communication Service; IT in Business;
• 出版者：Springer London
• ISSN：0219-3116
• 卷排序：50

文摘

From social science to biology, numerous applications often rely on graphlets for intuitive and meaningful characterization of networks. While graphlets have witnessed a tremendous success and impact in a variety of domains, there has yet to be a fast and efficient framework for computing the frequencies of these subgraph patterns. However, existing methods are not scalable to large networks with billions of nodes and edges. In this paper, we propose a fast, efficient, and parallel framework as well as a family of algorithms for counting k-node graphlets. The proposed framework leverages a number of theoretical combinatorial arguments that allow us to obtain significant improvement on the scalability of graphlet counting. For each edge, we count a few graphlets and obtain the exact counts of others in constant time using the combinatorial arguments. On a large collection of \(300+\) networks from a variety of domains, our graphlet counting strategies are on average \(460{\times }\) faster than existing methods. This brings new opportunities to investigate the use of graphlets on much larger networks and newer applications as we show in the experiments. To the best of our knowledge, this paper provides the largest graphlet computations to date.