.png){kind=icon}
返回
Heterogeneous Graphlets
.png){kind=icon}
OA
AI
DOI：10.1145/3418773.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this article, we introduce a generalization of graphlets to heterogeneous networks called typed graphlets. Informally, typed graphlets are small typed induced subgraphs. Typed graphlets generalize graphlets to rich heterogeneous networks as they explicitly capture the higher-order typed connectivity patterns in such networks. To address this problem, we describe a general framework for counting the occurrences of such typed graphlets. The proposed algorithms leverage a number of combinatorial relationships for different typed graphlets. For each edge, we count a few typed graphlets, and with these counts along with the combinatorial relationships, we obtain the exact counts of the other typed graphlets in o(1) constant time. Notably, the worst-case time complexity of the proposed approach matches the time complexity of the best known untyped algorithm. In addition, the approach lends itself to an efficient lock-free and asynchronous parallel implementation. While there are no existing methods for typed graphlets, there has been some work that focused on computing a different and much simpler notion called colored graphlet. The experiments confirm that our proposed approach is orders of magnitude faster and more space-efficient than methods for computing the simpler notion of colored graphlet. Unlike these methods that take hours on small networks, the proposed approach takes only seconds on large networks with millions of edges. Notably, since typed graphlet is more general than colored graphlet (and untyped graphlets), the counts of various typed graphlets can be combined to obtain the counts of the much simpler notion of colored graphlets. The proposed methods give rise to new opportunities and applications for typed graphlets.
Keyword:
Typed graphlets
heterogeneous graphlets
position-aware typed
graphlets
labeled graphlets
heterogeneous network motifs
heterogeneous networks
attributed graphs
k-partite graphs
large networks
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
4.8
论文数:
1.3K
被引数:
4.4K
机构
引用论文
Erratum to: Orthorexia nervosa and self-attitudinal aspects of body image in female and male university students勘误：神经性正食症与女性和男性大学生身体意象的自我态度方面OAAI
.png){kind=icon}
OAAI分享收藏Insurance activity and economic performance: Fresh evidence from asymmetric panel causality testsOAAI
OAAI分享收藏
查看更多内容